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 #include <grpc/support/port_platform.h>
20
21 #include "src/core/ext/transport/chttp2/transport/hpack_parser.h"
22 #include "src/core/ext/transport/chttp2/transport/internal.h"
23
24 #include <assert.h>
25 #include <stddef.h>
26 #include <string.h>
27
28 #include <grpc/support/alloc.h>
29 #include <grpc/support/log.h>
30 #include <grpc/support/string_util.h>
31
32 #include "src/core/ext/transport/chttp2/transport/bin_encoder.h"
33 #include "src/core/lib/debug/stats.h"
34 #include "src/core/lib/gpr/string.h"
35 #include "src/core/lib/profiling/timers.h"
36 #include "src/core/lib/slice/slice_internal.h"
37 #include "src/core/lib/slice/slice_string_helpers.h"
38 #include "src/core/lib/surface/validate_metadata.h"
39 #include "src/core/lib/transport/http2_errors.h"
40
41 grpc_core::DebugOnlyTraceFlag grpc_trace_chttp2_hpack_parser(
42 false, "chttp2_hpack_parser");
43
44 typedef enum {
45 NOT_BINARY,
46 BINARY_BEGIN,
47 B64_BYTE0,
48 B64_BYTE1,
49 B64_BYTE2,
50 B64_BYTE3
51 } binary_state;
52
53 /* How parsing works:
54
55 The parser object keeps track of a function pointer which represents the
56 current parse state.
57
58 Each time new bytes are presented, we call into the current state, which
59 recursively parses until all bytes in the given chunk are exhausted.
60
61 The parse state that terminates then saves its function pointer to be the
62 current state so that it can resume when more bytes are available.
63
64 It's expected that most optimizing compilers will turn this code into
65 a set of indirect jumps, and so not waste stack space. */
66
67 /* forward declarations for parsing states */
68 static grpc_error* parse_begin(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
69 const uint8_t* end);
70 static grpc_error* parse_error(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
71 const uint8_t* end, grpc_error* error);
72 static grpc_error* still_parse_error(grpc_chttp2_hpack_parser* p,
73 const uint8_t* cur, const uint8_t* end);
74 static grpc_error* parse_illegal_op(grpc_chttp2_hpack_parser* p,
75 const uint8_t* cur, const uint8_t* end);
76
77 static grpc_error* parse_string_prefix(grpc_chttp2_hpack_parser* p,
78 const uint8_t* cur, const uint8_t* end);
79 static grpc_error* parse_key_string(grpc_chttp2_hpack_parser* p,
80 const uint8_t* cur, const uint8_t* end);
81 static grpc_error* parse_value_string_with_indexed_key(
82 grpc_chttp2_hpack_parser* p, const uint8_t* cur, const uint8_t* end);
83 static grpc_error* parse_value_string_with_literal_key(
84 grpc_chttp2_hpack_parser* p, const uint8_t* cur, const uint8_t* end);
85
86 static grpc_error* parse_value0(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
87 const uint8_t* end);
88 static grpc_error* parse_value1(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
89 const uint8_t* end);
90 static grpc_error* parse_value2(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
91 const uint8_t* end);
92 static grpc_error* parse_value3(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
93 const uint8_t* end);
94 static grpc_error* parse_value4(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
95 const uint8_t* end);
96 static grpc_error* parse_value5up(grpc_chttp2_hpack_parser* p,
97 const uint8_t* cur, const uint8_t* end);
98
99 static grpc_error* parse_indexed_field(grpc_chttp2_hpack_parser* p,
100 const uint8_t* cur, const uint8_t* end);
101 static grpc_error* parse_indexed_field_x(grpc_chttp2_hpack_parser* p,
102 const uint8_t* cur,
103 const uint8_t* end);
104 static grpc_error* parse_lithdr_incidx(grpc_chttp2_hpack_parser* p,
105 const uint8_t* cur, const uint8_t* end);
106 static grpc_error* parse_lithdr_incidx_x(grpc_chttp2_hpack_parser* p,
107 const uint8_t* cur,
108 const uint8_t* end);
109 static grpc_error* parse_lithdr_incidx_v(grpc_chttp2_hpack_parser* p,
110 const uint8_t* cur,
111 const uint8_t* end);
112 static grpc_error* parse_lithdr_notidx(grpc_chttp2_hpack_parser* p,
113 const uint8_t* cur, const uint8_t* end);
114 static grpc_error* parse_lithdr_notidx_x(grpc_chttp2_hpack_parser* p,
115 const uint8_t* cur,
116 const uint8_t* end);
117 static grpc_error* parse_lithdr_notidx_v(grpc_chttp2_hpack_parser* p,
118 const uint8_t* cur,
119 const uint8_t* end);
120 static grpc_error* parse_lithdr_nvridx(grpc_chttp2_hpack_parser* p,
121 const uint8_t* cur, const uint8_t* end);
122 static grpc_error* parse_lithdr_nvridx_x(grpc_chttp2_hpack_parser* p,
123 const uint8_t* cur,
124 const uint8_t* end);
125 static grpc_error* parse_lithdr_nvridx_v(grpc_chttp2_hpack_parser* p,
126 const uint8_t* cur,
127 const uint8_t* end);
128 static grpc_error* parse_max_tbl_size(grpc_chttp2_hpack_parser* p,
129 const uint8_t* cur, const uint8_t* end);
130 static grpc_error* parse_max_tbl_size_x(grpc_chttp2_hpack_parser* p,
131 const uint8_t* cur, const uint8_t* end);
132
133 /* we translate the first byte of a hpack field into one of these decoding
134 cases, then use a lookup table to jump directly to the appropriate parser.
135
136 _X => the integer index is all ones, meaning we need to do varint decoding
137 _V => the integer index is all zeros, meaning we need to decode an additional
138 string value */
139 typedef enum {
140 INDEXED_FIELD,
141 INDEXED_FIELD_X,
142 LITHDR_INCIDX,
143 LITHDR_INCIDX_X,
144 LITHDR_INCIDX_V,
145 LITHDR_NOTIDX,
146 LITHDR_NOTIDX_X,
147 LITHDR_NOTIDX_V,
148 LITHDR_NVRIDX,
149 LITHDR_NVRIDX_X,
150 LITHDR_NVRIDX_V,
151 MAX_TBL_SIZE,
152 MAX_TBL_SIZE_X,
153 ILLEGAL
154 } first_byte_type;
155
156 /* jump table of parse state functions -- order must match first_byte_type
157 above */
158 static const grpc_chttp2_hpack_parser_state first_byte_action[] = {
159 parse_indexed_field, parse_indexed_field_x, parse_lithdr_incidx,
160 parse_lithdr_incidx_x, parse_lithdr_incidx_v, parse_lithdr_notidx,
161 parse_lithdr_notidx_x, parse_lithdr_notidx_v, parse_lithdr_nvridx,
162 parse_lithdr_nvridx_x, parse_lithdr_nvridx_v, parse_max_tbl_size,
163 parse_max_tbl_size_x, parse_illegal_op};
164
165 /* indexes the first byte to a parse state function - generated by
166 gen_hpack_tables.c */
167 static const uint8_t first_byte_lut[256] = {
168 LITHDR_NOTIDX_V, LITHDR_NOTIDX, LITHDR_NOTIDX, LITHDR_NOTIDX,
169 LITHDR_NOTIDX, LITHDR_NOTIDX, LITHDR_NOTIDX, LITHDR_NOTIDX,
170 LITHDR_NOTIDX, LITHDR_NOTIDX, LITHDR_NOTIDX, LITHDR_NOTIDX,
171 LITHDR_NOTIDX, LITHDR_NOTIDX, LITHDR_NOTIDX, LITHDR_NOTIDX_X,
172 LITHDR_NVRIDX_V, LITHDR_NVRIDX, LITHDR_NVRIDX, LITHDR_NVRIDX,
173 LITHDR_NVRIDX, LITHDR_NVRIDX, LITHDR_NVRIDX, LITHDR_NVRIDX,
174 LITHDR_NVRIDX, LITHDR_NVRIDX, LITHDR_NVRIDX, LITHDR_NVRIDX,
175 LITHDR_NVRIDX, LITHDR_NVRIDX, LITHDR_NVRIDX, LITHDR_NVRIDX_X,
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,
178 MAX_TBL_SIZE, MAX_TBL_SIZE, MAX_TBL_SIZE, MAX_TBL_SIZE,
179 MAX_TBL_SIZE, MAX_TBL_SIZE, MAX_TBL_SIZE, MAX_TBL_SIZE,
180 MAX_TBL_SIZE, MAX_TBL_SIZE, MAX_TBL_SIZE, MAX_TBL_SIZE,
181 MAX_TBL_SIZE, MAX_TBL_SIZE, MAX_TBL_SIZE, MAX_TBL_SIZE,
182 MAX_TBL_SIZE, MAX_TBL_SIZE, MAX_TBL_SIZE, MAX_TBL_SIZE,
183 MAX_TBL_SIZE, MAX_TBL_SIZE, MAX_TBL_SIZE, MAX_TBL_SIZE_X,
184 LITHDR_INCIDX_V, 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,
194 LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX,
195 LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX,
196 LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX,
197 LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX,
198 LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX,
199 LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX, LITHDR_INCIDX_X,
200 ILLEGAL, 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,
226 INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
227 INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
228 INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
229 INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
230 INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD,
231 INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD, INDEXED_FIELD_X,
232 };
233
234 /* state table for huffman decoding: given a state, gives an index/16 into
235 next_sub_tbl. Taking that index and adding the value of the nibble being
236 considered returns the next state.
237
238 generated by gen_hpack_tables.c */
239 static const uint8_t next_tbl[256] = {
240 0, 1, 2, 3, 4, 1, 2, 5, 6, 1, 7, 8, 1, 3, 3, 9, 10, 11, 1, 1,
241 1, 12, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2,
242 14, 1, 15, 16, 1, 17, 1, 15, 2, 7, 3, 18, 19, 1, 1, 1, 1, 20, 1, 1,
243 1, 1, 1, 1, 1, 1, 1, 1, 15, 2, 2, 7, 21, 1, 22, 1, 1, 1, 1, 1,
244 1, 1, 1, 15, 2, 2, 2, 2, 2, 2, 23, 24, 25, 1, 1, 1, 1, 2, 2, 2,
245 26, 3, 3, 27, 10, 28, 1, 1, 1, 1, 1, 1, 2, 3, 29, 10, 30, 1, 1, 1,
246 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 31, 1, 1, 1, 1, 1, 1, 1, 2,
247 2, 2, 2, 2, 2, 2, 2, 32, 1, 1, 15, 33, 1, 34, 35, 9, 36, 1, 1, 1,
248 1, 1, 1, 1, 37, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 26, 9,
249 38, 1, 1, 1, 1, 1, 1, 1, 15, 2, 2, 2, 2, 26, 3, 3, 39, 1, 1, 1,
250 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 7, 3, 3, 3, 40, 2,
251 41, 1, 1, 1, 42, 43, 1, 1, 44, 1, 1, 1, 1, 15, 2, 2, 2, 2, 2, 2,
252 3, 3, 3, 45, 46, 1, 1, 2, 2, 2, 35, 3, 3, 18, 47, 2,
253 };
254
255 /* next state, based upon current state and the current nibble: see above.
256 generated by gen_hpack_tables.c */
257 static const int16_t next_sub_tbl[48 * 16] = {
258 1, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217,
259 218, 2, 6, 10, 13, 14, 15, 16, 17, 2, 6, 10, 13, 14, 15,
260 16, 17, 3, 7, 11, 24, 3, 7, 11, 24, 3, 7, 11, 24, 3,
261 7, 11, 24, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8,
262 4, 8, 4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5,
263 199, 200, 201, 202, 203, 4, 8, 4, 8, 0, 0, 0, 0, 0, 0,
264 0, 0, 0, 0, 0, 0, 9, 133, 134, 135, 136, 137, 138, 139, 140,
265 141, 142, 143, 144, 145, 146, 147, 3, 7, 11, 24, 3, 7, 11, 24,
266 4, 8, 4, 8, 4, 8, 4, 8, 0, 0, 0, 0, 0, 0, 0,
267 0, 0, 0, 0, 0, 0, 0, 12, 132, 4, 8, 4, 8, 4, 8,
268 4, 8, 4, 8, 4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0,
269 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
270 0, 0, 0, 0, 0, 0, 0, 0, 18, 19, 20, 21, 4, 8, 4,
271 8, 4, 8, 4, 8, 4, 8, 0, 0, 0, 22, 23, 91, 25, 26,
272 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 3,
273 7, 11, 24, 3, 7, 11, 24, 0, 0, 0, 0, 0, 41, 42, 43,
274 2, 6, 10, 13, 14, 15, 16, 17, 3, 7, 11, 24, 3, 7, 11,
275 24, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 0, 0,
276 44, 45, 2, 6, 10, 13, 14, 15, 16, 17, 46, 47, 48, 49, 50,
277 51, 52, 57, 4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
278 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
279 0, 53, 54, 55, 56, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67,
280 68, 69, 70, 71, 72, 74, 0, 0, 0, 0, 0, 0, 0, 0, 0,
281 0, 0, 0, 0, 0, 0, 73, 75, 76, 77, 78, 79, 80, 81, 82,
282 83, 84, 85, 86, 87, 88, 89, 90, 3, 7, 11, 24, 3, 7, 11,
283 24, 3, 7, 11, 24, 0, 0, 0, 0, 3, 7, 11, 24, 3, 7,
284 11, 24, 4, 8, 4, 8, 0, 0, 0, 92, 0, 0, 0, 93, 94,
285 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 3, 7, 11, 24,
286 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4,
287 8, 4, 8, 4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
288 0, 0, 0, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 4,
289 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 0, 0,
290 0, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130,
291 131, 2, 6, 10, 13, 14, 15, 16, 17, 4, 8, 4, 8, 4, 8,
292 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 148,
293 149, 150, 151, 3, 7, 11, 24, 4, 8, 4, 8, 0, 0, 0, 0,
294 0, 0, 152, 153, 3, 7, 11, 24, 3, 7, 11, 24, 3, 7, 11,
295 24, 154, 155, 156, 164, 3, 7, 11, 24, 3, 7, 11, 24, 3, 7,
296 11, 24, 4, 8, 4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0,
297 157, 158, 159, 160, 161, 162, 163, 165, 166, 167, 168, 169, 170, 171, 172,
298 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187,
299 188, 189, 190, 191, 192, 193, 194, 195, 196, 4, 8, 4, 8, 4, 8,
300 4, 8, 4, 8, 4, 8, 4, 8, 197, 198, 4, 8, 4, 8, 4,
301 8, 4, 8, 0, 0, 0, 0, 0, 0, 219, 220, 3, 7, 11, 24,
302 4, 8, 4, 8, 4, 8, 0, 0, 221, 222, 223, 224, 3, 7, 11,
303 24, 3, 7, 11, 24, 4, 8, 4, 8, 4, 8, 225, 228, 4, 8,
304 4, 8, 4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 226, 227, 229,
305 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244,
306 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 0, 0, 0, 0, 0,
307 0, 0, 0, 0, 0, 0, 0, 245, 246, 247, 248, 249, 250, 251, 252,
308 253, 254, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
309 0, 0, 255,
310 };
311
312 /* emission table: indexed like next_tbl, ultimately gives the byte to be
313 emitted, or -1 for no byte, or 256 for end of stream
314
315 generated by gen_hpack_tables.c */
316 static const uint16_t emit_tbl[256] = {
317 0, 1, 2, 3, 4, 5, 6, 7, 0, 8, 9, 10, 11, 12, 13,
318 14, 15, 16, 17, 18, 19, 20, 21, 22, 0, 23, 24, 25, 26, 27,
319 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42,
320 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 0, 55, 56,
321 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 0,
322 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85,
323 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100,
324 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115,
325 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130,
326 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145,
327 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 0,
328 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174,
329 0, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188,
330 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203,
331 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218,
332 219, 220, 221, 0, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232,
333 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247,
334 248,
335 };
336
337 /* generated by gen_hpack_tables.c */
338 static const int16_t emit_sub_tbl[249 * 16] = {
339 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
340 -1, 48, 48, 48, 48, 48, 48, 48, 48, 49, 49, 49, 49, 49, 49,
341 49, 49, 48, 48, 48, 48, 49, 49, 49, 49, 50, 50, 50, 50, 97,
342 97, 97, 97, 48, 48, 49, 49, 50, 50, 97, 97, 99, 99, 101, 101,
343 105, 105, 111, 111, 48, 49, 50, 97, 99, 101, 105, 111, 115, 116, -1,
344 -1, -1, -1, -1, -1, 32, 32, 32, 32, 32, 32, 32, 32, 37, 37,
345 37, 37, 37, 37, 37, 37, 99, 99, 99, 99, 101, 101, 101, 101, 105,
346 105, 105, 105, 111, 111, 111, 111, 115, 115, 116, 116, 32, 37, 45, 46,
347 47, 51, 52, 53, 54, 55, 56, 57, 61, 61, 61, 61, 61, 61, 61,
348 61, 65, 65, 65, 65, 65, 65, 65, 65, 115, 115, 115, 115, 116, 116,
349 116, 116, 32, 32, 37, 37, 45, 45, 46, 46, 61, 65, 95, 98, 100,
350 102, 103, 104, 108, 109, 110, 112, 114, 117, -1, -1, 58, 58, 58, 58,
351 58, 58, 58, 58, 66, 66, 66, 66, 66, 66, 66, 66, 47, 47, 51,
352 51, 52, 52, 53, 53, 54, 54, 55, 55, 56, 56, 57, 57, 61, 61,
353 65, 65, 95, 95, 98, 98, 100, 100, 102, 102, 103, 103, 104, 104, 108,
354 108, 109, 109, 110, 110, 112, 112, 114, 114, 117, 117, 58, 66, 67, 68,
355 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83,
356 84, 85, 86, 87, 89, 106, 107, 113, 118, 119, 120, 121, 122, -1, -1,
357 -1, -1, 38, 38, 38, 38, 38, 38, 38, 38, 42, 42, 42, 42, 42,
358 42, 42, 42, 44, 44, 44, 44, 44, 44, 44, 44, 59, 59, 59, 59,
359 59, 59, 59, 59, 88, 88, 88, 88, 88, 88, 88, 88, 90, 90, 90,
360 90, 90, 90, 90, 90, 33, 33, 34, 34, 40, 40, 41, 41, 63, 63,
361 39, 43, 124, -1, -1, -1, 35, 35, 35, 35, 35, 35, 35, 35, 62,
362 62, 62, 62, 62, 62, 62, 62, 0, 0, 0, 0, 36, 36, 36, 36,
363 64, 64, 64, 64, 91, 91, 91, 91, 69, 69, 69, 69, 69, 69, 69,
364 69, 70, 70, 70, 70, 70, 70, 70, 70, 71, 71, 71, 71, 71, 71,
365 71, 71, 72, 72, 72, 72, 72, 72, 72, 72, 73, 73, 73, 73, 73,
366 73, 73, 73, 74, 74, 74, 74, 74, 74, 74, 74, 75, 75, 75, 75,
367 75, 75, 75, 75, 76, 76, 76, 76, 76, 76, 76, 76, 77, 77, 77,
368 77, 77, 77, 77, 77, 78, 78, 78, 78, 78, 78, 78, 78, 79, 79,
369 79, 79, 79, 79, 79, 79, 80, 80, 80, 80, 80, 80, 80, 80, 81,
370 81, 81, 81, 81, 81, 81, 81, 82, 82, 82, 82, 82, 82, 82, 82,
371 83, 83, 83, 83, 83, 83, 83, 83, 84, 84, 84, 84, 84, 84, 84,
372 84, 85, 85, 85, 85, 85, 85, 85, 85, 86, 86, 86, 86, 86, 86,
373 86, 86, 87, 87, 87, 87, 87, 87, 87, 87, 89, 89, 89, 89, 89,
374 89, 89, 89, 106, 106, 106, 106, 106, 106, 106, 106, 107, 107, 107, 107,
375 107, 107, 107, 107, 113, 113, 113, 113, 113, 113, 113, 113, 118, 118, 118,
376 118, 118, 118, 118, 118, 119, 119, 119, 119, 119, 119, 119, 119, 120, 120,
377 120, 120, 120, 120, 120, 120, 121, 121, 121, 121, 121, 121, 121, 121, 122,
378 122, 122, 122, 122, 122, 122, 122, 38, 38, 38, 38, 42, 42, 42, 42,
379 44, 44, 44, 44, 59, 59, 59, 59, 88, 88, 88, 88, 90, 90, 90,
380 90, 33, 34, 40, 41, 63, -1, -1, -1, 39, 39, 39, 39, 39, 39,
381 39, 39, 43, 43, 43, 43, 43, 43, 43, 43, 124, 124, 124, 124, 124,
382 124, 124, 124, 35, 35, 35, 35, 62, 62, 62, 62, 0, 0, 36, 36,
383 64, 64, 91, 91, 93, 93, 126, 126, 94, 125, -1, -1, 60, 60, 60,
384 60, 60, 60, 60, 60, 96, 96, 96, 96, 96, 96, 96, 96, 123, 123,
385 123, 123, 123, 123, 123, 123, -1, -1, -1, -1, -1, -1, -1, -1, 92,
386 92, 92, 92, 92, 92, 92, 92, 195, 195, 195, 195, 195, 195, 195, 195,
387 208, 208, 208, 208, 208, 208, 208, 208, 128, 128, 128, 128, 130, 130, 130,
388 130, 131, 131, 131, 131, 162, 162, 162, 162, 184, 184, 184, 184, 194, 194,
389 194, 194, 224, 224, 224, 224, 226, 226, 226, 226, 153, 153, 161, 161, 167,
390 167, 172, 172, 176, 176, 177, 177, 179, 179, 209, 209, 216, 216, 217, 217,
391 227, 227, 229, 229, 230, 230, 129, 132, 133, 134, 136, 146, 154, 156, 160,
392 163, 164, 169, 170, 173, 178, 181, 185, 186, 187, 189, 190, 196, 198, 228,
393 232, 233, -1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 135,
394 135, 135, 135, 135, 135, 135, 135, 137, 137, 137, 137, 137, 137, 137, 137,
395 138, 138, 138, 138, 138, 138, 138, 138, 139, 139, 139, 139, 139, 139, 139,
396 139, 140, 140, 140, 140, 140, 140, 140, 140, 141, 141, 141, 141, 141, 141,
397 141, 141, 143, 143, 143, 143, 143, 143, 143, 143, 147, 147, 147, 147, 147,
398 147, 147, 147, 149, 149, 149, 149, 149, 149, 149, 149, 150, 150, 150, 150,
399 150, 150, 150, 150, 151, 151, 151, 151, 151, 151, 151, 151, 152, 152, 152,
400 152, 152, 152, 152, 152, 155, 155, 155, 155, 155, 155, 155, 155, 157, 157,
401 157, 157, 157, 157, 157, 157, 158, 158, 158, 158, 158, 158, 158, 158, 165,
402 165, 165, 165, 165, 165, 165, 165, 166, 166, 166, 166, 166, 166, 166, 166,
403 168, 168, 168, 168, 168, 168, 168, 168, 174, 174, 174, 174, 174, 174, 174,
404 174, 175, 175, 175, 175, 175, 175, 175, 175, 180, 180, 180, 180, 180, 180,
405 180, 180, 182, 182, 182, 182, 182, 182, 182, 182, 183, 183, 183, 183, 183,
406 183, 183, 183, 188, 188, 188, 188, 188, 188, 188, 188, 191, 191, 191, 191,
407 191, 191, 191, 191, 197, 197, 197, 197, 197, 197, 197, 197, 231, 231, 231,
408 231, 231, 231, 231, 231, 239, 239, 239, 239, 239, 239, 239, 239, 9, 9,
409 9, 9, 142, 142, 142, 142, 144, 144, 144, 144, 145, 145, 145, 145, 148,
410 148, 148, 148, 159, 159, 159, 159, 171, 171, 171, 171, 206, 206, 206, 206,
411 215, 215, 215, 215, 225, 225, 225, 225, 236, 236, 236, 236, 237, 237, 237,
412 237, 199, 199, 207, 207, 234, 234, 235, 235, 192, 193, 200, 201, 202, 205,
413 210, 213, 218, 219, 238, 240, 242, 243, 255, -1, 203, 203, 203, 203, 203,
414 203, 203, 203, 204, 204, 204, 204, 204, 204, 204, 204, 211, 211, 211, 211,
415 211, 211, 211, 211, 212, 212, 212, 212, 212, 212, 212, 212, 214, 214, 214,
416 214, 214, 214, 214, 214, 221, 221, 221, 221, 221, 221, 221, 221, 222, 222,
417 222, 222, 222, 222, 222, 222, 223, 223, 223, 223, 223, 223, 223, 223, 241,
418 241, 241, 241, 241, 241, 241, 241, 244, 244, 244, 244, 244, 244, 244, 244,
419 245, 245, 245, 245, 245, 245, 245, 245, 246, 246, 246, 246, 246, 246, 246,
420 246, 247, 247, 247, 247, 247, 247, 247, 247, 248, 248, 248, 248, 248, 248,
421 248, 248, 250, 250, 250, 250, 250, 250, 250, 250, 251, 251, 251, 251, 251,
422 251, 251, 251, 252, 252, 252, 252, 252, 252, 252, 252, 253, 253, 253, 253,
423 253, 253, 253, 253, 254, 254, 254, 254, 254, 254, 254, 254, 2, 2, 2,
424 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6,
425 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 11, 11, 11, 11, 12,
426 12, 12, 12, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16,
427 17, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19, 20, 20, 20,
428 20, 21, 21, 21, 21, 23, 23, 23, 23, 24, 24, 24, 24, 25, 25,
429 25, 25, 26, 26, 26, 26, 27, 27, 27, 27, 28, 28, 28, 28, 29,
430 29, 29, 29, 30, 30, 30, 30, 31, 31, 31, 31, 127, 127, 127, 127,
431 220, 220, 220, 220, 249, 249, 249, 249, 10, 13, 22, 256, 93, 93, 93,
432 93, 126, 126, 126, 126, 94, 94, 125, 125, 60, 96, 123, -1, 92, 195,
433 208, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 128,
434 128, 128, 128, 128, 128, 128, 128, 130, 130, 130, 130, 130, 130, 130, 130,
435 131, 131, 131, 131, 131, 131, 131, 131, 162, 162, 162, 162, 162, 162, 162,
436 162, 184, 184, 184, 184, 184, 184, 184, 184, 194, 194, 194, 194, 194, 194,
437 194, 194, 224, 224, 224, 224, 224, 224, 224, 224, 226, 226, 226, 226, 226,
438 226, 226, 226, 153, 153, 153, 153, 161, 161, 161, 161, 167, 167, 167, 167,
439 172, 172, 172, 172, 176, 176, 176, 176, 177, 177, 177, 177, 179, 179, 179,
440 179, 209, 209, 209, 209, 216, 216, 216, 216, 217, 217, 217, 217, 227, 227,
441 227, 227, 229, 229, 229, 229, 230, 230, 230, 230, 129, 129, 132, 132, 133,
442 133, 134, 134, 136, 136, 146, 146, 154, 154, 156, 156, 160, 160, 163, 163,
443 164, 164, 169, 169, 170, 170, 173, 173, 178, 178, 181, 181, 185, 185, 186,
444 186, 187, 187, 189, 189, 190, 190, 196, 196, 198, 198, 228, 228, 232, 232,
445 233, 233, 1, 135, 137, 138, 139, 140, 141, 143, 147, 149, 150, 151, 152,
446 155, 157, 158, 165, 166, 168, 174, 175, 180, 182, 183, 188, 191, 197, 231,
447 239, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 9, 9, 9,
448 9, 9, 9, 9, 9, 142, 142, 142, 142, 142, 142, 142, 142, 144, 144,
449 144, 144, 144, 144, 144, 144, 145, 145, 145, 145, 145, 145, 145, 145, 148,
450 148, 148, 148, 148, 148, 148, 148, 159, 159, 159, 159, 159, 159, 159, 159,
451 171, 171, 171, 171, 171, 171, 171, 171, 206, 206, 206, 206, 206, 206, 206,
452 206, 215, 215, 215, 215, 215, 215, 215, 215, 225, 225, 225, 225, 225, 225,
453 225, 225, 236, 236, 236, 236, 236, 236, 236, 236, 237, 237, 237, 237, 237,
454 237, 237, 237, 199, 199, 199, 199, 207, 207, 207, 207, 234, 234, 234, 234,
455 235, 235, 235, 235, 192, 192, 193, 193, 200, 200, 201, 201, 202, 202, 205,
456 205, 210, 210, 213, 213, 218, 218, 219, 219, 238, 238, 240, 240, 242, 242,
457 243, 243, 255, 255, 203, 204, 211, 212, 214, 221, 222, 223, 241, 244, 245,
458 246, 247, 248, 250, 251, 252, 253, 254, -1, -1, -1, -1, -1, -1, -1,
459 -1, -1, -1, -1, -1, -1, -1, -1, 2, 2, 2, 2, 2, 2, 2,
460 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4,
461 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6,
462 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8,
463 8, 8, 8, 8, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12,
464 12, 12, 12, 12, 12, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15,
465 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 17,
466 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 18,
467 19, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20,
468 20, 21, 21, 21, 21, 21, 21, 21, 21, 23, 23, 23, 23, 23, 23,
469 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25,
470 25, 25, 25, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27,
471 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29,
472 29, 29, 29, 29, 29, 30, 30, 30, 30, 30, 30, 30, 30, 31, 31,
473 31, 31, 31, 31, 31, 31, 127, 127, 127, 127, 127, 127, 127, 127, 220,
474 220, 220, 220, 220, 220, 220, 220, 249, 249, 249, 249, 249, 249, 249, 249,
475 10, 10, 13, 13, 22, 22, 256, 256, 67, 67, 67, 67, 67, 67, 67,
476 67, 68, 68, 68, 68, 68, 68, 68, 68, 95, 95, 95, 95, 95, 95,
477 95, 95, 98, 98, 98, 98, 98, 98, 98, 98, 100, 100, 100, 100, 100,
478 100, 100, 100, 102, 102, 102, 102, 102, 102, 102, 102, 103, 103, 103, 103,
479 103, 103, 103, 103, 104, 104, 104, 104, 104, 104, 104, 104, 108, 108, 108,
480 108, 108, 108, 108, 108, 109, 109, 109, 109, 109, 109, 109, 109, 110, 110,
481 110, 110, 110, 110, 110, 110, 112, 112, 112, 112, 112, 112, 112, 112, 114,
482 114, 114, 114, 114, 114, 114, 114, 117, 117, 117, 117, 117, 117, 117, 117,
483 58, 58, 58, 58, 66, 66, 66, 66, 67, 67, 67, 67, 68, 68, 68,
484 68, 69, 69, 69, 69, 70, 70, 70, 70, 71, 71, 71, 71, 72, 72,
485 72, 72, 73, 73, 73, 73, 74, 74, 74, 74, 75, 75, 75, 75, 76,
486 76, 76, 76, 77, 77, 77, 77, 78, 78, 78, 78, 79, 79, 79, 79,
487 80, 80, 80, 80, 81, 81, 81, 81, 82, 82, 82, 82, 83, 83, 83,
488 83, 84, 84, 84, 84, 85, 85, 85, 85, 86, 86, 86, 86, 87, 87,
489 87, 87, 89, 89, 89, 89, 106, 106, 106, 106, 107, 107, 107, 107, 113,
490 113, 113, 113, 118, 118, 118, 118, 119, 119, 119, 119, 120, 120, 120, 120,
491 121, 121, 121, 121, 122, 122, 122, 122, 38, 38, 42, 42, 44, 44, 59,
492 59, 88, 88, 90, 90, -1, -1, -1, -1, 33, 33, 33, 33, 33, 33,
493 33, 33, 34, 34, 34, 34, 34, 34, 34, 34, 40, 40, 40, 40, 40,
494 40, 40, 40, 41, 41, 41, 41, 41, 41, 41, 41, 63, 63, 63, 63,
495 63, 63, 63, 63, 39, 39, 39, 39, 43, 43, 43, 43, 124, 124, 124,
496 124, 35, 35, 62, 62, 0, 36, 64, 91, 93, 126, -1, -1, 94, 94,
497 94, 94, 94, 94, 94, 94, 125, 125, 125, 125, 125, 125, 125, 125, 60,
498 60, 60, 60, 96, 96, 96, 96, 123, 123, 123, 123, -1, -1, -1, -1,
499 92, 92, 92, 92, 195, 195, 195, 195, 208, 208, 208, 208, 128, 128, 130,
500 130, 131, 131, 162, 162, 184, 184, 194, 194, 224, 224, 226, 226, 153, 161,
501 167, 172, 176, 177, 179, 209, 216, 217, 227, 229, 230, -1, -1, -1, -1,
502 -1, -1, -1, 129, 129, 129, 129, 129, 129, 129, 129, 132, 132, 132, 132,
503 132, 132, 132, 132, 133, 133, 133, 133, 133, 133, 133, 133, 134, 134, 134,
504 134, 134, 134, 134, 134, 136, 136, 136, 136, 136, 136, 136, 136, 146, 146,
505 146, 146, 146, 146, 146, 146, 154, 154, 154, 154, 154, 154, 154, 154, 156,
506 156, 156, 156, 156, 156, 156, 156, 160, 160, 160, 160, 160, 160, 160, 160,
507 163, 163, 163, 163, 163, 163, 163, 163, 164, 164, 164, 164, 164, 164, 164,
508 164, 169, 169, 169, 169, 169, 169, 169, 169, 170, 170, 170, 170, 170, 170,
509 170, 170, 173, 173, 173, 173, 173, 173, 173, 173, 178, 178, 178, 178, 178,
510 178, 178, 178, 181, 181, 181, 181, 181, 181, 181, 181, 185, 185, 185, 185,
511 185, 185, 185, 185, 186, 186, 186, 186, 186, 186, 186, 186, 187, 187, 187,
512 187, 187, 187, 187, 187, 189, 189, 189, 189, 189, 189, 189, 189, 190, 190,
513 190, 190, 190, 190, 190, 190, 196, 196, 196, 196, 196, 196, 196, 196, 198,
514 198, 198, 198, 198, 198, 198, 198, 228, 228, 228, 228, 228, 228, 228, 228,
515 232, 232, 232, 232, 232, 232, 232, 232, 233, 233, 233, 233, 233, 233, 233,
516 233, 1, 1, 1, 1, 135, 135, 135, 135, 137, 137, 137, 137, 138, 138,
517 138, 138, 139, 139, 139, 139, 140, 140, 140, 140, 141, 141, 141, 141, 143,
518 143, 143, 143, 147, 147, 147, 147, 149, 149, 149, 149, 150, 150, 150, 150,
519 151, 151, 151, 151, 152, 152, 152, 152, 155, 155, 155, 155, 157, 157, 157,
520 157, 158, 158, 158, 158, 165, 165, 165, 165, 166, 166, 166, 166, 168, 168,
521 168, 168, 174, 174, 174, 174, 175, 175, 175, 175, 180, 180, 180, 180, 182,
522 182, 182, 182, 183, 183, 183, 183, 188, 188, 188, 188, 191, 191, 191, 191,
523 197, 197, 197, 197, 231, 231, 231, 231, 239, 239, 239, 239, 9, 9, 142,
524 142, 144, 144, 145, 145, 148, 148, 159, 159, 171, 171, 206, 206, 215, 215,
525 225, 225, 236, 236, 237, 237, 199, 207, 234, 235, 192, 192, 192, 192, 192,
526 192, 192, 192, 193, 193, 193, 193, 193, 193, 193, 193, 200, 200, 200, 200,
527 200, 200, 200, 200, 201, 201, 201, 201, 201, 201, 201, 201, 202, 202, 202,
528 202, 202, 202, 202, 202, 205, 205, 205, 205, 205, 205, 205, 205, 210, 210,
529 210, 210, 210, 210, 210, 210, 213, 213, 213, 213, 213, 213, 213, 213, 218,
530 218, 218, 218, 218, 218, 218, 218, 219, 219, 219, 219, 219, 219, 219, 219,
531 238, 238, 238, 238, 238, 238, 238, 238, 240, 240, 240, 240, 240, 240, 240,
532 240, 242, 242, 242, 242, 242, 242, 242, 242, 243, 243, 243, 243, 243, 243,
533 243, 243, 255, 255, 255, 255, 255, 255, 255, 255, 203, 203, 203, 203, 204,
534 204, 204, 204, 211, 211, 211, 211, 212, 212, 212, 212, 214, 214, 214, 214,
535 221, 221, 221, 221, 222, 222, 222, 222, 223, 223, 223, 223, 241, 241, 241,
536 241, 244, 244, 244, 244, 245, 245, 245, 245, 246, 246, 246, 246, 247, 247,
537 247, 247, 248, 248, 248, 248, 250, 250, 250, 250, 251, 251, 251, 251, 252,
538 252, 252, 252, 253, 253, 253, 253, 254, 254, 254, 254, 2, 2, 3, 3,
539 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 11, 11, 12, 12, 14,
540 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21,
541 23, 23, 24, 24, 25, 25, 26, 26, 27, 27, 28, 28, 29, 29, 30,
542 30, 31, 31, 127, 127, 220, 220, 249, 249, -1, -1, 10, 10, 10, 10,
543 10, 10, 10, 10, 13, 13, 13, 13, 13, 13, 13, 13, 22, 22, 22,
544 22, 22, 22, 22, 22, 256, 256, 256, 256, 256, 256, 256, 256, 45, 45,
545 45, 45, 45, 45, 45, 45, 46, 46, 46, 46, 46, 46, 46, 46, 47,
546 47, 47, 47, 47, 47, 47, 47, 51, 51, 51, 51, 51, 51, 51, 51,
547 52, 52, 52, 52, 52, 52, 52, 52, 53, 53, 53, 53, 53, 53, 53,
548 53, 54, 54, 54, 54, 54, 54, 54, 54, 55, 55, 55, 55, 55, 55,
549 55, 55, 56, 56, 56, 56, 56, 56, 56, 56, 57, 57, 57, 57, 57,
550 57, 57, 57, 50, 50, 50, 50, 50, 50, 50, 50, 97, 97, 97, 97,
551 97, 97, 97, 97, 99, 99, 99, 99, 99, 99, 99, 99, 101, 101, 101,
552 101, 101, 101, 101, 101, 105, 105, 105, 105, 105, 105, 105, 105, 111, 111,
553 111, 111, 111, 111, 111, 111, 115, 115, 115, 115, 115, 115, 115, 115, 116,
554 116, 116, 116, 116, 116, 116, 116, 32, 32, 32, 32, 37, 37, 37, 37,
555 45, 45, 45, 45, 46, 46, 46, 46, 47, 47, 47, 47, 51, 51, 51,
556 51, 52, 52, 52, 52, 53, 53, 53, 53, 54, 54, 54, 54, 55, 55,
557 55, 55, 56, 56, 56, 56, 57, 57, 57, 57, 61, 61, 61, 61, 65,
558 65, 65, 65, 95, 95, 95, 95, 98, 98, 98, 98, 100, 100, 100, 100,
559 102, 102, 102, 102, 103, 103, 103, 103, 104, 104, 104, 104, 108, 108, 108,
560 108, 109, 109, 109, 109, 110, 110, 110, 110, 112, 112, 112, 112, 114, 114,
561 114, 114, 117, 117, 117, 117, 58, 58, 66, 66, 67, 67, 68, 68, 69,
562 69, 70, 70, 71, 71, 72, 72, 73, 73, 74, 74, 75, 75, 76, 76,
563 77, 77, 78, 78, 79, 79, 80, 80, 81, 81, 82, 82, 83, 83, 84,
564 84, 85, 85, 86, 86, 87, 87, 89, 89, 106, 106, 107, 107, 113, 113,
565 118, 118, 119, 119, 120, 120, 121, 121, 122, 122, 38, 42, 44, 59, 88,
566 90, -1, -1, 33, 33, 33, 33, 34, 34, 34, 34, 40, 40, 40, 40,
567 41, 41, 41, 41, 63, 63, 63, 63, 39, 39, 43, 43, 124, 124, 35,
568 62, -1, -1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 36, 36,
569 36, 36, 36, 36, 36, 36, 64, 64, 64, 64, 64, 64, 64, 64, 91,
570 91, 91, 91, 91, 91, 91, 91, 93, 93, 93, 93, 93, 93, 93, 93,
571 126, 126, 126, 126, 126, 126, 126, 126, 94, 94, 94, 94, 125, 125, 125,
572 125, 60, 60, 96, 96, 123, 123, -1, -1, 92, 92, 195, 195, 208, 208,
573 128, 130, 131, 162, 184, 194, 224, 226, -1, -1, 153, 153, 153, 153, 153,
574 153, 153, 153, 161, 161, 161, 161, 161, 161, 161, 161, 167, 167, 167, 167,
575 167, 167, 167, 167, 172, 172, 172, 172, 172, 172, 172, 172, 176, 176, 176,
576 176, 176, 176, 176, 176, 177, 177, 177, 177, 177, 177, 177, 177, 179, 179,
577 179, 179, 179, 179, 179, 179, 209, 209, 209, 209, 209, 209, 209, 209, 216,
578 216, 216, 216, 216, 216, 216, 216, 217, 217, 217, 217, 217, 217, 217, 217,
579 227, 227, 227, 227, 227, 227, 227, 227, 229, 229, 229, 229, 229, 229, 229,
580 229, 230, 230, 230, 230, 230, 230, 230, 230, 129, 129, 129, 129, 132, 132,
581 132, 132, 133, 133, 133, 133, 134, 134, 134, 134, 136, 136, 136, 136, 146,
582 146, 146, 146, 154, 154, 154, 154, 156, 156, 156, 156, 160, 160, 160, 160,
583 163, 163, 163, 163, 164, 164, 164, 164, 169, 169, 169, 169, 170, 170, 170,
584 170, 173, 173, 173, 173, 178, 178, 178, 178, 181, 181, 181, 181, 185, 185,
585 185, 185, 186, 186, 186, 186, 187, 187, 187, 187, 189, 189, 189, 189, 190,
586 190, 190, 190, 196, 196, 196, 196, 198, 198, 198, 198, 228, 228, 228, 228,
587 232, 232, 232, 232, 233, 233, 233, 233, 1, 1, 135, 135, 137, 137, 138,
588 138, 139, 139, 140, 140, 141, 141, 143, 143, 147, 147, 149, 149, 150, 150,
589 151, 151, 152, 152, 155, 155, 157, 157, 158, 158, 165, 165, 166, 166, 168,
590 168, 174, 174, 175, 175, 180, 180, 182, 182, 183, 183, 188, 188, 191, 191,
591 197, 197, 231, 231, 239, 239, 9, 142, 144, 145, 148, 159, 171, 206, 215,
592 225, 236, 237, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 199, 199,
593 199, 199, 199, 199, 199, 199, 207, 207, 207, 207, 207, 207, 207, 207, 234,
594 234, 234, 234, 234, 234, 234, 234, 235, 235, 235, 235, 235, 235, 235, 235,
595 192, 192, 192, 192, 193, 193, 193, 193, 200, 200, 200, 200, 201, 201, 201,
596 201, 202, 202, 202, 202, 205, 205, 205, 205, 210, 210, 210, 210, 213, 213,
597 213, 213, 218, 218, 218, 218, 219, 219, 219, 219, 238, 238, 238, 238, 240,
598 240, 240, 240, 242, 242, 242, 242, 243, 243, 243, 243, 255, 255, 255, 255,
599 203, 203, 204, 204, 211, 211, 212, 212, 214, 214, 221, 221, 222, 222, 223,
600 223, 241, 241, 244, 244, 245, 245, 246, 246, 247, 247, 248, 248, 250, 250,
601 251, 251, 252, 252, 253, 253, 254, 254, 2, 3, 4, 5, 6, 7, 8,
602 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27,
603 28, 29, 30, 31, 127, 220, 249, -1, 10, 10, 10, 10, 13, 13, 13,
604 13, 22, 22, 22, 22, 256, 256, 256, 256,
605 };
606
607 static const uint8_t inverse_base64[256] = {
608 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
609 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
610 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 62, 255,
611 255, 255, 63, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 255, 255,
612 255, 64, 255, 255, 255, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
613 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
614 25, 255, 255, 255, 255, 255, 255, 26, 27, 28, 29, 30, 31, 32, 33,
615 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48,
616 49, 50, 51, 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, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
620 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
621 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
622 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
623 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
624 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
625 255,
626 };
627
on_hdr_log(grpc_mdelem md)628 static void GPR_ATTRIBUTE_NOINLINE on_hdr_log(grpc_mdelem md) {
629 char* k = grpc_slice_to_c_string(GRPC_MDKEY(md));
630 char* v = nullptr;
631 if (grpc_is_binary_header_internal(GRPC_MDKEY(md))) {
632 v = grpc_dump_slice(GRPC_MDVALUE(md), GPR_DUMP_HEX);
633 } else {
634 v = grpc_slice_to_c_string(GRPC_MDVALUE(md));
635 }
636 gpr_log(
637 GPR_INFO,
638 "Decode: '%s: %s', elem_interned=%d [%d], k_interned=%d, v_interned=%d",
639 k, v, GRPC_MDELEM_IS_INTERNED(md), GRPC_MDELEM_STORAGE(md),
640 grpc_slice_is_interned(GRPC_MDKEY(md)),
641 grpc_slice_is_interned(GRPC_MDVALUE(md)));
642 gpr_free(k);
643 gpr_free(v);
644 }
645
646 /* emission helpers */
647 template <bool do_add>
on_hdr(grpc_chttp2_hpack_parser * p,grpc_mdelem md)648 static grpc_error* on_hdr(grpc_chttp2_hpack_parser* p, grpc_mdelem md) {
649 if (GRPC_TRACE_FLAG_ENABLED(grpc_trace_chttp2_hpack_parser)) {
650 on_hdr_log(md);
651 }
652 if (do_add) {
653 GPR_DEBUG_ASSERT(GRPC_MDELEM_STORAGE(md) == GRPC_MDELEM_STORAGE_INTERNED ||
654 GRPC_MDELEM_STORAGE(md) == GRPC_MDELEM_STORAGE_STATIC);
655 grpc_error* err = grpc_chttp2_hptbl_add(&p->table, md);
656 if (GPR_UNLIKELY(err != GRPC_ERROR_NONE)) return err;
657 }
658 return p->on_header(p->on_header_user_data, md);
659 }
660
take_string_extern(grpc_chttp2_hpack_parser *,grpc_chttp2_hpack_parser_string * str)661 static grpc_core::UnmanagedMemorySlice take_string_extern(
662 grpc_chttp2_hpack_parser* /*p*/, grpc_chttp2_hpack_parser_string* str) {
663 grpc_core::UnmanagedMemorySlice s;
664 if (!str->copied) {
665 GPR_DEBUG_ASSERT(!grpc_slice_is_interned(str->data.referenced));
666 s = static_cast<grpc_core::UnmanagedMemorySlice&>(str->data.referenced);
667 str->copied = true;
668 str->data.referenced = grpc_core::UnmanagedMemorySlice();
669 } else {
670 s = grpc_core::UnmanagedMemorySlice(str->data.copied.str,
671 str->data.copied.length);
672 }
673 str->data.copied.length = 0;
674 return s;
675 }
676
take_string_intern(grpc_chttp2_hpack_parser *,grpc_chttp2_hpack_parser_string * str)677 static grpc_core::ManagedMemorySlice take_string_intern(
678 grpc_chttp2_hpack_parser* /*p*/, grpc_chttp2_hpack_parser_string* str) {
679 grpc_core::ManagedMemorySlice s;
680 if (!str->copied) {
681 s = grpc_core::ManagedMemorySlice(&str->data.referenced);
682 grpc_slice_unref_internal(str->data.referenced);
683 str->copied = true;
684 str->data.referenced = grpc_empty_slice();
685 } else {
686 s = grpc_core::ManagedMemorySlice(str->data.copied.str,
687 str->data.copied.length);
688 }
689 str->data.copied.length = 0;
690 return s;
691 }
692
693 /* jump to the next state */
parse_next(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)694 static grpc_error* parse_next(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
695 const uint8_t* end) {
696 p->state = *p->next_state++;
697 return p->state(p, cur, end);
698 }
699
700 /* begin parsing a header: all functionality is encoded into lookup tables
701 above */
parse_begin(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)702 static grpc_error* parse_begin(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
703 const uint8_t* end) {
704 if (cur == end) {
705 p->state = parse_begin;
706 return GRPC_ERROR_NONE;
707 }
708
709 return first_byte_action[first_byte_lut[*cur]](p, cur, end);
710 }
711
712 /* stream dependency and prioritization data: we just skip it */
parse_stream_weight(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)713 static grpc_error* parse_stream_weight(grpc_chttp2_hpack_parser* p,
714 const uint8_t* cur, const uint8_t* end) {
715 if (cur == end) {
716 p->state = parse_stream_weight;
717 return GRPC_ERROR_NONE;
718 }
719
720 return p->after_prioritization(p, cur + 1, end);
721 }
722
parse_stream_dep3(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)723 static grpc_error* parse_stream_dep3(grpc_chttp2_hpack_parser* p,
724 const uint8_t* cur, const uint8_t* end) {
725 if (cur == end) {
726 p->state = parse_stream_dep3;
727 return GRPC_ERROR_NONE;
728 }
729
730 return parse_stream_weight(p, cur + 1, end);
731 }
732
parse_stream_dep2(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)733 static grpc_error* parse_stream_dep2(grpc_chttp2_hpack_parser* p,
734 const uint8_t* cur, const uint8_t* end) {
735 if (cur == end) {
736 p->state = parse_stream_dep2;
737 return GRPC_ERROR_NONE;
738 }
739
740 return parse_stream_dep3(p, cur + 1, end);
741 }
742
parse_stream_dep1(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)743 static grpc_error* parse_stream_dep1(grpc_chttp2_hpack_parser* p,
744 const uint8_t* cur, const uint8_t* end) {
745 if (cur == end) {
746 p->state = parse_stream_dep1;
747 return GRPC_ERROR_NONE;
748 }
749
750 return parse_stream_dep2(p, cur + 1, end);
751 }
752
parse_stream_dep0(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)753 static grpc_error* parse_stream_dep0(grpc_chttp2_hpack_parser* p,
754 const uint8_t* cur, const uint8_t* end) {
755 if (cur == end) {
756 p->state = parse_stream_dep0;
757 return GRPC_ERROR_NONE;
758 }
759
760 return parse_stream_dep1(p, cur + 1, end);
761 }
762
763 static grpc_error* GPR_ATTRIBUTE_NOINLINE
on_invalid_hpack_idx(grpc_chttp2_hpack_parser * p)764 on_invalid_hpack_idx(grpc_chttp2_hpack_parser* p) {
765 return grpc_error_set_int(
766 grpc_error_set_int(
767 GRPC_ERROR_CREATE_FROM_STATIC_STRING("Invalid HPACK index received"),
768 GRPC_ERROR_INT_INDEX, static_cast<intptr_t>(p->index)),
769 GRPC_ERROR_INT_SIZE, static_cast<intptr_t>(p->table.num_ents));
770 }
771
772 /* emit an indexed field; jumps to begin the next field on completion */
finish_indexed_field(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)773 static grpc_error* finish_indexed_field(grpc_chttp2_hpack_parser* p,
774 const uint8_t* cur,
775 const uint8_t* end) {
776 grpc_mdelem md = grpc_chttp2_hptbl_lookup<true>(&p->table, p->index);
777 if (GPR_UNLIKELY(GRPC_MDISNULL(md))) {
778 return on_invalid_hpack_idx(p);
779 }
780 GRPC_STATS_INC_HPACK_RECV_INDEXED();
781 grpc_error* err = on_hdr<false>(p, md);
782 if (GPR_UNLIKELY(err != GRPC_ERROR_NONE)) return err;
783 return parse_begin(p, cur, end);
784 }
785
786 /* parse an indexed field with index < 127 */
parse_indexed_field(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)787 static grpc_error* parse_indexed_field(grpc_chttp2_hpack_parser* p,
788 const uint8_t* cur, const uint8_t* end) {
789 p->dynamic_table_update_allowed = 0;
790 p->index = (*cur) & 0x7f;
791 p->md_for_index.payload = 0; /* Invalidate cached md when index changes. */
792 return finish_indexed_field(p, cur + 1, end);
793 }
794
795 /* parse an indexed field with index >= 127 */
parse_indexed_field_x(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)796 static grpc_error* parse_indexed_field_x(grpc_chttp2_hpack_parser* p,
797 const uint8_t* cur,
798 const uint8_t* end) {
799 static const grpc_chttp2_hpack_parser_state and_then[] = {
800 finish_indexed_field};
801 p->dynamic_table_update_allowed = 0;
802 p->next_state = and_then;
803 p->index = 0x7f;
804 p->md_for_index.payload = 0; /* Invalidate cached md when index changes. */
805 p->parsing.value = &p->index;
806 return parse_value0(p, cur + 1, end);
807 }
808
809 /* When finishing with a header, get the cached md element for this index.
810 This is set in parse_value_string(). We ensure (in debug mode) that the
811 cached metadata corresponds with the index we are examining. */
get_precomputed_md_for_idx(grpc_chttp2_hpack_parser * p)812 static grpc_mdelem get_precomputed_md_for_idx(grpc_chttp2_hpack_parser* p) {
813 GPR_DEBUG_ASSERT(p->md_for_index.payload != 0);
814 GPR_DEBUG_ASSERT(static_cast<int64_t>(p->index) == p->precomputed_md_index);
815 grpc_mdelem md = p->md_for_index;
816 GPR_DEBUG_ASSERT(!GRPC_MDISNULL(md)); /* handled in string parsing */
817 p->md_for_index.payload = 0; /* Invalidate cached md when index changes. */
818 #ifndef NDEBUG
819 p->precomputed_md_index = -1;
820 #endif
821 return md;
822 }
823
get_indexed_key(grpc_mdelem md)824 static const grpc_core::ManagedMemorySlice& get_indexed_key(grpc_mdelem md) {
825 GPR_DEBUG_ASSERT(GRPC_MDELEM_IS_INTERNED(md));
826 return static_cast<const grpc_core::ManagedMemorySlice&>(
827 grpc_slice_ref_internal(GRPC_MDKEY(md)));
828 }
829
830 /* finish a literal header with incremental indexing */
finish_lithdr_incidx(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)831 static grpc_error* finish_lithdr_incidx(grpc_chttp2_hpack_parser* p,
832 const uint8_t* cur,
833 const uint8_t* end) {
834 GRPC_STATS_INC_HPACK_RECV_LITHDR_INCIDX();
835 grpc_mdelem md = get_precomputed_md_for_idx(p);
836 grpc_error* err = on_hdr<true>(
837 p, grpc_mdelem_from_slices(get_indexed_key(md),
838 take_string_intern(p, &p->value)));
839 if (err != GRPC_ERROR_NONE) return parse_error(p, cur, end, err);
840 return parse_begin(p, cur, end);
841 }
842
843 /* finish a literal header with incremental indexing with no index */
finish_lithdr_incidx_v(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)844 static grpc_error* finish_lithdr_incidx_v(grpc_chttp2_hpack_parser* p,
845 const uint8_t* cur,
846 const uint8_t* end) {
847 GRPC_STATS_INC_HPACK_RECV_LITHDR_INCIDX_V();
848 grpc_error* err = on_hdr<true>(
849 p, grpc_mdelem_from_slices(take_string_intern(p, &p->key),
850 take_string_intern(p, &p->value)));
851 if (err != GRPC_ERROR_NONE) return parse_error(p, cur, end, err);
852 return parse_begin(p, cur, end);
853 }
854
855 /* parse a literal header with incremental indexing; index < 63 */
parse_lithdr_incidx(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)856 static grpc_error* parse_lithdr_incidx(grpc_chttp2_hpack_parser* p,
857 const uint8_t* cur, const uint8_t* end) {
858 static const grpc_chttp2_hpack_parser_state and_then[] = {
859 parse_value_string_with_indexed_key, finish_lithdr_incidx};
860 p->dynamic_table_update_allowed = 0;
861 p->next_state = and_then;
862 p->index = (*cur) & 0x3f;
863 p->md_for_index.payload = 0; /* Invalidate cached md when index changes. */
864 return parse_string_prefix(p, cur + 1, end);
865 }
866
867 /* parse a literal header with incremental indexing; index >= 63 */
parse_lithdr_incidx_x(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)868 static grpc_error* parse_lithdr_incidx_x(grpc_chttp2_hpack_parser* p,
869 const uint8_t* cur,
870 const uint8_t* end) {
871 static const grpc_chttp2_hpack_parser_state and_then[] = {
872 parse_string_prefix, parse_value_string_with_indexed_key,
873 finish_lithdr_incidx};
874 p->dynamic_table_update_allowed = 0;
875 p->next_state = and_then;
876 p->index = 0x3f;
877 p->md_for_index.payload = 0; /* Invalidate cached md when index changes. */
878 p->parsing.value = &p->index;
879 return parse_value0(p, cur + 1, end);
880 }
881
882 /* parse a literal header with incremental indexing; index = 0 */
parse_lithdr_incidx_v(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)883 static grpc_error* parse_lithdr_incidx_v(grpc_chttp2_hpack_parser* p,
884 const uint8_t* cur,
885 const uint8_t* end) {
886 static const grpc_chttp2_hpack_parser_state and_then[] = {
887 parse_key_string, parse_string_prefix,
888 parse_value_string_with_literal_key, finish_lithdr_incidx_v};
889 p->dynamic_table_update_allowed = 0;
890 p->next_state = and_then;
891 return parse_string_prefix(p, cur + 1, end);
892 }
893
894 /* finish a literal header without incremental indexing */
finish_lithdr_notidx(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)895 static grpc_error* finish_lithdr_notidx(grpc_chttp2_hpack_parser* p,
896 const uint8_t* cur,
897 const uint8_t* end) {
898 GRPC_STATS_INC_HPACK_RECV_LITHDR_NOTIDX();
899 grpc_mdelem md = get_precomputed_md_for_idx(p);
900 grpc_error* err = on_hdr<false>(
901 p, grpc_mdelem_from_slices(get_indexed_key(md),
902 take_string_extern(p, &p->value)));
903 if (err != GRPC_ERROR_NONE) return parse_error(p, cur, end, err);
904 return parse_begin(p, cur, end);
905 }
906
907 /* finish a literal header without incremental indexing with index = 0 */
finish_lithdr_notidx_v(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)908 static grpc_error* finish_lithdr_notidx_v(grpc_chttp2_hpack_parser* p,
909 const uint8_t* cur,
910 const uint8_t* end) {
911 GRPC_STATS_INC_HPACK_RECV_LITHDR_NOTIDX_V();
912 grpc_error* err = on_hdr<false>(
913 p, grpc_mdelem_from_slices(take_string_intern(p, &p->key),
914 take_string_extern(p, &p->value)));
915 if (err != GRPC_ERROR_NONE) return parse_error(p, cur, end, err);
916 return parse_begin(p, cur, end);
917 }
918
919 /* parse a literal header without incremental indexing; index < 15 */
parse_lithdr_notidx(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)920 static grpc_error* parse_lithdr_notidx(grpc_chttp2_hpack_parser* p,
921 const uint8_t* cur, const uint8_t* end) {
922 static const grpc_chttp2_hpack_parser_state and_then[] = {
923 parse_value_string_with_indexed_key, finish_lithdr_notidx};
924 p->dynamic_table_update_allowed = 0;
925 p->next_state = and_then;
926 p->index = (*cur) & 0xf;
927 p->md_for_index.payload = 0; /* Invalidate cached md when index changes. */
928 return parse_string_prefix(p, cur + 1, end);
929 }
930
931 /* parse a literal header without incremental indexing; index >= 15 */
parse_lithdr_notidx_x(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)932 static grpc_error* parse_lithdr_notidx_x(grpc_chttp2_hpack_parser* p,
933 const uint8_t* cur,
934 const uint8_t* end) {
935 static const grpc_chttp2_hpack_parser_state and_then[] = {
936 parse_string_prefix, parse_value_string_with_indexed_key,
937 finish_lithdr_notidx};
938 p->dynamic_table_update_allowed = 0;
939 p->next_state = and_then;
940 p->index = 0xf;
941 p->md_for_index.payload = 0; /* Invalidate cached md when index changes. */
942 p->parsing.value = &p->index;
943 return parse_value0(p, cur + 1, end);
944 }
945
946 /* parse a literal header without incremental indexing; index == 0 */
parse_lithdr_notidx_v(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)947 static grpc_error* parse_lithdr_notidx_v(grpc_chttp2_hpack_parser* p,
948 const uint8_t* cur,
949 const uint8_t* end) {
950 static const grpc_chttp2_hpack_parser_state and_then[] = {
951 parse_key_string, parse_string_prefix,
952 parse_value_string_with_literal_key, finish_lithdr_notidx_v};
953 p->dynamic_table_update_allowed = 0;
954 p->next_state = and_then;
955 return parse_string_prefix(p, cur + 1, end);
956 }
957
958 /* finish a literal header that is never indexed */
finish_lithdr_nvridx(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)959 static grpc_error* finish_lithdr_nvridx(grpc_chttp2_hpack_parser* p,
960 const uint8_t* cur,
961 const uint8_t* end) {
962 GRPC_STATS_INC_HPACK_RECV_LITHDR_NVRIDX();
963 grpc_mdelem md = get_precomputed_md_for_idx(p);
964 grpc_error* err = on_hdr<false>(
965 p, grpc_mdelem_from_slices(get_indexed_key(md),
966 take_string_extern(p, &p->value)));
967 if (err != GRPC_ERROR_NONE) return parse_error(p, cur, end, err);
968 return parse_begin(p, cur, end);
969 }
970
971 /* finish a literal header that is never indexed with an extra value */
finish_lithdr_nvridx_v(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)972 static grpc_error* finish_lithdr_nvridx_v(grpc_chttp2_hpack_parser* p,
973 const uint8_t* cur,
974 const uint8_t* end) {
975 GRPC_STATS_INC_HPACK_RECV_LITHDR_NVRIDX_V();
976 grpc_error* err = on_hdr<false>(
977 p, grpc_mdelem_from_slices(take_string_intern(p, &p->key),
978 take_string_extern(p, &p->value)));
979 if (err != GRPC_ERROR_NONE) return parse_error(p, cur, end, err);
980 return parse_begin(p, cur, end);
981 }
982
983 /* parse a literal header that is never indexed; index < 15 */
parse_lithdr_nvridx(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)984 static grpc_error* parse_lithdr_nvridx(grpc_chttp2_hpack_parser* p,
985 const uint8_t* cur, const uint8_t* end) {
986 static const grpc_chttp2_hpack_parser_state and_then[] = {
987 parse_value_string_with_indexed_key, finish_lithdr_nvridx};
988 p->dynamic_table_update_allowed = 0;
989 p->next_state = and_then;
990 p->index = (*cur) & 0xf;
991 p->md_for_index.payload = 0; /* Invalidate cached md when index changes. */
992 return parse_string_prefix(p, cur + 1, end);
993 }
994
995 /* parse a literal header that is never indexed; index >= 15 */
parse_lithdr_nvridx_x(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)996 static grpc_error* parse_lithdr_nvridx_x(grpc_chttp2_hpack_parser* p,
997 const uint8_t* cur,
998 const uint8_t* end) {
999 static const grpc_chttp2_hpack_parser_state and_then[] = {
1000 parse_string_prefix, parse_value_string_with_indexed_key,
1001 finish_lithdr_nvridx};
1002 p->dynamic_table_update_allowed = 0;
1003 p->next_state = and_then;
1004 p->index = 0xf;
1005 p->md_for_index.payload = 0; /* Invalidate cached md when index changes. */
1006 p->parsing.value = &p->index;
1007 return parse_value0(p, cur + 1, end);
1008 }
1009
1010 /* parse a literal header that is never indexed; index == 0 */
parse_lithdr_nvridx_v(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)1011 static grpc_error* parse_lithdr_nvridx_v(grpc_chttp2_hpack_parser* p,
1012 const uint8_t* cur,
1013 const uint8_t* end) {
1014 static const grpc_chttp2_hpack_parser_state and_then[] = {
1015 parse_key_string, parse_string_prefix,
1016 parse_value_string_with_literal_key, finish_lithdr_nvridx_v};
1017 p->dynamic_table_update_allowed = 0;
1018 p->next_state = and_then;
1019 return parse_string_prefix(p, cur + 1, end);
1020 }
1021
1022 /* finish parsing a max table size change */
finish_max_tbl_size(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)1023 static grpc_error* finish_max_tbl_size(grpc_chttp2_hpack_parser* p,
1024 const uint8_t* cur, const uint8_t* end) {
1025 if (GRPC_TRACE_FLAG_ENABLED(grpc_trace_chttp2_hpack_parser)) {
1026 gpr_log(GPR_INFO, "MAX TABLE SIZE: %d", p->index);
1027 }
1028 grpc_error* err =
1029 grpc_chttp2_hptbl_set_current_table_size(&p->table, p->index);
1030 if (err != GRPC_ERROR_NONE) return parse_error(p, cur, end, err);
1031 return parse_begin(p, cur, end);
1032 }
1033
1034 /* parse a max table size change, max size < 15 */
parse_max_tbl_size(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)1035 static grpc_error* parse_max_tbl_size(grpc_chttp2_hpack_parser* p,
1036 const uint8_t* cur, const uint8_t* end) {
1037 if (p->dynamic_table_update_allowed == 0) {
1038 return parse_error(
1039 p, cur, end,
1040 GRPC_ERROR_CREATE_FROM_STATIC_STRING(
1041 "More than two max table size changes in a single frame"));
1042 }
1043 p->dynamic_table_update_allowed--;
1044 p->index = (*cur) & 0x1f;
1045 p->md_for_index.payload = 0; /* Invalidate cached md when index changes. */
1046 return finish_max_tbl_size(p, cur + 1, end);
1047 }
1048
1049 /* parse a max table size change, max size >= 15 */
parse_max_tbl_size_x(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)1050 static grpc_error* parse_max_tbl_size_x(grpc_chttp2_hpack_parser* p,
1051 const uint8_t* cur,
1052 const uint8_t* end) {
1053 static const grpc_chttp2_hpack_parser_state and_then[] = {
1054 finish_max_tbl_size};
1055 if (p->dynamic_table_update_allowed == 0) {
1056 return parse_error(
1057 p, cur, end,
1058 GRPC_ERROR_CREATE_FROM_STATIC_STRING(
1059 "More than two max table size changes in a single frame"));
1060 }
1061 p->dynamic_table_update_allowed--;
1062 p->next_state = and_then;
1063 p->index = 0x1f;
1064 p->md_for_index.payload = 0; /* Invalidate cached md when index changes. */
1065 p->parsing.value = &p->index;
1066 return parse_value0(p, cur + 1, end);
1067 }
1068
1069 /* a parse error: jam the parse state into parse_error, and return error */
parse_error(grpc_chttp2_hpack_parser * p,const uint8_t *,const uint8_t *,grpc_error * err)1070 static grpc_error* parse_error(grpc_chttp2_hpack_parser* p,
1071 const uint8_t* /*cur*/, const uint8_t* /*end*/,
1072 grpc_error* err) {
1073 GPR_ASSERT(err != GRPC_ERROR_NONE);
1074 if (p->last_error == GRPC_ERROR_NONE) {
1075 p->last_error = GRPC_ERROR_REF(err);
1076 }
1077 p->state = still_parse_error;
1078 return err;
1079 }
1080
still_parse_error(grpc_chttp2_hpack_parser * p,const uint8_t *,const uint8_t *)1081 static grpc_error* still_parse_error(grpc_chttp2_hpack_parser* p,
1082 const uint8_t* /*cur*/,
1083 const uint8_t* /*end*/) {
1084 return GRPC_ERROR_REF(p->last_error);
1085 }
1086
parse_illegal_op(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)1087 static grpc_error* parse_illegal_op(grpc_chttp2_hpack_parser* p,
1088 const uint8_t* cur, const uint8_t* end) {
1089 GPR_ASSERT(cur != end);
1090 char* msg;
1091 gpr_asprintf(&msg, "Illegal hpack op code %d", *cur);
1092 grpc_error* err = GRPC_ERROR_CREATE_FROM_COPIED_STRING(msg);
1093 gpr_free(msg);
1094 return parse_error(p, cur, end, err);
1095 }
1096
1097 /* parse the 1st byte of a varint into p->parsing.value
1098 no overflow is possible */
parse_value0(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)1099 static grpc_error* parse_value0(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
1100 const uint8_t* end) {
1101 if (cur == end) {
1102 p->state = parse_value0;
1103 return GRPC_ERROR_NONE;
1104 }
1105
1106 *p->parsing.value += (*cur) & 0x7f;
1107
1108 if ((*cur) & 0x80) {
1109 return parse_value1(p, cur + 1, end);
1110 } else {
1111 return parse_next(p, cur + 1, end);
1112 }
1113 }
1114
1115 /* parse the 2nd byte of a varint into p->parsing.value
1116 no overflow is possible */
parse_value1(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)1117 static grpc_error* parse_value1(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
1118 const uint8_t* end) {
1119 if (cur == end) {
1120 p->state = parse_value1;
1121 return GRPC_ERROR_NONE;
1122 }
1123
1124 *p->parsing.value += ((static_cast<uint32_t>(*cur)) & 0x7f) << 7;
1125
1126 if ((*cur) & 0x80) {
1127 return parse_value2(p, cur + 1, end);
1128 } else {
1129 return parse_next(p, cur + 1, end);
1130 }
1131 }
1132
1133 /* parse the 3rd byte of a varint into p->parsing.value
1134 no overflow is possible */
parse_value2(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)1135 static grpc_error* parse_value2(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
1136 const uint8_t* end) {
1137 if (cur == end) {
1138 p->state = parse_value2;
1139 return GRPC_ERROR_NONE;
1140 }
1141
1142 *p->parsing.value += ((static_cast<uint32_t>(*cur)) & 0x7f) << 14;
1143
1144 if ((*cur) & 0x80) {
1145 return parse_value3(p, cur + 1, end);
1146 } else {
1147 return parse_next(p, cur + 1, end);
1148 }
1149 }
1150
1151 /* parse the 4th byte of a varint into p->parsing.value
1152 no overflow is possible */
parse_value3(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)1153 static grpc_error* parse_value3(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
1154 const uint8_t* end) {
1155 if (cur == end) {
1156 p->state = parse_value3;
1157 return GRPC_ERROR_NONE;
1158 }
1159
1160 *p->parsing.value += ((static_cast<uint32_t>(*cur)) & 0x7f) << 21;
1161
1162 if ((*cur) & 0x80) {
1163 return parse_value4(p, cur + 1, end);
1164 } else {
1165 return parse_next(p, cur + 1, end);
1166 }
1167 }
1168
1169 /* parse the 5th byte of a varint into p->parsing.value
1170 depending on the byte, we may overflow, and care must be taken */
parse_value4(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)1171 static grpc_error* parse_value4(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
1172 const uint8_t* end) {
1173 uint8_t c;
1174 uint32_t cur_value;
1175 uint32_t add_value;
1176 char* msg;
1177
1178 if (cur == end) {
1179 p->state = parse_value4;
1180 return GRPC_ERROR_NONE;
1181 }
1182
1183 c = (*cur) & 0x7f;
1184 if (c > 0xf) {
1185 goto error;
1186 }
1187
1188 cur_value = *p->parsing.value;
1189 add_value = (static_cast<uint32_t>(c)) << 28;
1190 if (add_value > 0xffffffffu - cur_value) {
1191 goto error;
1192 }
1193
1194 *p->parsing.value = cur_value + add_value;
1195
1196 if ((*cur) & 0x80) {
1197 return parse_value5up(p, cur + 1, end);
1198 } else {
1199 return parse_next(p, cur + 1, end);
1200 }
1201
1202 error:
1203 gpr_asprintf(&msg,
1204 "integer overflow in hpack integer decoding: have 0x%08x, "
1205 "got byte 0x%02x on byte 5",
1206 *p->parsing.value, *cur);
1207 grpc_error* err = GRPC_ERROR_CREATE_FROM_COPIED_STRING(msg);
1208 gpr_free(msg);
1209 return parse_error(p, cur, end, err);
1210 }
1211
1212 /* parse any trailing bytes in a varint: it's possible to append an arbitrary
1213 number of 0x80's and not affect the value - a zero will terminate - and
1214 anything else will overflow */
parse_value5up(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)1215 static grpc_error* parse_value5up(grpc_chttp2_hpack_parser* p,
1216 const uint8_t* cur, const uint8_t* end) {
1217 while (cur != end && *cur == 0x80) {
1218 ++cur;
1219 }
1220
1221 if (cur == end) {
1222 p->state = parse_value5up;
1223 return GRPC_ERROR_NONE;
1224 }
1225
1226 if (*cur == 0) {
1227 return parse_next(p, cur + 1, end);
1228 }
1229
1230 char* msg;
1231 gpr_asprintf(&msg,
1232 "integer overflow in hpack integer decoding: have 0x%08x, "
1233 "got byte 0x%02x sometime after byte 5",
1234 *p->parsing.value, *cur);
1235 grpc_error* err = GRPC_ERROR_CREATE_FROM_COPIED_STRING(msg);
1236 gpr_free(msg);
1237 return parse_error(p, cur, end, err);
1238 }
1239
1240 /* parse a string prefix */
parse_string_prefix(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)1241 static grpc_error* parse_string_prefix(grpc_chttp2_hpack_parser* p,
1242 const uint8_t* cur, const uint8_t* end) {
1243 if (cur == end) {
1244 p->state = parse_string_prefix;
1245 return GRPC_ERROR_NONE;
1246 }
1247
1248 p->strlen = (*cur) & 0x7f;
1249 p->huff = (*cur) >> 7;
1250 if (p->strlen == 0x7f) {
1251 p->parsing.value = &p->strlen;
1252 return parse_value0(p, cur + 1, end);
1253 } else {
1254 return parse_next(p, cur + 1, end);
1255 }
1256 }
1257
1258 /* append some bytes to a string */
append_bytes(grpc_chttp2_hpack_parser_string * str,const uint8_t * data,size_t length)1259 static void append_bytes(grpc_chttp2_hpack_parser_string* str,
1260 const uint8_t* data, size_t length) {
1261 if (length == 0) return;
1262 if (length + str->data.copied.length > str->data.copied.capacity) {
1263 GPR_ASSERT(str->data.copied.length + length <= UINT32_MAX);
1264 str->data.copied.capacity =
1265 static_cast<uint32_t>(str->data.copied.length + length);
1266 str->data.copied.str = static_cast<char*>(
1267 gpr_realloc(str->data.copied.str, str->data.copied.capacity));
1268 }
1269 memcpy(str->data.copied.str + str->data.copied.length, data, length);
1270 GPR_ASSERT(length <= UINT32_MAX - str->data.copied.length);
1271 str->data.copied.length += static_cast<uint32_t>(length);
1272 }
1273
append_string(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)1274 static grpc_error* append_string(grpc_chttp2_hpack_parser* p,
1275 const uint8_t* cur, const uint8_t* end) {
1276 grpc_chttp2_hpack_parser_string* str = p->parsing.str;
1277 uint32_t bits;
1278 uint8_t decoded[3];
1279 switch (static_cast<binary_state>(p->binary)) {
1280 case NOT_BINARY:
1281 append_bytes(str, cur, static_cast<size_t>(end - cur));
1282 return GRPC_ERROR_NONE;
1283 case BINARY_BEGIN:
1284 if (cur == end) {
1285 p->binary = BINARY_BEGIN;
1286 return GRPC_ERROR_NONE;
1287 }
1288 if (*cur == 0) {
1289 /* 'true-binary' case */
1290 ++cur;
1291 p->binary = NOT_BINARY;
1292 GRPC_STATS_INC_HPACK_RECV_BINARY();
1293 append_bytes(str, cur, static_cast<size_t>(end - cur));
1294 return GRPC_ERROR_NONE;
1295 }
1296 GRPC_STATS_INC_HPACK_RECV_BINARY_BASE64();
1297 /* fallthrough */
1298 b64_byte0:
1299 case B64_BYTE0:
1300 if (cur == end) {
1301 p->binary = B64_BYTE0;
1302 return GRPC_ERROR_NONE;
1303 }
1304 bits = inverse_base64[*cur];
1305 ++cur;
1306 if (bits == 255)
1307 return parse_error(
1308 p, cur, end,
1309 GRPC_ERROR_CREATE_FROM_STATIC_STRING("Illegal base64 character"));
1310 else if (bits == 64)
1311 goto b64_byte0;
1312 p->base64_buffer = bits << 18;
1313 /* fallthrough */
1314 b64_byte1:
1315 case B64_BYTE1:
1316 if (cur == end) {
1317 p->binary = B64_BYTE1;
1318 return GRPC_ERROR_NONE;
1319 }
1320 bits = inverse_base64[*cur];
1321 ++cur;
1322 if (bits == 255)
1323 return parse_error(
1324 p, cur, end,
1325 GRPC_ERROR_CREATE_FROM_STATIC_STRING("Illegal base64 character"));
1326 else if (bits == 64)
1327 goto b64_byte1;
1328 p->base64_buffer |= bits << 12;
1329 /* fallthrough */
1330 b64_byte2:
1331 case B64_BYTE2:
1332 if (cur == end) {
1333 p->binary = B64_BYTE2;
1334 return GRPC_ERROR_NONE;
1335 }
1336 bits = inverse_base64[*cur];
1337 ++cur;
1338 if (bits == 255)
1339 return parse_error(
1340 p, cur, end,
1341 GRPC_ERROR_CREATE_FROM_STATIC_STRING("Illegal base64 character"));
1342 else if (bits == 64)
1343 goto b64_byte2;
1344 p->base64_buffer |= bits << 6;
1345 /* fallthrough */
1346 b64_byte3:
1347 case B64_BYTE3:
1348 if (cur == end) {
1349 p->binary = B64_BYTE3;
1350 return GRPC_ERROR_NONE;
1351 }
1352 bits = inverse_base64[*cur];
1353 ++cur;
1354 if (bits == 255)
1355 return parse_error(
1356 p, cur, end,
1357 GRPC_ERROR_CREATE_FROM_STATIC_STRING("Illegal base64 character"));
1358 else if (bits == 64)
1359 goto b64_byte3;
1360 p->base64_buffer |= bits;
1361 bits = p->base64_buffer;
1362 decoded[0] = static_cast<uint8_t>(bits >> 16);
1363 decoded[1] = static_cast<uint8_t>(bits >> 8);
1364 decoded[2] = static_cast<uint8_t>(bits);
1365 append_bytes(str, decoded, 3);
1366 goto b64_byte0;
1367 }
1368 GPR_UNREACHABLE_CODE(return parse_error(
1369 p, cur, end,
1370 GRPC_ERROR_CREATE_FROM_STATIC_STRING("Should never reach here")));
1371 }
1372
finish_str(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)1373 static grpc_error* finish_str(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
1374 const uint8_t* end) {
1375 uint8_t decoded[2];
1376 uint32_t bits;
1377 grpc_chttp2_hpack_parser_string* str = p->parsing.str;
1378 switch (static_cast<binary_state>(p->binary)) {
1379 case NOT_BINARY:
1380 break;
1381 case BINARY_BEGIN:
1382 break;
1383 case B64_BYTE0:
1384 break;
1385 case B64_BYTE1:
1386 return parse_error(p, cur, end,
1387 GRPC_ERROR_CREATE_FROM_STATIC_STRING(
1388 "illegal base64 encoding")); /* illegal encoding */
1389 case B64_BYTE2:
1390 bits = p->base64_buffer;
1391 if (bits & 0xffff) {
1392 char* msg;
1393 gpr_asprintf(&msg, "trailing bits in base64 encoding: 0x%04x",
1394 bits & 0xffff);
1395 grpc_error* err = GRPC_ERROR_CREATE_FROM_COPIED_STRING(msg);
1396 gpr_free(msg);
1397 return parse_error(p, cur, end, err);
1398 }
1399 decoded[0] = static_cast<uint8_t>(bits >> 16);
1400 append_bytes(str, decoded, 1);
1401 break;
1402 case B64_BYTE3:
1403 bits = p->base64_buffer;
1404 if (bits & 0xff) {
1405 char* msg;
1406 gpr_asprintf(&msg, "trailing bits in base64 encoding: 0x%02x",
1407 bits & 0xff);
1408 grpc_error* err = GRPC_ERROR_CREATE_FROM_COPIED_STRING(msg);
1409 gpr_free(msg);
1410 return parse_error(p, cur, end, err);
1411 }
1412 decoded[0] = static_cast<uint8_t>(bits >> 16);
1413 decoded[1] = static_cast<uint8_t>(bits >> 8);
1414 append_bytes(str, decoded, 2);
1415 break;
1416 }
1417 return GRPC_ERROR_NONE;
1418 }
1419
1420 /* decode a nibble from a huffman encoded stream */
huff_nibble(grpc_chttp2_hpack_parser * p,uint8_t nibble)1421 static grpc_error* huff_nibble(grpc_chttp2_hpack_parser* p, uint8_t nibble) {
1422 int16_t emit = emit_sub_tbl[16 * emit_tbl[p->huff_state] + nibble];
1423 int16_t next = next_sub_tbl[16 * next_tbl[p->huff_state] + nibble];
1424 if (emit != -1) {
1425 if (emit >= 0 && emit < 256) {
1426 uint8_t c = static_cast<uint8_t>(emit);
1427 grpc_error* err = append_string(p, &c, (&c) + 1);
1428 if (err != GRPC_ERROR_NONE) return err;
1429 } else {
1430 assert(emit == 256);
1431 }
1432 }
1433 p->huff_state = next;
1434 return GRPC_ERROR_NONE;
1435 }
1436
1437 /* decode full bytes from a huffman encoded stream */
add_huff_bytes(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)1438 static grpc_error* add_huff_bytes(grpc_chttp2_hpack_parser* p,
1439 const uint8_t* cur, const uint8_t* end) {
1440 for (; cur != end; ++cur) {
1441 grpc_error* err = huff_nibble(p, *cur >> 4);
1442 if (err != GRPC_ERROR_NONE) return parse_error(p, cur, end, err);
1443 err = huff_nibble(p, *cur & 0xf);
1444 if (err != GRPC_ERROR_NONE) return parse_error(p, cur, end, err);
1445 }
1446 return GRPC_ERROR_NONE;
1447 }
1448
1449 /* decode some string bytes based on the current decoding mode
1450 (huffman or not) */
add_str_bytes(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)1451 static grpc_error* add_str_bytes(grpc_chttp2_hpack_parser* p,
1452 const uint8_t* cur, const uint8_t* end) {
1453 if (p->huff) {
1454 return add_huff_bytes(p, cur, end);
1455 } else {
1456 return append_string(p, cur, end);
1457 }
1458 }
1459
1460 /* parse a string - tries to do large chunks at a time */
parse_string(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)1461 static grpc_error* parse_string(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
1462 const uint8_t* end) {
1463 size_t remaining = p->strlen - p->strgot;
1464 size_t given = static_cast<size_t>(end - cur);
1465 if (remaining <= given) {
1466 grpc_error* err = add_str_bytes(p, cur, cur + remaining);
1467 if (err != GRPC_ERROR_NONE) return parse_error(p, cur, end, err);
1468 err = finish_str(p, cur + remaining, end);
1469 if (err != GRPC_ERROR_NONE) return parse_error(p, cur, end, err);
1470 return parse_next(p, cur + remaining, end);
1471 } else {
1472 grpc_error* err = add_str_bytes(p, cur, cur + given);
1473 if (err != GRPC_ERROR_NONE) return parse_error(p, cur, end, err);
1474 GPR_ASSERT(given <= UINT32_MAX - p->strgot);
1475 p->strgot += static_cast<uint32_t>(given);
1476 p->state = parse_string;
1477 return GRPC_ERROR_NONE;
1478 }
1479 }
1480
1481 /* begin parsing a string - performs setup, calls parse_string */
begin_parse_string(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end,uint8_t binary,grpc_chttp2_hpack_parser_string * str)1482 static grpc_error* begin_parse_string(grpc_chttp2_hpack_parser* p,
1483 const uint8_t* cur, const uint8_t* end,
1484 uint8_t binary,
1485 grpc_chttp2_hpack_parser_string* str) {
1486 if (!p->huff && binary == NOT_BINARY &&
1487 static_cast<uint32_t>(end - cur) >= p->strlen &&
1488 p->current_slice_refcount != nullptr) {
1489 GRPC_STATS_INC_HPACK_RECV_UNCOMPRESSED();
1490 str->copied = false;
1491 str->data.referenced.refcount = p->current_slice_refcount;
1492 str->data.referenced.data.refcounted.bytes = const_cast<uint8_t*>(cur);
1493 str->data.referenced.data.refcounted.length = p->strlen;
1494 grpc_slice_ref_internal(str->data.referenced);
1495 return parse_next(p, cur + p->strlen, end);
1496 }
1497 p->strgot = 0;
1498 str->copied = true;
1499 str->data.copied.length = 0;
1500 p->parsing.str = str;
1501 p->huff_state = 0;
1502 p->binary = binary;
1503 switch (p->binary) {
1504 case NOT_BINARY:
1505 if (p->huff) {
1506 GRPC_STATS_INC_HPACK_RECV_HUFFMAN();
1507 } else {
1508 GRPC_STATS_INC_HPACK_RECV_UNCOMPRESSED();
1509 }
1510 break;
1511 case BINARY_BEGIN:
1512 /* stats incremented later: don't know true binary or not */
1513 break;
1514 default:
1515 abort();
1516 }
1517 return parse_string(p, cur, end);
1518 }
1519
1520 /* parse the key string */
parse_key_string(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)1521 static grpc_error* parse_key_string(grpc_chttp2_hpack_parser* p,
1522 const uint8_t* cur, const uint8_t* end) {
1523 return begin_parse_string(p, cur, end, NOT_BINARY, &p->key);
1524 }
1525
1526 /* check if a key represents a binary header or not */
1527
is_binary_literal_header(grpc_chttp2_hpack_parser * p)1528 static bool is_binary_literal_header(grpc_chttp2_hpack_parser* p) {
1529 /* We know that either argument here is a reference counter slice.
1530 * 1. If it is a grpc_core::StaticSlice, the refcount is set to kNoopRefcount.
1531 * 2. If it's p->key.data.referenced, then p->key.copied was set to false,
1532 * which occurs in begin_parse_string() - where the refcount is set to
1533 * p->current_slice_refcount, which is not null. */
1534 return grpc_is_refcounted_slice_binary_header(
1535 p->key.copied ? grpc_core::ExternallyManagedSlice(
1536 p->key.data.copied.str, p->key.data.copied.length)
1537 : p->key.data.referenced);
1538 }
1539
1540 /* Cache the metadata for the given index during initial parsing. This avoids a
1541 pointless recomputation of the metadata when finishing a header. We read the
1542 cached value in get_precomputed_md_for_idx(). */
set_precomputed_md_idx(grpc_chttp2_hpack_parser * p,grpc_mdelem md)1543 static void set_precomputed_md_idx(grpc_chttp2_hpack_parser* p,
1544 grpc_mdelem md) {
1545 GPR_DEBUG_ASSERT(p->md_for_index.payload == 0);
1546 GPR_DEBUG_ASSERT(p->precomputed_md_index == -1);
1547 p->md_for_index = md;
1548 #ifndef NDEBUG
1549 p->precomputed_md_index = p->index;
1550 #endif
1551 }
1552
1553 /* Determines if a metadata element key associated with the current parser index
1554 is a binary indexed header during string parsing. We'll need to revisit this
1555 metadata when we're done parsing, so we cache the metadata for this index
1556 here using set_precomputed_md_idx(). */
is_binary_indexed_header(grpc_chttp2_hpack_parser * p,bool * is)1557 static grpc_error* is_binary_indexed_header(grpc_chttp2_hpack_parser* p,
1558 bool* is) {
1559 grpc_mdelem elem = grpc_chttp2_hptbl_lookup(&p->table, p->index);
1560 if (GPR_UNLIKELY(GRPC_MDISNULL(elem))) {
1561 return on_invalid_hpack_idx(p);
1562 }
1563 /* We know that GRPC_MDKEY(elem) points to a reference counted slice since:
1564 * 1. elem was a result of grpc_chttp2_hptbl_lookup
1565 * 2. An item in this table is either static (see entries with
1566 * index < GRPC_CHTTP2_LAST_STATIC_ENTRY or added via
1567 * grpc_chttp2_hptbl_add).
1568 * 3. If added via grpc_chttp2_hptbl_add, the entry is either static or
1569 * interned.
1570 * 4. Both static and interned element slices have non-null refcounts. */
1571 *is = grpc_is_refcounted_slice_binary_header(GRPC_MDKEY(elem));
1572 set_precomputed_md_idx(p, elem);
1573 return GRPC_ERROR_NONE;
1574 }
1575
1576 /* parse the value string */
parse_value_string(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end,bool is_binary)1577 static grpc_error* parse_value_string(grpc_chttp2_hpack_parser* p,
1578 const uint8_t* cur, const uint8_t* end,
1579 bool is_binary) {
1580 return begin_parse_string(p, cur, end, is_binary ? BINARY_BEGIN : NOT_BINARY,
1581 &p->value);
1582 }
1583
parse_value_string_with_indexed_key(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)1584 static grpc_error* parse_value_string_with_indexed_key(
1585 grpc_chttp2_hpack_parser* p, const uint8_t* cur, const uint8_t* end) {
1586 bool is_binary = false;
1587 grpc_error* err = is_binary_indexed_header(p, &is_binary);
1588 if (err != GRPC_ERROR_NONE) return parse_error(p, cur, end, err);
1589 return parse_value_string(p, cur, end, is_binary);
1590 }
1591
parse_value_string_with_literal_key(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)1592 static grpc_error* parse_value_string_with_literal_key(
1593 grpc_chttp2_hpack_parser* p, const uint8_t* cur, const uint8_t* end) {
1594 return parse_value_string(p, cur, end, is_binary_literal_header(p));
1595 }
1596
1597 /* "Uninitialized" header parser to save us a branch in on_hdr(). */
on_header_uninitialized(void *,grpc_mdelem md)1598 static grpc_error* on_header_uninitialized(void* /*user_data*/,
1599 grpc_mdelem md) {
1600 GRPC_MDELEM_UNREF(md);
1601 return GRPC_ERROR_CREATE_FROM_STATIC_STRING("on_header callback not set");
1602 }
1603
1604 /* PUBLIC INTERFACE */
1605
grpc_chttp2_hpack_parser_init(grpc_chttp2_hpack_parser * p)1606 void grpc_chttp2_hpack_parser_init(grpc_chttp2_hpack_parser* p) {
1607 p->on_header = on_header_uninitialized;
1608 p->on_header_user_data = nullptr;
1609 p->state = parse_begin;
1610 p->key.data.referenced = grpc_empty_slice();
1611 p->key.data.copied.str = nullptr;
1612 p->key.data.copied.capacity = 0;
1613 p->key.data.copied.length = 0;
1614 p->value.data.referenced = grpc_empty_slice();
1615 p->value.data.copied.str = nullptr;
1616 p->value.data.copied.capacity = 0;
1617 p->value.data.copied.length = 0;
1618 /* Cached metadata for the current index the parser is handling. This is set
1619 to 0 initially, invalidated when the index changes, and invalidated when it
1620 is read (by get_precomputed_md_for_idx()). It is set during string parsing,
1621 by set_precomputed_md_idx() - which is called by parse_value_string().
1622 The goal here is to avoid recomputing the metadata for the index when
1623 finishing with a header as well as the initial parse. */
1624 p->md_for_index.payload = 0;
1625 #ifndef NDEBUG
1626 /* In debug mode, this ensures that the cached metadata we're reading is in
1627 * fact correct for the index we are examining. */
1628 p->precomputed_md_index = -1;
1629 #endif
1630 p->dynamic_table_update_allowed = 2;
1631 p->last_error = GRPC_ERROR_NONE;
1632 }
1633
grpc_chttp2_hpack_parser_set_has_priority(grpc_chttp2_hpack_parser * p)1634 void grpc_chttp2_hpack_parser_set_has_priority(grpc_chttp2_hpack_parser* p) {
1635 p->after_prioritization = p->state;
1636 p->state = parse_stream_dep0;
1637 }
1638
grpc_chttp2_hpack_parser_destroy(grpc_chttp2_hpack_parser * p)1639 void grpc_chttp2_hpack_parser_destroy(grpc_chttp2_hpack_parser* p) {
1640 grpc_chttp2_hptbl_destroy(&p->table);
1641 GRPC_ERROR_UNREF(p->last_error);
1642 grpc_slice_unref_internal(p->key.data.referenced);
1643 grpc_slice_unref_internal(p->value.data.referenced);
1644 gpr_free(p->key.data.copied.str);
1645 gpr_free(p->value.data.copied.str);
1646 }
1647
grpc_chttp2_hpack_parser_parse(grpc_chttp2_hpack_parser * p,const grpc_slice & slice)1648 grpc_error* grpc_chttp2_hpack_parser_parse(grpc_chttp2_hpack_parser* p,
1649 const grpc_slice& slice) {
1650 /* max number of bytes to parse at a time... limits call stack depth on
1651 * compilers without TCO */
1652 #define MAX_PARSE_LENGTH 1024
1653 p->current_slice_refcount = slice.refcount;
1654 const uint8_t* start = GRPC_SLICE_START_PTR(slice);
1655 const uint8_t* end = GRPC_SLICE_END_PTR(slice);
1656 grpc_error* error = GRPC_ERROR_NONE;
1657 while (start != end && error == GRPC_ERROR_NONE) {
1658 const uint8_t* target = start + GPR_MIN(MAX_PARSE_LENGTH, end - start);
1659 error = p->state(p, start, target);
1660 start = target;
1661 }
1662 p->current_slice_refcount = nullptr;
1663 return error;
1664 }
1665
1666 typedef void (*maybe_complete_func_type)(grpc_chttp2_transport* t,
1667 grpc_chttp2_stream* s);
1668 static const maybe_complete_func_type maybe_complete_funcs[] = {
1669 grpc_chttp2_maybe_complete_recv_initial_metadata,
1670 grpc_chttp2_maybe_complete_recv_trailing_metadata};
1671
force_client_rst_stream(void * sp,grpc_error *)1672 static void force_client_rst_stream(void* sp, grpc_error* /*error*/) {
1673 grpc_chttp2_stream* s = static_cast<grpc_chttp2_stream*>(sp);
1674 grpc_chttp2_transport* t = s->t;
1675 if (!s->write_closed) {
1676 grpc_chttp2_add_rst_stream_to_next_write(t, s->id, GRPC_HTTP2_NO_ERROR,
1677 &s->stats.outgoing);
1678 grpc_chttp2_initiate_write(t, GRPC_CHTTP2_INITIATE_WRITE_FORCE_RST_STREAM);
1679 grpc_chttp2_mark_stream_closed(t, s, true, true, GRPC_ERROR_NONE);
1680 }
1681 GRPC_CHTTP2_STREAM_UNREF(s, "final_rst");
1682 }
1683
parse_stream_compression_md(grpc_chttp2_transport *,grpc_chttp2_stream * s,grpc_metadata_batch * initial_metadata)1684 static void parse_stream_compression_md(grpc_chttp2_transport* /*t*/,
1685 grpc_chttp2_stream* s,
1686 grpc_metadata_batch* initial_metadata) {
1687 if (initial_metadata->idx.named.content_encoding == nullptr ||
1688 grpc_stream_compression_method_parse(
1689 GRPC_MDVALUE(initial_metadata->idx.named.content_encoding->md), false,
1690 &s->stream_decompression_method) == 0) {
1691 s->stream_decompression_method =
1692 GRPC_STREAM_COMPRESSION_IDENTITY_DECOMPRESS;
1693 }
1694
1695 if (s->stream_decompression_method !=
1696 GRPC_STREAM_COMPRESSION_IDENTITY_DECOMPRESS) {
1697 s->stream_decompression_ctx = nullptr;
1698 grpc_slice_buffer_init(&s->decompressed_data_buffer);
1699 }
1700 }
1701
grpc_chttp2_header_parser_parse(void * hpack_parser,grpc_chttp2_transport * t,grpc_chttp2_stream * s,const grpc_slice & slice,int is_last)1702 grpc_error* grpc_chttp2_header_parser_parse(void* hpack_parser,
1703 grpc_chttp2_transport* t,
1704 grpc_chttp2_stream* s,
1705 const grpc_slice& slice,
1706 int is_last) {
1707 GPR_TIMER_SCOPE("grpc_chttp2_header_parser_parse", 0);
1708 grpc_chttp2_hpack_parser* parser =
1709 static_cast<grpc_chttp2_hpack_parser*>(hpack_parser);
1710 if (s != nullptr) {
1711 s->stats.incoming.header_bytes += GRPC_SLICE_LENGTH(slice);
1712 }
1713 grpc_error* error = grpc_chttp2_hpack_parser_parse(parser, slice);
1714 if (error != GRPC_ERROR_NONE) {
1715 return error;
1716 }
1717 if (is_last) {
1718 if (parser->is_boundary && parser->state != parse_begin) {
1719 return GRPC_ERROR_CREATE_FROM_STATIC_STRING(
1720 "end of header frame not aligned with a hpack record boundary");
1721 }
1722 /* need to check for null stream: this can occur if we receive an invalid
1723 stream id on a header */
1724 if (s != nullptr) {
1725 if (parser->is_boundary) {
1726 if (s->header_frames_received == GPR_ARRAY_SIZE(s->metadata_buffer)) {
1727 return GRPC_ERROR_CREATE_FROM_STATIC_STRING(
1728 "Too many trailer frames");
1729 }
1730 /* Process stream compression md element if it exists */
1731 if (s->header_frames_received ==
1732 0) { /* Only acts on initial metadata */
1733 parse_stream_compression_md(t, s, &s->metadata_buffer[0].batch);
1734 }
1735 s->published_metadata[s->header_frames_received] =
1736 GRPC_METADATA_PUBLISHED_FROM_WIRE;
1737 maybe_complete_funcs[s->header_frames_received](t, s);
1738 s->header_frames_received++;
1739 }
1740 if (parser->is_eof) {
1741 if (t->is_client && !s->write_closed) {
1742 /* server eof ==> complete closure; we may need to forcefully close
1743 the stream. Wait until the combiner lock is ready to be released
1744 however -- it might be that we receive a RST_STREAM following this
1745 and can avoid the extra write */
1746 GRPC_CHTTP2_STREAM_REF(s, "final_rst");
1747 t->combiner->FinallyRun(
1748 GRPC_CLOSURE_CREATE(force_client_rst_stream, s, nullptr),
1749 GRPC_ERROR_NONE);
1750 }
1751 grpc_chttp2_mark_stream_closed(t, s, true, false, GRPC_ERROR_NONE);
1752 }
1753 }
1754 parser->on_header = on_header_uninitialized;
1755 parser->on_header_user_data = nullptr;
1756 parser->is_boundary = 0xde;
1757 parser->is_eof = 0xde;
1758 parser->dynamic_table_update_allowed = 2;
1759 }
1760 return GRPC_ERROR_NONE;
1761 }
1762