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