src/core/ext/transport/chttp2/transport/hpack_parser.cc

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