Line data Source code
1 : /*
2 : *
3 : * Copyright 2015, Google Inc.
4 : * All rights reserved.
5 : *
6 : * Redistribution and use in source and binary forms, with or without
7 : * modification, are permitted provided that the following conditions are
8 : * met:
9 : *
10 : * * Redistributions of source code must retain the above copyright
11 : * notice, this list of conditions and the following disclaimer.
12 : * * Redistributions in binary form must reproduce the above
13 : * copyright notice, this list of conditions and the following disclaimer
14 : * in the documentation and/or other materials provided with the
15 : * distribution.
16 : * * Neither the name of Google Inc. nor the names of its
17 : * contributors may be used to endorse or promote products derived from
18 : * this software without specific prior written permission.
19 : *
20 : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 : * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 : * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23 : * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24 : * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25 : * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26 : * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 : * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 : * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 : * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30 : * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 : *
32 : */
33 :
34 : #include "src/core/transport/chttp2/hpack_parser.h"
35 : #include "src/core/transport/chttp2/internal.h"
36 :
37 : #include <stddef.h>
38 : #include <string.h>
39 : #include <assert.h>
40 :
41 : #include "src/core/transport/chttp2/bin_encoder.h"
42 : #include "src/core/support/string.h"
43 : #include <grpc/support/alloc.h>
44 : #include <grpc/support/log.h>
45 : #include <grpc/support/port_platform.h>
46 : #include <grpc/support/useful.h>
47 :
48 : typedef enum {
49 : NOT_BINARY,
50 : B64_BYTE0,
51 : B64_BYTE1,
52 : B64_BYTE2,
53 : B64_BYTE3
54 : } binary_state;
55 :
56 : /* How parsing works:
57 :
58 : The parser object keeps track of a function pointer which represents the
59 : current parse state.
60 :
61 : Each time new bytes are presented, we call into the current state, which
62 : recursively parses until all bytes in the given chunk are exhausted.
63 :
64 : The parse state that terminates then saves its function pointer to be the
65 : current state so that it can resume when more bytes are available.
66 :
67 : It's expected that most optimizing compilers will turn this code into
68 : a set of indirect jumps, and so not waste stack space. */
69 :
70 : /* forward declarations for parsing states */
71 : static int parse_begin(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
72 : const gpr_uint8 *end);
73 : static int parse_error(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
74 : const gpr_uint8 *end);
75 :
76 : static int parse_string_prefix(grpc_chttp2_hpack_parser *p,
77 : const gpr_uint8 *cur, const gpr_uint8 *end);
78 : static int parse_key_string(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
79 : const gpr_uint8 *end);
80 : static int parse_value_string_with_indexed_key(grpc_chttp2_hpack_parser *p,
81 : const gpr_uint8 *cur,
82 : const gpr_uint8 *end);
83 : static int parse_value_string_with_literal_key(grpc_chttp2_hpack_parser *p,
84 : const gpr_uint8 *cur,
85 : const gpr_uint8 *end);
86 :
87 : static int parse_value0(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
88 : const gpr_uint8 *end);
89 : static int parse_value1(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
90 : const gpr_uint8 *end);
91 : static int parse_value2(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
92 : const gpr_uint8 *end);
93 : static int parse_value3(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
94 : const gpr_uint8 *end);
95 : static int parse_value4(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
96 : const gpr_uint8 *end);
97 : static int parse_value5up(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
98 : const gpr_uint8 *end);
99 :
100 : static int parse_indexed_field(grpc_chttp2_hpack_parser *p,
101 : const gpr_uint8 *cur, const gpr_uint8 *end);
102 : static int parse_indexed_field_x(grpc_chttp2_hpack_parser *p,
103 : const gpr_uint8 *cur, const gpr_uint8 *end);
104 : static int parse_lithdr_incidx(grpc_chttp2_hpack_parser *p,
105 : const gpr_uint8 *cur, const gpr_uint8 *end);
106 : static int parse_lithdr_incidx_x(grpc_chttp2_hpack_parser *p,
107 : const gpr_uint8 *cur, const gpr_uint8 *end);
108 : static int parse_lithdr_incidx_v(grpc_chttp2_hpack_parser *p,
109 : const gpr_uint8 *cur, const gpr_uint8 *end);
110 : static int parse_lithdr_notidx(grpc_chttp2_hpack_parser *p,
111 : const gpr_uint8 *cur, const gpr_uint8 *end);
112 : static int parse_lithdr_notidx_x(grpc_chttp2_hpack_parser *p,
113 : const gpr_uint8 *cur, const gpr_uint8 *end);
114 : static int parse_lithdr_notidx_v(grpc_chttp2_hpack_parser *p,
115 : const gpr_uint8 *cur, const gpr_uint8 *end);
116 : static int parse_lithdr_nvridx(grpc_chttp2_hpack_parser *p,
117 : const gpr_uint8 *cur, const gpr_uint8 *end);
118 : static int parse_lithdr_nvridx_x(grpc_chttp2_hpack_parser *p,
119 : const gpr_uint8 *cur, const gpr_uint8 *end);
120 : static int parse_lithdr_nvridx_v(grpc_chttp2_hpack_parser *p,
121 : const gpr_uint8 *cur, const gpr_uint8 *end);
122 : static int parse_max_tbl_size(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
123 : const gpr_uint8 *end);
124 : static int parse_max_tbl_size_x(grpc_chttp2_hpack_parser *p,
125 : const gpr_uint8 *cur, const gpr_uint8 *end);
126 :
127 : /* we translate the first byte of a hpack field into one of these decoding
128 : cases, then use a lookup table to jump directly to the appropriate parser.
129 :
130 : _X => the integer index is all ones, meaning we need to do varint decoding
131 : _V => the integer index is all zeros, meaning we need to decode an additional
132 : string value */
133 : typedef enum {
134 : INDEXED_FIELD,
135 : INDEXED_FIELD_X,
136 : LITHDR_INCIDX,
137 : LITHDR_INCIDX_X,
138 : LITHDR_INCIDX_V,
139 : LITHDR_NOTIDX,
140 : LITHDR_NOTIDX_X,
141 : LITHDR_NOTIDX_V,
142 : LITHDR_NVRIDX,
143 : LITHDR_NVRIDX_X,
144 : LITHDR_NVRIDX_V,
145 : MAX_TBL_SIZE,
146 : MAX_TBL_SIZE_X,
147 : ILLEGAL
148 : } first_byte_type;
149 :
150 : /* jump table of parse state functions -- order must match first_byte_type
151 : above */
152 : static const grpc_chttp2_hpack_parser_state first_byte_action[] = {
153 : parse_indexed_field, parse_indexed_field_x, parse_lithdr_incidx,
154 : parse_lithdr_incidx_x, parse_lithdr_incidx_v, parse_lithdr_notidx,
155 : parse_lithdr_notidx_x, parse_lithdr_notidx_v, parse_lithdr_nvridx,
156 : parse_lithdr_nvridx_x, parse_lithdr_nvridx_v, parse_max_tbl_size,
157 : parse_max_tbl_size_x, parse_error};
158 :
159 : /* indexes the first byte to a parse state function - generated by
160 : gen_hpack_tables.c */
161 : static const gpr_uint8 first_byte_lut[256] = {
162 : LITHDR_NOTIDX_V, LITHDR_NOTIDX, LITHDR_NOTIDX, LITHDR_NOTIDX,
163 : LITHDR_NOTIDX, LITHDR_NOTIDX, LITHDR_NOTIDX, LITHDR_NOTIDX,
164 : LITHDR_NOTIDX, LITHDR_NOTIDX, LITHDR_NOTIDX, LITHDR_NOTIDX,
165 : LITHDR_NOTIDX, LITHDR_NOTIDX, LITHDR_NOTIDX, LITHDR_NOTIDX_X,
166 : LITHDR_NVRIDX_V, LITHDR_NVRIDX, LITHDR_NVRIDX, LITHDR_NVRIDX,
167 : LITHDR_NVRIDX, LITHDR_NVRIDX, LITHDR_NVRIDX, LITHDR_NVRIDX,
168 : LITHDR_NVRIDX, LITHDR_NVRIDX, LITHDR_NVRIDX, LITHDR_NVRIDX,
169 : LITHDR_NVRIDX, LITHDR_NVRIDX, LITHDR_NVRIDX, LITHDR_NVRIDX_X,
170 : ILLEGAL, MAX_TBL_SIZE, MAX_TBL_SIZE, MAX_TBL_SIZE,
171 : MAX_TBL_SIZE, MAX_TBL_SIZE, MAX_TBL_SIZE, MAX_TBL_SIZE,
172 : MAX_TBL_SIZE, MAX_TBL_SIZE, MAX_TBL_SIZE, MAX_TBL_SIZE,
173 : MAX_TBL_SIZE, MAX_TBL_SIZE, MAX_TBL_SIZE, MAX_TBL_SIZE,
174 : MAX_TBL_SIZE, MAX_TBL_SIZE, MAX_TBL_SIZE, MAX_TBL_SIZE,
175 : MAX_TBL_SIZE, MAX_TBL_SIZE, MAX_TBL_SIZE, MAX_TBL_SIZE,
176 : MAX_TBL_SIZE, MAX_TBL_SIZE, MAX_TBL_SIZE, MAX_TBL_SIZE,
177 : MAX_TBL_SIZE, MAX_TBL_SIZE, MAX_TBL_SIZE, MAX_TBL_SIZE_X,
178 : LITHDR_INCIDX_V, LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX,
179 : LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX,
180 : LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX,
181 : LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX,
182 : LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX,
183 : LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX,
184 : LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX,
185 : LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX,
186 : LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX,
187 : LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX,
188 : LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX,
189 : LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX,
190 : LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX,
191 : LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX,
192 : LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX,
193 : LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX_X,
194 : ILLEGAL, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
195 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
196 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
197 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
198 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
199 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
200 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
201 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
202 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
203 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
204 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
205 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
206 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
207 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
208 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
209 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
210 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
211 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
212 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
213 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
214 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
215 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
216 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
217 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
218 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
219 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
220 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
221 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
222 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
223 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
224 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
225 : INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD_X,
226 : };
227 :
228 : /* state table for huffman decoding: given a state, gives an index/16 into
229 : next_sub_tbl. Taking that index and adding the value of the nibble being
230 : considered returns the next state.
231 :
232 : generated by gen_hpack_tables.c */
233 : static const gpr_uint8 next_tbl[256] = {
234 : 0, 1, 2, 3, 4, 1, 2, 5, 6, 1, 7, 8, 1, 3, 3, 9, 10, 11, 1, 1,
235 : 1, 12, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2,
236 : 14, 1, 15, 16, 1, 17, 1, 15, 2, 7, 3, 18, 19, 1, 1, 1, 1, 20, 1, 1,
237 : 1, 1, 1, 1, 1, 1, 1, 1, 15, 2, 2, 7, 21, 1, 22, 1, 1, 1, 1, 1,
238 : 1, 1, 1, 15, 2, 2, 2, 2, 2, 2, 23, 24, 25, 1, 1, 1, 1, 2, 2, 2,
239 : 26, 3, 3, 27, 10, 28, 1, 1, 1, 1, 1, 1, 2, 3, 29, 10, 30, 1, 1, 1,
240 : 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 31, 1, 1, 1, 1, 1, 1, 1, 2,
241 : 2, 2, 2, 2, 2, 2, 2, 32, 1, 1, 15, 33, 1, 34, 35, 9, 36, 1, 1, 1,
242 : 1, 1, 1, 1, 37, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 26, 9,
243 : 38, 1, 1, 1, 1, 1, 1, 1, 15, 2, 2, 2, 2, 26, 3, 3, 39, 1, 1, 1,
244 : 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 7, 3, 3, 3, 40, 2,
245 : 41, 1, 1, 1, 42, 43, 1, 1, 44, 1, 1, 1, 1, 15, 2, 2, 2, 2, 2, 2,
246 : 3, 3, 3, 45, 46, 1, 1, 2, 2, 2, 35, 3, 3, 18, 47, 2,
247 : };
248 :
249 : /* next state, based upon current state and the current nibble: see above.
250 : generated by gen_hpack_tables.c */
251 : static const gpr_int16 next_sub_tbl[48 * 16] = {
252 : 1, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217,
253 : 218, 2, 6, 10, 13, 14, 15, 16, 17, 2, 6, 10, 13, 14, 15,
254 : 16, 17, 3, 7, 11, 24, 3, 7, 11, 24, 3, 7, 11, 24, 3,
255 : 7, 11, 24, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8,
256 : 4, 8, 4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5,
257 : 199, 200, 201, 202, 203, 4, 8, 4, 8, 0, 0, 0, 0, 0, 0,
258 : 0, 0, 0, 0, 0, 0, 9, 133, 134, 135, 136, 137, 138, 139, 140,
259 : 141, 142, 143, 144, 145, 146, 147, 3, 7, 11, 24, 3, 7, 11, 24,
260 : 4, 8, 4, 8, 4, 8, 4, 8, 0, 0, 0, 0, 0, 0, 0,
261 : 0, 0, 0, 0, 0, 0, 0, 12, 132, 4, 8, 4, 8, 4, 8,
262 : 4, 8, 4, 8, 4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0,
263 : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
264 : 0, 0, 0, 0, 0, 0, 0, 0, 18, 19, 20, 21, 4, 8, 4,
265 : 8, 4, 8, 4, 8, 4, 8, 0, 0, 0, 22, 23, 91, 25, 26,
266 : 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 3,
267 : 7, 11, 24, 3, 7, 11, 24, 0, 0, 0, 0, 0, 41, 42, 43,
268 : 2, 6, 10, 13, 14, 15, 16, 17, 3, 7, 11, 24, 3, 7, 11,
269 : 24, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 0, 0,
270 : 44, 45, 2, 6, 10, 13, 14, 15, 16, 17, 46, 47, 48, 49, 50,
271 : 51, 52, 57, 4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
272 : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
273 : 0, 53, 54, 55, 56, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67,
274 : 68, 69, 70, 71, 72, 74, 0, 0, 0, 0, 0, 0, 0, 0, 0,
275 : 0, 0, 0, 0, 0, 0, 73, 75, 76, 77, 78, 79, 80, 81, 82,
276 : 83, 84, 85, 86, 87, 88, 89, 90, 3, 7, 11, 24, 3, 7, 11,
277 : 24, 3, 7, 11, 24, 0, 0, 0, 0, 3, 7, 11, 24, 3, 7,
278 : 11, 24, 4, 8, 4, 8, 0, 0, 0, 92, 0, 0, 0, 93, 94,
279 : 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 3, 7, 11, 24,
280 : 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4,
281 : 8, 4, 8, 4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
282 : 0, 0, 0, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 4,
283 : 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 0, 0,
284 : 0, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130,
285 : 131, 2, 6, 10, 13, 14, 15, 16, 17, 4, 8, 4, 8, 4, 8,
286 : 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 148,
287 : 149, 150, 151, 3, 7, 11, 24, 4, 8, 4, 8, 0, 0, 0, 0,
288 : 0, 0, 152, 153, 3, 7, 11, 24, 3, 7, 11, 24, 3, 7, 11,
289 : 24, 154, 155, 156, 164, 3, 7, 11, 24, 3, 7, 11, 24, 3, 7,
290 : 11, 24, 4, 8, 4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0,
291 : 157, 158, 159, 160, 161, 162, 163, 165, 166, 167, 168, 169, 170, 171, 172,
292 : 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187,
293 : 188, 189, 190, 191, 192, 193, 194, 195, 196, 4, 8, 4, 8, 4, 8,
294 : 4, 8, 4, 8, 4, 8, 4, 8, 197, 198, 4, 8, 4, 8, 4,
295 : 8, 4, 8, 0, 0, 0, 0, 0, 0, 219, 220, 3, 7, 11, 24,
296 : 4, 8, 4, 8, 4, 8, 0, 0, 221, 222, 223, 224, 3, 7, 11,
297 : 24, 3, 7, 11, 24, 4, 8, 4, 8, 4, 8, 225, 228, 4, 8,
298 : 4, 8, 4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 226, 227, 229,
299 : 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244,
300 : 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 0, 0, 0, 0, 0,
301 : 0, 0, 0, 0, 0, 0, 0, 245, 246, 247, 248, 249, 250, 251, 252,
302 : 253, 254, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
303 : 0, 0, 255,
304 : };
305 :
306 : /* emission table: indexed like next_tbl, ultimately gives the byte to be
307 : emitted, or -1 for no byte, or 256 for end of stream
308 :
309 : generated by gen_hpack_tables.c */
310 : static const gpr_uint16 emit_tbl[256] = {
311 : 0, 1, 2, 3, 4, 5, 6, 7, 0, 8, 9, 10, 11, 12, 13,
312 : 14, 15, 16, 17, 18, 19, 20, 21, 22, 0, 23, 24, 25, 26, 27,
313 : 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42,
314 : 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 0, 55, 56,
315 : 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 0,
316 : 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85,
317 : 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100,
318 : 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115,
319 : 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130,
320 : 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145,
321 : 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 0,
322 : 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174,
323 : 0, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188,
324 : 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203,
325 : 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218,
326 : 219, 220, 221, 0, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232,
327 : 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247,
328 : 248,
329 : };
330 :
331 : /* generated by gen_hpack_tables.c */
332 : static const gpr_int16 emit_sub_tbl[249 * 16] = {
333 : -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
334 : -1, 48, 48, 48, 48, 48, 48, 48, 48, 49, 49, 49, 49, 49, 49,
335 : 49, 49, 48, 48, 48, 48, 49, 49, 49, 49, 50, 50, 50, 50, 97,
336 : 97, 97, 97, 48, 48, 49, 49, 50, 50, 97, 97, 99, 99, 101, 101,
337 : 105, 105, 111, 111, 48, 49, 50, 97, 99, 101, 105, 111, 115, 116, -1,
338 : -1, -1, -1, -1, -1, 32, 32, 32, 32, 32, 32, 32, 32, 37, 37,
339 : 37, 37, 37, 37, 37, 37, 99, 99, 99, 99, 101, 101, 101, 101, 105,
340 : 105, 105, 105, 111, 111, 111, 111, 115, 115, 116, 116, 32, 37, 45, 46,
341 : 47, 51, 52, 53, 54, 55, 56, 57, 61, 61, 61, 61, 61, 61, 61,
342 : 61, 65, 65, 65, 65, 65, 65, 65, 65, 115, 115, 115, 115, 116, 116,
343 : 116, 116, 32, 32, 37, 37, 45, 45, 46, 46, 61, 65, 95, 98, 100,
344 : 102, 103, 104, 108, 109, 110, 112, 114, 117, -1, -1, 58, 58, 58, 58,
345 : 58, 58, 58, 58, 66, 66, 66, 66, 66, 66, 66, 66, 47, 47, 51,
346 : 51, 52, 52, 53, 53, 54, 54, 55, 55, 56, 56, 57, 57, 61, 61,
347 : 65, 65, 95, 95, 98, 98, 100, 100, 102, 102, 103, 103, 104, 104, 108,
348 : 108, 109, 109, 110, 110, 112, 112, 114, 114, 117, 117, 58, 66, 67, 68,
349 : 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83,
350 : 84, 85, 86, 87, 89, 106, 107, 113, 118, 119, 120, 121, 122, -1, -1,
351 : -1, -1, 38, 38, 38, 38, 38, 38, 38, 38, 42, 42, 42, 42, 42,
352 : 42, 42, 42, 44, 44, 44, 44, 44, 44, 44, 44, 59, 59, 59, 59,
353 : 59, 59, 59, 59, 88, 88, 88, 88, 88, 88, 88, 88, 90, 90, 90,
354 : 90, 90, 90, 90, 90, 33, 33, 34, 34, 40, 40, 41, 41, 63, 63,
355 : 39, 43, 124, -1, -1, -1, 35, 35, 35, 35, 35, 35, 35, 35, 62,
356 : 62, 62, 62, 62, 62, 62, 62, 0, 0, 0, 0, 36, 36, 36, 36,
357 : 64, 64, 64, 64, 91, 91, 91, 91, 69, 69, 69, 69, 69, 69, 69,
358 : 69, 70, 70, 70, 70, 70, 70, 70, 70, 71, 71, 71, 71, 71, 71,
359 : 71, 71, 72, 72, 72, 72, 72, 72, 72, 72, 73, 73, 73, 73, 73,
360 : 73, 73, 73, 74, 74, 74, 74, 74, 74, 74, 74, 75, 75, 75, 75,
361 : 75, 75, 75, 75, 76, 76, 76, 76, 76, 76, 76, 76, 77, 77, 77,
362 : 77, 77, 77, 77, 77, 78, 78, 78, 78, 78, 78, 78, 78, 79, 79,
363 : 79, 79, 79, 79, 79, 79, 80, 80, 80, 80, 80, 80, 80, 80, 81,
364 : 81, 81, 81, 81, 81, 81, 81, 82, 82, 82, 82, 82, 82, 82, 82,
365 : 83, 83, 83, 83, 83, 83, 83, 83, 84, 84, 84, 84, 84, 84, 84,
366 : 84, 85, 85, 85, 85, 85, 85, 85, 85, 86, 86, 86, 86, 86, 86,
367 : 86, 86, 87, 87, 87, 87, 87, 87, 87, 87, 89, 89, 89, 89, 89,
368 : 89, 89, 89, 106, 106, 106, 106, 106, 106, 106, 106, 107, 107, 107, 107,
369 : 107, 107, 107, 107, 113, 113, 113, 113, 113, 113, 113, 113, 118, 118, 118,
370 : 118, 118, 118, 118, 118, 119, 119, 119, 119, 119, 119, 119, 119, 120, 120,
371 : 120, 120, 120, 120, 120, 120, 121, 121, 121, 121, 121, 121, 121, 121, 122,
372 : 122, 122, 122, 122, 122, 122, 122, 38, 38, 38, 38, 42, 42, 42, 42,
373 : 44, 44, 44, 44, 59, 59, 59, 59, 88, 88, 88, 88, 90, 90, 90,
374 : 90, 33, 34, 40, 41, 63, -1, -1, -1, 39, 39, 39, 39, 39, 39,
375 : 39, 39, 43, 43, 43, 43, 43, 43, 43, 43, 124, 124, 124, 124, 124,
376 : 124, 124, 124, 35, 35, 35, 35, 62, 62, 62, 62, 0, 0, 36, 36,
377 : 64, 64, 91, 91, 93, 93, 126, 126, 94, 125, -1, -1, 60, 60, 60,
378 : 60, 60, 60, 60, 60, 96, 96, 96, 96, 96, 96, 96, 96, 123, 123,
379 : 123, 123, 123, 123, 123, 123, -1, -1, -1, -1, -1, -1, -1, -1, 92,
380 : 92, 92, 92, 92, 92, 92, 92, 195, 195, 195, 195, 195, 195, 195, 195,
381 : 208, 208, 208, 208, 208, 208, 208, 208, 128, 128, 128, 128, 130, 130, 130,
382 : 130, 131, 131, 131, 131, 162, 162, 162, 162, 184, 184, 184, 184, 194, 194,
383 : 194, 194, 224, 224, 224, 224, 226, 226, 226, 226, 153, 153, 161, 161, 167,
384 : 167, 172, 172, 176, 176, 177, 177, 179, 179, 209, 209, 216, 216, 217, 217,
385 : 227, 227, 229, 229, 230, 230, 129, 132, 133, 134, 136, 146, 154, 156, 160,
386 : 163, 164, 169, 170, 173, 178, 181, 185, 186, 187, 189, 190, 196, 198, 228,
387 : 232, 233, -1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 135,
388 : 135, 135, 135, 135, 135, 135, 135, 137, 137, 137, 137, 137, 137, 137, 137,
389 : 138, 138, 138, 138, 138, 138, 138, 138, 139, 139, 139, 139, 139, 139, 139,
390 : 139, 140, 140, 140, 140, 140, 140, 140, 140, 141, 141, 141, 141, 141, 141,
391 : 141, 141, 143, 143, 143, 143, 143, 143, 143, 143, 147, 147, 147, 147, 147,
392 : 147, 147, 147, 149, 149, 149, 149, 149, 149, 149, 149, 150, 150, 150, 150,
393 : 150, 150, 150, 150, 151, 151, 151, 151, 151, 151, 151, 151, 152, 152, 152,
394 : 152, 152, 152, 152, 152, 155, 155, 155, 155, 155, 155, 155, 155, 157, 157,
395 : 157, 157, 157, 157, 157, 157, 158, 158, 158, 158, 158, 158, 158, 158, 165,
396 : 165, 165, 165, 165, 165, 165, 165, 166, 166, 166, 166, 166, 166, 166, 166,
397 : 168, 168, 168, 168, 168, 168, 168, 168, 174, 174, 174, 174, 174, 174, 174,
398 : 174, 175, 175, 175, 175, 175, 175, 175, 175, 180, 180, 180, 180, 180, 180,
399 : 180, 180, 182, 182, 182, 182, 182, 182, 182, 182, 183, 183, 183, 183, 183,
400 : 183, 183, 183, 188, 188, 188, 188, 188, 188, 188, 188, 191, 191, 191, 191,
401 : 191, 191, 191, 191, 197, 197, 197, 197, 197, 197, 197, 197, 231, 231, 231,
402 : 231, 231, 231, 231, 231, 239, 239, 239, 239, 239, 239, 239, 239, 9, 9,
403 : 9, 9, 142, 142, 142, 142, 144, 144, 144, 144, 145, 145, 145, 145, 148,
404 : 148, 148, 148, 159, 159, 159, 159, 171, 171, 171, 171, 206, 206, 206, 206,
405 : 215, 215, 215, 215, 225, 225, 225, 225, 236, 236, 236, 236, 237, 237, 237,
406 : 237, 199, 199, 207, 207, 234, 234, 235, 235, 192, 193, 200, 201, 202, 205,
407 : 210, 213, 218, 219, 238, 240, 242, 243, 255, -1, 203, 203, 203, 203, 203,
408 : 203, 203, 203, 204, 204, 204, 204, 204, 204, 204, 204, 211, 211, 211, 211,
409 : 211, 211, 211, 211, 212, 212, 212, 212, 212, 212, 212, 212, 214, 214, 214,
410 : 214, 214, 214, 214, 214, 221, 221, 221, 221, 221, 221, 221, 221, 222, 222,
411 : 222, 222, 222, 222, 222, 222, 223, 223, 223, 223, 223, 223, 223, 223, 241,
412 : 241, 241, 241, 241, 241, 241, 241, 244, 244, 244, 244, 244, 244, 244, 244,
413 : 245, 245, 245, 245, 245, 245, 245, 245, 246, 246, 246, 246, 246, 246, 246,
414 : 246, 247, 247, 247, 247, 247, 247, 247, 247, 248, 248, 248, 248, 248, 248,
415 : 248, 248, 250, 250, 250, 250, 250, 250, 250, 250, 251, 251, 251, 251, 251,
416 : 251, 251, 251, 252, 252, 252, 252, 252, 252, 252, 252, 253, 253, 253, 253,
417 : 253, 253, 253, 253, 254, 254, 254, 254, 254, 254, 254, 254, 2, 2, 2,
418 : 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6,
419 : 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 11, 11, 11, 11, 12,
420 : 12, 12, 12, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16,
421 : 17, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19, 20, 20, 20,
422 : 20, 21, 21, 21, 21, 23, 23, 23, 23, 24, 24, 24, 24, 25, 25,
423 : 25, 25, 26, 26, 26, 26, 27, 27, 27, 27, 28, 28, 28, 28, 29,
424 : 29, 29, 29, 30, 30, 30, 30, 31, 31, 31, 31, 127, 127, 127, 127,
425 : 220, 220, 220, 220, 249, 249, 249, 249, 10, 13, 22, 256, 93, 93, 93,
426 : 93, 126, 126, 126, 126, 94, 94, 125, 125, 60, 96, 123, -1, 92, 195,
427 : 208, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 128,
428 : 128, 128, 128, 128, 128, 128, 128, 130, 130, 130, 130, 130, 130, 130, 130,
429 : 131, 131, 131, 131, 131, 131, 131, 131, 162, 162, 162, 162, 162, 162, 162,
430 : 162, 184, 184, 184, 184, 184, 184, 184, 184, 194, 194, 194, 194, 194, 194,
431 : 194, 194, 224, 224, 224, 224, 224, 224, 224, 224, 226, 226, 226, 226, 226,
432 : 226, 226, 226, 153, 153, 153, 153, 161, 161, 161, 161, 167, 167, 167, 167,
433 : 172, 172, 172, 172, 176, 176, 176, 176, 177, 177, 177, 177, 179, 179, 179,
434 : 179, 209, 209, 209, 209, 216, 216, 216, 216, 217, 217, 217, 217, 227, 227,
435 : 227, 227, 229, 229, 229, 229, 230, 230, 230, 230, 129, 129, 132, 132, 133,
436 : 133, 134, 134, 136, 136, 146, 146, 154, 154, 156, 156, 160, 160, 163, 163,
437 : 164, 164, 169, 169, 170, 170, 173, 173, 178, 178, 181, 181, 185, 185, 186,
438 : 186, 187, 187, 189, 189, 190, 190, 196, 196, 198, 198, 228, 228, 232, 232,
439 : 233, 233, 1, 135, 137, 138, 139, 140, 141, 143, 147, 149, 150, 151, 152,
440 : 155, 157, 158, 165, 166, 168, 174, 175, 180, 182, 183, 188, 191, 197, 231,
441 : 239, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 9, 9, 9,
442 : 9, 9, 9, 9, 9, 142, 142, 142, 142, 142, 142, 142, 142, 144, 144,
443 : 144, 144, 144, 144, 144, 144, 145, 145, 145, 145, 145, 145, 145, 145, 148,
444 : 148, 148, 148, 148, 148, 148, 148, 159, 159, 159, 159, 159, 159, 159, 159,
445 : 171, 171, 171, 171, 171, 171, 171, 171, 206, 206, 206, 206, 206, 206, 206,
446 : 206, 215, 215, 215, 215, 215, 215, 215, 215, 225, 225, 225, 225, 225, 225,
447 : 225, 225, 236, 236, 236, 236, 236, 236, 236, 236, 237, 237, 237, 237, 237,
448 : 237, 237, 237, 199, 199, 199, 199, 207, 207, 207, 207, 234, 234, 234, 234,
449 : 235, 235, 235, 235, 192, 192, 193, 193, 200, 200, 201, 201, 202, 202, 205,
450 : 205, 210, 210, 213, 213, 218, 218, 219, 219, 238, 238, 240, 240, 242, 242,
451 : 243, 243, 255, 255, 203, 204, 211, 212, 214, 221, 222, 223, 241, 244, 245,
452 : 246, 247, 248, 250, 251, 252, 253, 254, -1, -1, -1, -1, -1, -1, -1,
453 : -1, -1, -1, -1, -1, -1, -1, -1, 2, 2, 2, 2, 2, 2, 2,
454 : 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4,
455 : 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6,
456 : 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8,
457 : 8, 8, 8, 8, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12,
458 : 12, 12, 12, 12, 12, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15,
459 : 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 17,
460 : 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 18,
461 : 19, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20,
462 : 20, 21, 21, 21, 21, 21, 21, 21, 21, 23, 23, 23, 23, 23, 23,
463 : 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25,
464 : 25, 25, 25, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27,
465 : 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29,
466 : 29, 29, 29, 29, 29, 30, 30, 30, 30, 30, 30, 30, 30, 31, 31,
467 : 31, 31, 31, 31, 31, 31, 127, 127, 127, 127, 127, 127, 127, 127, 220,
468 : 220, 220, 220, 220, 220, 220, 220, 249, 249, 249, 249, 249, 249, 249, 249,
469 : 10, 10, 13, 13, 22, 22, 256, 256, 67, 67, 67, 67, 67, 67, 67,
470 : 67, 68, 68, 68, 68, 68, 68, 68, 68, 95, 95, 95, 95, 95, 95,
471 : 95, 95, 98, 98, 98, 98, 98, 98, 98, 98, 100, 100, 100, 100, 100,
472 : 100, 100, 100, 102, 102, 102, 102, 102, 102, 102, 102, 103, 103, 103, 103,
473 : 103, 103, 103, 103, 104, 104, 104, 104, 104, 104, 104, 104, 108, 108, 108,
474 : 108, 108, 108, 108, 108, 109, 109, 109, 109, 109, 109, 109, 109, 110, 110,
475 : 110, 110, 110, 110, 110, 110, 112, 112, 112, 112, 112, 112, 112, 112, 114,
476 : 114, 114, 114, 114, 114, 114, 114, 117, 117, 117, 117, 117, 117, 117, 117,
477 : 58, 58, 58, 58, 66, 66, 66, 66, 67, 67, 67, 67, 68, 68, 68,
478 : 68, 69, 69, 69, 69, 70, 70, 70, 70, 71, 71, 71, 71, 72, 72,
479 : 72, 72, 73, 73, 73, 73, 74, 74, 74, 74, 75, 75, 75, 75, 76,
480 : 76, 76, 76, 77, 77, 77, 77, 78, 78, 78, 78, 79, 79, 79, 79,
481 : 80, 80, 80, 80, 81, 81, 81, 81, 82, 82, 82, 82, 83, 83, 83,
482 : 83, 84, 84, 84, 84, 85, 85, 85, 85, 86, 86, 86, 86, 87, 87,
483 : 87, 87, 89, 89, 89, 89, 106, 106, 106, 106, 107, 107, 107, 107, 113,
484 : 113, 113, 113, 118, 118, 118, 118, 119, 119, 119, 119, 120, 120, 120, 120,
485 : 121, 121, 121, 121, 122, 122, 122, 122, 38, 38, 42, 42, 44, 44, 59,
486 : 59, 88, 88, 90, 90, -1, -1, -1, -1, 33, 33, 33, 33, 33, 33,
487 : 33, 33, 34, 34, 34, 34, 34, 34, 34, 34, 40, 40, 40, 40, 40,
488 : 40, 40, 40, 41, 41, 41, 41, 41, 41, 41, 41, 63, 63, 63, 63,
489 : 63, 63, 63, 63, 39, 39, 39, 39, 43, 43, 43, 43, 124, 124, 124,
490 : 124, 35, 35, 62, 62, 0, 36, 64, 91, 93, 126, -1, -1, 94, 94,
491 : 94, 94, 94, 94, 94, 94, 125, 125, 125, 125, 125, 125, 125, 125, 60,
492 : 60, 60, 60, 96, 96, 96, 96, 123, 123, 123, 123, -1, -1, -1, -1,
493 : 92, 92, 92, 92, 195, 195, 195, 195, 208, 208, 208, 208, 128, 128, 130,
494 : 130, 131, 131, 162, 162, 184, 184, 194, 194, 224, 224, 226, 226, 153, 161,
495 : 167, 172, 176, 177, 179, 209, 216, 217, 227, 229, 230, -1, -1, -1, -1,
496 : -1, -1, -1, 129, 129, 129, 129, 129, 129, 129, 129, 132, 132, 132, 132,
497 : 132, 132, 132, 132, 133, 133, 133, 133, 133, 133, 133, 133, 134, 134, 134,
498 : 134, 134, 134, 134, 134, 136, 136, 136, 136, 136, 136, 136, 136, 146, 146,
499 : 146, 146, 146, 146, 146, 146, 154, 154, 154, 154, 154, 154, 154, 154, 156,
500 : 156, 156, 156, 156, 156, 156, 156, 160, 160, 160, 160, 160, 160, 160, 160,
501 : 163, 163, 163, 163, 163, 163, 163, 163, 164, 164, 164, 164, 164, 164, 164,
502 : 164, 169, 169, 169, 169, 169, 169, 169, 169, 170, 170, 170, 170, 170, 170,
503 : 170, 170, 173, 173, 173, 173, 173, 173, 173, 173, 178, 178, 178, 178, 178,
504 : 178, 178, 178, 181, 181, 181, 181, 181, 181, 181, 181, 185, 185, 185, 185,
505 : 185, 185, 185, 185, 186, 186, 186, 186, 186, 186, 186, 186, 187, 187, 187,
506 : 187, 187, 187, 187, 187, 189, 189, 189, 189, 189, 189, 189, 189, 190, 190,
507 : 190, 190, 190, 190, 190, 190, 196, 196, 196, 196, 196, 196, 196, 196, 198,
508 : 198, 198, 198, 198, 198, 198, 198, 228, 228, 228, 228, 228, 228, 228, 228,
509 : 232, 232, 232, 232, 232, 232, 232, 232, 233, 233, 233, 233, 233, 233, 233,
510 : 233, 1, 1, 1, 1, 135, 135, 135, 135, 137, 137, 137, 137, 138, 138,
511 : 138, 138, 139, 139, 139, 139, 140, 140, 140, 140, 141, 141, 141, 141, 143,
512 : 143, 143, 143, 147, 147, 147, 147, 149, 149, 149, 149, 150, 150, 150, 150,
513 : 151, 151, 151, 151, 152, 152, 152, 152, 155, 155, 155, 155, 157, 157, 157,
514 : 157, 158, 158, 158, 158, 165, 165, 165, 165, 166, 166, 166, 166, 168, 168,
515 : 168, 168, 174, 174, 174, 174, 175, 175, 175, 175, 180, 180, 180, 180, 182,
516 : 182, 182, 182, 183, 183, 183, 183, 188, 188, 188, 188, 191, 191, 191, 191,
517 : 197, 197, 197, 197, 231, 231, 231, 231, 239, 239, 239, 239, 9, 9, 142,
518 : 142, 144, 144, 145, 145, 148, 148, 159, 159, 171, 171, 206, 206, 215, 215,
519 : 225, 225, 236, 236, 237, 237, 199, 207, 234, 235, 192, 192, 192, 192, 192,
520 : 192, 192, 192, 193, 193, 193, 193, 193, 193, 193, 193, 200, 200, 200, 200,
521 : 200, 200, 200, 200, 201, 201, 201, 201, 201, 201, 201, 201, 202, 202, 202,
522 : 202, 202, 202, 202, 202, 205, 205, 205, 205, 205, 205, 205, 205, 210, 210,
523 : 210, 210, 210, 210, 210, 210, 213, 213, 213, 213, 213, 213, 213, 213, 218,
524 : 218, 218, 218, 218, 218, 218, 218, 219, 219, 219, 219, 219, 219, 219, 219,
525 : 238, 238, 238, 238, 238, 238, 238, 238, 240, 240, 240, 240, 240, 240, 240,
526 : 240, 242, 242, 242, 242, 242, 242, 242, 242, 243, 243, 243, 243, 243, 243,
527 : 243, 243, 255, 255, 255, 255, 255, 255, 255, 255, 203, 203, 203, 203, 204,
528 : 204, 204, 204, 211, 211, 211, 211, 212, 212, 212, 212, 214, 214, 214, 214,
529 : 221, 221, 221, 221, 222, 222, 222, 222, 223, 223, 223, 223, 241, 241, 241,
530 : 241, 244, 244, 244, 244, 245, 245, 245, 245, 246, 246, 246, 246, 247, 247,
531 : 247, 247, 248, 248, 248, 248, 250, 250, 250, 250, 251, 251, 251, 251, 252,
532 : 252, 252, 252, 253, 253, 253, 253, 254, 254, 254, 254, 2, 2, 3, 3,
533 : 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 11, 11, 12, 12, 14,
534 : 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21,
535 : 23, 23, 24, 24, 25, 25, 26, 26, 27, 27, 28, 28, 29, 29, 30,
536 : 30, 31, 31, 127, 127, 220, 220, 249, 249, -1, -1, 10, 10, 10, 10,
537 : 10, 10, 10, 10, 13, 13, 13, 13, 13, 13, 13, 13, 22, 22, 22,
538 : 22, 22, 22, 22, 22, 256, 256, 256, 256, 256, 256, 256, 256, 45, 45,
539 : 45, 45, 45, 45, 45, 45, 46, 46, 46, 46, 46, 46, 46, 46, 47,
540 : 47, 47, 47, 47, 47, 47, 47, 51, 51, 51, 51, 51, 51, 51, 51,
541 : 52, 52, 52, 52, 52, 52, 52, 52, 53, 53, 53, 53, 53, 53, 53,
542 : 53, 54, 54, 54, 54, 54, 54, 54, 54, 55, 55, 55, 55, 55, 55,
543 : 55, 55, 56, 56, 56, 56, 56, 56, 56, 56, 57, 57, 57, 57, 57,
544 : 57, 57, 57, 50, 50, 50, 50, 50, 50, 50, 50, 97, 97, 97, 97,
545 : 97, 97, 97, 97, 99, 99, 99, 99, 99, 99, 99, 99, 101, 101, 101,
546 : 101, 101, 101, 101, 101, 105, 105, 105, 105, 105, 105, 105, 105, 111, 111,
547 : 111, 111, 111, 111, 111, 111, 115, 115, 115, 115, 115, 115, 115, 115, 116,
548 : 116, 116, 116, 116, 116, 116, 116, 32, 32, 32, 32, 37, 37, 37, 37,
549 : 45, 45, 45, 45, 46, 46, 46, 46, 47, 47, 47, 47, 51, 51, 51,
550 : 51, 52, 52, 52, 52, 53, 53, 53, 53, 54, 54, 54, 54, 55, 55,
551 : 55, 55, 56, 56, 56, 56, 57, 57, 57, 57, 61, 61, 61, 61, 65,
552 : 65, 65, 65, 95, 95, 95, 95, 98, 98, 98, 98, 100, 100, 100, 100,
553 : 102, 102, 102, 102, 103, 103, 103, 103, 104, 104, 104, 104, 108, 108, 108,
554 : 108, 109, 109, 109, 109, 110, 110, 110, 110, 112, 112, 112, 112, 114, 114,
555 : 114, 114, 117, 117, 117, 117, 58, 58, 66, 66, 67, 67, 68, 68, 69,
556 : 69, 70, 70, 71, 71, 72, 72, 73, 73, 74, 74, 75, 75, 76, 76,
557 : 77, 77, 78, 78, 79, 79, 80, 80, 81, 81, 82, 82, 83, 83, 84,
558 : 84, 85, 85, 86, 86, 87, 87, 89, 89, 106, 106, 107, 107, 113, 113,
559 : 118, 118, 119, 119, 120, 120, 121, 121, 122, 122, 38, 42, 44, 59, 88,
560 : 90, -1, -1, 33, 33, 33, 33, 34, 34, 34, 34, 40, 40, 40, 40,
561 : 41, 41, 41, 41, 63, 63, 63, 63, 39, 39, 43, 43, 124, 124, 35,
562 : 62, -1, -1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 36, 36,
563 : 36, 36, 36, 36, 36, 36, 64, 64, 64, 64, 64, 64, 64, 64, 91,
564 : 91, 91, 91, 91, 91, 91, 91, 93, 93, 93, 93, 93, 93, 93, 93,
565 : 126, 126, 126, 126, 126, 126, 126, 126, 94, 94, 94, 94, 125, 125, 125,
566 : 125, 60, 60, 96, 96, 123, 123, -1, -1, 92, 92, 195, 195, 208, 208,
567 : 128, 130, 131, 162, 184, 194, 224, 226, -1, -1, 153, 153, 153, 153, 153,
568 : 153, 153, 153, 161, 161, 161, 161, 161, 161, 161, 161, 167, 167, 167, 167,
569 : 167, 167, 167, 167, 172, 172, 172, 172, 172, 172, 172, 172, 176, 176, 176,
570 : 176, 176, 176, 176, 176, 177, 177, 177, 177, 177, 177, 177, 177, 179, 179,
571 : 179, 179, 179, 179, 179, 179, 209, 209, 209, 209, 209, 209, 209, 209, 216,
572 : 216, 216, 216, 216, 216, 216, 216, 217, 217, 217, 217, 217, 217, 217, 217,
573 : 227, 227, 227, 227, 227, 227, 227, 227, 229, 229, 229, 229, 229, 229, 229,
574 : 229, 230, 230, 230, 230, 230, 230, 230, 230, 129, 129, 129, 129, 132, 132,
575 : 132, 132, 133, 133, 133, 133, 134, 134, 134, 134, 136, 136, 136, 136, 146,
576 : 146, 146, 146, 154, 154, 154, 154, 156, 156, 156, 156, 160, 160, 160, 160,
577 : 163, 163, 163, 163, 164, 164, 164, 164, 169, 169, 169, 169, 170, 170, 170,
578 : 170, 173, 173, 173, 173, 178, 178, 178, 178, 181, 181, 181, 181, 185, 185,
579 : 185, 185, 186, 186, 186, 186, 187, 187, 187, 187, 189, 189, 189, 189, 190,
580 : 190, 190, 190, 196, 196, 196, 196, 198, 198, 198, 198, 228, 228, 228, 228,
581 : 232, 232, 232, 232, 233, 233, 233, 233, 1, 1, 135, 135, 137, 137, 138,
582 : 138, 139, 139, 140, 140, 141, 141, 143, 143, 147, 147, 149, 149, 150, 150,
583 : 151, 151, 152, 152, 155, 155, 157, 157, 158, 158, 165, 165, 166, 166, 168,
584 : 168, 174, 174, 175, 175, 180, 180, 182, 182, 183, 183, 188, 188, 191, 191,
585 : 197, 197, 231, 231, 239, 239, 9, 142, 144, 145, 148, 159, 171, 206, 215,
586 : 225, 236, 237, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 199, 199,
587 : 199, 199, 199, 199, 199, 199, 207, 207, 207, 207, 207, 207, 207, 207, 234,
588 : 234, 234, 234, 234, 234, 234, 234, 235, 235, 235, 235, 235, 235, 235, 235,
589 : 192, 192, 192, 192, 193, 193, 193, 193, 200, 200, 200, 200, 201, 201, 201,
590 : 201, 202, 202, 202, 202, 205, 205, 205, 205, 210, 210, 210, 210, 213, 213,
591 : 213, 213, 218, 218, 218, 218, 219, 219, 219, 219, 238, 238, 238, 238, 240,
592 : 240, 240, 240, 242, 242, 242, 242, 243, 243, 243, 243, 255, 255, 255, 255,
593 : 203, 203, 204, 204, 211, 211, 212, 212, 214, 214, 221, 221, 222, 222, 223,
594 : 223, 241, 241, 244, 244, 245, 245, 246, 246, 247, 247, 248, 248, 250, 250,
595 : 251, 251, 252, 252, 253, 253, 254, 254, 2, 3, 4, 5, 6, 7, 8,
596 : 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27,
597 : 28, 29, 30, 31, 127, 220, 249, -1, 10, 10, 10, 10, 13, 13, 13,
598 : 13, 22, 22, 22, 22, 256, 256, 256, 256,
599 : };
600 :
601 : static const gpr_uint8 inverse_base64[256] = {
602 : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
603 : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
604 : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 62, 255,
605 : 255, 255, 63, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 255, 255,
606 : 255, 64, 255, 255, 255, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
607 : 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
608 : 25, 255, 255, 255, 255, 255, 255, 26, 27, 28, 29, 30, 31, 32, 33,
609 : 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48,
610 : 49, 50, 51, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
611 : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
612 : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
613 : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
614 : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
615 : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
616 : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
617 : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
618 : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
619 : 255,
620 : };
621 :
622 : /* emission helpers */
623 18945816 : static void on_hdr(grpc_chttp2_hpack_parser *p, grpc_mdelem *md,
624 : int add_to_table) {
625 18945816 : if (add_to_table) {
626 37155 : GRPC_MDELEM_REF(md);
627 37155 : grpc_chttp2_hptbl_add(&p->table, md);
628 : }
629 18945816 : p->on_header(p->on_header_user_data, md);
630 18920637 : }
631 :
632 256854 : static grpc_mdstr *take_string(grpc_chttp2_hpack_parser *p,
633 : grpc_chttp2_hpack_parser_string *str) {
634 256854 : grpc_mdstr *s = grpc_mdstr_from_buffer(p->table.mdctx, (gpr_uint8 *)str->str,
635 256854 : str->length);
636 256854 : str->length = 0;
637 256854 : return s;
638 : }
639 :
640 : /* jump to the next state */
641 532235 : static int parse_next(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
642 : const gpr_uint8 *end) {
643 532235 : p->state = *p->next_state++;
644 532235 : return p->state(p, cur, end);
645 : }
646 :
647 : /* begin parsing a header: all functionality is encoded into lookup tables
648 : above */
649 23121608 : static int parse_begin(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
650 : const gpr_uint8 *end) {
651 23121608 : if (cur == end) {
652 4219623 : p->state = parse_begin;
653 4219623 : return 1;
654 : }
655 :
656 18901985 : return first_byte_action[first_byte_lut[*cur]](p, cur, end);
657 : }
658 :
659 : /* stream dependency and prioritization data: we just skip it */
660 0 : static int parse_stream_weight(grpc_chttp2_hpack_parser *p,
661 : const gpr_uint8 *cur, const gpr_uint8 *end) {
662 0 : if (cur == end) {
663 0 : p->state = parse_stream_weight;
664 0 : return 1;
665 : }
666 :
667 0 : return p->after_prioritization(p, cur + 1, end);
668 : }
669 :
670 0 : static int parse_stream_dep3(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
671 : const gpr_uint8 *end) {
672 0 : if (cur == end) {
673 0 : p->state = parse_stream_dep3;
674 0 : return 1;
675 : }
676 :
677 0 : return parse_stream_weight(p, cur + 1, end);
678 : }
679 :
680 0 : static int parse_stream_dep2(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
681 : const gpr_uint8 *end) {
682 0 : if (cur == end) {
683 0 : p->state = parse_stream_dep2;
684 0 : return 1;
685 : }
686 :
687 0 : return parse_stream_dep3(p, cur + 1, end);
688 : }
689 :
690 0 : static int parse_stream_dep1(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
691 : const gpr_uint8 *end) {
692 0 : if (cur == end) {
693 0 : p->state = parse_stream_dep1;
694 0 : return 1;
695 : }
696 :
697 0 : return parse_stream_dep2(p, cur + 1, end);
698 : }
699 :
700 0 : static int parse_stream_dep0(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
701 : const gpr_uint8 *end) {
702 0 : if (cur == end) {
703 0 : p->state = parse_stream_dep0;
704 0 : return 1;
705 : }
706 :
707 0 : return parse_stream_dep1(p, cur + 1, end);
708 : }
709 :
710 : /* emit an indexed field; for now just logs it to console; jumps to
711 : begin the next field on completion */
712 18766868 : static int finish_indexed_field(grpc_chttp2_hpack_parser *p,
713 : const gpr_uint8 *cur, const gpr_uint8 *end) {
714 18766868 : grpc_mdelem *md = grpc_chttp2_hptbl_lookup(&p->table, p->index);
715 18768258 : GRPC_MDELEM_REF(md);
716 18806953 : on_hdr(p, md, 0);
717 18782515 : return parse_begin(p, cur, end);
718 : }
719 :
720 : /* parse an indexed field with index < 127 */
721 18766319 : static int parse_indexed_field(grpc_chttp2_hpack_parser *p,
722 : const gpr_uint8 *cur, const gpr_uint8 *end) {
723 18766319 : p->index = (*cur) & 0x7f;
724 18766319 : return finish_indexed_field(p, cur + 1, end);
725 : }
726 :
727 : /* parse an indexed field with index >= 127 */
728 825 : static int parse_indexed_field_x(grpc_chttp2_hpack_parser *p,
729 : const gpr_uint8 *cur, const gpr_uint8 *end) {
730 : static const grpc_chttp2_hpack_parser_state and_then[] = {
731 : finish_indexed_field};
732 825 : p->next_state = and_then;
733 825 : p->index = 0x7f;
734 825 : p->parsing.value = &p->index;
735 825 : return parse_value0(p, cur + 1, end);
736 : }
737 :
738 : /* finish a literal header with incremental indexing: just log, and jump to '
739 : begin */
740 2229 : static int finish_lithdr_incidx(grpc_chttp2_hpack_parser *p,
741 : const gpr_uint8 *cur, const gpr_uint8 *end) {
742 2229 : grpc_mdelem *md = grpc_chttp2_hptbl_lookup(&p->table, p->index);
743 2229 : on_hdr(p, grpc_mdelem_from_metadata_strings(p->table.mdctx,
744 : GRPC_MDSTR_REF(md->key),
745 : take_string(p, &p->value)),
746 : 1);
747 2229 : return parse_begin(p, cur, end);
748 : }
749 :
750 : /* finish a literal header with incremental indexing with no index */
751 34926 : static int finish_lithdr_incidx_v(grpc_chttp2_hpack_parser *p,
752 : const gpr_uint8 *cur, const gpr_uint8 *end) {
753 34926 : on_hdr(p, grpc_mdelem_from_metadata_strings(p->table.mdctx,
754 : take_string(p, &p->key),
755 : take_string(p, &p->value)),
756 : 1);
757 34926 : return parse_begin(p, cur, end);
758 : }
759 :
760 : /* parse a literal header with incremental indexing; index < 63 */
761 160 : static int parse_lithdr_incidx(grpc_chttp2_hpack_parser *p,
762 : const gpr_uint8 *cur, const gpr_uint8 *end) {
763 : static const grpc_chttp2_hpack_parser_state and_then[] = {
764 : parse_value_string_with_indexed_key, finish_lithdr_incidx};
765 160 : p->next_state = and_then;
766 160 : p->index = (*cur) & 0x3f;
767 160 : return parse_string_prefix(p, cur + 1, end);
768 : }
769 :
770 : /* parse a literal header with incremental indexing; index >= 63 */
771 2069 : static int parse_lithdr_incidx_x(grpc_chttp2_hpack_parser *p,
772 : const gpr_uint8 *cur, const gpr_uint8 *end) {
773 : static const grpc_chttp2_hpack_parser_state and_then[] = {
774 : parse_string_prefix, parse_value_string_with_indexed_key,
775 : finish_lithdr_incidx};
776 2069 : p->next_state = and_then;
777 2069 : p->index = 0x3f;
778 2069 : p->parsing.value = &p->index;
779 2069 : return parse_value0(p, cur + 1, end);
780 : }
781 :
782 : /* parse a literal header with incremental indexing; index = 0 */
783 34926 : static int parse_lithdr_incidx_v(grpc_chttp2_hpack_parser *p,
784 : const gpr_uint8 *cur, const gpr_uint8 *end) {
785 : static const grpc_chttp2_hpack_parser_state and_then[] = {
786 : parse_key_string, parse_string_prefix,
787 : parse_value_string_with_literal_key, finish_lithdr_incidx_v};
788 34926 : p->next_state = and_then;
789 34926 : return parse_string_prefix(p, cur + 1, end);
790 : }
791 :
792 : /* finish a literal header without incremental indexing */
793 15635 : static int finish_lithdr_notidx(grpc_chttp2_hpack_parser *p,
794 : const gpr_uint8 *cur, const gpr_uint8 *end) {
795 15635 : grpc_mdelem *md = grpc_chttp2_hptbl_lookup(&p->table, p->index);
796 15635 : on_hdr(p, grpc_mdelem_from_metadata_strings(p->table.mdctx,
797 : GRPC_MDSTR_REF(md->key),
798 : take_string(p, &p->value)),
799 : 0);
800 15635 : return parse_begin(p, cur, end);
801 : }
802 :
803 : /* finish a literal header without incremental indexing with index = 0 */
804 84567 : static int finish_lithdr_notidx_v(grpc_chttp2_hpack_parser *p,
805 : const gpr_uint8 *cur, const gpr_uint8 *end) {
806 84567 : on_hdr(p, grpc_mdelem_from_metadata_strings(p->table.mdctx,
807 : take_string(p, &p->key),
808 : take_string(p, &p->value)),
809 : 0);
810 84567 : return parse_begin(p, cur, end);
811 : }
812 :
813 : /* parse a literal header without incremental indexing; index < 15 */
814 2 : static int parse_lithdr_notidx(grpc_chttp2_hpack_parser *p,
815 : const gpr_uint8 *cur, const gpr_uint8 *end) {
816 : static const grpc_chttp2_hpack_parser_state and_then[] = {
817 : parse_value_string_with_indexed_key, finish_lithdr_notidx};
818 2 : p->next_state = and_then;
819 2 : p->index = (*cur) & 0xf;
820 2 : return parse_string_prefix(p, cur + 1, end);
821 : }
822 :
823 : /* parse a literal header without incremental indexing; index >= 15 */
824 15633 : static int parse_lithdr_notidx_x(grpc_chttp2_hpack_parser *p,
825 : const gpr_uint8 *cur, const gpr_uint8 *end) {
826 : static const grpc_chttp2_hpack_parser_state and_then[] = {
827 : parse_string_prefix, parse_value_string_with_indexed_key,
828 : finish_lithdr_notidx};
829 15633 : p->next_state = and_then;
830 15633 : p->index = 0xf;
831 15633 : p->parsing.value = &p->index;
832 15633 : return parse_value0(p, cur + 1, end);
833 : }
834 :
835 : /* parse a literal header without incremental indexing; index == 0 */
836 84567 : static int parse_lithdr_notidx_v(grpc_chttp2_hpack_parser *p,
837 : const gpr_uint8 *cur, const gpr_uint8 *end) {
838 : static const grpc_chttp2_hpack_parser_state and_then[] = {
839 : parse_key_string, parse_string_prefix,
840 : parse_value_string_with_literal_key, finish_lithdr_notidx_v};
841 84567 : p->next_state = and_then;
842 84567 : return parse_string_prefix(p, cur + 1, end);
843 : }
844 :
845 : /* finish a literal header that is never indexed */
846 0 : static int finish_lithdr_nvridx(grpc_chttp2_hpack_parser *p,
847 : const gpr_uint8 *cur, const gpr_uint8 *end) {
848 0 : grpc_mdelem *md = grpc_chttp2_hptbl_lookup(&p->table, p->index);
849 0 : on_hdr(p, grpc_mdelem_from_metadata_strings(p->table.mdctx,
850 : GRPC_MDSTR_REF(md->key),
851 : take_string(p, &p->value)),
852 : 0);
853 0 : return parse_begin(p, cur, end);
854 : }
855 :
856 : /* finish a literal header that is never indexed with an extra value */
857 2 : static int finish_lithdr_nvridx_v(grpc_chttp2_hpack_parser *p,
858 : const gpr_uint8 *cur, const gpr_uint8 *end) {
859 2 : on_hdr(p, grpc_mdelem_from_metadata_strings(p->table.mdctx,
860 : take_string(p, &p->key),
861 : take_string(p, &p->value)),
862 : 0);
863 2 : return parse_begin(p, cur, end);
864 : }
865 :
866 : /* parse a literal header that is never indexed; index < 15 */
867 0 : static int parse_lithdr_nvridx(grpc_chttp2_hpack_parser *p,
868 : const gpr_uint8 *cur, const gpr_uint8 *end) {
869 : static const grpc_chttp2_hpack_parser_state and_then[] = {
870 : parse_value_string_with_indexed_key, finish_lithdr_nvridx};
871 0 : p->next_state = and_then;
872 0 : p->index = (*cur) & 0xf;
873 0 : return parse_string_prefix(p, cur + 1, end);
874 : }
875 :
876 : /* parse a literal header that is never indexed; index >= 15 */
877 0 : static int parse_lithdr_nvridx_x(grpc_chttp2_hpack_parser *p,
878 : const gpr_uint8 *cur, const gpr_uint8 *end) {
879 : static const grpc_chttp2_hpack_parser_state and_then[] = {
880 : parse_string_prefix, parse_value_string_with_indexed_key,
881 : finish_lithdr_nvridx};
882 0 : p->next_state = and_then;
883 0 : p->index = 0xf;
884 0 : p->parsing.value = &p->index;
885 0 : return parse_value0(p, cur + 1, end);
886 : }
887 :
888 : /* parse a literal header that is never indexed; index == 0 */
889 2 : static int parse_lithdr_nvridx_v(grpc_chttp2_hpack_parser *p,
890 : const gpr_uint8 *cur, const gpr_uint8 *end) {
891 : static const grpc_chttp2_hpack_parser_state and_then[] = {
892 : parse_key_string, parse_string_prefix,
893 : parse_value_string_with_literal_key, finish_lithdr_nvridx_v};
894 2 : p->next_state = and_then;
895 2 : return parse_string_prefix(p, cur + 1, end);
896 : }
897 :
898 : /* finish parsing a max table size change */
899 0 : static int finish_max_tbl_size(grpc_chttp2_hpack_parser *p,
900 : const gpr_uint8 *cur, const gpr_uint8 *end) {
901 0 : gpr_log(GPR_INFO, "MAX TABLE SIZE: %d", p->index);
902 0 : abort(); /* not implemented */
903 : return parse_begin(p, cur, end);
904 : }
905 :
906 : /* parse a max table size change, max size < 15 */
907 0 : static int parse_max_tbl_size(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
908 : const gpr_uint8 *end) {
909 0 : p->index = (*cur) & 0xf;
910 0 : return finish_max_tbl_size(p, cur + 1, end);
911 : }
912 :
913 : /* parse a max table size change, max size >= 15 */
914 0 : static int parse_max_tbl_size_x(grpc_chttp2_hpack_parser *p,
915 : const gpr_uint8 *cur, const gpr_uint8 *end) {
916 : static const grpc_chttp2_hpack_parser_state and_then[] = {
917 : finish_max_tbl_size};
918 0 : p->next_state = and_then;
919 0 : p->index = 0xf;
920 0 : p->parsing.value = &p->index;
921 0 : return parse_value0(p, cur + 1, end);
922 : }
923 :
924 : /* a parse error: jam the parse state into parse_error, and return error */
925 0 : static int parse_error(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
926 : const gpr_uint8 *end) {
927 0 : p->state = parse_error;
928 0 : return 0;
929 : }
930 :
931 : /* parse the 1st byte of a varint into p->parsing.value
932 : no overflow is possible */
933 21035 : static int parse_value0(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
934 : const gpr_uint8 *end) {
935 21035 : if (cur == end) {
936 10 : p->state = parse_value0;
937 10 : return 1;
938 : }
939 :
940 21025 : *p->parsing.value += (*cur) & 0x7f;
941 :
942 21025 : if ((*cur) & 0x80) {
943 1449 : return parse_value1(p, cur + 1, end);
944 : } else {
945 19576 : return parse_next(p, cur + 1, end);
946 : }
947 : }
948 :
949 : /* parse the 2nd byte of a varint into p->parsing.value
950 : no overflow is possible */
951 1451 : static int parse_value1(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
952 : const gpr_uint8 *end) {
953 1451 : if (cur == end) {
954 2 : p->state = parse_value1;
955 2 : return 1;
956 : }
957 :
958 1449 : *p->parsing.value += (((gpr_uint32)*cur) & 0x7f) << 7;
959 :
960 1449 : if ((*cur) & 0x80) {
961 26 : return parse_value2(p, cur + 1, end);
962 : } else {
963 1423 : return parse_next(p, cur + 1, end);
964 : }
965 : }
966 :
967 : /* parse the 3rd byte of a varint into p->parsing.value
968 : no overflow is possible */
969 28 : static int parse_value2(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
970 : const gpr_uint8 *end) {
971 28 : if (cur == end) {
972 2 : p->state = parse_value2;
973 2 : return 1;
974 : }
975 :
976 26 : *p->parsing.value += (((gpr_uint32)*cur) & 0x7f) << 14;
977 :
978 26 : if ((*cur) & 0x80) {
979 0 : return parse_value3(p, cur + 1, end);
980 : } else {
981 26 : return parse_next(p, cur + 1, end);
982 : }
983 : }
984 :
985 : /* parse the 4th byte of a varint into p->parsing.value
986 : no overflow is possible */
987 0 : static int parse_value3(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
988 : const gpr_uint8 *end) {
989 0 : if (cur == end) {
990 0 : p->state = parse_value3;
991 0 : return 1;
992 : }
993 :
994 0 : *p->parsing.value += (((gpr_uint32)*cur) & 0x7f) << 21;
995 :
996 0 : if ((*cur) & 0x80) {
997 0 : return parse_value4(p, cur + 1, end);
998 : } else {
999 0 : return parse_next(p, cur + 1, end);
1000 : }
1001 : }
1002 :
1003 : /* parse the 5th byte of a varint into p->parsing.value
1004 : depending on the byte, we may overflow, and care must be taken */
1005 0 : static int parse_value4(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
1006 : const gpr_uint8 *end) {
1007 : gpr_uint8 c;
1008 : gpr_uint32 cur_value;
1009 : gpr_uint32 add_value;
1010 :
1011 0 : if (cur == end) {
1012 0 : p->state = parse_value4;
1013 0 : return 1;
1014 : }
1015 :
1016 0 : c = (*cur) & 0x7f;
1017 0 : if (c > 0xf) {
1018 0 : goto error;
1019 : }
1020 :
1021 0 : cur_value = *p->parsing.value;
1022 0 : add_value = ((gpr_uint32)c) << 28;
1023 0 : if (add_value > 0xffffffffu - cur_value) {
1024 0 : goto error;
1025 : }
1026 :
1027 0 : *p->parsing.value = cur_value + add_value;
1028 :
1029 0 : if ((*cur) & 0x80) {
1030 0 : return parse_value5up(p, cur + 1, end);
1031 : } else {
1032 0 : return parse_next(p, cur + 1, end);
1033 : }
1034 :
1035 : error:
1036 0 : gpr_log(GPR_ERROR,
1037 : "integer overflow in hpack integer decoding: have 0x%08x, "
1038 : "got byte 0x%02x",
1039 0 : *p->parsing.value, *cur);
1040 0 : return parse_error(p, cur, end);
1041 : }
1042 :
1043 : /* parse any trailing bytes in a varint: it's possible to append an arbitrary
1044 : number of 0x80's and not affect the value - a zero will terminate - and
1045 : anything else will overflow */
1046 0 : static int parse_value5up(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
1047 : const gpr_uint8 *end) {
1048 0 : while (cur != end && *cur == 0x80) {
1049 0 : ++cur;
1050 : }
1051 :
1052 0 : if (cur == end) {
1053 0 : p->state = parse_value5up;
1054 0 : return 1;
1055 : }
1056 :
1057 0 : if (*cur == 0) {
1058 0 : return parse_next(p, cur + 1, end);
1059 : }
1060 :
1061 0 : gpr_log(GPR_ERROR,
1062 : "integer overflow in hpack integer decoding: have 0x%08x, "
1063 : "got byte 0x%02x sometime after byte 4");
1064 0 : return parse_error(p, cur, end);
1065 : }
1066 :
1067 : /* parse a string prefix */
1068 259975 : static int parse_string_prefix(grpc_chttp2_hpack_parser *p,
1069 : const gpr_uint8 *cur, const gpr_uint8 *end) {
1070 259975 : if (cur == end) {
1071 3121 : p->state = parse_string_prefix;
1072 3121 : return 1;
1073 : }
1074 :
1075 256854 : p->strlen = (*cur) & 0x7f;
1076 256854 : p->huff = (*cur) >> 7;
1077 256854 : if (p->strlen == 0x7f) {
1078 2498 : p->parsing.value = &p->strlen;
1079 2498 : return parse_value0(p, cur + 1, end);
1080 : } else {
1081 254356 : return parse_next(p, cur + 1, end);
1082 : }
1083 : }
1084 :
1085 : /* append some bytes to a string */
1086 674998 : static void append_bytes(grpc_chttp2_hpack_parser_string *str,
1087 : const gpr_uint8 *data, size_t length) {
1088 674998 : if (length + str->length > str->capacity) {
1089 182570 : GPR_ASSERT(str->length + length <= GPR_UINT32_MAX);
1090 182570 : str->capacity = (gpr_uint32)(str->length + length);
1091 182570 : str->str = gpr_realloc(str->str, str->capacity);
1092 : }
1093 674998 : memcpy(str->str + str->length, data, length);
1094 674998 : GPR_ASSERT(length <= GPR_UINT32_MAX - str->length);
1095 674998 : str->length += (gpr_uint32)length;
1096 674998 : }
1097 :
1098 419736 : static int append_string(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
1099 : const gpr_uint8 *end) {
1100 419736 : grpc_chttp2_hpack_parser_string *str = p->parsing.str;
1101 : gpr_uint32 bits;
1102 : gpr_uint8 decoded[3];
1103 419736 : switch ((binary_state)p->binary) {
1104 : case NOT_BINARY:
1105 417568 : append_bytes(str, cur, (size_t)(end - cur));
1106 417568 : return 1;
1107 : b64_byte0:
1108 : case B64_BYTE0:
1109 1070 : if (cur == end) {
1110 494 : p->binary = B64_BYTE0;
1111 494 : return 1;
1112 : }
1113 576 : bits = inverse_base64[*cur];
1114 576 : ++cur;
1115 576 : if (bits == 255)
1116 0 : return 0;
1117 576 : else if (bits == 64)
1118 0 : goto b64_byte0;
1119 576 : p->base64_buffer = bits << 18;
1120 : /* fallthrough */
1121 : b64_byte1:
1122 : case B64_BYTE1:
1123 1152 : if (cur == end) {
1124 576 : p->binary = B64_BYTE1;
1125 576 : return 1;
1126 : }
1127 576 : bits = inverse_base64[*cur];
1128 576 : ++cur;
1129 576 : if (bits == 255)
1130 0 : return 0;
1131 576 : else if (bits == 64)
1132 0 : goto b64_byte1;
1133 576 : p->base64_buffer |= bits << 12;
1134 : /* fallthrough */
1135 : b64_byte2:
1136 : case B64_BYTE2:
1137 1098 : if (cur == end) {
1138 576 : p->binary = B64_BYTE2;
1139 576 : return 1;
1140 : }
1141 522 : bits = inverse_base64[*cur];
1142 522 : ++cur;
1143 522 : if (bits == 255)
1144 0 : return 0;
1145 522 : else if (bits == 64)
1146 0 : goto b64_byte2;
1147 522 : p->base64_buffer |= bits << 6;
1148 : /* fallthrough */
1149 : b64_byte3:
1150 : case B64_BYTE3:
1151 1016 : if (cur == end) {
1152 522 : p->binary = B64_BYTE3;
1153 522 : return 1;
1154 : }
1155 494 : bits = inverse_base64[*cur];
1156 494 : ++cur;
1157 494 : if (bits == 255)
1158 0 : return 0;
1159 494 : else if (bits == 64)
1160 0 : goto b64_byte3;
1161 494 : p->base64_buffer |= bits;
1162 494 : bits = p->base64_buffer;
1163 494 : decoded[0] = (gpr_uint8)(bits >> 16);
1164 494 : decoded[1] = (gpr_uint8)(bits >> 8);
1165 494 : decoded[2] = (gpr_uint8)(bits);
1166 494 : append_bytes(str, decoded, 3);
1167 494 : goto b64_byte0;
1168 : }
1169 0 : GPR_UNREACHABLE_CODE(return 1);
1170 : }
1171 :
1172 : /* append a null terminator to a string */
1173 256854 : static int finish_str(grpc_chttp2_hpack_parser *p) {
1174 256854 : gpr_uint8 terminator = 0;
1175 : gpr_uint8 decoded[2];
1176 : gpr_uint32 bits;
1177 256854 : grpc_chttp2_hpack_parser_string *str = p->parsing.str;
1178 256854 : switch ((binary_state)p->binary) {
1179 : case NOT_BINARY:
1180 256744 : break;
1181 : case B64_BYTE0:
1182 28 : break;
1183 : case B64_BYTE1:
1184 0 : gpr_log(GPR_ERROR, "illegal base64 encoding");
1185 0 : return 0; /* illegal encoding */
1186 : case B64_BYTE2:
1187 54 : bits = p->base64_buffer;
1188 54 : if (bits & 0xffff) {
1189 0 : gpr_log(GPR_ERROR, "trailing bits in base64 encoding: 0x%04x",
1190 : bits & 0xffff);
1191 0 : return 0;
1192 : }
1193 54 : decoded[0] = (gpr_uint8)(bits >> 16);
1194 54 : append_bytes(str, decoded, 1);
1195 54 : break;
1196 : case B64_BYTE3:
1197 28 : bits = p->base64_buffer;
1198 28 : if (bits & 0xff) {
1199 0 : gpr_log(GPR_ERROR, "trailing bits in base64 encoding: 0x%02x",
1200 : bits & 0xff);
1201 0 : return 0;
1202 : }
1203 28 : decoded[0] = (gpr_uint8)(bits >> 16);
1204 28 : decoded[1] = (gpr_uint8)(bits >> 8);
1205 28 : append_bytes(str, decoded, 2);
1206 28 : break;
1207 : }
1208 256854 : append_bytes(str, &terminator, 1);
1209 256854 : p->parsing.str->length--; /* don't actually count the null terminator */
1210 256854 : return 1;
1211 : }
1212 :
1213 : /* decode a nibble from a huffman encoded stream */
1214 4236 : static int huff_nibble(grpc_chttp2_hpack_parser *p, gpr_uint8 nibble) {
1215 4236 : gpr_int16 emit = emit_sub_tbl[16 * emit_tbl[p->huff_state] + nibble];
1216 4236 : gpr_int16 next = next_sub_tbl[16 * next_tbl[p->huff_state] + nibble];
1217 4236 : if (emit != -1) {
1218 5132 : if (emit >= 0 && emit < 256) {
1219 2566 : gpr_uint8 c = (gpr_uint8)emit;
1220 2566 : if (!append_string(p, &c, (&c) + 1)) return 0;
1221 : } else {
1222 0 : assert(emit == 256);
1223 : }
1224 : }
1225 4236 : p->huff_state = next;
1226 4236 : return 1;
1227 : }
1228 :
1229 : /* decode full bytes from a huffman encoded stream */
1230 420 : static int add_huff_bytes(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
1231 : const gpr_uint8 *end) {
1232 2538 : for (; cur != end; ++cur) {
1233 2118 : if (!huff_nibble(p, *cur >> 4) || !huff_nibble(p, *cur & 0xf)) return 0;
1234 : }
1235 420 : return 1;
1236 : }
1237 :
1238 : /* decode some string bytes based on the current decoding mode
1239 : (huffman or not) */
1240 417590 : static int add_str_bytes(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
1241 : const gpr_uint8 *end) {
1242 417590 : if (p->huff) {
1243 420 : return add_huff_bytes(p, cur, end);
1244 : } else {
1245 417170 : return append_string(p, cur, end);
1246 : }
1247 : }
1248 :
1249 : /* parse a string - tries to do large chunks at a time */
1250 417590 : static int parse_string(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
1251 : const gpr_uint8 *end) {
1252 417590 : size_t remaining = p->strlen - p->strgot;
1253 417590 : size_t given = (size_t)(end - cur);
1254 417590 : if (remaining <= given) {
1255 513708 : return add_str_bytes(p, cur, cur + remaining) && finish_str(p) &&
1256 256854 : parse_next(p, cur + remaining, end);
1257 : } else {
1258 160736 : if (!add_str_bytes(p, cur, cur + given)) return 0;
1259 160736 : GPR_ASSERT(given <= GPR_UINT32_MAX - p->strgot);
1260 160736 : p->strgot += (gpr_uint32)given;
1261 160736 : p->state = parse_string;
1262 160736 : return 1;
1263 : }
1264 : }
1265 :
1266 : /* begin parsing a string - performs setup, calls parse_string */
1267 256854 : static int begin_parse_string(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
1268 : const gpr_uint8 *end, gpr_uint8 binary,
1269 : grpc_chttp2_hpack_parser_string *str) {
1270 256854 : p->strgot = 0;
1271 256854 : str->length = 0;
1272 256854 : p->parsing.str = str;
1273 256854 : p->huff_state = 0;
1274 256854 : p->binary = binary;
1275 256854 : return parse_string(p, cur, end);
1276 : }
1277 :
1278 : /* parse the key string */
1279 119495 : static int parse_key_string(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
1280 : const gpr_uint8 *end) {
1281 119495 : return begin_parse_string(p, cur, end, NOT_BINARY, &p->key);
1282 : }
1283 :
1284 : /* check if a key represents a binary header or not */
1285 : typedef enum { BINARY_HEADER, PLAINTEXT_HEADER, ERROR_HEADER } is_binary_header;
1286 :
1287 119495 : static is_binary_header is_binary_literal_header(grpc_chttp2_hpack_parser *p) {
1288 238990 : return grpc_is_binary_header(p->key.str, p->key.length) ? BINARY_HEADER
1289 119495 : : PLAINTEXT_HEADER;
1290 : }
1291 :
1292 17864 : static is_binary_header is_binary_indexed_header(grpc_chttp2_hpack_parser *p) {
1293 17864 : grpc_mdelem *elem = grpc_chttp2_hptbl_lookup(&p->table, p->index);
1294 17864 : if (!elem) return ERROR_HEADER;
1295 89320 : return grpc_is_binary_header(
1296 35728 : (const char *)GPR_SLICE_START_PTR(elem->key->slice),
1297 35728 : GPR_SLICE_LENGTH(elem->key->slice))
1298 : ? BINARY_HEADER
1299 17864 : : PLAINTEXT_HEADER;
1300 : }
1301 :
1302 : /* parse the value string */
1303 137359 : static int parse_value_string(grpc_chttp2_hpack_parser *p, const gpr_uint8 *cur,
1304 : const gpr_uint8 *end, is_binary_header type) {
1305 137359 : switch (type) {
1306 : case BINARY_HEADER:
1307 110 : return begin_parse_string(p, cur, end, B64_BYTE0, &p->value);
1308 : case PLAINTEXT_HEADER:
1309 137249 : return begin_parse_string(p, cur, end, NOT_BINARY, &p->value);
1310 : case ERROR_HEADER:
1311 0 : return 0;
1312 : }
1313 : /* Add code to prevent return without value error */
1314 0 : GPR_UNREACHABLE_CODE(return 0);
1315 : }
1316 :
1317 17864 : static int parse_value_string_with_indexed_key(grpc_chttp2_hpack_parser *p,
1318 : const gpr_uint8 *cur,
1319 : const gpr_uint8 *end) {
1320 17864 : return parse_value_string(p, cur, end, is_binary_indexed_header(p));
1321 : }
1322 :
1323 119495 : static int parse_value_string_with_literal_key(grpc_chttp2_hpack_parser *p,
1324 : const gpr_uint8 *cur,
1325 : const gpr_uint8 *end) {
1326 119495 : return parse_value_string(p, cur, end, is_binary_literal_header(p));
1327 : }
1328 :
1329 : /* PUBLIC INTERFACE */
1330 :
1331 0 : static void on_header_not_set(void *user_data, grpc_mdelem *md) {
1332 0 : char *keyhex = gpr_dump_slice(md->key->slice, GPR_DUMP_HEX | GPR_DUMP_ASCII);
1333 0 : char *valuehex =
1334 0 : gpr_dump_slice(md->value->slice, GPR_DUMP_HEX | GPR_DUMP_ASCII);
1335 0 : gpr_log(GPR_ERROR, "on_header callback not set; key=%s value=%s", keyhex,
1336 : valuehex);
1337 0 : gpr_free(keyhex);
1338 0 : gpr_free(valuehex);
1339 0 : GRPC_MDELEM_UNREF(md);
1340 0 : abort();
1341 : }
1342 :
1343 4033 : void grpc_chttp2_hpack_parser_init(grpc_chttp2_hpack_parser *p,
1344 : grpc_mdctx *mdctx) {
1345 4033 : p->on_header = on_header_not_set;
1346 4033 : p->on_header_user_data = NULL;
1347 4033 : p->state = parse_begin;
1348 4033 : p->key.str = NULL;
1349 4033 : p->key.capacity = 0;
1350 4033 : p->key.length = 0;
1351 4033 : p->value.str = NULL;
1352 4033 : p->value.capacity = 0;
1353 4033 : p->value.length = 0;
1354 4033 : grpc_chttp2_hptbl_init(&p->table, mdctx);
1355 4035 : }
1356 :
1357 0 : void grpc_chttp2_hpack_parser_set_has_priority(grpc_chttp2_hpack_parser *p) {
1358 0 : p->after_prioritization = p->state;
1359 0 : p->state = parse_stream_dep0;
1360 0 : }
1361 :
1362 4035 : void grpc_chttp2_hpack_parser_destroy(grpc_chttp2_hpack_parser *p) {
1363 4035 : grpc_chttp2_hptbl_destroy(&p->table);
1364 4035 : gpr_free(p->key.str);
1365 4035 : gpr_free(p->value.str);
1366 4035 : }
1367 :
1368 4384420 : int grpc_chttp2_hpack_parser_parse(grpc_chttp2_hpack_parser *p,
1369 : const gpr_uint8 *beg, const gpr_uint8 *end) {
1370 : /* TODO(ctiller): limit the distance of end from beg, and perform multiple
1371 : steps in the event of a large chunk of data to limit
1372 : stack space usage when no tail call optimization is
1373 : available */
1374 4384420 : return p->state(p, beg, end);
1375 : }
1376 :
1377 4273863 : grpc_chttp2_parse_error grpc_chttp2_header_parser_parse(
1378 : grpc_exec_ctx *exec_ctx, void *hpack_parser,
1379 : grpc_chttp2_transport_parsing *transport_parsing,
1380 : grpc_chttp2_stream_parsing *stream_parsing, gpr_slice slice, int is_last) {
1381 4273863 : grpc_chttp2_hpack_parser *parser = hpack_parser;
1382 8714093 : if (!grpc_chttp2_hpack_parser_parse(parser, GPR_SLICE_START_PTR(slice),
1383 8714093 : GPR_SLICE_END_PTR(slice))) {
1384 0 : return GRPC_CHTTP2_CONNECTION_ERROR;
1385 : }
1386 4271012 : if (is_last) {
1387 4103231 : if (parser->is_boundary && parser->state != parse_begin) {
1388 0 : gpr_log(GPR_ERROR,
1389 : "end of header frame not aligned with a hpack record boundary");
1390 0 : return GRPC_CHTTP2_CONNECTION_ERROR;
1391 : }
1392 4103231 : if (parser->is_boundary) {
1393 4103338 : grpc_chttp2_incoming_metadata_buffer_place_metadata_batch_into(
1394 : &stream_parsing->incoming_metadata,
1395 : &stream_parsing->data_parser.incoming_sopb);
1396 4106890 : grpc_chttp2_list_add_parsing_seen_stream(transport_parsing,
1397 : stream_parsing);
1398 : }
1399 4106758 : if (parser->is_eof) {
1400 1403963 : stream_parsing->received_close = 1;
1401 : }
1402 4106758 : parser->on_header = on_header_not_set;
1403 4106758 : parser->on_header_user_data = NULL;
1404 4106758 : parser->is_boundary = 0xde;
1405 4106758 : parser->is_eof = 0xde;
1406 : }
1407 4274539 : return GRPC_CHTTP2_PARSE_OK;
1408 : }
|