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