nghttp2_hd.c

/*
 * nghttp2 - HTTP/2 C Library
 *
 * Copyright (c) 2013 Tatsuhiro Tsujikawa
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
#include "nghttp2_hd.h"

#include <string.h>
#include <assert.h>
#include <stdio.h>

#include "nghttp2_helper.h"
#include "nghttp2_int.h"
#include "nghttp2_debug.h"

/* Make scalar initialization form of nghttp2_hd_entry */
#define MAKE_STATIC_ENT(N, V, T, H)                                            \
  {                                                                            \
    {NULL, NULL, (uint8_t *)(N), nghttp2_strlen_lit((N)), -1},                 \
    {NULL, NULL, (uint8_t *)(V), nghttp2_strlen_lit((V)), -1},                 \
    {(uint8_t *)(N), (uint8_t *)(V), nghttp2_strlen_lit((N)),                  \
     nghttp2_strlen_lit((V)), 0},                                              \
    T,                                                                         \
    H,                                                                         \
  }

/* 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 const 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;
}

/*
 * This function was generated by genlibtokenlookup.py.  Inspired by
 * h2o header lookup.  https://github.com/h2o/h2o
 */
static 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;
    case 'y':
      if (memeq("priorit", name, 7)) {
        return NGHTTP2_TOKEN_PRIORITY;
      }
      break;
    }
    break;
  case 9:
    switch (name[8]) {
    case 'l':
      if (memeq(":protoco", name, 8)) {
        return NGHTTP2_TOKEN__PROTOCOL;
      }
      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;
}

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);
}

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

static int name_eq(const nghttp2_hd_nv *a, const nghttp2_nv *b) {
  return a->name->len == b->namelen &&
         memeq(a->name->base, b->name, b->namelen);
}

static int value_eq(const nghttp2_hd_nv *a, const nghttp2_nv *b) {
  return a->value->len == b->valuelen &&
         memeq(a->value->base, b->value, b->valuelen);
}

static uint32_t name_hash(const nghttp2_nv *nv) {
  /* 32 bit FNV-1a: http://isthe.com/chongo/tech/comp/fnv/ */
  uint32_t h = 2166136261u;
  size_t i;

  for (i = 0; i < nv->namelen; ++i) {
    h ^= nv->name[i];
    h += (h << 1) + (h << 4) + (h << 7) + (h << 8) + (h << 24);
  }

  return h;
}

static void hd_map_init(nghttp2_hd_map *map) {
  memset(map, 0, sizeof(nghttp2_hd_map));
}

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 nghttp2_hd_entry *hd_map_find(nghttp2_hd_map *map, int *exact_match,
                                     const nghttp2_nv *nv, int32_t token,
                                     uint32_t hash, int name_only) {
  nghttp2_hd_entry *p;
  nghttp2_hd_entry *res = NULL;

  *exact_match = 0;

  for (p = map->table[hash & (HD_MAP_SIZE - 1)]; p; p = p->next) {
    if (token != p->nv.token ||
        (token == -1 && (hash != p->hash || !name_eq(&p->nv, nv)))) {
      continue;
    }
    if (!res) {
      res = p;
      if (name_only) {
        break;
      }
    }
    if (value_eq(&p->nv, nv)) {
      res = p;
      *exact_match = 1;
      break;
    }
  }

  return res;
}

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_init(nghttp2_hd_ringbuf *ringbuf, size_t bufsize,
                           nghttp2_mem *mem) {
  size_t size;
  const size_t max_size = SIZE_MAX / sizeof(nghttp2_hd_entry *);

  if (bufsize > max_size) {
    return NGHTTP2_ERR_NOMEM;
  }

  for (size = 1; size < bufsize; size <<= 1)
    ;

  if (size > max_size) {
    return NGHTTP2_ERR_NOMEM;
  }

  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 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];
}

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;
}

static void hd_ringbuf_free(nghttp2_hd_ringbuf *ringbuf, nghttp2_mem *mem) {
  size_t i;
  if (ringbuf == NULL) {
    return;
  }
  for (i = 0; i < ringbuf->len; ++i) {
    nghttp2_hd_entry *ent = hd_ringbuf_get(ringbuf, i);

    nghttp2_hd_entry_free(ent);
    nghttp2_mem_free(mem, ent);
  }
  nghttp2_mem_free(mem, ringbuf->buffer);
}

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_ringbuf_pop_back(nghttp2_hd_ringbuf *ringbuf) {
  assert(ringbuf->len > 0);
  --ringbuf->len;
}

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 void hd_context_free(nghttp2_hd_context *context) {
  hd_ringbuf_free(&context->hd_table, context->mem);
}

int nghttp2_hd_deflate_init(nghttp2_hd_deflater *deflater, nghttp2_mem *mem) {
  return nghttp2_hd_deflate_init2(
    deflater, NGHTTP2_HD_DEFAULT_MAX_DEFLATE_BUFFER_SIZE, mem);
}

int nghttp2_hd_deflate_init2(nghttp2_hd_deflater *deflater,
                             size_t max_deflate_dynamic_table_size,
                             nghttp2_mem *mem) {
  int rv;
  rv = hd_context_init(&deflater->ctx, mem);
  if (rv != 0) {
    return rv;
  }

  hd_map_init(&deflater->map);

  if (max_deflate_dynamic_table_size < NGHTTP2_HD_DEFAULT_MAX_BUFFER_SIZE) {
    deflater->notify_table_size_change = 1;
    deflater->ctx.hd_table_bufsize_max = max_deflate_dynamic_table_size;
  } else {
    deflater->notify_table_size_change = 0;
  }

  deflater->deflate_hd_table_bufsize_max = max_deflate_dynamic_table_size;
  deflater->min_hd_table_bufsize_max = UINT32_MAX;

  return 0;
}

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;
}

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;
}

void nghttp2_hd_deflate_free(nghttp2_hd_deflater *deflater) {
  hd_context_free(&deflater->ctx);
}

void nghttp2_hd_inflate_free(nghttp2_hd_inflater *inflater) {
  hd_inflate_keep_free(inflater);

  nghttp2_rcbuf_decref(inflater->valuercbuf);
  nghttp2_rcbuf_decref(inflater->namercbuf);

  hd_context_free(&inflater->ctx);
}

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;
}

static size_t count_encoded_length(size_t n, size_t prefix) {
  size_t k = (size_t)((1 << prefix) - 1);
  size_t len = 0;

  if (n < k) {
    return 1;
  }

  n -= k;
  ++len;

  for (; n >= 128; n >>= 7, ++len)
    ;

  return len + 1;
}

static size_t encode_length(uint8_t *buf, size_t n, size_t prefix) {
  size_t k = (size_t)((1 << prefix) - 1);
  uint8_t *begin = buf;

  *buf = (uint8_t)(*buf & ~k);

  if (n < k) {
    *buf = (uint8_t)(*buf | n);
    return 1;
  }

  *buf = (uint8_t)(*buf | k);
  ++buf;

  n -= k;

  for (; n >= 128; n >>= 7) {
    *buf++ = (uint8_t)((1 << 7) | (n & 0x7f));
  }

  *buf++ = (uint8_t)n;

  return (size_t)(buf - begin);
}

/*
 * 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 nghttp2_ssize 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 (nghttp2_ssize)(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 (nghttp2_ssize)(in - start);
  }

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

static int emit_table_size(nghttp2_bufs *bufs, size_t table_size) {
  int rv;
  uint8_t *bufp;
  size_t blocklen;
  uint8_t sb[16];

  DEBUGF("deflatehd: emit table_size=%zu\n", table_size);

  blocklen = count_encoded_length(table_size, 5);

  if (sizeof(sb) < blocklen) {
    return NGHTTP2_ERR_HEADER_COMP;
  }

  bufp = sb;

  *bufp = 0x20u;

  encode_length(bufp, table_size, 5);

  rv = nghttp2_bufs_add(bufs, sb, blocklen);
  if (rv != 0) {
    return rv;
  }

  return 0;
}

static int emit_indexed_block(nghttp2_bufs *bufs, size_t idx) {
  int rv;
  size_t blocklen;
  uint8_t sb[16];
  uint8_t *bufp;

  blocklen = count_encoded_length(idx + 1, 7);

  DEBUGF("deflatehd: emit indexed index=%zu, %zu bytes\n", idx, blocklen);

  if (sizeof(sb) < blocklen) {
    return NGHTTP2_ERR_HEADER_COMP;
  }

  bufp = sb;
  *bufp = 0x80u;
  encode_length(bufp, idx + 1, 7);

  rv = nghttp2_bufs_add(bufs, sb, blocklen);
  if (rv != 0) {
    return rv;
  }

  return 0;
}

static int emit_string(nghttp2_bufs *bufs, const uint8_t *str, size_t len) {
  int rv;
  uint8_t sb[16];
  uint8_t *bufp;
  size_t blocklen;
  size_t enclen;
  int huffman = 0;

  enclen = nghttp2_hd_huff_encode_count(str, len);

  if (enclen < len) {
    huffman = 1;
  } else {
    enclen = len;
  }

  blocklen = count_encoded_length(enclen, 7);

  DEBUGF("deflatehd: emit string str=%.*s, length=%zu, huffman=%d, "
         "encoded_length=%zu\n",
         (int)len, (const char *)str, len, huffman, enclen);

  if (sizeof(sb) < blocklen) {
    return NGHTTP2_ERR_HEADER_COMP;
  }

  bufp = sb;
  *bufp = huffman ? 1 << 7 : 0;
  encode_length(bufp, enclen, 7);

  rv = nghttp2_bufs_add(bufs, sb, blocklen);
  if (rv != 0) {
    return rv;
  }

  if (huffman) {
    rv = nghttp2_hd_huff_encode(bufs, str, len);
  } else {
    assert(enclen == len);
    rv = nghttp2_bufs_add(bufs, str, len);
  }

  return rv;
}

static uint8_t pack_first_byte(int indexing_mode) {
  switch (indexing_mode) {
  case NGHTTP2_HD_WITH_INDEXING:
    return 0x40u;
  case NGHTTP2_HD_WITHOUT_INDEXING:
    return 0;
  case NGHTTP2_HD_NEVER_INDEXING:
    return 0x10u;
  default:
    assert(0);
  }
  /* This is required to compile with android NDK r10d +
     --enable-werror */
  return 0;
}

static int emit_indname_block(nghttp2_bufs *bufs, size_t idx,
                              const nghttp2_nv *nv, int indexing_mode) {
  int rv;
  uint8_t *bufp;
  size_t blocklen;
  uint8_t sb[16];
  size_t prefixlen;

  if (indexing_mode == NGHTTP2_HD_WITH_INDEXING) {
    prefixlen = 6;
  } else {
    prefixlen = 4;
  }

  DEBUGF("deflatehd: emit indname index=%zu, valuelen=%zu, indexing_mode=%d\n",
         idx, nv->valuelen, indexing_mode);

  blocklen = count_encoded_length(idx + 1, prefixlen);

  if (sizeof(sb) < blocklen) {
    return NGHTTP2_ERR_HEADER_COMP;
  }

  bufp = sb;

  *bufp = pack_first_byte(indexing_mode);

  encode_length(bufp, idx + 1, prefixlen);

  rv = nghttp2_bufs_add(bufs, sb, blocklen);
  if (rv != 0) {
    return rv;
  }

  rv = emit_string(bufs, nv->value, nv->valuelen);
  if (rv != 0) {
    return rv;
  }

  return 0;
}

static int emit_newname_block(nghttp2_bufs *bufs, const nghttp2_nv *nv,
                              int indexing_mode) {
  int rv;

  DEBUGF(
    "deflatehd: emit newname namelen=%zu, valuelen=%zu, indexing_mode=%d\n",
    nv->namelen, nv->valuelen, indexing_mode);

  rv = nghttp2_bufs_addb(bufs, pack_first_byte(indexing_mode));
  if (rv != 0) {
    return rv;
  }

  rv = emit_string(bufs, nv->name, nv->namelen);
  if (rv != 0) {
    return rv;
  }

  rv = emit_string(bufs, nv->value, nv->valuelen);
  if (rv != 0) {
    return rv;
  }

  return 0;
}

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;
}

typedef struct {
  nghttp2_ssize index;
  /* Nonzero if both name and value are matched. */
  int name_value_match;
} search_result;

static search_result search_static_table(const nghttp2_nv *nv, int32_t token,
                                         int name_only) {
  search_result res = {token, 0};
  int i;
  const nghttp2_hd_static_entry *ent;

  if (name_only) {
    return res;
  }

  for (i = token;
       i <= NGHTTP2_TOKEN_WWW_AUTHENTICATE && static_table[i].token == token;
       ++i) {
    ent = &static_table[i];
    if (ent->value.len == nv->valuelen &&
        memcmp(ent->value.base, nv->value, nv->valuelen) == 0) {
      res.index = i;
      res.name_value_match = 1;
      return res;
    }
  }
  return res;
}

static search_result search_hd_table(nghttp2_hd_context *context,
                                     const nghttp2_nv *nv, int32_t token,
                                     int indexing_mode, nghttp2_hd_map *map,
                                     uint32_t hash) {
  search_result res = {-1, 0};
  const nghttp2_hd_entry *ent;
  int exact_match;
  int name_only = indexing_mode == NGHTTP2_HD_NEVER_INDEXING;

  exact_match = 0;
  ent = hd_map_find(map, &exact_match, nv, token, hash, name_only);

  if (!exact_match && token >= 0 && token <= NGHTTP2_TOKEN_WWW_AUTHENTICATE) {
    return search_static_table(nv, token, name_only);
  }

  if (ent == NULL) {
    return res;
  }

  res.index = (nghttp2_ssize)(context->next_seq - 1 - ent->seq +
                              NGHTTP2_STATIC_TABLE_LENGTH);
  res.name_value_match = exact_match;

  return res;
}

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_hd_deflate_change_table_size(
  nghttp2_hd_deflater *deflater, size_t settings_max_dynamic_table_size) {
  size_t next_bufsize = nghttp2_min_size(
    settings_max_dynamic_table_size, deflater->deflate_hd_table_bufsize_max);

  deflater->ctx.hd_table_bufsize_max = next_bufsize;

  deflater->min_hd_table_bufsize_max =
    nghttp2_min_size(deflater->min_hd_table_bufsize_max, next_bufsize);

  deflater->notify_table_size_change = 1;

  hd_context_shrink_table_size(&deflater->ctx, &deflater->map);
  return 0;
}

int nghttp2_hd_inflate_change_table_size(
  nghttp2_hd_inflater *inflater, size_t settings_max_dynamic_table_size) {
  switch (inflater->state) {
  case NGHTTP2_HD_STATE_EXPECT_TABLE_SIZE:
  case NGHTTP2_HD_STATE_INFLATE_START:
    break;
  default:
    return NGHTTP2_ERR_INVALID_STATE;
  }

  inflater->settings_hd_table_bufsize_max = settings_max_dynamic_table_size;

  /* It seems that encoder is not required to send dynamic table size
     update if the table size is not changed after applying
     SETTINGS_HEADER_TABLE_SIZE.  RFC 7541 is ambiguous here, but this
     is the intention of the editor.  If new maximum table size is
     strictly smaller than the current negotiated maximum size,
     encoder must send dynamic table size update.  In other cases, we
     cannot expect it to do so. */
  if (inflater->ctx.hd_table_bufsize_max > settings_max_dynamic_table_size) {
    inflater->state = NGHTTP2_HD_STATE_EXPECT_TABLE_SIZE;
    /* Remember minimum value, and validate that encoder sends the
       value less than or equal to this. */
    inflater->min_hd_table_bufsize_max = settings_max_dynamic_table_size;

    inflater->ctx.hd_table_bufsize_max = settings_max_dynamic_table_size;

    hd_context_shrink_table_size(&inflater->ctx, NULL);
  }

  return 0;
}

#define INDEX_RANGE_VALID(context, idx)                                        \
  ((idx) < (context)->hd_table.len + NGHTTP2_STATIC_TABLE_LENGTH)

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

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 {
    const nghttp2_hd_static_entry *ent = &static_table[idx];
    nghttp2_hd_nv nv = {(nghttp2_rcbuf *)&ent->name,
                        (nghttp2_rcbuf *)&ent->value, ent->token,
                        NGHTTP2_NV_FLAG_NONE};
    return nv;
  }
}

static const nghttp2_nv *nghttp2_hd_table_get2(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)
              ->cnv;
  }

  return &static_table[idx].cnv;
}

static int hd_deflate_decide_indexing(nghttp2_hd_deflater *deflater,
                                      const nghttp2_nv *nv, int32_t token) {
  if (token == NGHTTP2_TOKEN__PATH || token == NGHTTP2_TOKEN_AGE ||
      token == NGHTTP2_TOKEN_CONTENT_LENGTH || token == NGHTTP2_TOKEN_ETAG ||
      token == NGHTTP2_TOKEN_IF_MODIFIED_SINCE ||
      token == NGHTTP2_TOKEN_IF_NONE_MATCH || token == NGHTTP2_TOKEN_LOCATION ||
      token == NGHTTP2_TOKEN_SET_COOKIE ||
      entry_room(nv->namelen, nv->valuelen) >
        deflater->ctx.hd_table_bufsize_max * 3 / 4) {
    return NGHTTP2_HD_WITHOUT_INDEXING;
  }

  return NGHTTP2_HD_WITH_INDEXING;
}

static int deflate_nv(nghttp2_hd_deflater *deflater, nghttp2_bufs *bufs,
                      const nghttp2_nv *nv) {
  int rv;
  search_result res;
  nghttp2_ssize idx;
  int indexing_mode;
  int32_t token;
  nghttp2_mem *mem;
  uint32_t hash = 0;

  DEBUGF("deflatehd: deflating %.*s: %.*s\n", (int)nv->namelen, nv->name,
         (int)nv->valuelen, nv->value);

  mem = deflater->ctx.mem;

  token = lookup_token(nv->name, nv->namelen);
  if (token == -1) {
    hash = name_hash(nv);
  } else if (token <= NGHTTP2_TOKEN_WWW_AUTHENTICATE) {
    hash = static_table[token].hash;
  }

  /* Don't index authorization header field since it may contain low
     entropy secret data (e.g., id/password).  Also cookie header
     field with less than 20 bytes value is also never indexed.  This
     is the same criteria used in Firefox codebase. */
  indexing_mode = token == NGHTTP2_TOKEN_AUTHORIZATION ||
                      (token == NGHTTP2_TOKEN_COOKIE && nv->valuelen < 20) ||
                      (nv->flags & NGHTTP2_NV_FLAG_NO_INDEX)
                    ? NGHTTP2_HD_NEVER_INDEXING
                    : hd_deflate_decide_indexing(deflater, nv, token);

  res = search_hd_table(&deflater->ctx, nv, token, indexing_mode,
                        &deflater->map, hash);

  idx = res.index;

  if (res.name_value_match) {
    DEBUGF("deflatehd: name/value match index=%td\n", idx);

    rv = emit_indexed_block(bufs, (size_t)idx);
    if (rv != 0) {
      return rv;
    }

    return 0;
  }

  if (res.index != -1) {
    DEBUGF("deflatehd: name match index=%td\n", res.index);
  }

  if (indexing_mode == NGHTTP2_HD_WITH_INDEXING) {
    nghttp2_hd_nv hd_nv;

    if (idx != -1) {
      hd_nv.name = nghttp2_hd_table_get(&deflater->ctx, (size_t)idx).name;
      nghttp2_rcbuf_incref(hd_nv.name);
    } else {
      rv = nghttp2_rcbuf_new2(&hd_nv.name, nv->name, nv->namelen, mem);
      if (rv != 0) {
        return rv;
      }
    }

    rv = nghttp2_rcbuf_new2(&hd_nv.value, nv->value, nv->valuelen, mem);

    if (rv != 0) {
      nghttp2_rcbuf_decref(hd_nv.name);
      return rv;
    }

    hd_nv.token = token;
    hd_nv.flags = NGHTTP2_NV_FLAG_NONE;

    rv = add_hd_table_incremental(&deflater->ctx, &hd_nv, &deflater->map, hash);

    nghttp2_rcbuf_decref(hd_nv.value);
    nghttp2_rcbuf_decref(hd_nv.name);

    if (rv != 0) {
      return NGHTTP2_ERR_HEADER_COMP;
    }
  }
  if (idx == -1) {
    rv = emit_newname_block(bufs, nv, indexing_mode);
  } else {
    rv = emit_indname_block(bufs, (size_t)idx, nv, indexing_mode);
  }
  if (rv != 0) {
    return rv;
  }

  return 0;
}

int nghttp2_hd_deflate_hd_bufs(nghttp2_hd_deflater *deflater,
                               nghttp2_bufs *bufs, const nghttp2_nv *nv,
                               size_t nvlen) {
  size_t i;
  int rv = 0;

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

  if (deflater->notify_table_size_change) {
    size_t min_hd_table_bufsize_max;

    min_hd_table_bufsize_max = deflater->min_hd_table_bufsize_max;

    deflater->notify_table_size_change = 0;
    deflater->min_hd_table_bufsize_max = UINT32_MAX;

    if (deflater->ctx.hd_table_bufsize_max > min_hd_table_bufsize_max) {
      rv = emit_table_size(bufs, min_hd_table_bufsize_max);

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

    rv = emit_table_size(bufs, deflater->ctx.hd_table_bufsize_max);

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

  for (i = 0; i < nvlen; ++i) {
    rv = deflate_nv(deflater, bufs, &nv[i]);
    if (rv != 0) {
      goto fail;
    }
  }

  DEBUGF("deflatehd: all input name/value pairs were deflated\n");

  return 0;
fail:
  DEBUGF("deflatehd: error return %d\n", rv);

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

ssize_t nghttp2_hd_deflate_hd(nghttp2_hd_deflater *deflater, uint8_t *buf,
                              size_t buflen, const nghttp2_nv *nv,
                              size_t nvlen) {
  return (ssize_t)nghttp2_hd_deflate_hd2(deflater, buf, buflen, nv, nvlen);
}

nghttp2_ssize nghttp2_hd_deflate_hd2(nghttp2_hd_deflater *deflater,
                                     uint8_t *buf, size_t buflen,
                                     const nghttp2_nv *nv, size_t nvlen) {
  nghttp2_bufs bufs;
  int rv;
  nghttp2_mem *mem;

  mem = deflater->ctx.mem;

  rv = nghttp2_bufs_wrap_init(&bufs, buf, buflen, mem);

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

  rv = nghttp2_hd_deflate_hd_bufs(deflater, &bufs, nv, nvlen);

  buflen = nghttp2_bufs_len(&bufs);

  nghttp2_bufs_wrap_free(&bufs);

  if (rv == NGHTTP2_ERR_BUFFER_ERROR) {
    return NGHTTP2_ERR_INSUFF_BUFSIZE;
  }

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

  return (nghttp2_ssize)buflen;
}

ssize_t nghttp2_hd_deflate_hd_vec(nghttp2_hd_deflater *deflater,
                                  const nghttp2_vec *vec, size_t veclen,
                                  const nghttp2_nv *nv, size_t nvlen) {
  return (ssize_t)nghttp2_hd_deflate_hd_vec2(deflater, vec, veclen, nv, nvlen);
}

nghttp2_ssize nghttp2_hd_deflate_hd_vec2(nghttp2_hd_deflater *deflater,
                                         const nghttp2_vec *vec, size_t veclen,
                                         const nghttp2_nv *nv, size_t nvlen) {
  nghttp2_bufs bufs;
  int rv;
  nghttp2_mem *mem;
  size_t buflen;

  mem = deflater->ctx.mem;

  rv = nghttp2_bufs_wrap_init2(&bufs, vec, veclen, mem);

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

  rv = nghttp2_hd_deflate_hd_bufs(deflater, &bufs, nv, nvlen);

  buflen = nghttp2_bufs_len(&bufs);

  nghttp2_bufs_wrap_free(&bufs);

  if (rv == NGHTTP2_ERR_BUFFER_ERROR) {
    return NGHTTP2_ERR_INSUFF_BUFSIZE;
  }

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

  return (nghttp2_ssize)buflen;
}

size_t nghttp2_hd_deflate_bound(nghttp2_hd_deflater *deflater,
                                const nghttp2_nv *nva, size_t nvlen) {
  size_t n = 0;
  size_t i;
  (void)deflater;

  /* Possible Maximum Header Table Size Change.  Encoding (1u << 31) -
     1 using 4 bit prefix requires 6 bytes.  We may emit this at most
     twice. */
  n += 12;

  /* Use Literal Header Field without indexing - New Name, since it is
     most space consuming format.  Also we choose the less one between
     non-huffman and huffman, so using literal byte count is
     sufficient for upper bound.

     Encoding (1u << 31) - 1 using 7 bit prefix requires 6 bytes.  We
     need 2 of this for |nvlen| header fields. */
  n += 6 * 2 * nvlen;

  for (i = 0; i < nvlen; ++i) {
    n += nva[i].namelen + nva[i].valuelen;
  }

  return n;
}

int nghttp2_hd_deflate_new(nghttp2_hd_deflater **deflater_ptr,
                           size_t deflate_hd_table_bufsize_max) {
  return nghttp2_hd_deflate_new2(deflater_ptr, deflate_hd_table_bufsize_max,
                                 NULL);
}

int nghttp2_hd_deflate_new2(nghttp2_hd_deflater **deflater_ptr,
                            size_t deflate_hd_table_bufsize_max,
                            nghttp2_mem *mem) {
  int rv;
  nghttp2_hd_deflater *deflater;

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

  deflater = nghttp2_mem_malloc(mem, sizeof(nghttp2_hd_deflater));

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

  rv = nghttp2_hd_deflate_init2(deflater, deflate_hd_table_bufsize_max, mem);

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

    return rv;
  }

  *deflater_ptr = deflater;

  return 0;
}

void nghttp2_hd_deflate_del(nghttp2_hd_deflater *deflater) {
  nghttp2_mem *mem;

  mem = deflater->ctx.mem;

  nghttp2_hd_deflate_free(deflater);

  nghttp2_mem_free(mem, deflater);
}

static void hd_inflate_set_huffman_encoded(nghttp2_hd_inflater *inflater,
                                           const uint8_t *in) {
  inflater->huffman_encoded = (*in & (1 << 7)) != 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 nghttp2_ssize hd_inflate_read_len(nghttp2_hd_inflater *inflater,
                                         int *rfin, const uint8_t *in,
                                         const uint8_t *last, size_t prefix,
                                         size_t maxlen) {
  nghttp2_ssize 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;
}

/*
 * 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 nghttp2_ssize hd_inflate_read_huff(nghttp2_hd_inflater *inflater,
                                          nghttp2_buf *buf, const uint8_t *in,
                                          const uint8_t *last) {
  nghttp2_ssize 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;
  }
  if (nghttp2_hd_huff_decode_failure_state(&inflater->huff_decode_ctx)) {
    DEBUGF("inflatehd: huffman decoding failed\n");
    return NGHTTP2_ERR_HEADER_COMP;
  }

  inflater->left -= (size_t)readlen;
  return readlen;
}

/*
 * 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 nghttp2_ssize hd_inflate_read(nghttp2_hd_inflater *inflater,
                                     nghttp2_buf *buf, const uint8_t *in,
                                     const uint8_t *last) {
  size_t len = nghttp2_min_size((size_t)(last - in), inflater->left);

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

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

/*
 * 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);
}

/*
 * 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;
}

/*
 * 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;
}

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);
}

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) {
  return (nghttp2_ssize)nghttp2_hd_inflate_hd3(inflater, nv_out, inflate_flags,
                                               in, inlen, in_final);
}

nghttp2_ssize nghttp2_hd_inflate_hd3(nghttp2_hd_inflater *inflater,
                                     nghttp2_nv *nv_out, int *inflate_flags,
                                     const uint8_t *in, size_t inlen,
                                     int in_final) {
  nghttp2_ssize 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;
}

nghttp2_ssize 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) {
  nghttp2_ssize 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_size(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 (nghttp2_ssize)(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,
          nghttp2_huff_estimate_decode_length(inflater->left) + 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: %td 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: %td 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,
          nghttp2_huff_estimate_decode_length(inflater->left) + 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: %td 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 (nghttp2_ssize)(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 %td: %s\n", rv,
               nghttp2_strerror((int)rv));
        goto fail;
      }

      in += rv;

      DEBUGF("inflatehd: %td 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 (nghttp2_ssize)(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 (nghttp2_ssize)(in - first);

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

    rv = NGHTTP2_ERR_HEADER_COMP;

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

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

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

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

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;
}

void nghttp2_hd_inflate_del(nghttp2_hd_inflater *inflater) {
  nghttp2_mem *mem;

  mem = inflater->ctx.mem;
  nghttp2_hd_inflate_free(inflater);

  nghttp2_mem_free(mem, inflater);
}

int nghttp2_hd_emit_indname_block(nghttp2_bufs *bufs, size_t idx,
                                  nghttp2_nv *nv, int indexing_mode) {
  return emit_indname_block(bufs, idx, nv, indexing_mode);
}

int nghttp2_hd_emit_newname_block(nghttp2_bufs *bufs, nghttp2_nv *nv,
                                  int indexing_mode) {
  return emit_newname_block(bufs, nv, indexing_mode);
}

int nghttp2_hd_emit_table_size(nghttp2_bufs *bufs, size_t table_size) {
  return emit_table_size(bufs, table_size);
}

nghttp2_ssize nghttp2_hd_decode_length(uint32_t *res, size_t *shift_ptr,
                                       int *fin, uint32_t initial, size_t shift,
                                       uint8_t *in, uint8_t *last,
                                       size_t prefix) {
  return decode_length(res, shift_ptr, fin, initial, shift, in, last, prefix);
}

static const nghttp2_nv *hd_get_table_entry(nghttp2_hd_context *context,
                                            size_t idx) {
  if (idx == 0) {
    return NULL;
  }

  --idx;

  if (!INDEX_RANGE_VALID(context, idx)) {
    return NULL;
  }

  return nghttp2_hd_table_get2(context, idx);
}

size_t nghttp2_hd_deflate_get_num_table_entries(nghttp2_hd_deflater *deflater) {
  return get_max_index(&deflater->ctx);
}

const nghttp2_nv *
nghttp2_hd_deflate_get_table_entry(nghttp2_hd_deflater *deflater, size_t idx) {
  return hd_get_table_entry(&deflater->ctx, idx);
}

size_t
nghttp2_hd_deflate_get_dynamic_table_size(nghttp2_hd_deflater *deflater) {
  return deflater->ctx.hd_table_bufsize;
}

size_t
nghttp2_hd_deflate_get_max_dynamic_table_size(nghttp2_hd_deflater *deflater) {
  return deflater->ctx.hd_table_bufsize_max;
}

size_t nghttp2_hd_inflate_get_num_table_entries(nghttp2_hd_inflater *inflater) {
  return get_max_index(&inflater->ctx);
}

const nghttp2_nv *
nghttp2_hd_inflate_get_table_entry(nghttp2_hd_inflater *inflater, size_t idx) {
  return hd_get_table_entry(&inflater->ctx, idx);
}

size_t
nghttp2_hd_inflate_get_dynamic_table_size(nghttp2_hd_inflater *inflater) {
  return inflater->ctx.hd_table_bufsize;
}

size_t
nghttp2_hd_inflate_get_max_dynamic_table_size(nghttp2_hd_inflater *inflater) {
  return inflater->ctx.hd_table_bufsize_max;
}