http2ng.c

#include "http2ng.h"

extern const nghttp2_huff_sym huff_sym_table[];
extern const nghttp2_huff_decode huff_decode_table[][16];

/* Generated by mkstatictbl.py */
/* 3rd parameter is nghttp2_token value for header field name.  We use
   first enum value if same header names are repeated (e.g.,
   :status). */
static nghttp2_hd_static_entry static_table[] = {
    MAKE_STATIC_ENT(":authority", "", 0, 3153725150u),
    MAKE_STATIC_ENT(":method", "GET", 1, 695666056u),
    MAKE_STATIC_ENT(":method", "POST", 1, 695666056u),
    MAKE_STATIC_ENT(":path", "/", 3, 3292848686u),
    MAKE_STATIC_ENT(":path", "/index.html", 3, 3292848686u),
    MAKE_STATIC_ENT(":scheme", "http", 5, 2510477674u),
    MAKE_STATIC_ENT(":scheme", "https", 5, 2510477674u),
    MAKE_STATIC_ENT(":status", "200", 7, 4000288983u),
    MAKE_STATIC_ENT(":status", "204", 7, 4000288983u),
    MAKE_STATIC_ENT(":status", "206", 7, 4000288983u),
    MAKE_STATIC_ENT(":status", "304", 7, 4000288983u),
    MAKE_STATIC_ENT(":status", "400", 7, 4000288983u),
    MAKE_STATIC_ENT(":status", "404", 7, 4000288983u),
    MAKE_STATIC_ENT(":status", "500", 7, 4000288983u),
    MAKE_STATIC_ENT("accept-charset", "", 14, 3664010344u),
    MAKE_STATIC_ENT("accept-encoding", "gzip, deflate", 15, 3379649177u),
    MAKE_STATIC_ENT("accept-language", "", 16, 1979086614u),
    MAKE_STATIC_ENT("accept-ranges", "", 17, 1713753958u),
    MAKE_STATIC_ENT("accept", "", 18, 136609321u),
    MAKE_STATIC_ENT("access-control-allow-origin", "", 19, 2710797292u),
    MAKE_STATIC_ENT("age", "", 20, 742476188u),
    MAKE_STATIC_ENT("allow", "", 21, 2930878514u),
    MAKE_STATIC_ENT("authorization", "", 22, 2436257726u),
    MAKE_STATIC_ENT("cache-control", "", 23, 1355326669u),
    MAKE_STATIC_ENT("content-disposition", "", 24, 3889184348u),
    MAKE_STATIC_ENT("content-encoding", "", 25, 65203592u),
    MAKE_STATIC_ENT("content-language", "", 26, 24973587u),
    MAKE_STATIC_ENT("content-length", "", 27, 1308181789u),
    MAKE_STATIC_ENT("content-location", "", 28, 2302364718u),
    MAKE_STATIC_ENT("content-range", "", 29, 3555523146u),
    MAKE_STATIC_ENT("content-type", "", 30, 4244048277u),
    MAKE_STATIC_ENT("cookie", "", 31, 2007449791u),
    MAKE_STATIC_ENT("date", "", 32, 3564297305u),
    MAKE_STATIC_ENT("etag", "", 33, 113792960u),
    MAKE_STATIC_ENT("expect", "", 34, 2530896728u),
    MAKE_STATIC_ENT("expires", "", 35, 1049544579u),
    MAKE_STATIC_ENT("from", "", 36, 2513272949u),
    MAKE_STATIC_ENT("host", "", 37, 2952701295u),
    MAKE_STATIC_ENT("if-match", "", 38, 3597694698u),
    MAKE_STATIC_ENT("if-modified-since", "", 39, 2213050793u),
    MAKE_STATIC_ENT("if-none-match", "", 40, 2536202615u),
    MAKE_STATIC_ENT("if-range", "", 41, 2340978238u),
    MAKE_STATIC_ENT("if-unmodified-since", "", 42, 3794814858u),
    MAKE_STATIC_ENT("last-modified", "", 43, 3226950251u),
    MAKE_STATIC_ENT("link", "", 44, 232457833u),
    MAKE_STATIC_ENT("location", "", 45, 200649126u),
    MAKE_STATIC_ENT("max-forwards", "", 46, 1826162134u),
    MAKE_STATIC_ENT("proxy-authenticate", "", 47, 2709445359u),
    MAKE_STATIC_ENT("proxy-authorization", "", 48, 2686392507u),
    MAKE_STATIC_ENT("range", "", 49, 4208725202u),
    MAKE_STATIC_ENT("referer", "", 50, 3969579366u),
    MAKE_STATIC_ENT("refresh", "", 51, 3572655668u),
    MAKE_STATIC_ENT("retry-after", "", 52, 3336180598u),
    MAKE_STATIC_ENT("server", "", 53, 1085029842u),
    MAKE_STATIC_ENT("set-cookie", "", 54, 1848371000u),
    MAKE_STATIC_ENT("strict-transport-security", "", 55, 4138147361u),
    MAKE_STATIC_ENT("transfer-encoding", "", 56, 3719590988u),
    MAKE_STATIC_ENT("user-agent", "", 57, 606444526u),
    MAKE_STATIC_ENT("vary", "", 58, 1085005381u),
    MAKE_STATIC_ENT("via", "", 59, 1762798611u),
    MAKE_STATIC_ENT("www-authenticate", "", 60, 779865858u),
};

static int memeq(const void *s1, const void *s2, size_t n) {
  return memcmp(s1, s2, n) == 0;
}

#define nghttp2_min(A, B) ((A) < (B) ? (A) : (B))
#define nghttp2_max(A, B) ((A) > (B) ? (A) : (B))

static void hd_map_insert(nghttp2_hd_map *map, nghttp2_hd_entry *ent) {
  nghttp2_hd_entry **bucket;

  bucket = &map->table[ent->hash & (HD_MAP_SIZE - 1)];

  if (*bucket == NULL) {
    *bucket = ent;
    return;
  }

  /* lower index is linked near the root */
  ent->next = *bucket;
  *bucket = ent;
}

static size_t entry_room(size_t namelen, size_t valuelen) {
  return NGHTTP2_HD_ENTRY_OVERHEAD + namelen + valuelen;
}

static void emit_header(nghttp2_hd_nv *nv_out, nghttp2_hd_nv *nv) {
  DEBUGF("inflatehd: header emission: %s: %s\n", nv->name->base,
         nv->value->base);
  /* ent->ref may be 0. This happens if the encoder emits literal
     block larger than header table capacity with indexing. */
  *nv_out = *nv;
}

void nghttp2_buf_wrap_init(nghttp2_buf *buf, uint8_t *begin, size_t len) {
  buf->begin = buf->pos = buf->last = buf->mark = begin;
  buf->end = begin + len;
}

uint8_t *nghttp2_cpymem(uint8_t *dest, const void *src, size_t len) {
  if (len == 0) {
    return dest;
  }

  memcpy(dest, src, len);

  return dest + len;
}

static void hd_context_shrink_table_size(nghttp2_hd_context *context,
                                         nghttp2_hd_map *map) {
  nghttp2_mem *mem;

  mem = context->mem;

  while (context->hd_table_bufsize > context->hd_table_bufsize_max &&
         context->hd_table.len > 0) {
    size_t idx = context->hd_table.len - 1;
    nghttp2_hd_entry *ent = hd_ringbuf_get(&context->hd_table, idx);
    context->hd_table_bufsize -=
        entry_room(ent->nv.name->len, ent->nv.value->len);
    hd_ringbuf_pop_back(&context->hd_table);
    if (map) {
      hd_map_remove(map, ent);
    }

    nghttp2_hd_entry_free(ent);
    nghttp2_mem_free(mem, ent);
  }
}

int nghttp2_rcbuf_new(nghttp2_rcbuf **rcbuf_ptr, size_t size,
                      nghttp2_mem *mem) {
  uint8_t *p;

  p = nghttp2_mem_malloc(mem, sizeof(nghttp2_rcbuf) + size);
  if (p == NULL) {
    return NGHTTP2_ERR_NOMEM;
  }

  *rcbuf_ptr = (void *)p;

  (*rcbuf_ptr)->mem_user_data = mem->mem_user_data;
  (*rcbuf_ptr)->free = mem->free;
  (*rcbuf_ptr)->base = p + sizeof(nghttp2_rcbuf);
  (*rcbuf_ptr)->len = size;
  (*rcbuf_ptr)->ref = 1;

  return 0;
}

/*
 * Decodes the integer from the range [in, last).  The result is
 * assigned to |inflater->left|.  If the |inflater->left| is 0, then
 * it performs variable integer decoding from scratch. Otherwise, it
 * uses the |inflater->left| as the initial value and continues to
 * decode assuming that [in, last) begins with intermediary sequence.
 *
 * This function returns the number of bytes read if it succeeds, or
 * one of the following negative error codes:
 *
 * NGHTTP2_ERR_HEADER_COMP
 *   Integer decoding failed
 */
static ssize_t hd_inflate_read_len(nghttp2_hd_inflater *inflater, int *rfin,
                                   const uint8_t *in, const uint8_t *last,
                                   size_t prefix, size_t maxlen) {
  ssize_t rv;
  uint32_t out;

  *rfin = 0;

  rv = decode_length(&out, &inflater->shift, rfin, (uint32_t)inflater->left,
                     inflater->shift, in, last, prefix);

  if (rv == -1) {
    DEBUGF("inflatehd: integer decoding failed\n");
    return NGHTTP2_ERR_HEADER_COMP;
  }

  if (out > maxlen) {
    DEBUGF("inflatehd: integer exceeded the maximum value %zu\n", maxlen);
    return NGHTTP2_ERR_HEADER_COMP;
  }

  inflater->left = out;

  DEBUGF("inflatehd: decoded integer is %u\n", out);

  return rv;
}

static void hd_ringbuf_pop_back(nghttp2_hd_ringbuf *ringbuf) {
  assert(ringbuf->len > 0);
  --ringbuf->len;
}

void nghttp2_hd_entry_free(nghttp2_hd_entry *ent) {
  nghttp2_rcbuf_decref(ent->nv.value);
  nghttp2_rcbuf_decref(ent->nv.name);
}

void *nghttp2_mem_malloc(nghttp2_mem *mem, size_t size) {
  return mem->malloc(size, mem->mem_user_data);
}

void nghttp2_mem_free(nghttp2_mem *mem, void *ptr) {
  mem->free(ptr, mem->mem_user_data);
}

void nghttp2_mem_free2(nghttp2_free free_func, void *ptr, void *mem_user_data) {
  free_func(ptr, mem_user_data);
}

void *nghttp2_mem_calloc(nghttp2_mem *mem, size_t nmemb, size_t size) {
  return mem->calloc(nmemb, size, mem->mem_user_data);
}

void *nghttp2_mem_realloc(nghttp2_mem *mem, void *ptr, size_t size) {
  return mem->realloc(ptr, size, mem->mem_user_data);
}


static int add_hd_table_incremental(nghttp2_hd_context *context,
                                    nghttp2_hd_nv *nv, nghttp2_hd_map *map,
                                    uint32_t hash) {
  int rv;
  nghttp2_hd_entry *new_ent;
  size_t room;
  nghttp2_mem *mem;

  mem = context->mem;
  room = entry_room(nv->name->len, nv->value->len);

  while (context->hd_table_bufsize + room > context->hd_table_bufsize_max &&
         context->hd_table.len > 0) {

    size_t idx = context->hd_table.len - 1;
    nghttp2_hd_entry *ent = hd_ringbuf_get(&context->hd_table, idx);

    context->hd_table_bufsize -=
        entry_room(ent->nv.name->len, ent->nv.value->len);

    DEBUGF("hpack: remove item from header table: %s: %s\n",
           (char *)ent->nv.name->base, (char *)ent->nv.value->base);

    hd_ringbuf_pop_back(&context->hd_table);
    if (map) {
      hd_map_remove(map, ent);
    }

    nghttp2_hd_entry_free(ent);
    nghttp2_mem_free(mem, ent);
  }

  if (room > context->hd_table_bufsize_max) {
    /* The entry taking more than NGHTTP2_HD_MAX_BUFFER_SIZE is
       immediately evicted.  So we don't allocate memory for it. */
    return 0;
  }

  new_ent = nghttp2_mem_malloc(mem, sizeof(nghttp2_hd_entry));
  if (new_ent == NULL) {
    return NGHTTP2_ERR_NOMEM;
  }

  nghttp2_hd_entry_init(new_ent, nv);

  rv = hd_ringbuf_push_front(&context->hd_table, new_ent, mem);

  if (rv != 0) {
    nghttp2_hd_entry_free(new_ent);
    nghttp2_mem_free(mem, new_ent);

    return rv;
  }

  new_ent->seq = context->next_seq++;
  new_ent->hash = hash;

  if (map) {
    hd_map_insert(map, new_ent);
  }

  context->hd_table_bufsize += room;

  return 0;
}




/*
 * Reads |inflater->left| bytes from the range [in, last) and copies
 * them into the |buffer|.
 *
 * This function returns the number of bytes read if it succeeds, or
 * one of the following negative error codes:
 *
 * NGHTTP2_ERR_NOMEM
 *   Out of memory
 * NGHTTP2_ERR_HEADER_COMP
 *   Header decompression failed
 */
static ssize_t hd_inflate_read(nghttp2_hd_inflater *inflater, nghttp2_buf *buf,
                               const uint8_t *in, const uint8_t *last) {
  size_t len = nghttp2_min((size_t)(last - in), inflater->left);

  buf->last = nghttp2_cpymem(buf->last, in, len);

  inflater->left -= len;
  return (ssize_t)len;
}

ssize_t nghttp2_hd_inflate_hd2(nghttp2_hd_inflater *inflater,
                               nghttp2_nv *nv_out, int *inflate_flags,
                               const uint8_t *in, size_t inlen, int in_final) {
  ssize_t rv;
  nghttp2_hd_nv hd_nv;

  rv = nghttp2_hd_inflate_hd_nv(inflater, &hd_nv, inflate_flags, in, inlen,
                                in_final);

  if (rv < 0) {
    return rv;
  }

  if (*inflate_flags & NGHTTP2_HD_INFLATE_EMIT) {
    nv_out->name = hd_nv.name->base;
    nv_out->namelen = hd_nv.name->len;

    nv_out->value = hd_nv.value->base;
    nv_out->valuelen = hd_nv.value->len;

    nv_out->flags = hd_nv.flags;
  }

  return rv;
}

ssize_t nghttp2_hd_inflate_hd(nghttp2_hd_inflater *inflater, nghttp2_nv *nv_out,
                              int *inflate_flags, uint8_t *in, size_t inlen,
                              int in_final) {
  return nghttp2_hd_inflate_hd2(inflater, nv_out, inflate_flags, in, inlen,
                                in_final);
}

static size_t get_max_index(nghttp2_hd_context *context) {
  return context->hd_table.len + NGHTTP2_STATIC_TABLE_LENGTH;
}

/*
 * Frees |rcbuf| itself, regardless of its reference cout.
 */
void nghttp2_rcbuf_del(nghttp2_rcbuf *rcbuf) {
  nghttp2_mem_free2(rcbuf->free, rcbuf, rcbuf->mem_user_data);
}

void nghttp2_rcbuf_decref(nghttp2_rcbuf *rcbuf) {
  if (rcbuf == NULL || rcbuf->ref == -1) {
    return;
  }

  assert(rcbuf->ref > 0);

  if (--rcbuf->ref == 0) {
    nghttp2_rcbuf_del(rcbuf);
  }
}


static void hd_inflate_keep_free(nghttp2_hd_inflater *inflater) {
  nghttp2_rcbuf_decref(inflater->nv_value_keep);
  nghttp2_rcbuf_decref(inflater->nv_name_keep);

  inflater->nv_value_keep = NULL;
  inflater->nv_name_keep = NULL;
}


int nghttp2_hd_inflate_end_headers(nghttp2_hd_inflater *inflater) {
  hd_inflate_keep_free(inflater);
  inflater->state = NGHTTP2_HD_STATE_INFLATE_START;
  return 0;
}

void nghttp2_hd_huff_decode_context_init(nghttp2_hd_huff_decode_context *ctx) {
  ctx->state = 0;
  ctx->accept = 1;
}



#define nghttp2_buf_len(BUF) ((size_t)((BUF)->last - (BUF)->pos))
#define nghttp2_buf_avail(BUF) ((size_t)((BUF)->end - (BUF)->last))
#define nghttp2_buf_mark_avail(BUF) ((size_t)((BUF)->mark - (BUF)->last))
#define nghttp2_buf_cap(BUF) ((size_t)((BUF)->end - (BUF)->begin))

#define nghttp2_buf_pos_offset(BUF) ((size_t)((BUF)->pos - (BUF)->begin))
#define nghttp2_buf_last_offset(BUF) ((size_t)((BUF)->last - (BUF)->begin))


/*
 * Reads |inflater->left| bytes from the range [in, last) and performs
 * huffman decoding against them and pushes the result into the
 * |buffer|.
 *
 * This function returns the number of bytes read if it succeeds, or
 * one of the following negative error codes:
 *
 * NGHTTP2_ERR_NOMEM
 *   Out of memory
 * NGHTTP2_ERR_HEADER_COMP
 *   Huffman decoding failed
 */
static ssize_t hd_inflate_read_huff(nghttp2_hd_inflater *inflater,
                                    nghttp2_buf *buf, const uint8_t *in,
                                    const uint8_t *last) {
  ssize_t readlen;
  int fin = 0;
  if ((size_t)(last - in) >= inflater->left) {
    last = in + inflater->left;
    fin = 1;
  }
  readlen = nghttp2_hd_huff_decode(&inflater->huff_decode_ctx, buf, in,
                                   (size_t)(last - in), fin);

  if (readlen < 0) {
    DEBUGF("inflatehd: huffman decoding failed\n");
    return readlen;
  }
  inflater->left -= (size_t)readlen;
  return readlen;
}


static void hd_inflate_set_huffman_encoded(nghttp2_hd_inflater *inflater,
                                           const uint8_t *in) {
  inflater->huffman_encoded = (*in & (1 << 7)) != 0;
}

static nghttp2_hd_entry *hd_ringbuf_get(nghttp2_hd_ringbuf *ringbuf,
                                        size_t idx) {
  assert(idx < ringbuf->len);
  return ringbuf->buffer[(ringbuf->first + idx) & ringbuf->mask];
}

nghttp2_hd_nv nghttp2_hd_table_get(nghttp2_hd_context *context, size_t idx) {
  assert(INDEX_RANGE_VALID(context, idx));
  if (idx >= NGHTTP2_STATIC_TABLE_LENGTH) {
    return hd_ringbuf_get(&context->hd_table, idx - NGHTTP2_STATIC_TABLE_LENGTH)
        ->nv;
  } else {
    nghttp2_hd_static_entry *ent = &static_table[idx];
    nghttp2_hd_nv nv = {&ent->name, &ent->value, ent->token,
                        NGHTTP2_NV_FLAG_NONE};
    return nv;
  }
}

/*
 * Finalize literal header representation - indexed name-
 * reception. If header is emitted, |*nv_out| is filled with that
 * value and 0 is returned.
 *
 * This function returns 0 if it succeeds, or one of the following
 * negative error codes:
 *
 * NGHTTP2_ERR_NOMEM
 *   Out of memory
 */
static int hd_inflate_commit_indname(nghttp2_hd_inflater *inflater,
                                     nghttp2_hd_nv *nv_out) {
  nghttp2_hd_nv nv;
  int rv;

  nv = nghttp2_hd_table_get(&inflater->ctx, inflater->index);

  if (inflater->no_index) {
    nv.flags = NGHTTP2_NV_FLAG_NO_INDEX;
  } else {
    nv.flags = NGHTTP2_NV_FLAG_NONE;
  }

  nghttp2_rcbuf_incref(nv.name);

  nv.value = inflater->valuercbuf;

  if (inflater->index_required) {
    rv = add_hd_table_incremental(&inflater->ctx, &nv, NULL, 0);
    if (rv != 0) {
      nghttp2_rcbuf_decref(nv.name);
      return NGHTTP2_ERR_NOMEM;
    }
  }

  emit_header(nv_out, &nv);

  inflater->nv_name_keep = nv.name;
  inflater->nv_value_keep = nv.value;

  inflater->valuercbuf = NULL;

  return 0;
}



/*
 * Finalize literal header representation - new name- reception. If
 * header is emitted, |*nv_out| is filled with that value and 0 is
 * returned.
 *
 * This function returns 0 if it succeeds, or one of the following
 * negative error codes:
 *
 * NGHTTP2_ERR_NOMEM
 *   Out of memory
 */
static int hd_inflate_commit_newname(nghttp2_hd_inflater *inflater,
                                     nghttp2_hd_nv *nv_out) {
  nghttp2_hd_nv nv;
  int rv;

  if (inflater->no_index) {
    nv.flags = NGHTTP2_NV_FLAG_NO_INDEX;
  } else {
    nv.flags = NGHTTP2_NV_FLAG_NONE;
  }

  nv.name = inflater->namercbuf;
  nv.value = inflater->valuercbuf;
  nv.token = lookup_token(inflater->namercbuf->base, inflater->namercbuf->len);

  if (inflater->index_required) {
    rv = add_hd_table_incremental(&inflater->ctx, &nv, NULL, 0);

    if (rv != 0) {
      return rv;
    }
  }

  emit_header(nv_out, &nv);

  inflater->nv_name_keep = nv.name;
  inflater->nv_value_keep = nv.value;

  inflater->namercbuf = NULL;
  inflater->valuercbuf = NULL;

  return 0;
}

ssize_t nghttp2_hd_inflate_hd_nv(nghttp2_hd_inflater *inflater,
                                 nghttp2_hd_nv *nv_out, int *inflate_flags,
                                 const uint8_t *in, size_t inlen,
                                 int in_final) {
  ssize_t rv = 0;
  const uint8_t *first = in;
  const uint8_t *last = in + inlen;
  int rfin = 0;
  int busy = 0;
  nghttp2_mem *mem;

  mem = inflater->ctx.mem;

  if (inflater->ctx.bad) {
    return NGHTTP2_ERR_HEADER_COMP;
  }

  DEBUGF("inflatehd: start state=%d\n", inflater->state);
  hd_inflate_keep_free(inflater);
  *inflate_flags = NGHTTP2_HD_INFLATE_NONE;
  for (; in != last || busy;) {
    busy = 0;
    switch (inflater->state) {
    case NGHTTP2_HD_STATE_EXPECT_TABLE_SIZE:
      if ((*in & 0xe0u) != 0x20u) {
        DEBUGF("inflatehd: header table size change was expected, but saw "
               "0x%02x as first byte",
               *in);
        rv = NGHTTP2_ERR_HEADER_COMP;
        goto fail;
      }
    /* fall through */
    case NGHTTP2_HD_STATE_INFLATE_START:
    case NGHTTP2_HD_STATE_OPCODE:
      if ((*in & 0xe0u) == 0x20u) {
        DEBUGF("inflatehd: header table size change\n");
        if (inflater->state == NGHTTP2_HD_STATE_OPCODE) {
          DEBUGF("inflatehd: header table size change must appear at the head "
                 "of header block\n");
          rv = NGHTTP2_ERR_HEADER_COMP;
          goto fail;
        }
        inflater->opcode = NGHTTP2_HD_OPCODE_INDEXED;
        inflater->state = NGHTTP2_HD_STATE_READ_TABLE_SIZE;
      } else if (*in & 0x80u) {
        DEBUGF("inflatehd: indexed repr\n");
        inflater->opcode = NGHTTP2_HD_OPCODE_INDEXED;
        inflater->state = NGHTTP2_HD_STATE_READ_INDEX;
      } else {
        if (*in == 0x40u || *in == 0 || *in == 0x10u) {
          DEBUGF("inflatehd: literal header repr - new name\n");
          inflater->opcode = NGHTTP2_HD_OPCODE_NEWNAME;
          inflater->state = NGHTTP2_HD_STATE_NEWNAME_CHECK_NAMELEN;
        } else {
          DEBUGF("inflatehd: literal header repr - indexed name\n");
          inflater->opcode = NGHTTP2_HD_OPCODE_INDNAME;
          inflater->state = NGHTTP2_HD_STATE_READ_INDEX;
        }
        inflater->index_required = (*in & 0x40) != 0;
        inflater->no_index = (*in & 0xf0u) == 0x10u;
        DEBUGF("inflatehd: indexing required=%d, no_index=%d\n",
               inflater->index_required, inflater->no_index);
        if (inflater->opcode == NGHTTP2_HD_OPCODE_NEWNAME) {
          ++in;
        }
      }
      inflater->left = 0;
      inflater->shift = 0;
      break;
    case NGHTTP2_HD_STATE_READ_TABLE_SIZE:
      rfin = 0;
      rv = hd_inflate_read_len(
          inflater, &rfin, in, last, 5,
          nghttp2_min(inflater->min_hd_table_bufsize_max,
                      inflater->settings_hd_table_bufsize_max));
      if (rv < 0) {
        goto fail;
      }
      in += rv;
      if (!rfin) {
        goto almost_ok;
      }
      DEBUGF("inflatehd: table_size=%zu\n", inflater->left);
      inflater->min_hd_table_bufsize_max = UINT32_MAX;
      inflater->ctx.hd_table_bufsize_max = inflater->left;
      hd_context_shrink_table_size(&inflater->ctx, NULL);
      inflater->state = NGHTTP2_HD_STATE_INFLATE_START;
      break;
    case NGHTTP2_HD_STATE_READ_INDEX: {
      size_t prefixlen;

      if (inflater->opcode == NGHTTP2_HD_OPCODE_INDEXED) {
        prefixlen = 7;
      } else if (inflater->index_required) {
        prefixlen = 6;
      } else {
        prefixlen = 4;
      }

      rfin = 0;
      rv = hd_inflate_read_len(inflater, &rfin, in, last, prefixlen,
                               get_max_index(&inflater->ctx));
      if (rv < 0) {
        goto fail;
      }

      in += rv;

      if (!rfin) {
        goto almost_ok;
      }

      if (inflater->left == 0) {
        rv = NGHTTP2_ERR_HEADER_COMP;
        goto fail;
      }

      DEBUGF("inflatehd: index=%zu\n", inflater->left);
      if (inflater->opcode == NGHTTP2_HD_OPCODE_INDEXED) {
        inflater->index = inflater->left;
        --inflater->index;

        hd_inflate_commit_indexed(inflater, nv_out);

        inflater->state = NGHTTP2_HD_STATE_OPCODE;
        *inflate_flags |= NGHTTP2_HD_INFLATE_EMIT;
        return (ssize_t)(in - first);
      } else {
        inflater->index = inflater->left;
        --inflater->index;

        inflater->state = NGHTTP2_HD_STATE_CHECK_VALUELEN;
      }
      break;
    }
    case NGHTTP2_HD_STATE_NEWNAME_CHECK_NAMELEN:
      hd_inflate_set_huffman_encoded(inflater, in);
      inflater->state = NGHTTP2_HD_STATE_NEWNAME_READ_NAMELEN;
      inflater->left = 0;
      inflater->shift = 0;
      DEBUGF("inflatehd: huffman encoded=%d\n", inflater->huffman_encoded != 0);
    /* Fall through */
    case NGHTTP2_HD_STATE_NEWNAME_READ_NAMELEN:
      rfin = 0;
      rv = hd_inflate_read_len(inflater, &rfin, in, last, 7, NGHTTP2_HD_MAX_NV);
      if (rv < 0) {
        goto fail;
      }
      in += rv;
      if (!rfin) {
        DEBUGF("inflatehd: integer not fully decoded. current=%zu\n",
               inflater->left);

        goto almost_ok;
      }

      if (inflater->huffman_encoded) {
        nghttp2_hd_huff_decode_context_init(&inflater->huff_decode_ctx);

        inflater->state = NGHTTP2_HD_STATE_NEWNAME_READ_NAMEHUFF;

        rv = nghttp2_rcbuf_new(&inflater->namercbuf, inflater->left * 2 + 1,
                               mem);
      } else {
        inflater->state = NGHTTP2_HD_STATE_NEWNAME_READ_NAME;
        rv = nghttp2_rcbuf_new(&inflater->namercbuf, inflater->left + 1, mem);
      }

      if (rv != 0) {
        goto fail;
      }

      nghttp2_buf_wrap_init(&inflater->namebuf, inflater->namercbuf->base,
                            inflater->namercbuf->len);

      break;
    case NGHTTP2_HD_STATE_NEWNAME_READ_NAMEHUFF:
      rv = hd_inflate_read_huff(inflater, &inflater->namebuf, in, last);
      if (rv < 0) {
        goto fail;
      }

      in += rv;

      DEBUGF("inflatehd: %zd bytes read\n", rv);

      if (inflater->left) {
        DEBUGF("inflatehd: still %zu bytes to go\n", inflater->left);

        goto almost_ok;
      }

      *inflater->namebuf.last = '\0';
      inflater->namercbuf->len = nghttp2_buf_len(&inflater->namebuf);

      inflater->state = NGHTTP2_HD_STATE_CHECK_VALUELEN;

      break;
    case NGHTTP2_HD_STATE_NEWNAME_READ_NAME:
      rv = hd_inflate_read(inflater, &inflater->namebuf, in, last);
      if (rv < 0) {
        goto fail;
      }

      in += rv;

      DEBUGF("inflatehd: %zd bytes read\n", rv);
      if (inflater->left) {
        DEBUGF("inflatehd: still %zu bytes to go\n", inflater->left);

        goto almost_ok;
      }

      *inflater->namebuf.last = '\0';
      inflater->namercbuf->len = nghttp2_buf_len(&inflater->namebuf);

      inflater->state = NGHTTP2_HD_STATE_CHECK_VALUELEN;

      break;
    case NGHTTP2_HD_STATE_CHECK_VALUELEN:
      hd_inflate_set_huffman_encoded(inflater, in);
      inflater->state = NGHTTP2_HD_STATE_READ_VALUELEN;
      inflater->left = 0;
      inflater->shift = 0;
      DEBUGF("inflatehd: huffman encoded=%d\n", inflater->huffman_encoded != 0);
    /* Fall through */
    case NGHTTP2_HD_STATE_READ_VALUELEN:
      rfin = 0;
      rv = hd_inflate_read_len(inflater, &rfin, in, last, 7, NGHTTP2_HD_MAX_NV);
      if (rv < 0) {
        goto fail;
      }

      in += rv;

      if (!rfin) {
        goto almost_ok;
      }

      DEBUGF("inflatehd: valuelen=%zu\n", inflater->left);

      if (inflater->huffman_encoded) {
        nghttp2_hd_huff_decode_context_init(&inflater->huff_decode_ctx);

        inflater->state = NGHTTP2_HD_STATE_READ_VALUEHUFF;

        rv = nghttp2_rcbuf_new(&inflater->valuercbuf, inflater->left * 2 + 1,
                               mem);
      } else {
        inflater->state = NGHTTP2_HD_STATE_READ_VALUE;

        rv = nghttp2_rcbuf_new(&inflater->valuercbuf, inflater->left + 1, mem);
      }

      if (rv != 0) {
        goto fail;
      }

      nghttp2_buf_wrap_init(&inflater->valuebuf, inflater->valuercbuf->base,
                            inflater->valuercbuf->len);

      busy = 1;

      break;
    case NGHTTP2_HD_STATE_READ_VALUEHUFF:
      rv = hd_inflate_read_huff(inflater, &inflater->valuebuf, in, last);
      if (rv < 0) {
        goto fail;
      }

      in += rv;

      DEBUGF("inflatehd: %zd bytes read\n", rv);

      if (inflater->left) {
        DEBUGF("inflatehd: still %zu bytes to go\n", inflater->left);

        goto almost_ok;
      }

      *inflater->valuebuf.last = '\0';
      inflater->valuercbuf->len = nghttp2_buf_len(&inflater->valuebuf);

      if (inflater->opcode == NGHTTP2_HD_OPCODE_NEWNAME) {
        rv = hd_inflate_commit_newname(inflater, nv_out);
      } else {
        rv = hd_inflate_commit_indname(inflater, nv_out);
      }

      if (rv != 0) {
        goto fail;
      }

      inflater->state = NGHTTP2_HD_STATE_OPCODE;
      *inflate_flags |= NGHTTP2_HD_INFLATE_EMIT;

      return (ssize_t)(in - first);
    case NGHTTP2_HD_STATE_READ_VALUE:
      rv = hd_inflate_read(inflater, &inflater->valuebuf, in, last);
      if (rv < 0) {
        DEBUGF("inflatehd: value read failure %zd: %s\n", rv,
               nghttp2_strerror((int)rv));
        goto fail;
      }

      in += rv;

      DEBUGF("inflatehd: %zd bytes read\n", rv);

      if (inflater->left) {
        DEBUGF("inflatehd: still %zu bytes to go\n", inflater->left);
        goto almost_ok;
      }

      *inflater->valuebuf.last = '\0';
      inflater->valuercbuf->len = nghttp2_buf_len(&inflater->valuebuf);

      if (inflater->opcode == NGHTTP2_HD_OPCODE_NEWNAME) {
        rv = hd_inflate_commit_newname(inflater, nv_out);
      } else {
        rv = hd_inflate_commit_indname(inflater, nv_out);
      }

      if (rv != 0) {
        goto fail;
      }

      inflater->state = NGHTTP2_HD_STATE_OPCODE;
      *inflate_flags |= NGHTTP2_HD_INFLATE_EMIT;

      return (ssize_t)(in - first);
    }
  }

  assert(in == last);

  DEBUGF("inflatehd: all input bytes were processed\n");

  if (in_final) {
    DEBUGF("inflatehd: in_final set\n");

    if (inflater->state != NGHTTP2_HD_STATE_OPCODE &&
        inflater->state != NGHTTP2_HD_STATE_INFLATE_START) {
      DEBUGF("inflatehd: unacceptable state=%d\n", inflater->state);
      rv = NGHTTP2_ERR_HEADER_COMP;

      goto fail;
    }
    *inflate_flags |= NGHTTP2_HD_INFLATE_FINAL;
  }
  return (ssize_t)(in - first);

almost_ok:
  if (in_final) {
    DEBUGF("inflatehd: input ended prematurely\n");

    rv = NGHTTP2_ERR_HEADER_COMP;

    goto fail;
  }
  return (ssize_t)(in - first);

fail:
  DEBUGF("inflatehd: error return %zd\n", rv);

  inflater->ctx.bad = 1;
  return rv;
}

const char *nghttp2_strerror(int error_code) {
  switch (error_code) {
  case 0:
    return "Success";
  case NGHTTP2_ERR_INVALID_ARGUMENT:
    return "Invalid argument";
  case NGHTTP2_ERR_BUFFER_ERROR:
    return "Out of buffer space";
  case NGHTTP2_ERR_UNSUPPORTED_VERSION:
    return "Unsupported SPDY version";
  case NGHTTP2_ERR_WOULDBLOCK:
    return "Operation would block";
  case NGHTTP2_ERR_PROTO:
    return "Protocol error";
  case NGHTTP2_ERR_INVALID_FRAME:
    return "Invalid frame octets";
  case NGHTTP2_ERR_EOF:
    return "EOF";
  case NGHTTP2_ERR_DEFERRED:
    return "Data transfer deferred";
  case NGHTTP2_ERR_STREAM_ID_NOT_AVAILABLE:
    return "No more Stream ID available";
  case NGHTTP2_ERR_STREAM_CLOSED:
    return "Stream was already closed or invalid";
  case NGHTTP2_ERR_STREAM_CLOSING:
    return "Stream is closing";
  case NGHTTP2_ERR_STREAM_SHUT_WR:
    return "The transmission is not allowed for this stream";
  case NGHTTP2_ERR_INVALID_STREAM_ID:
    return "Stream ID is invalid";
  case NGHTTP2_ERR_INVALID_STREAM_STATE:
    return "Invalid stream state";
  case NGHTTP2_ERR_DEFERRED_DATA_EXIST:
    return "Another DATA frame has already been deferred";
  case NGHTTP2_ERR_START_STREAM_NOT_ALLOWED:
    return "request HEADERS is not allowed";
  case NGHTTP2_ERR_GOAWAY_ALREADY_SENT:
    return "GOAWAY has already been sent";
  case NGHTTP2_ERR_INVALID_HEADER_BLOCK:
    return "Invalid header block";
  case NGHTTP2_ERR_INVALID_STATE:
    return "Invalid state";
  case NGHTTP2_ERR_TEMPORAL_CALLBACK_FAILURE:
    return "The user callback function failed due to the temporal error";
  case NGHTTP2_ERR_FRAME_SIZE_ERROR:
    return "The length of the frame is invalid";
  case NGHTTP2_ERR_HEADER_COMP:
    return "Header compression/decompression error";
  case NGHTTP2_ERR_FLOW_CONTROL:
    return "Flow control error";
  case NGHTTP2_ERR_INSUFF_BUFSIZE:
    return "Insufficient buffer size given to function";
  case NGHTTP2_ERR_PAUSE:
    return "Callback was paused by the application";
  case NGHTTP2_ERR_TOO_MANY_INFLIGHT_SETTINGS:
    return "Too many inflight SETTINGS";
  case NGHTTP2_ERR_PUSH_DISABLED:
    return "Server push is disabled by peer";
  case NGHTTP2_ERR_DATA_EXIST:
    return "DATA or HEADERS frame has already been submitted for the stream";
  case NGHTTP2_ERR_SESSION_CLOSING:
    return "The current session is closing";
  case NGHTTP2_ERR_HTTP_HEADER:
    return "Invalid HTTP header field was received";
  case NGHTTP2_ERR_HTTP_MESSAGING:
    return "Violation in HTTP messaging rule";
  case NGHTTP2_ERR_REFUSED_STREAM:
    return "Stream was refused";
  case NGHTTP2_ERR_INTERNAL:
    return "Internal error";
  case NGHTTP2_ERR_CANCEL:
    return "Cancel";
  case NGHTTP2_ERR_SETTINGS_EXPECTED:
    return "When a local endpoint expects to receive SETTINGS frame, it "
           "receives an other type of frame";
  case NGHTTP2_ERR_NOMEM:
    return "Out of memory";
  case NGHTTP2_ERR_CALLBACK_FAILURE:
    return "The user callback function failed";
  case NGHTTP2_ERR_BAD_CLIENT_MAGIC:
    return "Received bad client magic byte string";
  case NGHTTP2_ERR_FLOODED:
    return "Flooding was detected in this HTTP/2 session, and it must be "
           "closed";
  default:
    return "Unknown error code";
  }
}


/*
 * Finalize indexed header representation reception.  The referenced
 * header is always emitted, and |*nv_out| is filled with that value.
 */
static void hd_inflate_commit_indexed(nghttp2_hd_inflater *inflater,
                                      nghttp2_hd_nv *nv_out) {
  nghttp2_hd_nv nv = nghttp2_hd_table_get(&inflater->ctx, inflater->index);

  emit_header(nv_out, &nv);
}

/*
 * Decodes |prefix| prefixed integer stored from |in|.  The |last|
 * represents the 1 beyond the last of the valid contiguous memory
 * region from |in|.  The decoded integer must be less than or equal
 * to UINT32_MAX.
 *
 * If the |initial| is nonzero, it is used as a initial value, this
 * function assumes the |in| starts with intermediate data.
 *
 * An entire integer is decoded successfully, decoded, the |*fin| is
 * set to nonzero.
 *
 * This function stores the decoded integer in |*res| if it succeed,
 * including partial decoding (in this case, number of shift to make
 * in the next call will be stored in |*shift_ptr|) and returns number
 * of bytes processed, or returns -1, indicating decoding error.
 */
static ssize_t decode_length(uint32_t *res, size_t *shift_ptr, int *fin,
                             uint32_t initial, size_t shift, const uint8_t *in,
                             const uint8_t *last, size_t prefix) {
  uint32_t k = (uint8_t)((1 << prefix) - 1);
  uint32_t n = initial;
  const uint8_t *start = in;

  *shift_ptr = 0;
  *fin = 0;

  if (n == 0) {
    if ((*in & k) != k) {
      *res = (*in) & k;
      *fin = 1;
      return 1;
    }

    n = k;

    if (++in == last) {
      *res = n;
      return (ssize_t)(in - start);
    }
  }

  for (; in != last; ++in, shift += 7) {
    uint32_t add = *in & 0x7f;

    if (shift >= 32) {
      DEBUGF("inflate: shift exponent overflow\n");
      return -1;
    }

    if ((UINT32_MAX >> shift) < add) {
      DEBUGF("inflate: integer overflow on shift\n");
      return -1;
    }

    add <<= shift;

    if (UINT32_MAX - add < n) {
      DEBUGF("inflate: integer overflow on addition\n");
      return -1;
    }

    n += add;

    if ((*in & (1 << 7)) == 0) {
      break;
    }
  }

  *shift_ptr = shift;

  if (in == last) {
    *res = n;
    return (ssize_t)(in - start);
  }

  *res = n;
  *fin = 1;
  return (ssize_t)(in + 1 - start);
}

void nghttp2_rcbuf_incref(nghttp2_rcbuf *rcbuf) {
  if (rcbuf->ref == -1) {
    return;
  }

  ++rcbuf->ref;
}

void nghttp2_hd_entry_init(nghttp2_hd_entry *ent, nghttp2_hd_nv *nv) {
  ent->nv = *nv;
  ent->cnv.name = nv->name->base;
  ent->cnv.namelen = nv->name->len;
  ent->cnv.value = nv->value->base;
  ent->cnv.valuelen = nv->value->len;
  ent->cnv.flags = nv->flags;
  ent->next = NULL;
  ent->hash = 0;

  nghttp2_rcbuf_incref(ent->nv.name);
  nghttp2_rcbuf_incref(ent->nv.value);
}

static int hd_ringbuf_push_front(nghttp2_hd_ringbuf *ringbuf,
                                 nghttp2_hd_entry *ent, nghttp2_mem *mem) {
  int rv;

  rv = hd_ringbuf_reserve(ringbuf, ringbuf->len + 1, mem);

  if (rv != 0) {
    return rv;
  }

  ringbuf->buffer[--ringbuf->first & ringbuf->mask] = ent;
  ++ringbuf->len;

  return 0;
}

static void hd_map_remove(nghttp2_hd_map *map, nghttp2_hd_entry *ent) {
  nghttp2_hd_entry **dst;

  dst = &map->table[ent->hash & (HD_MAP_SIZE - 1)];

  for (; *dst; dst = &(*dst)->next) {
    if (*dst != ent) {
      continue;
    }

    *dst = ent->next;
    ent->next = NULL;
    return;
  }
}

static int hd_ringbuf_reserve(nghttp2_hd_ringbuf *ringbuf, size_t bufsize,
                              nghttp2_mem *mem) {
  size_t i;
  size_t size;
  nghttp2_hd_entry **buffer;

  if (ringbuf->mask + 1 >= bufsize) {
    return 0;
  }
  for (size = 1; size < bufsize; size <<= 1)
    ;
  buffer = nghttp2_mem_malloc(mem, sizeof(nghttp2_hd_entry *) * size);
  if (buffer == NULL) {
    return NGHTTP2_ERR_NOMEM;
  }
  for (i = 0; i < ringbuf->len; ++i) {
    buffer[i] = hd_ringbuf_get(ringbuf, i);
  }
  nghttp2_mem_free(mem, ringbuf->buffer);
  ringbuf->buffer = buffer;
  ringbuf->mask = size - 1;
  ringbuf->first = 0;
  return 0;
}


/*
 * This function was generated by genlibtokenlookup.py.  Inspired by
 * h2o header lookup.  https://github.com/h2o/h2o
 */
int32_t lookup_token(const uint8_t *name, size_t namelen) {
  switch (namelen) {
  case 2:
    switch (name[1]) {
    case 'e':
      if (memeq("t", name, 1)) {
        return NGHTTP2_TOKEN_TE;
      }
      break;
    }
    break;
  case 3:
    switch (name[2]) {
    case 'a':
      if (memeq("vi", name, 2)) {
        return NGHTTP2_TOKEN_VIA;
      }
      break;
    case 'e':
      if (memeq("ag", name, 2)) {
        return NGHTTP2_TOKEN_AGE;
      }
      break;
    }
    break;
  case 4:
    switch (name[3]) {
    case 'e':
      if (memeq("dat", name, 3)) {
        return NGHTTP2_TOKEN_DATE;
      }
      break;
    case 'g':
      if (memeq("eta", name, 3)) {
        return NGHTTP2_TOKEN_ETAG;
      }
      break;
    case 'k':
      if (memeq("lin", name, 3)) {
        return NGHTTP2_TOKEN_LINK;
      }
      break;
    case 'm':
      if (memeq("fro", name, 3)) {
        return NGHTTP2_TOKEN_FROM;
      }
      break;
    case 't':
      if (memeq("hos", name, 3)) {
        return NGHTTP2_TOKEN_HOST;
      }
      break;
    case 'y':
      if (memeq("var", name, 3)) {
        return NGHTTP2_TOKEN_VARY;
      }
      break;
    }
    break;
  case 5:
    switch (name[4]) {
    case 'e':
      if (memeq("rang", name, 4)) {
        return NGHTTP2_TOKEN_RANGE;
      }
      break;
    case 'h':
      if (memeq(":pat", name, 4)) {
        return NGHTTP2_TOKEN__PATH;
      }
      break;
    case 'w':
      if (memeq("allo", name, 4)) {
        return NGHTTP2_TOKEN_ALLOW;
      }
      break;
    }
    break;
  case 6:
    switch (name[5]) {
    case 'e':
      if (memeq("cooki", name, 5)) {
        return NGHTTP2_TOKEN_COOKIE;
      }
      break;
    case 'r':
      if (memeq("serve", name, 5)) {
        return NGHTTP2_TOKEN_SERVER;
      }
      break;
    case 't':
      if (memeq("accep", name, 5)) {
        return NGHTTP2_TOKEN_ACCEPT;
      }
      if (memeq("expec", name, 5)) {
        return NGHTTP2_TOKEN_EXPECT;
      }
      break;
    }
    break;
  case 7:
    switch (name[6]) {
    case 'd':
      if (memeq(":metho", name, 6)) {
        return NGHTTP2_TOKEN__METHOD;
      }
      break;
    case 'e':
      if (memeq(":schem", name, 6)) {
        return NGHTTP2_TOKEN__SCHEME;
      }
      if (memeq("upgrad", name, 6)) {
        return NGHTTP2_TOKEN_UPGRADE;
      }
      break;
    case 'h':
      if (memeq("refres", name, 6)) {
        return NGHTTP2_TOKEN_REFRESH;
      }
      break;
    case 'r':
      if (memeq("refere", name, 6)) {
        return NGHTTP2_TOKEN_REFERER;
      }
      break;
    case 's':
      if (memeq(":statu", name, 6)) {
        return NGHTTP2_TOKEN__STATUS;
      }
      if (memeq("expire", name, 6)) {
        return NGHTTP2_TOKEN_EXPIRES;
      }
      break;
    }
    break;
  case 8:
    switch (name[7]) {
    case 'e':
      if (memeq("if-rang", name, 7)) {
        return NGHTTP2_TOKEN_IF_RANGE;
      }
      break;
    case 'h':
      if (memeq("if-matc", name, 7)) {
        return NGHTTP2_TOKEN_IF_MATCH;
      }
      break;
    case 'n':
      if (memeq("locatio", name, 7)) {
        return NGHTTP2_TOKEN_LOCATION;
      }
      break;
    }
    break;
  case 10:
    switch (name[9]) {
    case 'e':
      if (memeq("keep-aliv", name, 9)) {
        return NGHTTP2_TOKEN_KEEP_ALIVE;
      }
      if (memeq("set-cooki", name, 9)) {
        return NGHTTP2_TOKEN_SET_COOKIE;
      }
      break;
    case 'n':
      if (memeq("connectio", name, 9)) {
        return NGHTTP2_TOKEN_CONNECTION;
      }
      break;
    case 't':
      if (memeq("user-agen", name, 9)) {
        return NGHTTP2_TOKEN_USER_AGENT;
      }
      break;
    case 'y':
      if (memeq(":authorit", name, 9)) {
        return NGHTTP2_TOKEN__AUTHORITY;
      }
      break;
    }
    break;
  case 11:
    switch (name[10]) {
    case 'r':
      if (memeq("retry-afte", name, 10)) {
        return NGHTTP2_TOKEN_RETRY_AFTER;
      }
      break;
    }
    break;
  case 12:
    switch (name[11]) {
    case 'e':
      if (memeq("content-typ", name, 11)) {
        return NGHTTP2_TOKEN_CONTENT_TYPE;
      }
      break;
    case 's':
      if (memeq("max-forward", name, 11)) {
        return NGHTTP2_TOKEN_MAX_FORWARDS;
      }
      break;
    }
    break;
  case 13:
    switch (name[12]) {
    case 'd':
      if (memeq("last-modifie", name, 12)) {
        return NGHTTP2_TOKEN_LAST_MODIFIED;
      }
      break;
    case 'e':
      if (memeq("content-rang", name, 12)) {
        return NGHTTP2_TOKEN_CONTENT_RANGE;
      }
      break;
    case 'h':
      if (memeq("if-none-matc", name, 12)) {
        return NGHTTP2_TOKEN_IF_NONE_MATCH;
      }
      break;
    case 'l':
      if (memeq("cache-contro", name, 12)) {
        return NGHTTP2_TOKEN_CACHE_CONTROL;
      }
      break;
    case 'n':
      if (memeq("authorizatio", name, 12)) {
        return NGHTTP2_TOKEN_AUTHORIZATION;
      }
      break;
    case 's':
      if (memeq("accept-range", name, 12)) {
        return NGHTTP2_TOKEN_ACCEPT_RANGES;
      }
      break;
    }
    break;
  case 14:
    switch (name[13]) {
    case 'h':
      if (memeq("content-lengt", name, 13)) {
        return NGHTTP2_TOKEN_CONTENT_LENGTH;
      }
      break;
    case 't':
      if (memeq("accept-charse", name, 13)) {
        return NGHTTP2_TOKEN_ACCEPT_CHARSET;
      }
      break;
    }
    break;
  case 15:
    switch (name[14]) {
    case 'e':
      if (memeq("accept-languag", name, 14)) {
        return NGHTTP2_TOKEN_ACCEPT_LANGUAGE;
      }
      break;
    case 'g':
      if (memeq("accept-encodin", name, 14)) {
        return NGHTTP2_TOKEN_ACCEPT_ENCODING;
      }
      break;
    }
    break;
  case 16:
    switch (name[15]) {
    case 'e':
      if (memeq("content-languag", name, 15)) {
        return NGHTTP2_TOKEN_CONTENT_LANGUAGE;
      }
      if (memeq("www-authenticat", name, 15)) {
        return NGHTTP2_TOKEN_WWW_AUTHENTICATE;
      }
      break;
    case 'g':
      if (memeq("content-encodin", name, 15)) {
        return NGHTTP2_TOKEN_CONTENT_ENCODING;
      }
      break;
    case 'n':
      if (memeq("content-locatio", name, 15)) {
        return NGHTTP2_TOKEN_CONTENT_LOCATION;
      }
      if (memeq("proxy-connectio", name, 15)) {
        return NGHTTP2_TOKEN_PROXY_CONNECTION;
      }
      break;
    }
    break;
  case 17:
    switch (name[16]) {
    case 'e':
      if (memeq("if-modified-sinc", name, 16)) {
        return NGHTTP2_TOKEN_IF_MODIFIED_SINCE;
      }
      break;
    case 'g':
      if (memeq("transfer-encodin", name, 16)) {
        return NGHTTP2_TOKEN_TRANSFER_ENCODING;
      }
      break;
    }
    break;
  case 18:
    switch (name[17]) {
    case 'e':
      if (memeq("proxy-authenticat", name, 17)) {
        return NGHTTP2_TOKEN_PROXY_AUTHENTICATE;
      }
      break;
    }
    break;
  case 19:
    switch (name[18]) {
    case 'e':
      if (memeq("if-unmodified-sinc", name, 18)) {
        return NGHTTP2_TOKEN_IF_UNMODIFIED_SINCE;
      }
      break;
    case 'n':
      if (memeq("content-dispositio", name, 18)) {
        return NGHTTP2_TOKEN_CONTENT_DISPOSITION;
      }
      if (memeq("proxy-authorizatio", name, 18)) {
        return NGHTTP2_TOKEN_PROXY_AUTHORIZATION;
      }
      break;
    }
    break;
  case 25:
    switch (name[24]) {
    case 'y':
      if (memeq("strict-transport-securit", name, 24)) {
        return NGHTTP2_TOKEN_STRICT_TRANSPORT_SECURITY;
      }
      break;
    }
    break;
  case 27:
    switch (name[26]) {
    case 'n':
      if (memeq("access-control-allow-origi", name, 26)) {
        return NGHTTP2_TOKEN_ACCESS_CONTROL_ALLOW_ORIGIN;
      }
      break;
    }
    break;
  }
  return -1;
}

ssize_t nghttp2_hd_huff_decode(nghttp2_hd_huff_decode_context *ctx,
                               nghttp2_buf *buf, const uint8_t *src,
                               size_t srclen, int final) {
  size_t i;

  /* We use the decoding algorithm described in
     http://graphics.ics.uci.edu/pub/Prefix.pdf */
  for (i = 0; i < srclen; ++i) {
    const nghttp2_huff_decode *t;

    t = &huff_decode_table[ctx->state][src[i] >> 4];
    if (t->flags & NGHTTP2_HUFF_FAIL) {
      return NGHTTP2_ERR_HEADER_COMP;
    }
    if (t->flags & NGHTTP2_HUFF_SYM) {
      *buf->last++ = t->sym;
    }

    t = &huff_decode_table[t->state][src[i] & 0xf];
    if (t->flags & NGHTTP2_HUFF_FAIL) {
      return NGHTTP2_ERR_HEADER_COMP;
    }
    if (t->flags & NGHTTP2_HUFF_SYM) {
      *buf->last++ = t->sym;
    }

    ctx->state = t->state;
    ctx->accept = (t->flags & NGHTTP2_HUFF_ACCEPTED) != 0;
  }
  if (final && !ctx->accept) {
    return NGHTTP2_ERR_HEADER_COMP;
  }
  return (ssize_t)i;
}

static void *default_malloc(size_t size, void *mem_user_data) {
  (void)mem_user_data;

  return malloc(size);
}

static void default_free(void *ptr, void *mem_user_data) {
  (void)mem_user_data;

  free(ptr);
}

static void *default_calloc(size_t nmemb, size_t size, void *mem_user_data) {
  (void)mem_user_data;

  return calloc(nmemb, size);
}

static void *default_realloc(void *ptr, size_t size, void *mem_user_data) {
  (void)mem_user_data;

  return realloc(ptr, size);
}

void nghttp2_buf_init(nghttp2_buf *buf) {
  buf->begin = NULL;
  buf->end = NULL;
  buf->pos = NULL;
  buf->last = NULL;
  buf->mark = NULL;
}

static int hd_ringbuf_init(nghttp2_hd_ringbuf *ringbuf, size_t bufsize,
                           nghttp2_mem *mem) {
  size_t size;
  for (size = 1; size < bufsize; size <<= 1)
    ;
  ringbuf->buffer = nghttp2_mem_malloc(mem, sizeof(nghttp2_hd_entry *) * size);
  if (ringbuf->buffer == NULL) {
    return NGHTTP2_ERR_NOMEM;
  }
  ringbuf->mask = size - 1;
  ringbuf->first = 0;
  ringbuf->len = 0;
  return 0;
}

static int hd_context_init(nghttp2_hd_context *context, nghttp2_mem *mem) {
  int rv;
  context->mem = mem;
  context->bad = 0;
  context->hd_table_bufsize_max = NGHTTP2_HD_DEFAULT_MAX_BUFFER_SIZE;
  rv = hd_ringbuf_init(
      &context->hd_table,
      context->hd_table_bufsize_max / NGHTTP2_HD_ENTRY_OVERHEAD, mem);
  if (rv != 0) {
    return rv;
  }

  context->hd_table_bufsize = 0;
  context->next_seq = 0;

  return 0;
}

static nghttp2_mem mem_default = {NULL, default_malloc, default_free,
                                  default_calloc, default_realloc};

nghttp2_mem *nghttp2_mem_default(void) { return &mem_default; }

int nghttp2_hd_inflate_init(nghttp2_hd_inflater *inflater, nghttp2_mem *mem) {
  int rv;

  rv = hd_context_init(&inflater->ctx, mem);
  if (rv != 0) {
    goto fail;
  }

  inflater->settings_hd_table_bufsize_max = NGHTTP2_HD_DEFAULT_MAX_BUFFER_SIZE;
  inflater->min_hd_table_bufsize_max = UINT32_MAX;

  inflater->nv_name_keep = NULL;
  inflater->nv_value_keep = NULL;

  inflater->opcode = NGHTTP2_HD_OPCODE_NONE;
  inflater->state = NGHTTP2_HD_STATE_INFLATE_START;

  nghttp2_buf_init(&inflater->namebuf);
  nghttp2_buf_init(&inflater->valuebuf);

  inflater->namercbuf = NULL;
  inflater->valuercbuf = NULL;

  inflater->huffman_encoded = 0;
  inflater->index = 0;
  inflater->left = 0;
  inflater->shift = 0;
  inflater->index_required = 0;
  inflater->no_index = 0;

  return 0;

fail:
  return rv;
}

int nghttp2_hd_inflate_new(nghttp2_hd_inflater **inflater_ptr) {
  return nghttp2_hd_inflate_new2(inflater_ptr, NULL);
}

int nghttp2_hd_inflate_new2(nghttp2_hd_inflater **inflater_ptr,
                            nghttp2_mem *mem) {
  int rv;
  nghttp2_hd_inflater *inflater;

  if (mem == NULL) {
    mem = nghttp2_mem_default();
  }

  inflater = nghttp2_mem_malloc(mem, sizeof(nghttp2_hd_inflater));

  if (inflater == NULL) {
    return NGHTTP2_ERR_NOMEM;
  }

  rv = nghttp2_hd_inflate_init(inflater, mem);

  if (rv != 0) {
    nghttp2_mem_free(mem, inflater);

    return rv;
  }

  *inflater_ptr = inflater;

  return 0;
}