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