3 * Copyright 2015 gRPC authors.
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
9 * http://www.apache.org/licenses/LICENSE-2.0
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.
19 #include <grpc/support/port_platform.h>
21 #include "src/core/ext/transport/chttp2/transport/hpack_parser.h"
22 #include "src/core/ext/transport/chttp2/transport/internal.h"
28 #include <grpc/support/alloc.h>
29 #include <grpc/support/log.h>
30 #include <grpc/support/string_util.h>
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"
51 The parser object keeps track of a function pointer which represents the
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.
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.
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. */
63 /* forward declarations for parsing states */
64 static grpc_error* parse_begin(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
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);
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);
82 static grpc_error* parse_value0(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
84 static grpc_error* parse_value1(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
86 static grpc_error* parse_value2(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
88 static grpc_error* parse_value3(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
90 static grpc_error* parse_value4(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
92 static grpc_error* parse_value5up(grpc_chttp2_hpack_parser* p,
93 const uint8_t* cur, const uint8_t* end);
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,
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,
105 static grpc_error* parse_lithdr_incidx_v(grpc_chttp2_hpack_parser* p,
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,
113 static grpc_error* parse_lithdr_notidx_v(grpc_chttp2_hpack_parser* p,
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,
121 static grpc_error* parse_lithdr_nvridx_v(grpc_chttp2_hpack_parser* p,
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);
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.
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
152 /* jump table of parse state functions -- order must match first_byte_type
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};
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,
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.
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,
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,
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
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,
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,
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,
624 /* emission helpers */
625 static grpc_error* on_hdr(grpc_chttp2_hpack_parser* p, grpc_mdelem md,
627 if (GRPC_TRACE_FLAG_ENABLED(grpc_http_trace)) {
628 char* k = grpc_slice_to_c_string(GRPC_MDKEY(md));
630 if (grpc_is_binary_header(GRPC_MDKEY(md))) {
631 v = grpc_dump_slice(GRPC_MDVALUE(md), GPR_DUMP_HEX);
633 v = grpc_slice_to_c_string(GRPC_MDVALUE(md));
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)));
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;
650 if (p->on_header == nullptr) {
651 GRPC_MDELEM_UNREF(md);
652 return GRPC_ERROR_CREATE_FROM_STATIC_STRING("on_header callback not set");
654 p->on_header(p->on_header_user_data, md);
655 return GRPC_ERROR_NONE;
658 static grpc_slice take_string(grpc_chttp2_hpack_parser* p,
659 grpc_chttp2_hpack_parser_string* str,
664 s = grpc_slice_intern(str->data.referenced);
665 grpc_slice_unref_internal(str->data.referenced);
667 s = str->data.referenced;
670 str->data.referenced = grpc_empty_slice();
672 s = grpc_slice_intern(grpc_slice_from_static_buffer(
673 str->data.copied.str, str->data.copied.length));
675 s = grpc_slice_from_copied_buffer(str->data.copied.str,
676 str->data.copied.length);
678 str->data.copied.length = 0;
682 /* jump to the next state */
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);
689 /* begin parsing a header: all functionality is encoded into lookup tables
691 static grpc_error* parse_begin(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
692 const uint8_t* end) {
694 p->state = parse_begin;
695 return GRPC_ERROR_NONE;
698 return first_byte_action[first_byte_lut[*cur]](p, cur, end);
701 /* stream dependency and prioritization data: we just skip it */
702 static grpc_error* parse_stream_weight(grpc_chttp2_hpack_parser* p,
703 const uint8_t* cur, const uint8_t* end) {
705 p->state = parse_stream_weight;
706 return GRPC_ERROR_NONE;
709 return p->after_prioritization(p, cur + 1, end);
712 static grpc_error* parse_stream_dep3(grpc_chttp2_hpack_parser* p,
713 const uint8_t* cur, const uint8_t* end) {
715 p->state = parse_stream_dep3;
716 return GRPC_ERROR_NONE;
719 return parse_stream_weight(p, cur + 1, end);
722 static grpc_error* parse_stream_dep2(grpc_chttp2_hpack_parser* p,
723 const uint8_t* cur, const uint8_t* end) {
725 p->state = parse_stream_dep2;
726 return GRPC_ERROR_NONE;
729 return parse_stream_dep3(p, cur + 1, end);
732 static grpc_error* parse_stream_dep1(grpc_chttp2_hpack_parser* p,
733 const uint8_t* cur, const uint8_t* end) {
735 p->state = parse_stream_dep1;
736 return GRPC_ERROR_NONE;
739 return parse_stream_dep2(p, cur + 1, end);
742 static grpc_error* parse_stream_dep0(grpc_chttp2_hpack_parser* p,
743 const uint8_t* cur, const uint8_t* end) {
745 p->state = parse_stream_dep0;
746 return GRPC_ERROR_NONE;
749 return parse_stream_dep1(p, cur + 1, end);
752 /* emit an indexed field; jumps to begin the next field on completion */
753 static grpc_error* finish_indexed_field(grpc_chttp2_hpack_parser* p,
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));
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);
772 /* parse an indexed field with index < 127 */
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);
780 /* parse an indexed field with index >= 127 */
781 static grpc_error* parse_indexed_field_x(grpc_chttp2_hpack_parser* p,
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;
789 p->parsing.value = &p->index;
790 return parse_value0(p, cur + 1, end);
793 /* finish a literal header with incremental indexing */
794 static grpc_error* finish_lithdr_incidx(grpc_chttp2_hpack_parser* p,
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();
802 grpc_mdelem_from_slices(grpc_slice_ref_internal(GRPC_MDKEY(md)),
803 take_string(p, &p->value, true)),
805 if (err != GRPC_ERROR_NONE) return parse_error(p, cur, end, err);
806 return parse_begin(p, cur, end);
809 /* finish a literal header with incremental indexing with no index */
810 static grpc_error* finish_lithdr_incidx_v(grpc_chttp2_hpack_parser* p,
812 const uint8_t* end) {
813 GRPC_STATS_INC_HPACK_RECV_LITHDR_INCIDX_V();
816 grpc_mdelem_from_slices(take_string(p, &p->key, true),
817 take_string(p, &p->value, true)),
819 if (err != GRPC_ERROR_NONE) return parse_error(p, cur, end, err);
820 return parse_begin(p, cur, end);
823 /* parse a literal header with incremental indexing; index < 63 */
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);
834 /* parse a literal header with incremental indexing; index >= 63 */
835 static grpc_error* parse_lithdr_incidx_x(grpc_chttp2_hpack_parser* p,
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;
844 p->parsing.value = &p->index;
845 return parse_value0(p, cur + 1, end);
848 /* parse a literal header with incremental indexing; index = 0 */
849 static grpc_error* parse_lithdr_incidx_v(grpc_chttp2_hpack_parser* p,
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);
860 /* finish a literal header without incremental indexing */
861 static grpc_error* finish_lithdr_notidx(grpc_chttp2_hpack_parser* p,
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();
869 grpc_mdelem_from_slices(grpc_slice_ref_internal(GRPC_MDKEY(md)),
870 take_string(p, &p->value, false)),
872 if (err != GRPC_ERROR_NONE) return parse_error(p, cur, end, err);
873 return parse_begin(p, cur, end);
876 /* finish a literal header without incremental indexing with index = 0 */
877 static grpc_error* finish_lithdr_notidx_v(grpc_chttp2_hpack_parser* p,
879 const uint8_t* end) {
880 GRPC_STATS_INC_HPACK_RECV_LITHDR_NOTIDX_V();
883 grpc_mdelem_from_slices(take_string(p, &p->key, true),
884 take_string(p, &p->value, false)),
886 if (err != GRPC_ERROR_NONE) return parse_error(p, cur, end, err);
887 return parse_begin(p, cur, end);
890 /* parse a literal header without incremental indexing; index < 15 */
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);
901 /* parse a literal header without incremental indexing; index >= 15 */
902 static grpc_error* parse_lithdr_notidx_x(grpc_chttp2_hpack_parser* p,
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;
911 p->parsing.value = &p->index;
912 return parse_value0(p, cur + 1, end);
915 /* parse a literal header without incremental indexing; index == 0 */
916 static grpc_error* parse_lithdr_notidx_v(grpc_chttp2_hpack_parser* p,
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);
927 /* finish a literal header that is never indexed */
928 static grpc_error* finish_lithdr_nvridx(grpc_chttp2_hpack_parser* p,
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();
936 grpc_mdelem_from_slices(grpc_slice_ref_internal(GRPC_MDKEY(md)),
937 take_string(p, &p->value, false)),
939 if (err != GRPC_ERROR_NONE) return parse_error(p, cur, end, err);
940 return parse_begin(p, cur, end);
943 /* finish a literal header that is never indexed with an extra value */
944 static grpc_error* finish_lithdr_nvridx_v(grpc_chttp2_hpack_parser* p,
946 const uint8_t* end) {
947 GRPC_STATS_INC_HPACK_RECV_LITHDR_NVRIDX_V();
950 grpc_mdelem_from_slices(take_string(p, &p->key, true),
951 take_string(p, &p->value, false)),
953 if (err != GRPC_ERROR_NONE) return parse_error(p, cur, end, err);
954 return parse_begin(p, cur, end);
957 /* parse a literal header that is never indexed; index < 15 */
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);
968 /* parse a literal header that is never indexed; index >= 15 */
969 static grpc_error* parse_lithdr_nvridx_x(grpc_chttp2_hpack_parser* p,
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;
978 p->parsing.value = &p->index;
979 return parse_value0(p, cur + 1, end);
982 /* parse a literal header that is never indexed; index == 0 */
983 static grpc_error* parse_lithdr_nvridx_v(grpc_chttp2_hpack_parser* p,
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);
994 /* finish parsing a max table size change */
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_TRACE_FLAG_ENABLED(grpc_http_trace)) {
998 gpr_log(GPR_INFO, "MAX TABLE SIZE: %d", p->index);
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);
1006 /* parse a max table size change, max size < 15 */
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) {
1012 GRPC_ERROR_CREATE_FROM_STATIC_STRING(
1013 "More than two max table size changes in a single frame"));
1015 p->dynamic_table_update_allowed--;
1016 p->index = (*cur) & 0x1f;
1017 return finish_max_tbl_size(p, cur + 1, end);
1020 /* parse a max table size change, max size >= 15 */
1021 static grpc_error* parse_max_tbl_size_x(grpc_chttp2_hpack_parser* p,
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) {
1029 GRPC_ERROR_CREATE_FROM_STATIC_STRING(
1030 "More than two max table size changes in a single frame"));
1032 p->dynamic_table_update_allowed--;
1033 p->next_state = and_then;
1035 p->parsing.value = &p->index;
1036 return parse_value0(p, cur + 1, end);
1039 /* a parse error: jam the parse state into parse_error, and return error */
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);
1046 p->state = still_parse_error;
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);
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);
1059 gpr_asprintf(&msg, "Illegal hpack op code %d", *cur);
1060 grpc_error* err = GRPC_ERROR_CREATE_FROM_COPIED_STRING(msg);
1062 return parse_error(p, cur, end, err);
1065 /* parse the 1st byte of a varint into p->parsing.value
1066 no overflow is possible */
1067 static grpc_error* parse_value0(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
1068 const uint8_t* end) {
1070 p->state = parse_value0;
1071 return GRPC_ERROR_NONE;
1074 *p->parsing.value += (*cur) & 0x7f;
1076 if ((*cur) & 0x80) {
1077 return parse_value1(p, cur + 1, end);
1079 return parse_next(p, cur + 1, end);
1083 /* parse the 2nd byte of a varint into p->parsing.value
1084 no overflow is possible */
1085 static grpc_error* parse_value1(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
1086 const uint8_t* end) {
1088 p->state = parse_value1;
1089 return GRPC_ERROR_NONE;
1092 *p->parsing.value += ((static_cast<uint32_t>(*cur)) & 0x7f) << 7;
1094 if ((*cur) & 0x80) {
1095 return parse_value2(p, cur + 1, end);
1097 return parse_next(p, cur + 1, end);
1101 /* parse the 3rd byte of a varint into p->parsing.value
1102 no overflow is possible */
1103 static grpc_error* parse_value2(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
1104 const uint8_t* end) {
1106 p->state = parse_value2;
1107 return GRPC_ERROR_NONE;
1110 *p->parsing.value += ((static_cast<uint32_t>(*cur)) & 0x7f) << 14;
1112 if ((*cur) & 0x80) {
1113 return parse_value3(p, cur + 1, end);
1115 return parse_next(p, cur + 1, end);
1119 /* parse the 4th byte of a varint into p->parsing.value
1120 no overflow is possible */
1121 static grpc_error* parse_value3(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
1122 const uint8_t* end) {
1124 p->state = parse_value3;
1125 return GRPC_ERROR_NONE;
1128 *p->parsing.value += ((static_cast<uint32_t>(*cur)) & 0x7f) << 21;
1130 if ((*cur) & 0x80) {
1131 return parse_value4(p, cur + 1, end);
1133 return parse_next(p, cur + 1, end);
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 */
1139 static grpc_error* parse_value4(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
1140 const uint8_t* end) {
1147 p->state = parse_value4;
1148 return GRPC_ERROR_NONE;
1156 cur_value = *p->parsing.value;
1157 add_value = (static_cast<uint32_t>(c)) << 28;
1158 if (add_value > 0xffffffffu - cur_value) {
1162 *p->parsing.value = cur_value + add_value;
1164 if ((*cur) & 0x80) {
1165 return parse_value5up(p, cur + 1, end);
1167 return parse_next(p, cur + 1, end);
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);
1177 return parse_error(p, cur, end, err);
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 */
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) {
1190 p->state = parse_value5up;
1191 return GRPC_ERROR_NONE;
1195 return parse_next(p, cur + 1, end);
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);
1205 return parse_error(p, cur, end, err);
1208 /* parse a string prefix */
1209 static grpc_error* parse_string_prefix(grpc_chttp2_hpack_parser* p,
1210 const uint8_t* cur, const uint8_t* end) {
1212 p->state = parse_string_prefix;
1213 return GRPC_ERROR_NONE;
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);
1222 return parse_next(p, cur + 1, end);
1226 /* append some bytes to a string */
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));
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);
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;
1247 switch (static_cast<binary_state>(p->binary)) {
1249 append_bytes(str, cur, static_cast<size_t>(end - cur));
1250 return GRPC_ERROR_NONE;
1253 p->binary = BINARY_BEGIN;
1254 return GRPC_ERROR_NONE;
1257 /* 'true-binary' case */
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;
1264 GRPC_STATS_INC_HPACK_RECV_BINARY_BASE64();
1269 p->binary = B64_BYTE0;
1270 return GRPC_ERROR_NONE;
1272 bits = inverse_base64[*cur];
1277 GRPC_ERROR_CREATE_FROM_STATIC_STRING("Illegal base64 character"));
1278 else if (bits == 64)
1280 p->base64_buffer = bits << 18;
1285 p->binary = B64_BYTE1;
1286 return GRPC_ERROR_NONE;
1288 bits = inverse_base64[*cur];
1293 GRPC_ERROR_CREATE_FROM_STATIC_STRING("Illegal base64 character"));
1294 else if (bits == 64)
1296 p->base64_buffer |= bits << 12;
1301 p->binary = B64_BYTE2;
1302 return GRPC_ERROR_NONE;
1304 bits = inverse_base64[*cur];
1309 GRPC_ERROR_CREATE_FROM_STATIC_STRING("Illegal base64 character"));
1310 else if (bits == 64)
1312 p->base64_buffer |= bits << 6;
1317 p->binary = B64_BYTE3;
1318 return GRPC_ERROR_NONE;
1320 bits = inverse_base64[*cur];
1325 GRPC_ERROR_CREATE_FROM_STATIC_STRING("Illegal base64 character"));
1326 else if (bits == 64)
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);
1336 GPR_UNREACHABLE_CODE(return parse_error(
1338 GRPC_ERROR_CREATE_FROM_STATIC_STRING("Should never reach here")));
1341 static grpc_error* finish_str(grpc_chttp2_hpack_parser* p, const uint8_t* cur,
1342 const uint8_t* end) {
1345 grpc_chttp2_hpack_parser_string* str = p->parsing.str;
1346 switch (static_cast<binary_state>(p->binary)) {
1354 return parse_error(p, cur, end,
1355 GRPC_ERROR_CREATE_FROM_STATIC_STRING(
1356 "illegal base64 encoding")); /* illegal encoding */
1358 bits = p->base64_buffer;
1359 if (bits & 0xffff) {
1361 gpr_asprintf(&msg, "trailing bits in base64 encoding: 0x%04x",
1363 grpc_error* err = GRPC_ERROR_CREATE_FROM_COPIED_STRING(msg);
1365 return parse_error(p, cur, end, err);
1367 decoded[0] = static_cast<uint8_t>(bits >> 16);
1368 append_bytes(str, decoded, 1);
1371 bits = p->base64_buffer;
1374 gpr_asprintf(&msg, "trailing bits in base64 encoding: 0x%02x",
1376 grpc_error* err = GRPC_ERROR_CREATE_FROM_COPIED_STRING(msg);
1378 return parse_error(p, cur, end, err);
1380 decoded[0] = static_cast<uint8_t>(bits >> 16);
1381 decoded[1] = static_cast<uint8_t>(bits >> 8);
1382 append_bytes(str, decoded, 2);
1385 return GRPC_ERROR_NONE;
1388 /* decode a nibble from a huffman encoded stream */
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];
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;
1398 assert(emit == 256);
1401 p->huff_state = next;
1402 return GRPC_ERROR_NONE;
1405 /* decode full bytes from a huffman encoded stream */
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);
1414 return GRPC_ERROR_NONE;
1417 /* decode some string bytes based on the current decoding mode
1419 static grpc_error* add_str_bytes(grpc_chttp2_hpack_parser* p,
1420 const uint8_t* cur, const uint8_t* end) {
1422 return add_huff_bytes(p, cur, end);
1424 return append_string(p, cur, end);
1428 /* parse a string - tries to do large chunks at a time */
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);
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;
1449 /* begin parsing a string - performs setup, calls parse_string */
1450 static grpc_error* begin_parse_string(grpc_chttp2_hpack_parser* p,
1451 const uint8_t* cur, const uint8_t* end,
1453 grpc_chttp2_hpack_parser_string* str) {
1454 if (!p->huff && binary == NOT_BINARY &&
1455 static_cast<uint32_t>(end - cur) >= 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);
1467 str->data.copied.length = 0;
1468 p->parsing.str = str;
1471 switch (p->binary) {
1474 GRPC_STATS_INC_HPACK_RECV_HUFFMAN();
1476 GRPC_STATS_INC_HPACK_RECV_UNCOMPRESSED();
1480 /* stats incremented later: don't know true binary or not */
1485 return parse_string(p, cur, end);
1488 /* parse the key string */
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);
1494 /* check if a key represents a binary header or not */
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);
1503 static grpc_error* is_binary_indexed_header(grpc_chttp2_hpack_parser* p,
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));
1514 *is = grpc_is_binary_header(GRPC_MDKEY(elem));
1515 return GRPC_ERROR_NONE;
1518 /* parse the value string */
1519 static grpc_error* parse_value_string(grpc_chttp2_hpack_parser* p,
1520 const uint8_t* cur, const uint8_t* end,
1522 return begin_parse_string(p, cur, end, is_binary ? BINARY_BEGIN : NOT_BINARY,
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);
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));
1539 /* PUBLIC INTERFACE */
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);
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;
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);
1572 grpc_error* grpc_chttp2_hpack_parser_parse(grpc_chttp2_hpack_parser* p,
1573 const 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 const uint8_t* start = GRPC_SLICE_START_PTR(slice);
1579 const uint8_t* end = GRPC_SLICE_END_PTR(slice);
1580 grpc_error* error = GRPC_ERROR_NONE;
1581 while (start != end && error == GRPC_ERROR_NONE) {
1582 const uint8_t* target = start + GPR_MIN(MAX_PARSE_LENGTH, end - start);
1583 error = p->state(p, start, target);
1586 p->current_slice_refcount = nullptr;
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};
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);
1606 GRPC_CHTTP2_STREAM_UNREF(s, "final_rst");
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;
1620 if (s->stream_decompression_method !=
1621 GRPC_STREAM_COMPRESSION_IDENTITY_DECOMPRESS) {
1622 s->stream_decompression_ctx = nullptr;
1623 grpc_slice_buffer_init(&s->decompressed_data_buffer);
1627 grpc_error* grpc_chttp2_header_parser_parse(void* hpack_parser,
1628 grpc_chttp2_transport* t,
1629 grpc_chttp2_stream* s,
1630 const grpc_slice& slice,
1632 GPR_TIMER_SCOPE("grpc_chttp2_header_parser_parse", 0);
1633 grpc_chttp2_hpack_parser* parser =
1634 static_cast<grpc_chttp2_hpack_parser*>(hpack_parser);
1636 s->stats.incoming.header_bytes += GRPC_SLICE_LENGTH(slice);
1638 grpc_error* error = grpc_chttp2_hpack_parser_parse(parser, slice);
1639 if (error != GRPC_ERROR_NONE) {
1643 if (parser->is_boundary && parser->state != parse_begin) {
1644 return GRPC_ERROR_CREATE_FROM_STATIC_STRING(
1645 "end of header frame not aligned with a hpack record boundary");
1647 /* need to check for null stream: this can occur if we receive an invalid
1648 stream id on a header */
1650 if (parser->is_boundary) {
1651 if (s->header_frames_received == GPR_ARRAY_SIZE(s->metadata_buffer)) {
1652 return GRPC_ERROR_CREATE_FROM_STATIC_STRING(
1653 "Too many trailer frames");
1655 /* Process stream compression md element if it exists */
1656 if (s->header_frames_received ==
1657 0) { /* Only acts on initial metadata */
1658 parse_stream_compression_md(t, s, &s->metadata_buffer[0].batch);
1660 s->published_metadata[s->header_frames_received] =
1661 GRPC_METADATA_PUBLISHED_FROM_WIRE;
1662 maybe_complete_funcs[s->header_frames_received](t, s);
1663 s->header_frames_received++;
1665 if (parser->is_eof) {
1666 if (t->is_client && !s->write_closed) {
1667 /* server eof ==> complete closure; we may need to forcefully close
1668 the stream. Wait until the combiner lock is ready to be released
1669 however -- it might be that we receive a RST_STREAM following this
1670 and can avoid the extra write */
1671 GRPC_CHTTP2_STREAM_REF(s, "final_rst");
1673 GRPC_CLOSURE_CREATE(force_client_rst_stream, s,
1674 grpc_combiner_finally_scheduler(t->combiner)),
1677 grpc_chttp2_mark_stream_closed(t, s, true, false, GRPC_ERROR_NONE);
1680 parser->on_header = nullptr;
1681 parser->on_header_user_data = nullptr;
1682 parser->is_boundary = 0xde;
1683 parser->is_eof = 0xde;
1684 parser->dynamic_table_update_allowed = 2;
1686 return GRPC_ERROR_NONE;