• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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