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