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 }
1311 p->base64_buffer = bits << 18;
1312 /* fallthrough */
1313 b64_byte1:
1314 case B64_BYTE1:
1315 if (cur == end) {
1316 p->binary = B64_BYTE1;
1317 return GRPC_ERROR_NONE;
1318 }
1319 bits = inverse_base64[*cur];
1320 ++cur;
1321 if (bits == 255) {
1322 return parse_error(
1323 p, cur, end,
1324 GRPC_ERROR_CREATE_FROM_STATIC_STRING("Illegal base64 character"));
1325 } else if (bits == 64) {
1326 goto b64_byte1;
1327 }
1328 p->base64_buffer |= bits << 12;
1329 /* fallthrough */
1330 b64_byte2:
1331 case B64_BYTE2:
1332 if (cur == end) {
1333 p->binary = B64_BYTE2;
1334 return GRPC_ERROR_NONE;
1335 }
1336 bits = inverse_base64[*cur];
1337 ++cur;
1338 if (bits == 255) {
1339 return parse_error(
1340 p, cur, end,
1341 GRPC_ERROR_CREATE_FROM_STATIC_STRING("Illegal base64 character"));
1342 } else if (bits == 64) {
1343 goto b64_byte2;
1344 }
1345 p->base64_buffer |= bits << 6;
1346 /* fallthrough */
1347 b64_byte3:
1348 case B64_BYTE3:
1349 if (cur == end) {
1350 p->binary = B64_BYTE3;
1351 return GRPC_ERROR_NONE;
1352 }
1353 bits = inverse_base64[*cur];
1354 ++cur;
1355 if (bits == 255) {
1356 return parse_error(
1357 p, cur, end,
1358 GRPC_ERROR_CREATE_FROM_STATIC_STRING("Illegal base64 character"));
1359 } else if (bits == 64) {
1360 goto b64_byte3;
1361 }
1362 p->base64_buffer |= bits;
1363 bits = p->base64_buffer;
1364 decoded[0] = static_cast<uint8_t>(bits >> 16);
1365 decoded[1] = static_cast<uint8_t>(bits >> 8);
1366 decoded[2] = static_cast<uint8_t>(bits);
1367 append_bytes(str, decoded, 3);
1368 goto b64_byte0;
1369 }
1370 GPR_UNREACHABLE_CODE(return parse_error(
1371 p, cur, end,
1372 GRPC_ERROR_CREATE_FROM_STATIC_STRING("Should never reach here")));
1373 }
1374
finish_str(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)1375 static grpc_error* finish_str(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
1376 const uint8_t* end) {
1377 uint8_t decoded[2];
1378 uint32_t bits;
1379 grpc_chttp2_hpack_parser_string* str = p->parsing.str;
1380 switch (static_cast<binary_state>(p->binary)) {
1381 case NOT_BINARY:
1382 break;
1383 case BINARY_BEGIN:
1384 break;
1385 case B64_BYTE0:
1386 break;
1387 case B64_BYTE1:
1388 return parse_error(p, cur, end,
1389 GRPC_ERROR_CREATE_FROM_STATIC_STRING(
1390 "illegal base64 encoding")); /* illegal encoding */
1391 case B64_BYTE2:
1392 bits = p->base64_buffer;
1393 if (bits & 0xffff) {
1394 grpc_error* err = GRPC_ERROR_CREATE_FROM_COPIED_STRING(
1395 absl::StrFormat("trailing bits in base64 encoding: 0x%04x",
1396 bits & 0xffff)
1397 .c_str());
1398 return parse_error(p, cur, end, err);
1399 }
1400 decoded[0] = static_cast<uint8_t>(bits >> 16);
1401 append_bytes(str, decoded, 1);
1402 break;
1403 case B64_BYTE3:
1404 bits = p->base64_buffer;
1405 if (bits & 0xff) {
1406 grpc_error* err = GRPC_ERROR_CREATE_FROM_COPIED_STRING(
1407 absl::StrFormat("trailing bits in base64 encoding: 0x%02x",
1408 bits & 0xff)
1409 .c_str());
1410 return parse_error(p, cur, end, err);
1411 }
1412 decoded[0] = static_cast<uint8_t>(bits >> 16);
1413 decoded[1] = static_cast<uint8_t>(bits >> 8);
1414 append_bytes(str, decoded, 2);
1415 break;
1416 }
1417 return GRPC_ERROR_NONE;
1418 }
1419
1420 /* decode a nibble from a huffman encoded stream */
huff_nibble(grpc_chttp2_hpack_parser * p,uint8_t nibble)1421 static grpc_error* huff_nibble(grpc_chttp2_hpack_parser* p, uint8_t nibble) {
1422 int16_t emit = emit_sub_tbl[16 * emit_tbl[p->huff_state] + nibble];
1423 int16_t next = next_sub_tbl[16 * next_tbl[p->huff_state] + nibble];
1424 if (emit != -1) {
1425 if (emit >= 0 && emit < 256) {
1426 uint8_t c = static_cast<uint8_t>(emit);
1427 grpc_error* err = append_string(p, &c, (&c) + 1);
1428 if (err != GRPC_ERROR_NONE) return err;
1429 } else {
1430 assert(emit == 256);
1431 }
1432 }
1433 p->huff_state = next;
1434 return GRPC_ERROR_NONE;
1435 }
1436
1437 /* decode full bytes from a huffman encoded stream */
add_huff_bytes(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)1438 static grpc_error* add_huff_bytes(grpc_chttp2_hpack_parser* p,
1439 const uint8_t* cur, const uint8_t* end) {
1440 for (; cur != end; ++cur) {
1441 grpc_error* err = huff_nibble(p, *cur >> 4);
1442 if (err != GRPC_ERROR_NONE) return parse_error(p, cur, end, err);
1443 err = huff_nibble(p, *cur & 0xf);
1444 if (err != GRPC_ERROR_NONE) return parse_error(p, cur, end, err);
1445 }
1446 return GRPC_ERROR_NONE;
1447 }
1448
1449 /* decode some string bytes based on the current decoding mode
1450 (huffman or not) */
add_str_bytes(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)1451 static grpc_error* add_str_bytes(grpc_chttp2_hpack_parser* p,
1452 const uint8_t* cur, const uint8_t* end) {
1453 if (p->huff) {
1454 return add_huff_bytes(p, cur, end);
1455 } else {
1456 return append_string(p, cur, end);
1457 }
1458 }
1459
1460 /* parse a string - tries to do large chunks at a time */
parse_string(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)1461 static grpc_error* parse_string(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
1462 const uint8_t* end) {
1463 size_t remaining = p->strlen - p->strgot;
1464 size_t given = static_cast<size_t>(end - cur);
1465 if (remaining <= given) {
1466 grpc_error* err = add_str_bytes(p, cur, cur + remaining);
1467 if (err != GRPC_ERROR_NONE) return parse_error(p, cur, end, err);
1468 err = finish_str(p, cur + remaining, end);
1469 if (err != GRPC_ERROR_NONE) return parse_error(p, cur, end, err);
1470 return parse_next(p, cur + remaining, end);
1471 } else {
1472 grpc_error* err = add_str_bytes(p, cur, cur + given);
1473 if (err != GRPC_ERROR_NONE) return parse_error(p, cur, end, err);
1474 GPR_ASSERT(given <= UINT32_MAX - p->strgot);
1475 p->strgot += static_cast<uint32_t>(given);
1476 p->state = parse_string;
1477 return GRPC_ERROR_NONE;
1478 }
1479 }
1480
1481 /* begin parsing a string - performs setup, calls parse_string */
begin_parse_string(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end,uint8_t binary,grpc_chttp2_hpack_parser_string * str)1482 static grpc_error* begin_parse_string(grpc_chttp2_hpack_parser* p,
1483 const uint8_t* cur, const uint8_t* end,
1484 uint8_t binary,
1485 grpc_chttp2_hpack_parser_string* str) {
1486 if (!p->huff && binary == NOT_BINARY &&
1487 static_cast<uint32_t>(end - cur) >= p->strlen &&
1488 p->current_slice_refcount != nullptr) {
1489 GRPC_STATS_INC_HPACK_RECV_UNCOMPRESSED();
1490 str->copied = false;
1491 str->data.referenced.refcount = p->current_slice_refcount;
1492 str->data.referenced.data.refcounted.bytes = const_cast<uint8_t*>(cur);
1493 str->data.referenced.data.refcounted.length = p->strlen;
1494 grpc_slice_ref_internal(str->data.referenced);
1495 return parse_next(p, cur + p->strlen, end);
1496 }
1497 p->strgot = 0;
1498 str->copied = true;
1499 str->data.copied.length = 0;
1500 p->parsing.str = str;
1501 p->huff_state = 0;
1502 p->binary = binary;
1503 switch (p->binary) {
1504 case NOT_BINARY:
1505 if (p->huff) {
1506 GRPC_STATS_INC_HPACK_RECV_HUFFMAN();
1507 } else {
1508 GRPC_STATS_INC_HPACK_RECV_UNCOMPRESSED();
1509 }
1510 break;
1511 case BINARY_BEGIN:
1512 /* stats incremented later: don't know true binary or not */
1513 break;
1514 default:
1515 abort();
1516 }
1517 return parse_string(p, cur, end);
1518 }
1519
1520 /* parse the key string */
parse_key_string(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)1521 static grpc_error* parse_key_string(grpc_chttp2_hpack_parser* p,
1522 const uint8_t* cur, const uint8_t* end) {
1523 return begin_parse_string(p, cur, end, NOT_BINARY, &p->key);
1524 }
1525
1526 /* check if a key represents a binary header or not */
1527
is_binary_literal_header(grpc_chttp2_hpack_parser * p)1528 static bool is_binary_literal_header(grpc_chttp2_hpack_parser* p) {
1529 /* We know that either argument here is a reference counter slice.
1530 * 1. If it is a grpc_core::StaticSlice, the refcount is set to kNoopRefcount.
1531 * 2. If it's p->key.data.referenced, then p->key.copied was set to false,
1532 * which occurs in begin_parse_string() - where the refcount is set to
1533 * p->current_slice_refcount, which is not null. */
1534 return grpc_is_refcounted_slice_binary_header(
1535 p->key.copied ? grpc_core::ExternallyManagedSlice(
1536 p->key.data.copied.str, p->key.data.copied.length)
1537 : p->key.data.referenced);
1538 }
1539
1540 /* Cache the metadata for the given index during initial parsing. This avoids a
1541 pointless recomputation of the metadata when finishing a header. We read the
1542 cached value in get_precomputed_md_for_idx(). */
set_precomputed_md_idx(grpc_chttp2_hpack_parser * p,grpc_mdelem md)1543 static void set_precomputed_md_idx(grpc_chttp2_hpack_parser* p,
1544 grpc_mdelem md) {
1545 GPR_DEBUG_ASSERT(p->md_for_index.payload == 0);
1546 GPR_DEBUG_ASSERT(p->precomputed_md_index == -1);
1547 p->md_for_index = md;
1548 #ifndef NDEBUG
1549 p->precomputed_md_index = p->index;
1550 #endif
1551 }
1552
1553 /* Determines if a metadata element key associated with the current parser index
1554 is a binary indexed header during string parsing. We'll need to revisit this
1555 metadata when we're done parsing, so we cache the metadata for this index
1556 here using set_precomputed_md_idx(). */
is_binary_indexed_header(grpc_chttp2_hpack_parser * p,bool * is)1557 static grpc_error* is_binary_indexed_header(grpc_chttp2_hpack_parser* p,
1558 bool* is) {
1559 grpc_mdelem elem = grpc_chttp2_hptbl_lookup(&p->table, p->index);
1560 if (GPR_UNLIKELY(GRPC_MDISNULL(elem))) {
1561 return on_invalid_hpack_idx(p);
1562 }
1563 /* We know that GRPC_MDKEY(elem) points to a reference counted slice since:
1564 * 1. elem was a result of grpc_chttp2_hptbl_lookup
1565 * 2. An item in this table is either static (see entries with
1566 * index < GRPC_CHTTP2_LAST_STATIC_ENTRY or added via
1567 * grpc_chttp2_hptbl_add).
1568 * 3. If added via grpc_chttp2_hptbl_add, the entry is either static or
1569 * interned.
1570 * 4. Both static and interned element slices have non-null refcounts. */
1571 *is = grpc_is_refcounted_slice_binary_header(GRPC_MDKEY(elem));
1572 set_precomputed_md_idx(p, elem);
1573 return GRPC_ERROR_NONE;
1574 }
1575
1576 /* parse the value string */
parse_value_string(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end,bool is_binary)1577 static grpc_error* parse_value_string(grpc_chttp2_hpack_parser* p,
1578 const uint8_t* cur, const uint8_t* end,
1579 bool is_binary) {
1580 return begin_parse_string(p, cur, end, is_binary ? BINARY_BEGIN : NOT_BINARY,
1581 &p->value);
1582 }
1583
parse_value_string_with_indexed_key(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)1584 static grpc_error* parse_value_string_with_indexed_key(
1585 grpc_chttp2_hpack_parser* p, const uint8_t* cur, const uint8_t* end) {
1586 bool is_binary = false;
1587 grpc_error* err = is_binary_indexed_header(p, &is_binary);
1588 if (err != GRPC_ERROR_NONE) return parse_error(p, cur, end, err);
1589 return parse_value_string(p, cur, end, is_binary);
1590 }
1591
parse_value_string_with_literal_key(grpc_chttp2_hpack_parser * p,const uint8_t * cur,const uint8_t * end)1592 static grpc_error* parse_value_string_with_literal_key(
1593 grpc_chttp2_hpack_parser* p, const uint8_t* cur, const uint8_t* end) {
1594 return parse_value_string(p, cur, end, is_binary_literal_header(p));
1595 }
1596
1597 /* "Uninitialized" header parser to save us a branch in on_hdr(). */
on_header_uninitialized(void *,grpc_mdelem md)1598 static grpc_error* on_header_uninitialized(void* /*user_data*/,
1599 grpc_mdelem md) {
1600 GRPC_MDELEM_UNREF(md);
1601 return GRPC_ERROR_CREATE_FROM_STATIC_STRING("on_header callback not set");
1602 }
1603
1604 /* PUBLIC INTERFACE */
1605
grpc_chttp2_hpack_parser_init(grpc_chttp2_hpack_parser * p)1606 void grpc_chttp2_hpack_parser_init(grpc_chttp2_hpack_parser* p) {
1607 p->on_header = on_header_uninitialized;
1608 p->on_header_user_data = nullptr;
1609 p->state = parse_begin;
1610 p->key.data.referenced = grpc_empty_slice();
1611 p->key.data.copied.str = nullptr;
1612 p->key.data.copied.capacity = 0;
1613 p->key.data.copied.length = 0;
1614 p->value.data.referenced = grpc_empty_slice();
1615 p->value.data.copied.str = nullptr;
1616 p->value.data.copied.capacity = 0;
1617 p->value.data.copied.length = 0;
1618 /* Cached metadata for the current index the parser is handling. This is set
1619 to 0 initially, invalidated when the index changes, and invalidated when it
1620 is read (by get_precomputed_md_for_idx()). It is set during string parsing,
1621 by set_precomputed_md_idx() - which is called by parse_value_string().
1622 The goal here is to avoid recomputing the metadata for the index when
1623 finishing with a header as well as the initial parse. */
1624 p->md_for_index.payload = 0;
1625 #ifndef NDEBUG
1626 /* In debug mode, this ensures that the cached metadata we're reading is in
1627 * fact correct for the index we are examining. */
1628 p->precomputed_md_index = -1;
1629 #endif
1630 p->dynamic_table_update_allowed = 2;
1631 p->last_error = GRPC_ERROR_NONE;
1632 }
1633
grpc_chttp2_hpack_parser_set_has_priority(grpc_chttp2_hpack_parser * p)1634 void grpc_chttp2_hpack_parser_set_has_priority(grpc_chttp2_hpack_parser* p) {
1635 p->after_prioritization = p->state;
1636 p->state = parse_stream_dep0;
1637 }
1638
grpc_chttp2_hpack_parser_destroy(grpc_chttp2_hpack_parser * p)1639 void grpc_chttp2_hpack_parser_destroy(grpc_chttp2_hpack_parser* p) {
1640 grpc_chttp2_hptbl_destroy(&p->table);
1641 GRPC_ERROR_UNREF(p->last_error);
1642 grpc_slice_unref_internal(p->key.data.referenced);
1643 grpc_slice_unref_internal(p->value.data.referenced);
1644 gpr_free(p->key.data.copied.str);
1645 gpr_free(p->value.data.copied.str);
1646 }
1647
grpc_chttp2_hpack_parser_parse(grpc_chttp2_hpack_parser * p,const grpc_slice & slice)1648 grpc_error* grpc_chttp2_hpack_parser_parse(grpc_chttp2_hpack_parser* p,
1649 const grpc_slice& slice) {
1650 /* max number of bytes to parse at a time... limits call stack depth on
1651 * compilers without TCO */
1652 #define MAX_PARSE_LENGTH 1024
1653 p->current_slice_refcount = slice.refcount;
1654 const uint8_t* start = GRPC_SLICE_START_PTR(slice);
1655 const uint8_t* end = GRPC_SLICE_END_PTR(slice);
1656 grpc_error* error = GRPC_ERROR_NONE;
1657 while (start != end && error == GRPC_ERROR_NONE) {
1658 const uint8_t* target = start + GPR_MIN(MAX_PARSE_LENGTH, end - start);
1659 error = p->state(p, start, target);
1660 start = target;
1661 }
1662 p->current_slice_refcount = nullptr;
1663 return error;
1664 }
1665
1666 typedef void (*maybe_complete_func_type)(grpc_chttp2_transport* t,
1667 grpc_chttp2_stream* s);
1668 static const maybe_complete_func_type maybe_complete_funcs[] = {
1669 grpc_chttp2_maybe_complete_recv_initial_metadata,
1670 grpc_chttp2_maybe_complete_recv_trailing_metadata};
1671
force_client_rst_stream(void * sp,grpc_error *)1672 static void force_client_rst_stream(void* sp, grpc_error* /*error*/) {
1673 grpc_chttp2_stream* s = static_cast<grpc_chttp2_stream*>(sp);
1674 grpc_chttp2_transport* t = s->t;
1675 if (!s->write_closed) {
1676 grpc_chttp2_add_rst_stream_to_next_write(t, s->id, GRPC_HTTP2_NO_ERROR,
1677 &s->stats.outgoing);
1678 grpc_chttp2_initiate_write(t, GRPC_CHTTP2_INITIATE_WRITE_FORCE_RST_STREAM);
1679 grpc_chttp2_mark_stream_closed(t, s, true, true, GRPC_ERROR_NONE);
1680 }
1681 GRPC_CHTTP2_STREAM_UNREF(s, "final_rst");
1682 }
1683
parse_stream_compression_md(grpc_chttp2_transport *,grpc_chttp2_stream * s,grpc_metadata_batch * initial_metadata)1684 static void parse_stream_compression_md(grpc_chttp2_transport* /*t*/,
1685 grpc_chttp2_stream* s,
1686 grpc_metadata_batch* initial_metadata) {
1687 if (initial_metadata->idx.named.content_encoding == nullptr ||
1688 grpc_stream_compression_method_parse(
1689 GRPC_MDVALUE(initial_metadata->idx.named.content_encoding->md), false,
1690 &s->stream_decompression_method) == 0) {
1691 s->stream_decompression_method =
1692 GRPC_STREAM_COMPRESSION_IDENTITY_DECOMPRESS;
1693 }
1694
1695 if (s->stream_decompression_method !=
1696 GRPC_STREAM_COMPRESSION_IDENTITY_DECOMPRESS) {
1697 s->stream_decompression_ctx = nullptr;
1698 grpc_slice_buffer_init(&s->decompressed_data_buffer);
1699 }
1700 }
1701
grpc_chttp2_header_parser_parse(void * hpack_parser,grpc_chttp2_transport * t,grpc_chttp2_stream * s,const grpc_slice & slice,int is_last)1702 grpc_error* grpc_chttp2_header_parser_parse(void* hpack_parser,
1703 grpc_chttp2_transport* t,
1704 grpc_chttp2_stream* s,
1705 const grpc_slice& slice,
1706 int is_last) {
1707 GPR_TIMER_SCOPE("grpc_chttp2_header_parser_parse", 0);
1708 grpc_chttp2_hpack_parser* parser =
1709 static_cast<grpc_chttp2_hpack_parser*>(hpack_parser);
1710 if (s != nullptr) {
1711 s->stats.incoming.header_bytes += GRPC_SLICE_LENGTH(slice);
1712 }
1713 grpc_error* error = grpc_chttp2_hpack_parser_parse(parser, slice);
1714 if (error != GRPC_ERROR_NONE) {
1715 return error;
1716 }
1717 if (is_last) {
1718 if (parser->is_boundary && parser->state != parse_begin) {
1719 return GRPC_ERROR_CREATE_FROM_STATIC_STRING(
1720 "end of header frame not aligned with a hpack record boundary");
1721 }
1722 /* need to check for null stream: this can occur if we receive an invalid
1723 stream id on a header */
1724 if (s != nullptr) {
1725 if (parser->is_boundary) {
1726 if (s->header_frames_received == GPR_ARRAY_SIZE(s->metadata_buffer)) {
1727 return GRPC_ERROR_CREATE_FROM_STATIC_STRING(
1728 "Too many trailer frames");
1729 }
1730 /* Process stream compression md element if it exists */
1731 if (s->header_frames_received ==
1732 0) { /* Only acts on initial metadata */
1733 parse_stream_compression_md(t, s, &s->metadata_buffer[0].batch);
1734 }
1735 s->published_metadata[s->header_frames_received] =
1736 GRPC_METADATA_PUBLISHED_FROM_WIRE;
1737 maybe_complete_funcs[s->header_frames_received](t, s);
1738 s->header_frames_received++;
1739 }
1740 if (parser->is_eof) {
1741 if (t->is_client && !s->write_closed) {
1742 /* server eof ==> complete closure; we may need to forcefully close
1743 the stream. Wait until the combiner lock is ready to be released
1744 however -- it might be that we receive a RST_STREAM following this
1745 and can avoid the extra write */
1746 GRPC_CHTTP2_STREAM_REF(s, "final_rst");
1747 t->combiner->FinallyRun(
1748 GRPC_CLOSURE_CREATE(force_client_rst_stream, s, nullptr),
1749 GRPC_ERROR_NONE);
1750 }
1751 grpc_chttp2_mark_stream_closed(t, s, true, false, GRPC_ERROR_NONE);
1752 }
1753 }
1754 parser->on_header = on_header_uninitialized;
1755 parser->on_header_user_data = nullptr;
1756 parser->is_boundary = 0xde;
1757 parser->is_eof = 0xde;
1758 parser->dynamic_table_update_allowed = 2;
1759 }
1760 return GRPC_ERROR_NONE;
1761 }
1762