ydb/contrib/libs/nghttp3/lib/nghttp3_qpack.c

/*
 * nghttp3
 *
 * Copyright (c) 2019 nghttp3 contributors
 * Copyright (c) 2013 nghttp2 contributors
 *
 * 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 "nghttp3_qpack.h"

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

#include "nghttp3_str.h"
#include "nghttp3_macro.h"
#include "nghttp3_debug.h"
#include "nghttp3_unreachable.h"

/* NGHTTP3_QPACK_MAX_QPACK_STREAMS is the maximum number of concurrent
   nghttp3_qpack_stream object to handle a client which never cancel
   or acknowledge header block.  After this limit, encoder stops using
   dynamic table. */
#define NGHTTP3_QPACK_MAX_QPACK_STREAMS 2000

/* Make scalar initialization form of nghttp3_qpack_static_entry */
#define MAKE_STATIC_ENT(I, T, H) {I, T, H}

/* Generated by mkstatichdtbl.py */
static nghttp3_qpack_static_entry token_stable[] = {
  MAKE_STATIC_ENT(0, NGHTTP3_QPACK_TOKEN__AUTHORITY, 3153725150u),
  MAKE_STATIC_ENT(15, NGHTTP3_QPACK_TOKEN__METHOD, 695666056u),
  MAKE_STATIC_ENT(16, NGHTTP3_QPACK_TOKEN__METHOD, 695666056u),
  MAKE_STATIC_ENT(17, NGHTTP3_QPACK_TOKEN__METHOD, 695666056u),
  MAKE_STATIC_ENT(18, NGHTTP3_QPACK_TOKEN__METHOD, 695666056u),
  MAKE_STATIC_ENT(19, NGHTTP3_QPACK_TOKEN__METHOD, 695666056u),
  MAKE_STATIC_ENT(20, NGHTTP3_QPACK_TOKEN__METHOD, 695666056u),
  MAKE_STATIC_ENT(21, NGHTTP3_QPACK_TOKEN__METHOD, 695666056u),
  MAKE_STATIC_ENT(1, NGHTTP3_QPACK_TOKEN__PATH, 3292848686u),
  MAKE_STATIC_ENT(22, NGHTTP3_QPACK_TOKEN__SCHEME, 2510477674u),
  MAKE_STATIC_ENT(23, NGHTTP3_QPACK_TOKEN__SCHEME, 2510477674u),
  MAKE_STATIC_ENT(24, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u),
  MAKE_STATIC_ENT(25, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u),
  MAKE_STATIC_ENT(26, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u),
  MAKE_STATIC_ENT(27, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u),
  MAKE_STATIC_ENT(28, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u),
  MAKE_STATIC_ENT(63, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u),
  MAKE_STATIC_ENT(64, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u),
  MAKE_STATIC_ENT(65, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u),
  MAKE_STATIC_ENT(66, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u),
  MAKE_STATIC_ENT(67, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u),
  MAKE_STATIC_ENT(68, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u),
  MAKE_STATIC_ENT(69, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u),
  MAKE_STATIC_ENT(70, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u),
  MAKE_STATIC_ENT(71, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u),
  MAKE_STATIC_ENT(29, NGHTTP3_QPACK_TOKEN_ACCEPT, 136609321u),
  MAKE_STATIC_ENT(30, NGHTTP3_QPACK_TOKEN_ACCEPT, 136609321u),
  MAKE_STATIC_ENT(31, NGHTTP3_QPACK_TOKEN_ACCEPT_ENCODING, 3379649177u),
  MAKE_STATIC_ENT(72, NGHTTP3_QPACK_TOKEN_ACCEPT_LANGUAGE, 1979086614u),
  MAKE_STATIC_ENT(32, NGHTTP3_QPACK_TOKEN_ACCEPT_RANGES, 1713753958u),
  MAKE_STATIC_ENT(73, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_CREDENTIALS,
                  901040780u),
  MAKE_STATIC_ENT(74, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_CREDENTIALS,
                  901040780u),
  MAKE_STATIC_ENT(33, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_HEADERS,
                  1524311232u),
  MAKE_STATIC_ENT(34, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_HEADERS,
                  1524311232u),
  MAKE_STATIC_ENT(75, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_HEADERS,
                  1524311232u),
  MAKE_STATIC_ENT(76, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_METHODS,
                  2175229868u),
  MAKE_STATIC_ENT(77, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_METHODS,
                  2175229868u),
  MAKE_STATIC_ENT(78, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_METHODS,
                  2175229868u),
  MAKE_STATIC_ENT(35, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_ORIGIN,
                  2710797292u),
  MAKE_STATIC_ENT(79, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_EXPOSE_HEADERS,
                  2449824425u),
  MAKE_STATIC_ENT(80, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_REQUEST_HEADERS,
                  3599549072u),
  MAKE_STATIC_ENT(81, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_REQUEST_METHOD,
                  2417078055u),
  MAKE_STATIC_ENT(82, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_REQUEST_METHOD,
                  2417078055u),
  MAKE_STATIC_ENT(2, NGHTTP3_QPACK_TOKEN_AGE, 742476188u),
  MAKE_STATIC_ENT(83, NGHTTP3_QPACK_TOKEN_ALT_SVC, 2148877059u),
  MAKE_STATIC_ENT(84, NGHTTP3_QPACK_TOKEN_AUTHORIZATION, 2436257726u),
  MAKE_STATIC_ENT(36, NGHTTP3_QPACK_TOKEN_CACHE_CONTROL, 1355326669u),
  MAKE_STATIC_ENT(37, NGHTTP3_QPACK_TOKEN_CACHE_CONTROL, 1355326669u),
  MAKE_STATIC_ENT(38, NGHTTP3_QPACK_TOKEN_CACHE_CONTROL, 1355326669u),
  MAKE_STATIC_ENT(39, NGHTTP3_QPACK_TOKEN_CACHE_CONTROL, 1355326669u),
  MAKE_STATIC_ENT(40, NGHTTP3_QPACK_TOKEN_CACHE_CONTROL, 1355326669u),
  MAKE_STATIC_ENT(41, NGHTTP3_QPACK_TOKEN_CACHE_CONTROL, 1355326669u),
  MAKE_STATIC_ENT(3, NGHTTP3_QPACK_TOKEN_CONTENT_DISPOSITION, 3889184348u),
  MAKE_STATIC_ENT(42, NGHTTP3_QPACK_TOKEN_CONTENT_ENCODING, 65203592u),
  MAKE_STATIC_ENT(43, NGHTTP3_QPACK_TOKEN_CONTENT_ENCODING, 65203592u),
  MAKE_STATIC_ENT(4, NGHTTP3_QPACK_TOKEN_CONTENT_LENGTH, 1308181789u),
  MAKE_STATIC_ENT(85, NGHTTP3_QPACK_TOKEN_CONTENT_SECURITY_POLICY, 1569039836u),
  MAKE_STATIC_ENT(44, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u),
  MAKE_STATIC_ENT(45, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u),
  MAKE_STATIC_ENT(46, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u),
  MAKE_STATIC_ENT(47, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u),
  MAKE_STATIC_ENT(48, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u),
  MAKE_STATIC_ENT(49, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u),
  MAKE_STATIC_ENT(50, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u),
  MAKE_STATIC_ENT(51, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u),
  MAKE_STATIC_ENT(52, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u),
  MAKE_STATIC_ENT(53, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u),
  MAKE_STATIC_ENT(54, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u),
  MAKE_STATIC_ENT(5, NGHTTP3_QPACK_TOKEN_COOKIE, 2007449791u),
  MAKE_STATIC_ENT(6, NGHTTP3_QPACK_TOKEN_DATE, 3564297305u),
  MAKE_STATIC_ENT(86, NGHTTP3_QPACK_TOKEN_EARLY_DATA, 4080895051u),
  MAKE_STATIC_ENT(7, NGHTTP3_QPACK_TOKEN_ETAG, 113792960u),
  MAKE_STATIC_ENT(87, NGHTTP3_QPACK_TOKEN_EXPECT_CT, 1183214960u),
  MAKE_STATIC_ENT(88, NGHTTP3_QPACK_TOKEN_FORWARDED, 1485178027u),
  MAKE_STATIC_ENT(8, NGHTTP3_QPACK_TOKEN_IF_MODIFIED_SINCE, 2213050793u),
  MAKE_STATIC_ENT(9, NGHTTP3_QPACK_TOKEN_IF_NONE_MATCH, 2536202615u),
  MAKE_STATIC_ENT(89, NGHTTP3_QPACK_TOKEN_IF_RANGE, 2340978238u),
  MAKE_STATIC_ENT(10, NGHTTP3_QPACK_TOKEN_LAST_MODIFIED, 3226950251u),
  MAKE_STATIC_ENT(11, NGHTTP3_QPACK_TOKEN_LINK, 232457833u),
  MAKE_STATIC_ENT(12, NGHTTP3_QPACK_TOKEN_LOCATION, 200649126u),
  MAKE_STATIC_ENT(90, NGHTTP3_QPACK_TOKEN_ORIGIN, 3649018447u),
  MAKE_STATIC_ENT(91, NGHTTP3_QPACK_TOKEN_PURPOSE, 4212263681u),
  MAKE_STATIC_ENT(55, NGHTTP3_QPACK_TOKEN_RANGE, 4208725202u),
  MAKE_STATIC_ENT(13, NGHTTP3_QPACK_TOKEN_REFERER, 3969579366u),
  MAKE_STATIC_ENT(92, NGHTTP3_QPACK_TOKEN_SERVER, 1085029842u),
  MAKE_STATIC_ENT(14, NGHTTP3_QPACK_TOKEN_SET_COOKIE, 1848371000u),
  MAKE_STATIC_ENT(56, NGHTTP3_QPACK_TOKEN_STRICT_TRANSPORT_SECURITY,
                  4138147361u),
  MAKE_STATIC_ENT(57, NGHTTP3_QPACK_TOKEN_STRICT_TRANSPORT_SECURITY,
                  4138147361u),
  MAKE_STATIC_ENT(58, NGHTTP3_QPACK_TOKEN_STRICT_TRANSPORT_SECURITY,
                  4138147361u),
  MAKE_STATIC_ENT(93, NGHTTP3_QPACK_TOKEN_TIMING_ALLOW_ORIGIN, 2432297564u),
  MAKE_STATIC_ENT(94, NGHTTP3_QPACK_TOKEN_UPGRADE_INSECURE_REQUESTS,
                  2479169413u),
  MAKE_STATIC_ENT(95, NGHTTP3_QPACK_TOKEN_USER_AGENT, 606444526u),
  MAKE_STATIC_ENT(59, NGHTTP3_QPACK_TOKEN_VARY, 1085005381u),
  MAKE_STATIC_ENT(60, NGHTTP3_QPACK_TOKEN_VARY, 1085005381u),
  MAKE_STATIC_ENT(61, NGHTTP3_QPACK_TOKEN_X_CONTENT_TYPE_OPTIONS, 3644557769u),
  MAKE_STATIC_ENT(96, NGHTTP3_QPACK_TOKEN_X_FORWARDED_FOR, 2914187656u),
  MAKE_STATIC_ENT(97, NGHTTP3_QPACK_TOKEN_X_FRAME_OPTIONS, 3993834824u),
  MAKE_STATIC_ENT(98, NGHTTP3_QPACK_TOKEN_X_FRAME_OPTIONS, 3993834824u),
  MAKE_STATIC_ENT(62, NGHTTP3_QPACK_TOKEN_X_XSS_PROTECTION, 2501058888u),
};

/* Make scalar initialization form of nghttp3_qpack_static_entry */
#define MAKE_STATIC_HD(N, V, T)                                                \
  {                                                                            \
    {NULL, (uint8_t *)(N), sizeof((N)) - 1, -1},                               \
    {NULL, (uint8_t *)(V), sizeof((V)) - 1, -1},                               \
    T,                                                                         \
  }

static nghttp3_qpack_static_header stable[] = {
  MAKE_STATIC_HD(":authority", "", NGHTTP3_QPACK_TOKEN__AUTHORITY),
  MAKE_STATIC_HD(":path", "/", NGHTTP3_QPACK_TOKEN__PATH),
  MAKE_STATIC_HD("age", "0", NGHTTP3_QPACK_TOKEN_AGE),
  MAKE_STATIC_HD("content-disposition", "",
                 NGHTTP3_QPACK_TOKEN_CONTENT_DISPOSITION),
  MAKE_STATIC_HD("content-length", "0", NGHTTP3_QPACK_TOKEN_CONTENT_LENGTH),
  MAKE_STATIC_HD("cookie", "", NGHTTP3_QPACK_TOKEN_COOKIE),
  MAKE_STATIC_HD("date", "", NGHTTP3_QPACK_TOKEN_DATE),
  MAKE_STATIC_HD("etag", "", NGHTTP3_QPACK_TOKEN_ETAG),
  MAKE_STATIC_HD("if-modified-since", "",
                 NGHTTP3_QPACK_TOKEN_IF_MODIFIED_SINCE),
  MAKE_STATIC_HD("if-none-match", "", NGHTTP3_QPACK_TOKEN_IF_NONE_MATCH),
  MAKE_STATIC_HD("last-modified", "", NGHTTP3_QPACK_TOKEN_LAST_MODIFIED),
  MAKE_STATIC_HD("link", "", NGHTTP3_QPACK_TOKEN_LINK),
  MAKE_STATIC_HD("location", "", NGHTTP3_QPACK_TOKEN_LOCATION),
  MAKE_STATIC_HD("referer", "", NGHTTP3_QPACK_TOKEN_REFERER),
  MAKE_STATIC_HD("set-cookie", "", NGHTTP3_QPACK_TOKEN_SET_COOKIE),
  MAKE_STATIC_HD(":method", "CONNECT", NGHTTP3_QPACK_TOKEN__METHOD),
  MAKE_STATIC_HD(":method", "DELETE", NGHTTP3_QPACK_TOKEN__METHOD),
  MAKE_STATIC_HD(":method", "GET", NGHTTP3_QPACK_TOKEN__METHOD),
  MAKE_STATIC_HD(":method", "HEAD", NGHTTP3_QPACK_TOKEN__METHOD),
  MAKE_STATIC_HD(":method", "OPTIONS", NGHTTP3_QPACK_TOKEN__METHOD),
  MAKE_STATIC_HD(":method", "POST", NGHTTP3_QPACK_TOKEN__METHOD),
  MAKE_STATIC_HD(":method", "PUT", NGHTTP3_QPACK_TOKEN__METHOD),
  MAKE_STATIC_HD(":scheme", "http", NGHTTP3_QPACK_TOKEN__SCHEME),
  MAKE_STATIC_HD(":scheme", "https", NGHTTP3_QPACK_TOKEN__SCHEME),
  MAKE_STATIC_HD(":status", "103", NGHTTP3_QPACK_TOKEN__STATUS),
  MAKE_STATIC_HD(":status", "200", NGHTTP3_QPACK_TOKEN__STATUS),
  MAKE_STATIC_HD(":status", "304", NGHTTP3_QPACK_TOKEN__STATUS),
  MAKE_STATIC_HD(":status", "404", NGHTTP3_QPACK_TOKEN__STATUS),
  MAKE_STATIC_HD(":status", "503", NGHTTP3_QPACK_TOKEN__STATUS),
  MAKE_STATIC_HD("accept", "*/*", NGHTTP3_QPACK_TOKEN_ACCEPT),
  MAKE_STATIC_HD("accept", "application/dns-message",
                 NGHTTP3_QPACK_TOKEN_ACCEPT),
  MAKE_STATIC_HD("accept-encoding", "gzip, deflate, br",
                 NGHTTP3_QPACK_TOKEN_ACCEPT_ENCODING),
  MAKE_STATIC_HD("accept-ranges", "bytes", NGHTTP3_QPACK_TOKEN_ACCEPT_RANGES),
  MAKE_STATIC_HD("access-control-allow-headers", "cache-control",
                 NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_HEADERS),
  MAKE_STATIC_HD("access-control-allow-headers", "content-type",
                 NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_HEADERS),
  MAKE_STATIC_HD("access-control-allow-origin", "*",
                 NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_ORIGIN),
  MAKE_STATIC_HD("cache-control", "max-age=0",
                 NGHTTP3_QPACK_TOKEN_CACHE_CONTROL),
  MAKE_STATIC_HD("cache-control", "max-age=2592000",
                 NGHTTP3_QPACK_TOKEN_CACHE_CONTROL),
  MAKE_STATIC_HD("cache-control", "max-age=604800",
                 NGHTTP3_QPACK_TOKEN_CACHE_CONTROL),
  MAKE_STATIC_HD("cache-control", "no-cache",
                 NGHTTP3_QPACK_TOKEN_CACHE_CONTROL),
  MAKE_STATIC_HD("cache-control", "no-store",
                 NGHTTP3_QPACK_TOKEN_CACHE_CONTROL),
  MAKE_STATIC_HD("cache-control", "public, max-age=31536000",
                 NGHTTP3_QPACK_TOKEN_CACHE_CONTROL),
  MAKE_STATIC_HD("content-encoding", "br",
                 NGHTTP3_QPACK_TOKEN_CONTENT_ENCODING),
  MAKE_STATIC_HD("content-encoding", "gzip",
                 NGHTTP3_QPACK_TOKEN_CONTENT_ENCODING),
  MAKE_STATIC_HD("content-type", "application/dns-message",
                 NGHTTP3_QPACK_TOKEN_CONTENT_TYPE),
  MAKE_STATIC_HD("content-type", "application/javascript",
                 NGHTTP3_QPACK_TOKEN_CONTENT_TYPE),
  MAKE_STATIC_HD("content-type", "application/json",
                 NGHTTP3_QPACK_TOKEN_CONTENT_TYPE),
  MAKE_STATIC_HD("content-type", "application/x-www-form-urlencoded",
                 NGHTTP3_QPACK_TOKEN_CONTENT_TYPE),
  MAKE_STATIC_HD("content-type", "image/gif", NGHTTP3_QPACK_TOKEN_CONTENT_TYPE),
  MAKE_STATIC_HD("content-type", "image/jpeg",
                 NGHTTP3_QPACK_TOKEN_CONTENT_TYPE),
  MAKE_STATIC_HD("content-type", "image/png", NGHTTP3_QPACK_TOKEN_CONTENT_TYPE),
  MAKE_STATIC_HD("content-type", "text/css", NGHTTP3_QPACK_TOKEN_CONTENT_TYPE),
  MAKE_STATIC_HD("content-type", "text/html; charset=utf-8",
                 NGHTTP3_QPACK_TOKEN_CONTENT_TYPE),
  MAKE_STATIC_HD("content-type", "text/plain",
                 NGHTTP3_QPACK_TOKEN_CONTENT_TYPE),
  MAKE_STATIC_HD("content-type", "text/plain;charset=utf-8",
                 NGHTTP3_QPACK_TOKEN_CONTENT_TYPE),
  MAKE_STATIC_HD("range", "bytes=0-", NGHTTP3_QPACK_TOKEN_RANGE),
  MAKE_STATIC_HD("strict-transport-security", "max-age=31536000",
                 NGHTTP3_QPACK_TOKEN_STRICT_TRANSPORT_SECURITY),
  MAKE_STATIC_HD("strict-transport-security",
                 "max-age=31536000; includesubdomains",
                 NGHTTP3_QPACK_TOKEN_STRICT_TRANSPORT_SECURITY),
  MAKE_STATIC_HD("strict-transport-security",
                 "max-age=31536000; includesubdomains; preload",
                 NGHTTP3_QPACK_TOKEN_STRICT_TRANSPORT_SECURITY),
  MAKE_STATIC_HD("vary", "accept-encoding", NGHTTP3_QPACK_TOKEN_VARY),
  MAKE_STATIC_HD("vary", "origin", NGHTTP3_QPACK_TOKEN_VARY),
  MAKE_STATIC_HD("x-content-type-options", "nosniff",
                 NGHTTP3_QPACK_TOKEN_X_CONTENT_TYPE_OPTIONS),
  MAKE_STATIC_HD("x-xss-protection", "1; mode=block",
                 NGHTTP3_QPACK_TOKEN_X_XSS_PROTECTION),
  MAKE_STATIC_HD(":status", "100", NGHTTP3_QPACK_TOKEN__STATUS),
  MAKE_STATIC_HD(":status", "204", NGHTTP3_QPACK_TOKEN__STATUS),
  MAKE_STATIC_HD(":status", "206", NGHTTP3_QPACK_TOKEN__STATUS),
  MAKE_STATIC_HD(":status", "302", NGHTTP3_QPACK_TOKEN__STATUS),
  MAKE_STATIC_HD(":status", "400", NGHTTP3_QPACK_TOKEN__STATUS),
  MAKE_STATIC_HD(":status", "403", NGHTTP3_QPACK_TOKEN__STATUS),
  MAKE_STATIC_HD(":status", "421", NGHTTP3_QPACK_TOKEN__STATUS),
  MAKE_STATIC_HD(":status", "425", NGHTTP3_QPACK_TOKEN__STATUS),
  MAKE_STATIC_HD(":status", "500", NGHTTP3_QPACK_TOKEN__STATUS),
  MAKE_STATIC_HD("accept-language", "", NGHTTP3_QPACK_TOKEN_ACCEPT_LANGUAGE),
  MAKE_STATIC_HD("access-control-allow-credentials", "FALSE",
                 NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_CREDENTIALS),
  MAKE_STATIC_HD("access-control-allow-credentials", "TRUE",
                 NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_CREDENTIALS),
  MAKE_STATIC_HD("access-control-allow-headers", "*",
                 NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_HEADERS),
  MAKE_STATIC_HD("access-control-allow-methods", "get",
                 NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_METHODS),
  MAKE_STATIC_HD("access-control-allow-methods", "get, post, options",
                 NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_METHODS),
  MAKE_STATIC_HD("access-control-allow-methods", "options",
                 NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_METHODS),
  MAKE_STATIC_HD("access-control-expose-headers", "content-length",
                 NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_EXPOSE_HEADERS),
  MAKE_STATIC_HD("access-control-request-headers", "content-type",
                 NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_REQUEST_HEADERS),
  MAKE_STATIC_HD("access-control-request-method", "get",
                 NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_REQUEST_METHOD),
  MAKE_STATIC_HD("access-control-request-method", "post",
                 NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_REQUEST_METHOD),
  MAKE_STATIC_HD("alt-svc", "clear", NGHTTP3_QPACK_TOKEN_ALT_SVC),
  MAKE_STATIC_HD("authorization", "", NGHTTP3_QPACK_TOKEN_AUTHORIZATION),
  MAKE_STATIC_HD("content-security-policy",
                 "script-src 'none'; object-src 'none'; base-uri 'none'",
                 NGHTTP3_QPACK_TOKEN_CONTENT_SECURITY_POLICY),
  MAKE_STATIC_HD("early-data", "1", NGHTTP3_QPACK_TOKEN_EARLY_DATA),
  MAKE_STATIC_HD("expect-ct", "", NGHTTP3_QPACK_TOKEN_EXPECT_CT),
  MAKE_STATIC_HD("forwarded", "", NGHTTP3_QPACK_TOKEN_FORWARDED),
  MAKE_STATIC_HD("if-range", "", NGHTTP3_QPACK_TOKEN_IF_RANGE),
  MAKE_STATIC_HD("origin", "", NGHTTP3_QPACK_TOKEN_ORIGIN),
  MAKE_STATIC_HD("purpose", "prefetch", NGHTTP3_QPACK_TOKEN_PURPOSE),
  MAKE_STATIC_HD("server", "", NGHTTP3_QPACK_TOKEN_SERVER),
  MAKE_STATIC_HD("timing-allow-origin", "*",
                 NGHTTP3_QPACK_TOKEN_TIMING_ALLOW_ORIGIN),
  MAKE_STATIC_HD("upgrade-insecure-requests", "1",
                 NGHTTP3_QPACK_TOKEN_UPGRADE_INSECURE_REQUESTS),
  MAKE_STATIC_HD("user-agent", "", NGHTTP3_QPACK_TOKEN_USER_AGENT),
  MAKE_STATIC_HD("x-forwarded-for", "", NGHTTP3_QPACK_TOKEN_X_FORWARDED_FOR),
  MAKE_STATIC_HD("x-frame-options", "deny",
                 NGHTTP3_QPACK_TOKEN_X_FRAME_OPTIONS),
  MAKE_STATIC_HD("x-frame-options", "sameorigin",
                 NGHTTP3_QPACK_TOKEN_X_FRAME_OPTIONS),
};

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

/* Generated by genlibtokenlookup.py */
static int32_t qpack_lookup_token(const uint8_t *name, size_t namelen) {
  switch (namelen) {
  case 2:
    switch (name[1]) {
    case 'e':
      if (memeq("t", name, 1)) {
        return NGHTTP3_QPACK_TOKEN_TE;
      }
      break;
    }
    break;
  case 3:
    switch (name[2]) {
    case 'e':
      if (memeq("ag", name, 2)) {
        return NGHTTP3_QPACK_TOKEN_AGE;
      }
      break;
    }
    break;
  case 4:
    switch (name[3]) {
    case 'e':
      if (memeq("dat", name, 3)) {
        return NGHTTP3_QPACK_TOKEN_DATE;
      }
      break;
    case 'g':
      if (memeq("eta", name, 3)) {
        return NGHTTP3_QPACK_TOKEN_ETAG;
      }
      break;
    case 'k':
      if (memeq("lin", name, 3)) {
        return NGHTTP3_QPACK_TOKEN_LINK;
      }
      break;
    case 't':
      if (memeq("hos", name, 3)) {
        return NGHTTP3_QPACK_TOKEN_HOST;
      }
      break;
    case 'y':
      if (memeq("var", name, 3)) {
        return NGHTTP3_QPACK_TOKEN_VARY;
      }
      break;
    }
    break;
  case 5:
    switch (name[4]) {
    case 'e':
      if (memeq("rang", name, 4)) {
        return NGHTTP3_QPACK_TOKEN_RANGE;
      }
      break;
    case 'h':
      if (memeq(":pat", name, 4)) {
        return NGHTTP3_QPACK_TOKEN__PATH;
      }
      break;
    }
    break;
  case 6:
    switch (name[5]) {
    case 'e':
      if (memeq("cooki", name, 5)) {
        return NGHTTP3_QPACK_TOKEN_COOKIE;
      }
      break;
    case 'n':
      if (memeq("origi", name, 5)) {
        return NGHTTP3_QPACK_TOKEN_ORIGIN;
      }
      break;
    case 'r':
      if (memeq("serve", name, 5)) {
        return NGHTTP3_QPACK_TOKEN_SERVER;
      }
      break;
    case 't':
      if (memeq("accep", name, 5)) {
        return NGHTTP3_QPACK_TOKEN_ACCEPT;
      }
      break;
    }
    break;
  case 7:
    switch (name[6]) {
    case 'c':
      if (memeq("alt-sv", name, 6)) {
        return NGHTTP3_QPACK_TOKEN_ALT_SVC;
      }
      break;
    case 'd':
      if (memeq(":metho", name, 6)) {
        return NGHTTP3_QPACK_TOKEN__METHOD;
      }
      break;
    case 'e':
      if (memeq(":schem", name, 6)) {
        return NGHTTP3_QPACK_TOKEN__SCHEME;
      }
      if (memeq("purpos", name, 6)) {
        return NGHTTP3_QPACK_TOKEN_PURPOSE;
      }
      if (memeq("upgrad", name, 6)) {
        return NGHTTP3_QPACK_TOKEN_UPGRADE;
      }
      break;
    case 'r':
      if (memeq("refere", name, 6)) {
        return NGHTTP3_QPACK_TOKEN_REFERER;
      }
      break;
    case 's':
      if (memeq(":statu", name, 6)) {
        return NGHTTP3_QPACK_TOKEN__STATUS;
      }
      break;
    }
    break;
  case 8:
    switch (name[7]) {
    case 'e':
      if (memeq("if-rang", name, 7)) {
        return NGHTTP3_QPACK_TOKEN_IF_RANGE;
      }
      break;
    case 'n':
      if (memeq("locatio", name, 7)) {
        return NGHTTP3_QPACK_TOKEN_LOCATION;
      }
      break;
    case 'y':
      if (memeq("priorit", name, 7)) {
        return NGHTTP3_QPACK_TOKEN_PRIORITY;
      }
      break;
    }
    break;
  case 9:
    switch (name[8]) {
    case 'd':
      if (memeq("forwarde", name, 8)) {
        return NGHTTP3_QPACK_TOKEN_FORWARDED;
      }
      break;
    case 'l':
      if (memeq(":protoco", name, 8)) {
        return NGHTTP3_QPACK_TOKEN__PROTOCOL;
      }
      break;
    case 't':
      if (memeq("expect-c", name, 8)) {
        return NGHTTP3_QPACK_TOKEN_EXPECT_CT;
      }
      break;
    }
    break;
  case 10:
    switch (name[9]) {
    case 'a':
      if (memeq("early-dat", name, 9)) {
        return NGHTTP3_QPACK_TOKEN_EARLY_DATA;
      }
      break;
    case 'e':
      if (memeq("keep-aliv", name, 9)) {
        return NGHTTP3_QPACK_TOKEN_KEEP_ALIVE;
      }
      if (memeq("set-cooki", name, 9)) {
        return NGHTTP3_QPACK_TOKEN_SET_COOKIE;
      }
      break;
    case 'n':
      if (memeq("connectio", name, 9)) {
        return NGHTTP3_QPACK_TOKEN_CONNECTION;
      }
      break;
    case 't':
      if (memeq("user-agen", name, 9)) {
        return NGHTTP3_QPACK_TOKEN_USER_AGENT;
      }
      break;
    case 'y':
      if (memeq(":authorit", name, 9)) {
        return NGHTTP3_QPACK_TOKEN__AUTHORITY;
      }
      break;
    }
    break;
  case 12:
    switch (name[11]) {
    case 'e':
      if (memeq("content-typ", name, 11)) {
        return NGHTTP3_QPACK_TOKEN_CONTENT_TYPE;
      }
      break;
    }
    break;
  case 13:
    switch (name[12]) {
    case 'd':
      if (memeq("last-modifie", name, 12)) {
        return NGHTTP3_QPACK_TOKEN_LAST_MODIFIED;
      }
      break;
    case 'h':
      if (memeq("if-none-matc", name, 12)) {
        return NGHTTP3_QPACK_TOKEN_IF_NONE_MATCH;
      }
      break;
    case 'l':
      if (memeq("cache-contro", name, 12)) {
        return NGHTTP3_QPACK_TOKEN_CACHE_CONTROL;
      }
      break;
    case 'n':
      if (memeq("authorizatio", name, 12)) {
        return NGHTTP3_QPACK_TOKEN_AUTHORIZATION;
      }
      break;
    case 's':
      if (memeq("accept-range", name, 12)) {
        return NGHTTP3_QPACK_TOKEN_ACCEPT_RANGES;
      }
      break;
    }
    break;
  case 14:
    switch (name[13]) {
    case 'h':
      if (memeq("content-lengt", name, 13)) {
        return NGHTTP3_QPACK_TOKEN_CONTENT_LENGTH;
      }
      break;
    }
    break;
  case 15:
    switch (name[14]) {
    case 'e':
      if (memeq("accept-languag", name, 14)) {
        return NGHTTP3_QPACK_TOKEN_ACCEPT_LANGUAGE;
      }
      break;
    case 'g':
      if (memeq("accept-encodin", name, 14)) {
        return NGHTTP3_QPACK_TOKEN_ACCEPT_ENCODING;
      }
      break;
    case 'r':
      if (memeq("x-forwarded-fo", name, 14)) {
        return NGHTTP3_QPACK_TOKEN_X_FORWARDED_FOR;
      }
      break;
    case 's':
      if (memeq("x-frame-option", name, 14)) {
        return NGHTTP3_QPACK_TOKEN_X_FRAME_OPTIONS;
      }
      break;
    }
    break;
  case 16:
    switch (name[15]) {
    case 'g':
      if (memeq("content-encodin", name, 15)) {
        return NGHTTP3_QPACK_TOKEN_CONTENT_ENCODING;
      }
      break;
    case 'n':
      if (memeq("proxy-connectio", name, 15)) {
        return NGHTTP3_QPACK_TOKEN_PROXY_CONNECTION;
      }
      if (memeq("x-xss-protectio", name, 15)) {
        return NGHTTP3_QPACK_TOKEN_X_XSS_PROTECTION;
      }
      break;
    }
    break;
  case 17:
    switch (name[16]) {
    case 'e':
      if (memeq("if-modified-sinc", name, 16)) {
        return NGHTTP3_QPACK_TOKEN_IF_MODIFIED_SINCE;
      }
      break;
    case 'g':
      if (memeq("transfer-encodin", name, 16)) {
        return NGHTTP3_QPACK_TOKEN_TRANSFER_ENCODING;
      }
      break;
    }
    break;
  case 19:
    switch (name[18]) {
    case 'n':
      if (memeq("content-dispositio", name, 18)) {
        return NGHTTP3_QPACK_TOKEN_CONTENT_DISPOSITION;
      }
      if (memeq("timing-allow-origi", name, 18)) {
        return NGHTTP3_QPACK_TOKEN_TIMING_ALLOW_ORIGIN;
      }
      break;
    }
    break;
  case 22:
    switch (name[21]) {
    case 's':
      if (memeq("x-content-type-option", name, 21)) {
        return NGHTTP3_QPACK_TOKEN_X_CONTENT_TYPE_OPTIONS;
      }
      break;
    }
    break;
  case 23:
    switch (name[22]) {
    case 'y':
      if (memeq("content-security-polic", name, 22)) {
        return NGHTTP3_QPACK_TOKEN_CONTENT_SECURITY_POLICY;
      }
      break;
    }
    break;
  case 25:
    switch (name[24]) {
    case 's':
      if (memeq("upgrade-insecure-request", name, 24)) {
        return NGHTTP3_QPACK_TOKEN_UPGRADE_INSECURE_REQUESTS;
      }
      break;
    case 'y':
      if (memeq("strict-transport-securit", name, 24)) {
        return NGHTTP3_QPACK_TOKEN_STRICT_TRANSPORT_SECURITY;
      }
      break;
    }
    break;
  case 27:
    switch (name[26]) {
    case 'n':
      if (memeq("access-control-allow-origi", name, 26)) {
        return NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_ORIGIN;
      }
      break;
    }
    break;
  case 28:
    switch (name[27]) {
    case 's':
      if (memeq("access-control-allow-header", name, 27)) {
        return NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_HEADERS;
      }
      if (memeq("access-control-allow-method", name, 27)) {
        return NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_METHODS;
      }
      break;
    }
    break;
  case 29:
    switch (name[28]) {
    case 'd':
      if (memeq("access-control-request-metho", name, 28)) {
        return NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_REQUEST_METHOD;
      }
      break;
    case 's':
      if (memeq("access-control-expose-header", name, 28)) {
        return NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_EXPOSE_HEADERS;
      }
      break;
    }
    break;
  case 30:
    switch (name[29]) {
    case 's':
      if (memeq("access-control-request-header", name, 29)) {
        return NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_REQUEST_HEADERS;
      }
      break;
    }
    break;
  case 32:
    switch (name[31]) {
    case 's':
      if (memeq("access-control-allow-credential", name, 31)) {
        return NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_CREDENTIALS;
      }
      break;
    }
    break;
  }
  return -1;
}

static size_t table_space(size_t namelen, size_t valuelen) {
  return NGHTTP3_QPACK_ENTRY_OVERHEAD + namelen + valuelen;
}

static int qpack_nv_name_eq(const nghttp3_qpack_nv *a, const nghttp3_nv *b) {
  return a->name->len == b->namelen &&
         memeq(a->name->base, b->name, b->namelen);
}

static int qpack_nv_value_eq(const nghttp3_qpack_nv *a, const nghttp3_nv *b) {
  return a->value->len == b->valuelen &&
         memeq(a->value->base, b->value, b->valuelen);
}

static void qpack_map_init(nghttp3_qpack_map *map) {
  memset(map, 0, sizeof(nghttp3_qpack_map));
}

static void qpack_map_insert(nghttp3_qpack_map *map, nghttp3_qpack_entry *ent) {
  nghttp3_qpack_entry **bucket;

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

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

  /* larger absidx is linked near the root */
  ent->map_next = *bucket;
  *bucket = ent;
}

static void qpack_map_remove(nghttp3_qpack_map *map, nghttp3_qpack_entry *ent) {
  nghttp3_qpack_entry **dst;

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

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

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

/*
 * qpack_context_can_reference returns nonzero if dynamic table entry
 * at |absidx| can be referenced.  In other words, it is within
 * ctx->max_dtable_capacity.
 */
static int qpack_context_can_reference(nghttp3_qpack_context *ctx,
                                       uint64_t absidx) {
  nghttp3_qpack_entry *ent = nghttp3_qpack_context_dtable_get(ctx, absidx);
  return ctx->dtable_sum - ent->sum <= ctx->max_dtable_capacity;
}

/* |*ppb_match| (post-base match), if it is not NULL, is always exact
     match. */
static void encoder_qpack_map_find(nghttp3_qpack_encoder *encoder,
                                   int *exact_match,
                                   nghttp3_qpack_entry **pmatch,
                                   nghttp3_qpack_entry **ppb_match,
                                   const nghttp3_nv *nv, int32_t token,
                                   uint32_t hash, uint64_t krcnt,
                                   int allow_blocking, int name_only) {
  nghttp3_qpack_entry *p;

  *exact_match = 0;
  *pmatch = NULL;
  *ppb_match = NULL;

  for (p = encoder->dtable_map.table[hash & (NGHTTP3_QPACK_MAP_SIZE - 1)]; p;
       p = p->map_next) {
    if (token != p->nv.token ||
        (token == -1 && (hash != p->hash || !qpack_nv_name_eq(&p->nv, nv))) ||
        !qpack_context_can_reference(&encoder->ctx, p->absidx)) {
      continue;
    }
    if (allow_blocking || p->absidx + 1 <= krcnt) {
      if (!*pmatch) {
        *pmatch = p;
        if (name_only) {
          return;
        }
      }
      if (qpack_nv_value_eq(&p->nv, nv)) {
        *pmatch = p;
        *exact_match = 1;
        return;
      }
    } else if (!*ppb_match && qpack_nv_value_eq(&p->nv, nv)) {
      *ppb_match = p;
    }
  }
}

/*
 * qpack_context_init initializes |ctx|.  |hard_max_dtable_capacity|
 * is the upper bound of the dynamic table capacity.  |mem| is a
 * memory allocator.
 *
 * The maximum dynamic table size is governed by
 * ctx->max_dtable_capacity and it is initialized to 0.
 * |hard_max_dtable_capacity| is the upper bound of
 * ctx->max_dtable_capacity.
 *
 * This function returns 0 if it succeeds, or one of the following
 * negative error codes:
 *
 * NGHTTP3_ERR_NOMEM
 *     Out of memory.
 */
static int qpack_context_init(nghttp3_qpack_context *ctx,
                              size_t hard_max_dtable_capacity,
                              size_t max_blocked_streams,
                              const nghttp3_mem *mem) {
  int rv;
  size_t len = 4096 / NGHTTP3_QPACK_ENTRY_OVERHEAD;
  size_t len2;

  for (len2 = 1; len2 < len; len2 <<= 1)
    ;

  rv = nghttp3_ringbuf_init(&ctx->dtable, len2, sizeof(nghttp3_qpack_entry *),
                            mem);
  if (rv != 0) {
    return rv;
  }

  ctx->mem = mem;
  ctx->dtable_size = 0;
  ctx->dtable_sum = 0;
  ctx->hard_max_dtable_capacity = hard_max_dtable_capacity;
  ctx->max_dtable_capacity = 0;
  ctx->max_blocked_streams = max_blocked_streams;
  ctx->next_absidx = 0;
  ctx->bad = 0;

  return 0;
}

static void qpack_context_free(nghttp3_qpack_context *ctx) {
  nghttp3_qpack_entry *ent;
  size_t i, len = nghttp3_ringbuf_len(&ctx->dtable);

  for (i = 0; i < len; ++i) {
    ent = *(nghttp3_qpack_entry **)nghttp3_ringbuf_get(&ctx->dtable, i);
    nghttp3_qpack_entry_free(ent);
    nghttp3_mem_free(ctx->mem, ent);
  }
  nghttp3_ringbuf_free(&ctx->dtable);
}

static int ref_min_cnt_less(const nghttp3_pq_entry *lhsx,
                            const nghttp3_pq_entry *rhsx) {
  nghttp3_qpack_header_block_ref *lhs =
    nghttp3_struct_of(lhsx, nghttp3_qpack_header_block_ref, min_cnts_pe);
  nghttp3_qpack_header_block_ref *rhs =
    nghttp3_struct_of(rhsx, nghttp3_qpack_header_block_ref, min_cnts_pe);

  return lhs->min_cnt < rhs->min_cnt;
}

typedef struct nghttp3_blocked_streams_key {
  uint64_t max_cnt;
  uint64_t id;
} nghttp3_blocked_streams_key;

static int max_cnt_greater(const nghttp3_ksl_key *lhs,
                           const nghttp3_ksl_key *rhs) {
  const nghttp3_blocked_streams_key *a = lhs;
  const nghttp3_blocked_streams_key *b = rhs;
  return a->max_cnt > b->max_cnt || (a->max_cnt == b->max_cnt && a->id < b->id);
}

nghttp3_ksl_search_def(max_cnt_greater, max_cnt_greater)

int nghttp3_qpack_encoder_init(nghttp3_qpack_encoder *encoder,
                               size_t hard_max_dtable_capacity,
                               const nghttp3_mem *mem) {
  int rv;

  rv = qpack_context_init(&encoder->ctx, hard_max_dtable_capacity, 0, mem);
  if (rv != 0) {
    return rv;
  }

  nghttp3_map_init(&encoder->streams, mem);

  nghttp3_ksl_init(&encoder->blocked_streams, max_cnt_greater,
                   ksl_max_cnt_greater_search,
                   sizeof(nghttp3_blocked_streams_key), mem);

  qpack_map_init(&encoder->dtable_map);
  nghttp3_pq_init(&encoder->min_cnts, ref_min_cnt_less, mem);

  encoder->krcnt = 0;
  encoder->state = NGHTTP3_QPACK_DS_STATE_OPCODE;
  encoder->opcode = 0;
  encoder->min_dtable_update = SIZE_MAX;
  encoder->last_max_dtable_update = 0;
  encoder->uninterrupted_decoderlen = 0;
  encoder->flags = NGHTTP3_QPACK_ENCODER_FLAG_NONE;

  nghttp3_qpack_read_state_reset(&encoder->rstate);

  return 0;
}

static int map_stream_free(void *data, void *ptr) {
  const nghttp3_mem *mem = ptr;
  nghttp3_qpack_stream *stream = data;
  nghttp3_qpack_stream_del(stream, mem);
  return 0;
}

void nghttp3_qpack_encoder_free(nghttp3_qpack_encoder *encoder) {
  nghttp3_pq_free(&encoder->min_cnts);
  nghttp3_ksl_free(&encoder->blocked_streams);
  nghttp3_map_each(&encoder->streams, map_stream_free,
                   (void *)encoder->ctx.mem);
  nghttp3_map_free(&encoder->streams);
  qpack_context_free(&encoder->ctx);
}

void nghttp3_qpack_encoder_set_max_dtable_capacity(
  nghttp3_qpack_encoder *encoder, size_t max_dtable_capacity) {
  max_dtable_capacity = nghttp3_min_size(max_dtable_capacity,
                                         encoder->ctx.hard_max_dtable_capacity);

  if (encoder->ctx.max_dtable_capacity == max_dtable_capacity) {
    return;
  }

  encoder->flags |= NGHTTP3_QPACK_ENCODER_FLAG_PENDING_SET_DTABLE_CAP;

  if (encoder->min_dtable_update > max_dtable_capacity) {
    encoder->min_dtable_update = max_dtable_capacity;
    encoder->ctx.max_dtable_capacity = max_dtable_capacity;
  }
  encoder->last_max_dtable_update = max_dtable_capacity;
}

void nghttp3_qpack_encoder_set_max_blocked_streams(
  nghttp3_qpack_encoder *encoder, size_t max_blocked_streams) {
  encoder->ctx.max_blocked_streams = max_blocked_streams;
}

uint64_t nghttp3_qpack_encoder_get_min_cnt(nghttp3_qpack_encoder *encoder) {
  assert(!nghttp3_pq_empty(&encoder->min_cnts));

  return nghttp3_struct_of(nghttp3_pq_top(&encoder->min_cnts),
                           nghttp3_qpack_header_block_ref, min_cnts_pe)
    ->min_cnt;
}

void nghttp3_qpack_encoder_shrink_dtable(nghttp3_qpack_encoder *encoder) {
  nghttp3_ringbuf *dtable = &encoder->ctx.dtable;
  const nghttp3_mem *mem = encoder->ctx.mem;
  uint64_t min_cnt = UINT64_MAX;
  size_t len;
  nghttp3_qpack_entry *ent;

  if (encoder->ctx.dtable_size <= encoder->ctx.max_dtable_capacity) {
    return;
  }

  if (!nghttp3_pq_empty(&encoder->min_cnts)) {
    min_cnt = nghttp3_qpack_encoder_get_min_cnt(encoder);
  }

  for (; encoder->ctx.dtable_size > encoder->ctx.max_dtable_capacity;) {
    len = nghttp3_ringbuf_len(dtable);
    ent = *(nghttp3_qpack_entry **)nghttp3_ringbuf_get(dtable, len - 1);
    if (ent->absidx + 1 == min_cnt) {
      return;
    }

    encoder->ctx.dtable_size -=
      table_space(ent->nv.name->len, ent->nv.value->len);

    nghttp3_ringbuf_pop_back(dtable);
    qpack_map_remove(&encoder->dtable_map, ent);

    nghttp3_qpack_entry_free(ent);
    nghttp3_mem_free(mem, ent);
  }
}

/*
 * qpack_encoder_add_stream_ref adds another dynamic table reference
 * to a stream denoted by |stream_id|.  |stream| must be NULL if no
 * stream object is not found for the given stream ID.  |max_cnt| and
 * |min_cnt| is the maximum and minimum insert count it references
 * respectively.
 *
 * This function returns 0 if it succeeds, or one of the following
 * negative error codes:
 *
 * NGHTTP3_ERR_NOMEM
 *     Out of memory.
 */
static int qpack_encoder_add_stream_ref(nghttp3_qpack_encoder *encoder,
                                        int64_t stream_id,
                                        nghttp3_qpack_stream *stream,
                                        uint64_t max_cnt, uint64_t min_cnt) {
  nghttp3_qpack_header_block_ref *ref;
  const nghttp3_mem *mem = encoder->ctx.mem;
  uint64_t prev_max_cnt = 0;
  int rv;

  if (stream == NULL) {
    rv = nghttp3_qpack_stream_new(&stream, stream_id, mem);
    if (rv != 0) {
      assert(rv == NGHTTP3_ERR_NOMEM);
      return rv;
    }
    rv = nghttp3_map_insert(&encoder->streams,
                            (nghttp3_map_key_type)stream->stream_id, stream);
    if (rv != 0) {
      assert(rv == NGHTTP3_ERR_NOMEM);
      nghttp3_qpack_stream_del(stream, mem);
      return rv;
    }
  } else {
    prev_max_cnt = nghttp3_qpack_stream_get_max_cnt(stream);
    if (nghttp3_qpack_encoder_stream_is_blocked(encoder, stream) &&
        max_cnt > prev_max_cnt) {
      nghttp3_qpack_encoder_unblock_stream(encoder, stream);
    }
  }

  rv = nghttp3_qpack_header_block_ref_new(&ref, max_cnt, min_cnt, mem);
  if (rv != 0) {
    return rv;
  }

  rv = nghttp3_qpack_stream_add_ref(stream, ref);
  if (rv != 0) {
    nghttp3_qpack_header_block_ref_del(ref, mem);
    return rv;
  }

  if (max_cnt > prev_max_cnt &&
      nghttp3_qpack_encoder_stream_is_blocked(encoder, stream)) {
    rv = nghttp3_qpack_encoder_block_stream(encoder, stream);
    if (rv != 0) {
      return rv;
    }
  }

  return nghttp3_pq_push(&encoder->min_cnts, &ref->min_cnts_pe);
}

static void qpack_encoder_remove_stream(nghttp3_qpack_encoder *encoder,
                                        nghttp3_qpack_stream *stream) {
  size_t i, len;
  nghttp3_qpack_header_block_ref *ref;

  nghttp3_map_remove(&encoder->streams,
                     (nghttp3_map_key_type)stream->stream_id);

  len = nghttp3_ringbuf_len(&stream->refs);
  for (i = 0; i < len; ++i) {
    ref =
      *(nghttp3_qpack_header_block_ref **)nghttp3_ringbuf_get(&stream->refs, i);

    assert(ref->min_cnts_pe.index != NGHTTP3_PQ_BAD_INDEX);

    nghttp3_pq_remove(&encoder->min_cnts, &ref->min_cnts_pe);
  }
}

/*
 * reserve_buf ensures that |buf| contains at least |extra_size| of
 * free space.  In other words, if this function succeeds,
 * nghttp3_buf_left(buf) >= extra_size holds.
 *
 * This function returns 0 if it succeeds, or one of the following
 * negative error codes:
 *
 * NGHTTP3_ERR_NOMEM
 *     Out of memory.
 */
static int reserve_buf(nghttp3_buf *buf, size_t extra_size,
                       const nghttp3_mem *mem) {
  size_t left = nghttp3_buf_left(buf);
  size_t n = 32;

  if (left >= extra_size) {
    return 0;
  }

  n = nghttp3_max_size(n, nghttp3_buf_cap(buf) + extra_size - left);

  /* Check whether we are requesting too much memory */
  if (n > (1u << 31)) {
    return NGHTTP3_ERR_NOMEM;
  }

#ifndef WIN32
  n = 1u << (32 - __builtin_clz((uint32_t)n - 1));
#else  /* defined(WIN32) */
  /* Round up to the next highest power of 2 from Bit Twiddling
     Hacks */
  --n;
  n |= n >> 1;
  n |= n >> 2;
  n |= n >> 4;
  n |= n >> 8;
  n |= n >> 16;
  ++n;
#endif /* defined(WIN32) */

  return nghttp3_buf_reserve(buf, n, mem);
}

int nghttp3_qpack_encoder_encode(nghttp3_qpack_encoder *encoder,
                                 nghttp3_buf *pbuf, nghttp3_buf *rbuf,
                                 nghttp3_buf *ebuf, int64_t stream_id,
                                 const nghttp3_nv *nva, size_t nvlen) {
  size_t i;
  uint64_t max_cnt = 0, min_cnt = UINT64_MAX;
  uint64_t base;
  int rv = 0;
  int allow_blocking;
  int blocked_stream;
  nghttp3_qpack_stream *stream;

  if (encoder->ctx.bad) {
    return NGHTTP3_ERR_QPACK_FATAL;
  }

  rv = nghttp3_qpack_encoder_process_dtable_update(encoder, ebuf);
  if (rv != 0) {
    goto fail;
  }

  base = encoder->ctx.next_absidx;

  stream = nghttp3_qpack_encoder_find_stream(encoder, stream_id);
  blocked_stream =
    stream && nghttp3_qpack_encoder_stream_is_blocked(encoder, stream);
  allow_blocking =
    blocked_stream || encoder->ctx.max_blocked_streams >
                        nghttp3_ksl_len(&encoder->blocked_streams);

  DEBUGF("qpack::encode: stream %ld blocked=%d allow_blocking=%d\n", stream_id,
         blocked_stream, allow_blocking);

  for (i = 0; i < nvlen; ++i) {
    rv = nghttp3_qpack_encoder_encode_nv(encoder, &max_cnt, &min_cnt, rbuf,
                                         ebuf, &nva[i], base, allow_blocking);
    if (rv != 0) {
      goto fail;
    }
  }

  nghttp3_qpack_encoder_write_field_section_prefix(encoder, pbuf, max_cnt,
                                                   base);

  encoder->uninterrupted_decoderlen = 0;

  /* TODO If max_cnt == 0, no reference is made to dtable. */
  if (!max_cnt) {
    return 0;
  }

  rv =
    qpack_encoder_add_stream_ref(encoder, stream_id, stream, max_cnt, min_cnt);
  if (rv != 0) {
    goto fail;
  }

  return 0;

fail:
  encoder->ctx.bad = 1;
  return rv;
}

/*
 * qpack_write_number writes variable integer to |rbuf|.  |num| is an
 * integer to write.  |prefix| is a prefix of variable integer
 * encoding.
 *
 * This function returns 0 if it succeeds, or one of the following
 * negative error codes:
 *
 * NGHTTP3_ERR_NOMEM
 *     Out of memory.
 */
static int qpack_write_number(nghttp3_buf *rbuf, uint8_t fb, uint64_t num,
                              size_t prefix, const nghttp3_mem *mem) {
  int rv;
  size_t len = nghttp3_qpack_put_varint_len(num, prefix);
  uint8_t *p;

  rv = reserve_buf(rbuf, len, mem);
  if (rv != 0) {
    return rv;
  }

  p = rbuf->last;

  *p = fb;
  p = nghttp3_qpack_put_varint(p, num, prefix);

  assert((size_t)(p - rbuf->last) == len);

  rbuf->last = p;

  return 0;
}

int nghttp3_qpack_encoder_process_dtable_update(nghttp3_qpack_encoder *encoder,
                                                nghttp3_buf *ebuf) {
  int rv;

  nghttp3_qpack_encoder_shrink_dtable(encoder);

  if (encoder->ctx.max_dtable_capacity < encoder->ctx.dtable_size ||
      !(encoder->flags & NGHTTP3_QPACK_ENCODER_FLAG_PENDING_SET_DTABLE_CAP)) {
    return 0;
  }

  if (encoder->min_dtable_update < encoder->last_max_dtable_update) {
    rv = nghttp3_qpack_encoder_write_set_dtable_cap(encoder, ebuf,
                                                    encoder->min_dtable_update);
    if (rv != 0) {
      return rv;
    }
  }

  rv = nghttp3_qpack_encoder_write_set_dtable_cap(
    encoder, ebuf, encoder->last_max_dtable_update);
  if (rv != 0) {
    return rv;
  }

  encoder->flags &= (uint8_t)~NGHTTP3_QPACK_ENCODER_FLAG_PENDING_SET_DTABLE_CAP;
  encoder->min_dtable_update = SIZE_MAX;
  encoder->ctx.max_dtable_capacity = encoder->last_max_dtable_update;

  return 0;
}

int nghttp3_qpack_encoder_write_set_dtable_cap(nghttp3_qpack_encoder *encoder,
                                               nghttp3_buf *ebuf, size_t cap) {
  DEBUGF("qpack::encode: Set Dynamic Table Capacity capacity=%zu\n", cap);
  return qpack_write_number(ebuf, 0x20, cap, 5, encoder->ctx.mem);
}

nghttp3_qpack_stream *
nghttp3_qpack_encoder_find_stream(nghttp3_qpack_encoder *encoder,
                                  int64_t stream_id) {
  return nghttp3_map_find(&encoder->streams, (nghttp3_map_key_type)stream_id);
}

int nghttp3_qpack_encoder_stream_is_blocked(nghttp3_qpack_encoder *encoder,
                                            nghttp3_qpack_stream *stream) {
  return stream && encoder->krcnt < nghttp3_qpack_stream_get_max_cnt(stream);
}

static uint32_t qpack_hash_name(const nghttp3_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;
}

/*
 * qpack_encoder_decide_indexing_mode determines and returns indexing
 * mode for header field |nv|.  |token| is a token of header field
 * name.
 */
static nghttp3_qpack_indexing_mode
qpack_encoder_decide_indexing_mode(nghttp3_qpack_encoder *encoder,
                                   const nghttp3_nv *nv, int32_t token) {
  if (nv->flags & NGHTTP3_NV_FLAG_NEVER_INDEX) {
    return NGHTTP3_QPACK_INDEXING_MODE_NEVER;
  }

  switch (token) {
  case NGHTTP3_QPACK_TOKEN_AUTHORIZATION:
    return NGHTTP3_QPACK_INDEXING_MODE_NEVER;
  case NGHTTP3_QPACK_TOKEN_COOKIE:
    if (nv->valuelen < 20) {
      return NGHTTP3_QPACK_INDEXING_MODE_NEVER;
    }
    break;
  case -1:
  case NGHTTP3_QPACK_TOKEN__PATH:
  case NGHTTP3_QPACK_TOKEN_AGE:
  case NGHTTP3_QPACK_TOKEN_CONTENT_LENGTH:
  case NGHTTP3_QPACK_TOKEN_ETAG:
  case NGHTTP3_QPACK_TOKEN_IF_MODIFIED_SINCE:
  case NGHTTP3_QPACK_TOKEN_IF_NONE_MATCH:
  case NGHTTP3_QPACK_TOKEN_LOCATION:
  case NGHTTP3_QPACK_TOKEN_SET_COOKIE:
    if (nv->flags & NGHTTP3_NV_FLAG_TRY_INDEX) {
      break;
    }

    return NGHTTP3_QPACK_INDEXING_MODE_LITERAL;
  case NGHTTP3_QPACK_TOKEN_HOST:
  case NGHTTP3_QPACK_TOKEN_TE:
  case NGHTTP3_QPACK_TOKEN__PROTOCOL:
  case NGHTTP3_QPACK_TOKEN_PRIORITY:
    break;
  default:
    if (nv->flags & NGHTTP3_NV_FLAG_TRY_INDEX) {
      break;
    }

    if (token >= 1000) {
      return NGHTTP3_QPACK_INDEXING_MODE_LITERAL;
    }
  }

  if (table_space(nv->namelen, nv->valuelen) >
      encoder->ctx.max_dtable_capacity * 3 / 4) {
    return NGHTTP3_QPACK_INDEXING_MODE_LITERAL;
  }

  return NGHTTP3_QPACK_INDEXING_MODE_STORE;
}

/*
 * qpack_encoder_can_index returns nonzero if an entry which occupies
 * |need| bytes can be inserted into dynamic table.  |min_cnt| is the
 * minimum insert count which blocked stream requires.
 */
static int qpack_encoder_can_index(nghttp3_qpack_encoder *encoder, size_t need,
                                   uint64_t min_cnt) {
  size_t avail = 0;
  size_t len;
  uint64_t gmin_cnt;
  nghttp3_qpack_entry *min_ent, *last_ent;
  nghttp3_ringbuf *dtable = &encoder->ctx.dtable;

  if (encoder->ctx.max_dtable_capacity > encoder->ctx.dtable_size) {
    avail = encoder->ctx.max_dtable_capacity - encoder->ctx.dtable_size;
    if (need <= avail) {
      return 1;
    }
  }

  if (!nghttp3_pq_empty(&encoder->min_cnts)) {
    gmin_cnt = nghttp3_qpack_encoder_get_min_cnt(encoder);
    min_cnt = nghttp3_min_uint64(min_cnt, gmin_cnt);
  }

  if (min_cnt == UINT64_MAX) {
    return encoder->ctx.max_dtable_capacity >= need;
  }

  min_ent = nghttp3_qpack_context_dtable_get(&encoder->ctx, min_cnt - 1);

  len = nghttp3_ringbuf_len(&encoder->ctx.dtable);
  assert(len);
  last_ent = *(nghttp3_qpack_entry **)nghttp3_ringbuf_get(dtable, len - 1);

  if (min_ent == last_ent) {
    return 0;
  }

  return avail + min_ent->sum - last_ent->sum >= need;
}

/*
 * qpack_encoder_can_index_nv returns nonzero if header field |nv| can
 * be inserted into dynamic table.  |min_cnt| is the minimum insert
 * count which blocked stream requires.
 */
static int qpack_encoder_can_index_nv(nghttp3_qpack_encoder *encoder,
                                      const nghttp3_nv *nv, uint64_t min_cnt) {
  return qpack_encoder_can_index(
    encoder, table_space(nv->namelen, nv->valuelen), min_cnt);
}

/*
 * qpack_encoder_can_index_duplicate returns nonzero if an entry at
 * |absidx| in dynamic table can be inserted to dynamic table as
 * duplicate.  |min_cnt| is the minimum insert count which blocked
 * stream requires.
 */
static int qpack_encoder_can_index_duplicate(nghttp3_qpack_encoder *encoder,
                                             uint64_t absidx,
                                             uint64_t min_cnt) {
  nghttp3_qpack_entry *ent =
    nghttp3_qpack_context_dtable_get(&encoder->ctx, absidx);

  return qpack_encoder_can_index(
    encoder, table_space(ent->nv.name->len, ent->nv.value->len), min_cnt);
}

/*
 * qpack_context_check_draining returns nonzero if an entry at
 * |absidx| in dynamic table is one of draining entries.
 */
static int qpack_context_check_draining(nghttp3_qpack_context *ctx,
                                        uint64_t absidx) {
  const size_t safe = ctx->max_dtable_capacity -
                      nghttp3_min_size(512, ctx->max_dtable_capacity * 1 / 8);
  nghttp3_qpack_entry *ent = nghttp3_qpack_context_dtable_get(ctx, absidx);

  return ctx->dtable_sum - ent->sum > safe;
}

int nghttp3_qpack_encoder_encode_nv(nghttp3_qpack_encoder *encoder,
                                    uint64_t *pmax_cnt, uint64_t *pmin_cnt,
                                    nghttp3_buf *rbuf, nghttp3_buf *ebuf,
                                    const nghttp3_nv *nv, uint64_t base,
                                    int allow_blocking) {
  uint32_t hash = 0;
  int32_t token;
  nghttp3_qpack_indexing_mode indexing_mode;
  nghttp3_qpack_lookup_result sres = {-1, 0, -1}, dres = {-1, 0, -1};
  nghttp3_qpack_entry *new_ent = NULL;
  int static_entry;
  int just_index = 0;
  int rv;

  token = qpack_lookup_token(nv->name, nv->namelen);
  static_entry = token != -1 && (size_t)token < nghttp3_arraylen(token_stable);

  indexing_mode = qpack_encoder_decide_indexing_mode(encoder, nv, token);

  if (static_entry) {
    sres = nghttp3_qpack_lookup_stable(nv, token, indexing_mode);
    if (sres.index != -1 && sres.name_value_match) {
      return nghttp3_qpack_encoder_write_static_indexed(encoder, rbuf,
                                                        (size_t)sres.index);
    }
  }

  if (static_entry) {
    hash = token_stable[token].hash;
  } else {
    switch (token) {
    case NGHTTP3_QPACK_TOKEN_HOST:
      hash = 2952701295u;
      break;
    case NGHTTP3_QPACK_TOKEN_TE:
      hash = 1011170994u;
      break;
    case NGHTTP3_QPACK_TOKEN__PROTOCOL:
      hash = 1128642621u;
      break;
    case NGHTTP3_QPACK_TOKEN_PRIORITY:
      hash = 2498028297u;
      break;
    default:
      hash = qpack_hash_name(nv);
    }
  }

  if (nghttp3_map_size(&encoder->streams) < NGHTTP3_QPACK_MAX_QPACK_STREAMS) {
    dres = nghttp3_qpack_encoder_lookup_dtable(
      encoder, nv, token, hash, indexing_mode, encoder->krcnt, allow_blocking);
    just_index =
      indexing_mode == NGHTTP3_QPACK_INDEXING_MODE_STORE && dres.pb_index == -1;
  }

  if (dres.index != -1 && dres.name_value_match) {
    if (allow_blocking &&
        qpack_context_check_draining(&encoder->ctx, (size_t)dres.index) &&
        qpack_encoder_can_index_duplicate(encoder, (size_t)dres.index,
                                          *pmin_cnt)) {
      rv = nghttp3_qpack_encoder_write_duplicate_insert(encoder, ebuf,
                                                        (size_t)dres.index);
      if (rv != 0) {
        return rv;
      }
      rv =
        nghttp3_qpack_encoder_dtable_duplicate_add(encoder, (size_t)dres.index);
      if (rv != 0) {
        return rv;
      }

      new_ent = nghttp3_qpack_context_dtable_top(&encoder->ctx);
      dres.index = (nghttp3_ssize)new_ent->absidx;
    }
    *pmax_cnt = nghttp3_max_uint64(*pmax_cnt, (uint64_t)(dres.index + 1));
    *pmin_cnt = nghttp3_min_uint64(*pmin_cnt, (uint64_t)(dres.index + 1));

    return nghttp3_qpack_encoder_write_dynamic_indexed(
      encoder, rbuf, (size_t)dres.index, base);
  }

  if (sres.index != -1) {
    if (just_index && qpack_encoder_can_index_nv(encoder, nv, *pmin_cnt)) {
      rv = nghttp3_qpack_encoder_write_static_insert(encoder, ebuf,
                                                     (size_t)sres.index, nv);
      if (rv != 0) {
        return rv;
      }
      rv = nghttp3_qpack_encoder_dtable_static_add(encoder, (size_t)sres.index,
                                                   nv, hash);
      if (rv != 0) {
        return rv;
      }
      if (allow_blocking) {
        new_ent = nghttp3_qpack_context_dtable_top(&encoder->ctx);
        *pmax_cnt = nghttp3_max_uint64(*pmax_cnt, new_ent->absidx + 1);
        *pmin_cnt = nghttp3_min_uint64(*pmin_cnt, new_ent->absidx + 1);

        return nghttp3_qpack_encoder_write_dynamic_indexed(
          encoder, rbuf, new_ent->absidx, base);
      }
    }

    return nghttp3_qpack_encoder_write_static_indexed_name(
      encoder, rbuf, (size_t)sres.index, nv);
  }

  if (dres.index != -1) {
    if (just_index &&
        qpack_encoder_can_index_nv(
          encoder, nv,
          allow_blocking
            ? *pmin_cnt
            : nghttp3_min_uint64((uint64_t)dres.index + 1, *pmin_cnt))) {
      rv = nghttp3_qpack_encoder_write_dynamic_insert(encoder, ebuf,
                                                      (size_t)dres.index, nv);
      if (rv != 0) {
        return rv;
      }

      if (!allow_blocking) {
        *pmin_cnt = nghttp3_min_uint64(*pmin_cnt, (uint64_t)dres.index + 1);
      }

      rv = nghttp3_qpack_encoder_dtable_dynamic_add(encoder, (size_t)dres.index,
                                                    nv, hash);
      if (rv != 0) {
        return rv;
      }

      if (allow_blocking) {
        new_ent = nghttp3_qpack_context_dtable_top(&encoder->ctx);
        *pmax_cnt = nghttp3_max_uint64(*pmax_cnt, new_ent->absidx + 1);
        *pmin_cnt = nghttp3_min_uint64(*pmin_cnt, new_ent->absidx + 1);

        return nghttp3_qpack_encoder_write_dynamic_indexed(
          encoder, rbuf, new_ent->absidx, base);
      }
    }

    *pmax_cnt = nghttp3_max_uint64(*pmax_cnt, (uint64_t)(dres.index + 1));
    *pmin_cnt = nghttp3_min_uint64(*pmin_cnt, (uint64_t)(dres.index + 1));

    return nghttp3_qpack_encoder_write_dynamic_indexed_name(
      encoder, rbuf, (size_t)dres.index, base, nv);
  }

  if (just_index && qpack_encoder_can_index_nv(encoder, nv, *pmin_cnt)) {
    rv = nghttp3_qpack_encoder_dtable_literal_add(encoder, nv, token, hash);
    if (rv != 0) {
      return rv;
    }
    rv = nghttp3_qpack_encoder_write_literal_insert(encoder, ebuf, nv);
    if (rv != 0) {
      return rv;
    }
    if (allow_blocking) {
      new_ent = nghttp3_qpack_context_dtable_top(&encoder->ctx);
      *pmax_cnt = nghttp3_max_uint64(*pmax_cnt, new_ent->absidx + 1);
      *pmin_cnt = nghttp3_min_uint64(*pmin_cnt, new_ent->absidx + 1);

      return nghttp3_qpack_encoder_write_dynamic_indexed(encoder, rbuf,
                                                         new_ent->absidx, base);
    }
  }

  return nghttp3_qpack_encoder_write_literal(encoder, rbuf, nv);
}

nghttp3_qpack_lookup_result
nghttp3_qpack_lookup_stable(const nghttp3_nv *nv, int32_t token,
                            nghttp3_qpack_indexing_mode indexing_mode) {
  nghttp3_qpack_lookup_result res = {(nghttp3_ssize)token_stable[token].absidx,
                                     0, -1};
  nghttp3_qpack_static_entry *ent;
  nghttp3_qpack_static_header *hdr;
  size_t i;

  assert(token >= 0);

  if (indexing_mode == NGHTTP3_QPACK_INDEXING_MODE_NEVER) {
    return res;
  }

  for (i = (size_t)token;
       i < nghttp3_arraylen(token_stable) && token_stable[i].token == token;
       ++i) {
    ent = &token_stable[i];
    hdr = &stable[ent->absidx];
    if (hdr->value.len == nv->valuelen &&
        memeq(hdr->value.base, nv->value, nv->valuelen)) {
      res.index = (nghttp3_ssize)ent->absidx;
      res.name_value_match = 1;
      return res;
    }
  }
  return res;
}

nghttp3_qpack_lookup_result nghttp3_qpack_encoder_lookup_dtable(
  nghttp3_qpack_encoder *encoder, const nghttp3_nv *nv, int32_t token,
  uint32_t hash, nghttp3_qpack_indexing_mode indexing_mode, uint64_t krcnt,
  int allow_blocking) {
  nghttp3_qpack_lookup_result res = {-1, 0, -1};
  int exact_match = 0;
  nghttp3_qpack_entry *match, *pb_match;

  encoder_qpack_map_find(encoder, &exact_match, &match, &pb_match, nv, token,
                         hash, krcnt, allow_blocking,
                         indexing_mode == NGHTTP3_QPACK_INDEXING_MODE_NEVER);
  if (match) {
    res.index = (nghttp3_ssize)match->absidx;
    res.name_value_match = exact_match;
  }
  if (pb_match) {
    res.pb_index = (nghttp3_ssize)pb_match->absidx;
  }

  return res;
}

int nghttp3_qpack_header_block_ref_new(nghttp3_qpack_header_block_ref **pref,
                                       uint64_t max_cnt, uint64_t min_cnt,
                                       const nghttp3_mem *mem) {
  nghttp3_qpack_header_block_ref *ref =
    nghttp3_mem_malloc(mem, sizeof(nghttp3_qpack_header_block_ref));

  if (ref == NULL) {
    return NGHTTP3_ERR_NOMEM;
  }

  ref->max_cnts_pe.index = NGHTTP3_PQ_BAD_INDEX;
  ref->min_cnts_pe.index = NGHTTP3_PQ_BAD_INDEX;
  ref->max_cnt = max_cnt;
  ref->min_cnt = min_cnt;

  *pref = ref;

  return 0;
}

void nghttp3_qpack_header_block_ref_del(nghttp3_qpack_header_block_ref *ref,
                                        const nghttp3_mem *mem) {
  nghttp3_mem_free(mem, ref);
}

static int ref_max_cnt_greater(const nghttp3_pq_entry *lhsx,
                               const nghttp3_pq_entry *rhsx) {
  const nghttp3_qpack_header_block_ref *lhs =
    nghttp3_struct_of(lhsx, nghttp3_qpack_header_block_ref, max_cnts_pe);
  const nghttp3_qpack_header_block_ref *rhs =
    nghttp3_struct_of(rhsx, nghttp3_qpack_header_block_ref, max_cnts_pe);

  return lhs->max_cnt > rhs->max_cnt;
}

int nghttp3_qpack_stream_new(nghttp3_qpack_stream **pstream, int64_t stream_id,
                             const nghttp3_mem *mem) {
  int rv;
  nghttp3_qpack_stream *stream;

  stream = nghttp3_mem_malloc(mem, sizeof(nghttp3_qpack_stream));
  if (stream == NULL) {
    return NGHTTP3_ERR_NOMEM;
  }

  rv = nghttp3_ringbuf_init(&stream->refs, 4,
                            sizeof(nghttp3_qpack_header_block_ref *), mem);
  if (rv != 0) {
    nghttp3_mem_free(mem, stream);
    return rv;
  }

  nghttp3_pq_init(&stream->max_cnts, ref_max_cnt_greater, mem);

  stream->stream_id = stream_id;

  *pstream = stream;

  return 0;
}

void nghttp3_qpack_stream_del(nghttp3_qpack_stream *stream,
                              const nghttp3_mem *mem) {
  nghttp3_qpack_header_block_ref *ref;
  size_t i, len;

  if (stream == NULL) {
    return;
  }

  nghttp3_pq_free(&stream->max_cnts);

  len = nghttp3_ringbuf_len(&stream->refs);
  for (i = 0; i < len; ++i) {
    ref =
      *(nghttp3_qpack_header_block_ref **)nghttp3_ringbuf_get(&stream->refs, i);
    nghttp3_qpack_header_block_ref_del(ref, mem);
  }

  nghttp3_ringbuf_free(&stream->refs);

  nghttp3_mem_free(mem, stream);
}

uint64_t nghttp3_qpack_stream_get_max_cnt(const nghttp3_qpack_stream *stream) {
  nghttp3_qpack_header_block_ref *ref;

  if (nghttp3_pq_empty(&stream->max_cnts)) {
    return 0;
  }

  ref = nghttp3_struct_of(nghttp3_pq_top(&stream->max_cnts),
                          nghttp3_qpack_header_block_ref, max_cnts_pe);
  return ref->max_cnt;
}

int nghttp3_qpack_stream_add_ref(nghttp3_qpack_stream *stream,
                                 nghttp3_qpack_header_block_ref *ref) {
  nghttp3_qpack_header_block_ref **dest;
  int rv;

  if (nghttp3_ringbuf_full(&stream->refs)) {
    rv = nghttp3_ringbuf_reserve(&stream->refs,
                                 nghttp3_ringbuf_len(&stream->refs) * 2);
    if (rv != 0) {
      return rv;
    }
  }

  dest = nghttp3_ringbuf_push_back(&stream->refs);
  *dest = ref;

  return nghttp3_pq_push(&stream->max_cnts, &ref->max_cnts_pe);
}

void nghttp3_qpack_stream_pop_ref(nghttp3_qpack_stream *stream) {
  nghttp3_qpack_header_block_ref *ref;

  assert(nghttp3_ringbuf_len(&stream->refs));

  ref =
    *(nghttp3_qpack_header_block_ref **)nghttp3_ringbuf_get(&stream->refs, 0);

  assert(ref->max_cnts_pe.index != NGHTTP3_PQ_BAD_INDEX);

  nghttp3_pq_remove(&stream->max_cnts, &ref->max_cnts_pe);

  nghttp3_ringbuf_pop_front(&stream->refs);
}

int nghttp3_qpack_encoder_write_static_indexed(nghttp3_qpack_encoder *encoder,
                                               nghttp3_buf *rbuf,
                                               uint64_t absidx) {
  DEBUGF("qpack::encode: Indexed Field Line (static) absidx=%" PRIu64 "\n",
         absidx);
  return qpack_write_number(rbuf, 0xc0, absidx, 6, encoder->ctx.mem);
}

int nghttp3_qpack_encoder_write_dynamic_indexed(nghttp3_qpack_encoder *encoder,
                                                nghttp3_buf *rbuf,
                                                uint64_t absidx,
                                                uint64_t base) {
  DEBUGF("qpack::encode: Indexed Field Line (dynamic) absidx=%" PRIu64
         " base=%" PRIu64 "\n",
         absidx, base);

  if (absidx < base) {
    return qpack_write_number(rbuf, 0x80, base - absidx - 1, 6,
                              encoder->ctx.mem);
  }

  return qpack_write_number(rbuf, 0x10, absidx - base, 4, encoder->ctx.mem);
}

/*
 * qpack_encoder_write_indexed_name writes generic indexed name.  |fb|
 * is the first byte.  |nameidx| is an index of referenced name.
 * |prefix| is a prefix of variable integer encoding.  |nv| is a
 * header field to encode.
 *
 * This function returns 0 if it succeeds, or one of the following
 * negative error codes:
 *
 * NGHTTP3_ERR_NOMEM
 *     Out of memory.
 */
static int qpack_encoder_write_indexed_name(nghttp3_qpack_encoder *encoder,
                                            nghttp3_buf *buf, uint8_t fb,
                                            uint64_t nameidx, size_t prefix,
                                            const nghttp3_nv *nv) {
  int rv;
  size_t len = nghttp3_qpack_put_varint_len(nameidx, prefix);
  uint8_t *p;
  size_t hlen;
  int h = 0;

  hlen = nghttp3_qpack_huffman_encode_count(nv->value, nv->valuelen);
  if (hlen < nv->valuelen) {
    h = 1;
    len += nghttp3_qpack_put_varint_len(hlen, 7) + hlen;
  } else {
    len += nghttp3_qpack_put_varint_len(nv->valuelen, 7) + nv->valuelen;
  }

  rv = reserve_buf(buf, len, encoder->ctx.mem);
  if (rv != 0) {
    return rv;
  }

  p = buf->last;

  *p = fb;
  p = nghttp3_qpack_put_varint(p, nameidx, prefix);

  if (h) {
    *p = 0x80;
    p = nghttp3_qpack_put_varint(p, hlen, 7);
    p = nghttp3_qpack_huffman_encode(p, nv->value, nv->valuelen);
  } else {
    *p = 0;
    p = nghttp3_qpack_put_varint(p, nv->valuelen, 7);
    if (nv->valuelen) {
      p = nghttp3_cpymem(p, nv->value, nv->valuelen);
    }
  }

  assert((size_t)(p - buf->last) == len);

  buf->last = p;

  return 0;
}

int nghttp3_qpack_encoder_write_static_indexed_name(
  nghttp3_qpack_encoder *encoder, nghttp3_buf *rbuf, uint64_t absidx,
  const nghttp3_nv *nv) {
  uint8_t fb =
    (uint8_t)(0x50 | ((nv->flags & NGHTTP3_NV_FLAG_NEVER_INDEX) ? 0x20 : 0));

  DEBUGF("qpack::encode: Literal Field Line With Name Reference (static) "
         "absidx=%" PRIu64 " never=%d\n",
         absidx, (nv->flags & NGHTTP3_NV_FLAG_NEVER_INDEX) != 0);
  return qpack_encoder_write_indexed_name(encoder, rbuf, fb, absidx, 4, nv);
}

int nghttp3_qpack_encoder_write_dynamic_indexed_name(
  nghttp3_qpack_encoder *encoder, nghttp3_buf *rbuf, uint64_t absidx,
  uint64_t base, const nghttp3_nv *nv) {
  uint8_t fb;

  DEBUGF("qpack::encode: Literal Field Line With Name Reference (dynamic) "
         "absidx=%" PRIu64 " base=%" PRIu64 " never=%d\n",
         absidx, base, (nv->flags & NGHTTP3_NV_FLAG_NEVER_INDEX) != 0);

  if (absidx < base) {
    fb =
      (uint8_t)(0x40 | ((nv->flags & NGHTTP3_NV_FLAG_NEVER_INDEX) ? 0x20 : 0));
    return qpack_encoder_write_indexed_name(encoder, rbuf, fb,
                                            base - absidx - 1, 4, nv);
  }

  fb = (nv->flags & NGHTTP3_NV_FLAG_NEVER_INDEX) ? 0x08 : 0;
  return qpack_encoder_write_indexed_name(encoder, rbuf, fb, absidx - base, 3,
                                          nv);
}

/*
 * qpack_encoder_write_literal writes generic literal header field
 * representation.  |fb| is a first byte.  |prefix| is a prefix of
 * variable integer encoding for name length.  |nv| is a header field
 * to encode.
 *
 * This function returns 0 if it succeeds, or one of the following
 * negative error codes:
 *
 * NGHTTP3_ERR_NOMEM
 *     Out of memory.
 */
static int qpack_encoder_write_literal(nghttp3_qpack_encoder *encoder,
                                       nghttp3_buf *buf, uint8_t fb,
                                       size_t prefix, const nghttp3_nv *nv) {
  int rv;
  size_t len;
  uint8_t *p;
  size_t nhlen, vhlen;
  int nh = 0, vh = 0;

  nhlen = nghttp3_qpack_huffman_encode_count(nv->name, nv->namelen);
  if (nhlen < nv->namelen) {
    nh = 1;
    len = nghttp3_qpack_put_varint_len(nhlen, prefix) + nhlen;
  } else {
    len = nghttp3_qpack_put_varint_len(nv->namelen, prefix) + nv->namelen;
  }

  vhlen = nghttp3_qpack_huffman_encode_count(nv->value, nv->valuelen);
  if (vhlen < nv->valuelen) {
    vh = 1;
    len += nghttp3_qpack_put_varint_len(vhlen, 7) + vhlen;
  } else {
    len += nghttp3_qpack_put_varint_len(nv->valuelen, 7) + nv->valuelen;
  }

  rv = reserve_buf(buf, len, encoder->ctx.mem);
  if (rv != 0) {
    return rv;
  }

  p = buf->last;

  *p = fb;
  if (nh) {
    *p |= (uint8_t)(1 << prefix);
    p = nghttp3_qpack_put_varint(p, nhlen, prefix);
    p = nghttp3_qpack_huffman_encode(p, nv->name, nv->namelen);
  } else {
    p = nghttp3_qpack_put_varint(p, nv->namelen, prefix);
    if (nv->namelen) {
      p = nghttp3_cpymem(p, nv->name, nv->namelen);
    }
  }

  *p = 0;

  if (vh) {
    *p |= 0x80;
    p = nghttp3_qpack_put_varint(p, vhlen, 7);
    p = nghttp3_qpack_huffman_encode(p, nv->value, nv->valuelen);
  } else {
    p = nghttp3_qpack_put_varint(p, nv->valuelen, 7);
    if (nv->valuelen) {
      p = nghttp3_cpymem(p, nv->value, nv->valuelen);
    }
  }

  assert((size_t)(p - buf->last) == len);

  buf->last = p;

  return 0;
}

int nghttp3_qpack_encoder_write_literal(nghttp3_qpack_encoder *encoder,
                                        nghttp3_buf *rbuf,
                                        const nghttp3_nv *nv) {
  uint8_t fb =
    (uint8_t)(0x20 | ((nv->flags & NGHTTP3_NV_FLAG_NEVER_INDEX) ? 0x10 : 0));

  DEBUGF("qpack::encode: Literal Field Line With Literal Name\n");
  return qpack_encoder_write_literal(encoder, rbuf, fb, 3, nv);
}

int nghttp3_qpack_encoder_write_static_insert(nghttp3_qpack_encoder *encoder,
                                              nghttp3_buf *ebuf,
                                              uint64_t absidx,
                                              const nghttp3_nv *nv) {
  DEBUGF("qpack::encode: Insert With Name Reference (static) absidx=%" PRIu64
         "\n",
         absidx);
  return qpack_encoder_write_indexed_name(encoder, ebuf, 0xc0, absidx, 6, nv);
}

int nghttp3_qpack_encoder_write_dynamic_insert(nghttp3_qpack_encoder *encoder,
                                               nghttp3_buf *ebuf,
                                               uint64_t absidx,
                                               const nghttp3_nv *nv) {
  DEBUGF("qpack::encode: Insert With Name Reference (dynamic) absidx=%" PRIu64
         "\n",
         absidx);
  return qpack_encoder_write_indexed_name(
    encoder, ebuf, 0x80, encoder->ctx.next_absidx - absidx - 1, 6, nv);
}

int nghttp3_qpack_encoder_write_duplicate_insert(nghttp3_qpack_encoder *encoder,
                                                 nghttp3_buf *ebuf,
                                                 uint64_t absidx) {
  uint64_t idx = encoder->ctx.next_absidx - absidx - 1;
  size_t len = nghttp3_qpack_put_varint_len(idx, 5);
  uint8_t *p;
  int rv;

  DEBUGF("qpack::encode: Insert duplicate absidx=%" PRIu64 "\n", absidx);

  rv = reserve_buf(ebuf, len, encoder->ctx.mem);
  if (rv != 0) {
    return rv;
  }

  p = ebuf->last;

  *p = 0;
  p = nghttp3_qpack_put_varint(p, idx, 5);

  assert((size_t)(p - ebuf->last) == len);

  ebuf->last = p;

  return 0;
}

int nghttp3_qpack_encoder_write_literal_insert(nghttp3_qpack_encoder *encoder,
                                               nghttp3_buf *ebuf,
                                               const nghttp3_nv *nv) {
  DEBUGF("qpack::encode: Insert With Literal Name\n");
  return qpack_encoder_write_literal(encoder, ebuf, 0x40, 5, nv);
}

int nghttp3_qpack_context_dtable_add(nghttp3_qpack_context *ctx,
                                     nghttp3_qpack_nv *qnv,
                                     nghttp3_qpack_map *dtable_map,
                                     uint32_t hash) {
  nghttp3_qpack_entry *new_ent, **p, *ent;
  const nghttp3_mem *mem = ctx->mem;
  size_t space;
  size_t i;
  int rv;

  space = table_space(qnv->name->len, qnv->value->len);

  assert(space <= ctx->max_dtable_capacity);

  while (ctx->dtable_size + space > ctx->max_dtable_capacity) {
    i = nghttp3_ringbuf_len(&ctx->dtable);
    assert(i);
    ent = *(nghttp3_qpack_entry **)nghttp3_ringbuf_get(&ctx->dtable, i - 1);

    ctx->dtable_size -= table_space(ent->nv.name->len, ent->nv.value->len);

    nghttp3_ringbuf_pop_back(&ctx->dtable);
    if (dtable_map) {
      qpack_map_remove(dtable_map, ent);
    }

    nghttp3_qpack_entry_free(ent);
    nghttp3_mem_free(mem, ent);
  }

  new_ent = nghttp3_mem_malloc(mem, sizeof(nghttp3_qpack_entry));
  if (new_ent == NULL) {
    return NGHTTP3_ERR_NOMEM;
  }

  nghttp3_qpack_entry_init(new_ent, qnv, ctx->dtable_sum, ctx->next_absidx++,
                           hash);

  if (nghttp3_ringbuf_full(&ctx->dtable)) {
    rv = nghttp3_ringbuf_reserve(&ctx->dtable,
                                 nghttp3_ringbuf_len(&ctx->dtable) * 2);
    if (rv != 0) {
      goto fail;
    }
  }

  p = nghttp3_ringbuf_push_front(&ctx->dtable);
  *p = new_ent;

  if (dtable_map) {
    qpack_map_insert(dtable_map, new_ent);
  }

  ctx->dtable_size += space;
  ctx->dtable_sum += space;

  return 0;

fail:
  nghttp3_qpack_entry_free(new_ent);
  nghttp3_mem_free(mem, new_ent);

  return rv;
}

int nghttp3_qpack_encoder_dtable_static_add(nghttp3_qpack_encoder *encoder,
                                            uint64_t absidx,
                                            const nghttp3_nv *nv,
                                            uint32_t hash) {
  const nghttp3_qpack_static_header *shd;
  nghttp3_qpack_nv qnv;
  const nghttp3_mem *mem = encoder->ctx.mem;
  int rv;

  rv = nghttp3_rcbuf_new2(&qnv.value, nv->value, nv->valuelen, mem);
  if (rv != 0) {
    return rv;
  }

  assert(nghttp3_arraylen(stable) > absidx);

  shd = &stable[absidx];

  qnv.name = (nghttp3_rcbuf *)&shd->name;
  qnv.token = shd->token;
  qnv.flags = NGHTTP3_NV_FLAG_NONE;

  rv = nghttp3_qpack_context_dtable_add(&encoder->ctx, &qnv,
                                        &encoder->dtable_map, hash);

  nghttp3_rcbuf_decref(qnv.value);

  return rv;
}

int nghttp3_qpack_encoder_dtable_dynamic_add(nghttp3_qpack_encoder *encoder,
                                             uint64_t absidx,
                                             const nghttp3_nv *nv,
                                             uint32_t hash) {
  nghttp3_qpack_nv qnv;
  nghttp3_qpack_entry *ent;
  const nghttp3_mem *mem = encoder->ctx.mem;
  int rv;

  rv = nghttp3_rcbuf_new2(&qnv.value, nv->value, nv->valuelen, mem);
  if (rv != 0) {
    return rv;
  }

  ent = nghttp3_qpack_context_dtable_get(&encoder->ctx, absidx);

  qnv.name = ent->nv.name;
  qnv.token = ent->nv.token;
  qnv.flags = NGHTTP3_NV_FLAG_NONE;

  nghttp3_rcbuf_incref(qnv.name);

  rv = nghttp3_qpack_context_dtable_add(&encoder->ctx, &qnv,
                                        &encoder->dtable_map, hash);

  nghttp3_rcbuf_decref(qnv.value);
  nghttp3_rcbuf_decref(qnv.name);

  return rv;
}

int nghttp3_qpack_encoder_dtable_duplicate_add(nghttp3_qpack_encoder *encoder,
                                               uint64_t absidx) {
  nghttp3_qpack_nv qnv;
  nghttp3_qpack_entry *ent;
  int rv;

  ent = nghttp3_qpack_context_dtable_get(&encoder->ctx, absidx);

  qnv = ent->nv;
  nghttp3_rcbuf_incref(qnv.name);
  nghttp3_rcbuf_incref(qnv.value);

  rv = nghttp3_qpack_context_dtable_add(&encoder->ctx, &qnv,
                                        &encoder->dtable_map, ent->hash);

  nghttp3_rcbuf_decref(qnv.name);
  nghttp3_rcbuf_decref(qnv.value);

  return rv;
}

int nghttp3_qpack_encoder_dtable_literal_add(nghttp3_qpack_encoder *encoder,
                                             const nghttp3_nv *nv,
                                             int32_t token, uint32_t hash) {
  nghttp3_qpack_nv qnv;
  const nghttp3_mem *mem = encoder->ctx.mem;
  int rv;

  rv = nghttp3_rcbuf_new2(&qnv.name, nv->name, nv->namelen, mem);
  if (rv != 0) {
    return rv;
  }

  rv = nghttp3_rcbuf_new2(&qnv.value, nv->value, nv->valuelen, mem);
  if (rv != 0) {
    nghttp3_rcbuf_decref(qnv.name);
    return rv;
  }

  qnv.token = token;
  qnv.flags = NGHTTP3_NV_FLAG_NONE;

  rv = nghttp3_qpack_context_dtable_add(&encoder->ctx, &qnv,
                                        &encoder->dtable_map, hash);

  nghttp3_rcbuf_decref(qnv.value);
  nghttp3_rcbuf_decref(qnv.name);

  return rv;
}

nghttp3_qpack_entry *
nghttp3_qpack_context_dtable_get(nghttp3_qpack_context *ctx, uint64_t absidx) {
  size_t relidx;

  assert(ctx->next_absidx > absidx);
  assert(ctx->next_absidx - absidx - 1 < nghttp3_ringbuf_len(&ctx->dtable));

  relidx = (size_t)(ctx->next_absidx - absidx - 1);

  return *(nghttp3_qpack_entry **)nghttp3_ringbuf_get(&ctx->dtable, relidx);
}

nghttp3_qpack_entry *
nghttp3_qpack_context_dtable_top(nghttp3_qpack_context *ctx) {
  assert(nghttp3_ringbuf_len(&ctx->dtable));
  return *(nghttp3_qpack_entry **)nghttp3_ringbuf_get(&ctx->dtable, 0);
}

void nghttp3_qpack_entry_init(nghttp3_qpack_entry *ent, nghttp3_qpack_nv *qnv,
                              size_t sum, uint64_t absidx, uint32_t hash) {
  ent->nv = *qnv;
  ent->map_next = NULL;
  ent->sum = sum;
  ent->absidx = absidx;
  ent->hash = hash;

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

void nghttp3_qpack_entry_free(nghttp3_qpack_entry *ent) {
  nghttp3_rcbuf_decref(ent->nv.value);
  nghttp3_rcbuf_decref(ent->nv.name);
}

int nghttp3_qpack_encoder_block_stream(nghttp3_qpack_encoder *encoder,
                                       nghttp3_qpack_stream *stream) {
  nghttp3_blocked_streams_key bsk = {
    nghttp3_struct_of(nghttp3_pq_top(&stream->max_cnts),
                      nghttp3_qpack_header_block_ref, max_cnts_pe)
      ->max_cnt,
    (uint64_t)stream->stream_id};

  return nghttp3_ksl_insert(&encoder->blocked_streams, NULL, &bsk, stream);
}

void nghttp3_qpack_encoder_unblock_stream(nghttp3_qpack_encoder *encoder,
                                          nghttp3_qpack_stream *stream) {
  nghttp3_blocked_streams_key bsk = {
    nghttp3_struct_of(nghttp3_pq_top(&stream->max_cnts),
                      nghttp3_qpack_header_block_ref, max_cnts_pe)
      ->max_cnt,
    (uint64_t)stream->stream_id};
  nghttp3_ksl_it it;

  /* This is purely debugging purpose only */
  it = nghttp3_ksl_lower_bound(&encoder->blocked_streams, &bsk);

  assert(!nghttp3_ksl_it_end(&it));
  assert(nghttp3_ksl_it_get(&it) == stream);

  nghttp3_ksl_remove_hint(&encoder->blocked_streams, NULL, &it, &bsk);
}

void nghttp3_qpack_encoder_unblock(nghttp3_qpack_encoder *encoder,
                                   uint64_t max_cnt) {
  nghttp3_blocked_streams_key bsk = {max_cnt, 0};
  nghttp3_ksl_it it;

  it = nghttp3_ksl_lower_bound(&encoder->blocked_streams, &bsk);

  for (; !nghttp3_ksl_it_end(&it);) {
    bsk = *(nghttp3_blocked_streams_key *)nghttp3_ksl_it_key(&it);
    nghttp3_ksl_remove_hint(&encoder->blocked_streams, &it, &it, &bsk);
  }
}

int nghttp3_qpack_encoder_ack_header(nghttp3_qpack_encoder *encoder,
                                     int64_t stream_id) {
  nghttp3_qpack_stream *stream =
    nghttp3_qpack_encoder_find_stream(encoder, stream_id);
  const nghttp3_mem *mem = encoder->ctx.mem;
  nghttp3_qpack_header_block_ref *ref;

  if (stream == NULL) {
    return NGHTTP3_ERR_QPACK_DECODER_STREAM_ERROR;
  }

  assert(nghttp3_ringbuf_len(&stream->refs));

  ref =
    *(nghttp3_qpack_header_block_ref **)nghttp3_ringbuf_get(&stream->refs, 0);

  DEBUGF("qpack::encoder: Header acknowledgement stream=%ld ricnt=%" PRIu64
         " krcnt=%" PRIu64 "\n",
         stream_id, ref->max_cnt, encoder->krcnt);

  if (encoder->krcnt < ref->max_cnt) {
    encoder->krcnt = ref->max_cnt;

    nghttp3_qpack_encoder_unblock(encoder, ref->max_cnt);
  }

  nghttp3_qpack_stream_pop_ref(stream);

  assert(ref->min_cnts_pe.index != NGHTTP3_PQ_BAD_INDEX);

  nghttp3_pq_remove(&encoder->min_cnts, &ref->min_cnts_pe);

  nghttp3_qpack_header_block_ref_del(ref, mem);

  if (nghttp3_ringbuf_len(&stream->refs)) {
    return 0;
  }

  qpack_encoder_remove_stream(encoder, stream);

  nghttp3_qpack_stream_del(stream, mem);

  return 0;
}

int nghttp3_qpack_encoder_add_icnt(nghttp3_qpack_encoder *encoder, uint64_t n) {
  if (n == 0 || encoder->ctx.next_absidx - encoder->krcnt < n) {
    return NGHTTP3_ERR_QPACK_DECODER_STREAM_ERROR;
  }
  encoder->krcnt += n;

  nghttp3_qpack_encoder_unblock(encoder, encoder->krcnt);

  return 0;
}

void nghttp3_qpack_encoder_ack_everything(nghttp3_qpack_encoder *encoder) {
  encoder->krcnt = encoder->ctx.next_absidx;

  nghttp3_ksl_clear(&encoder->blocked_streams);
  nghttp3_pq_clear(&encoder->min_cnts);
  nghttp3_map_each(&encoder->streams, map_stream_free,
                   (void *)encoder->ctx.mem);
  nghttp3_map_clear(&encoder->streams);
}

void nghttp3_qpack_encoder_cancel_stream(nghttp3_qpack_encoder *encoder,
                                         int64_t stream_id) {
  nghttp3_qpack_stream *stream =
    nghttp3_qpack_encoder_find_stream(encoder, stream_id);
  const nghttp3_mem *mem = encoder->ctx.mem;

  if (stream == NULL) {
    return;
  }

  if (nghttp3_qpack_encoder_stream_is_blocked(encoder, stream)) {
    nghttp3_qpack_encoder_unblock_stream(encoder, stream);
  }

  qpack_encoder_remove_stream(encoder, stream);

  nghttp3_qpack_stream_del(stream, mem);
}

size_t
nghttp3_qpack_encoder_get_num_blocked_streams(nghttp3_qpack_encoder *encoder) {
  return nghttp3_ksl_len(&encoder->blocked_streams);
}

int nghttp3_qpack_encoder_write_field_section_prefix(
  nghttp3_qpack_encoder *encoder, nghttp3_buf *pbuf, uint64_t ricnt,
  uint64_t base) {
  size_t max_ents =
    encoder->ctx.hard_max_dtable_capacity / NGHTTP3_QPACK_ENTRY_OVERHEAD;
  uint64_t encricnt = ricnt == 0 ? 0 : (ricnt % (2 * max_ents)) + 1;
  int sign = base < ricnt;
  uint64_t delta_base = sign ? ricnt - base - 1 : base - ricnt;
  size_t len = nghttp3_qpack_put_varint_len(encricnt, 8) +
               nghttp3_qpack_put_varint_len(delta_base, 7);
  uint8_t *p;
  int rv;

  DEBUGF("qpack::encode: ricnt=%" PRIu64 " base=%" PRIu64 " icnt=%" PRIu64 "\n",
         ricnt, base, encoder->ctx.next_absidx);

  rv = reserve_buf(pbuf, len, encoder->ctx.mem);
  if (rv != 0) {
    return rv;
  }

  p = pbuf->last;

  p = nghttp3_qpack_put_varint(p, encricnt, 8);
  if (sign) {
    *p = 0x80;
  } else {
    *p = 0;
  }
  p = nghttp3_qpack_put_varint(p, delta_base, 7);

  assert((size_t)(p - pbuf->last) == len);

  pbuf->last = p;

  return 0;
}

/*
 * qpack_read_varint reads |rstate->prefix| prefixed integer stored
 * from |begin|.  The |end| represents the 1 beyond the last of the
 * valid contiguous memory region from |begin|.  The decoded integer
 * must be less than or equal to NGHTTP3_QPACK_INT_MAX.
 *
 * If the |rstate->left| is nonzero, it is used as an initial value,
 * and this function assumes the |begin| starts with intermediate
 * data.  |rstate->shift| is used as initial integer shift.
 *
 * If an entire integer is decoded successfully, the |*fin| is set to
 * nonzero.
 *
 * This function stores the decoded integer in |rstate->left| if it
 * succeeds, including partial decoding (in this case, number of shift
 * to make in the next call will be stored in |rstate->shift|) and
 * returns number of bytes processed, or returns negative error code
 * NGHTTP3_ERR_QPACK_FATAL, indicating decoding error.
 */
static nghttp3_ssize qpack_read_varint(int *fin,
                                       nghttp3_qpack_read_state *rstate,
                                       const uint8_t *begin,
                                       const uint8_t *end) {
  uint64_t k = (uint8_t)((1 << rstate->prefix) - 1);
  uint64_t n = rstate->left;
  uint64_t add;
  const uint8_t *p = begin;
  size_t shift = rstate->shift;

  rstate->shift = 0;
  *fin = 0;

  if (n == 0) {
    if (((*p) & k) != k) {
      rstate->left = (*p) & k;
      *fin = 1;
      return 1;
    }

    n = k;

    if (++p == end) {
      rstate->left = n;
      return (nghttp3_ssize)(p - begin);
    }
  }

  for (; p != end; ++p, shift += 7) {
    add = (*p) & 0x7f;

    if (shift > 62) {
      return NGHTTP3_ERR_QPACK_FATAL;
    }

    if ((NGHTTP3_QPACK_INT_MAX >> shift) < add) {
      return NGHTTP3_ERR_QPACK_FATAL;
    }

    add <<= shift;

    if (NGHTTP3_QPACK_INT_MAX - add < n) {
      return NGHTTP3_ERR_QPACK_FATAL;
    }

    n += add;

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

  rstate->shift = shift;

  if (p == end) {
    rstate->left = n;
    return (nghttp3_ssize)(p - begin);
  }

  rstate->left = n;
  *fin = 1;
  return (nghttp3_ssize)(p + 1 - begin);
}

nghttp3_ssize nghttp3_qpack_encoder_read_decoder(nghttp3_qpack_encoder *encoder,
                                                 const uint8_t *src,
                                                 size_t srclen) {
  const uint8_t *p = src, *end;
  int rv;
  nghttp3_ssize nread;
  int rfin;

  if (encoder->ctx.bad) {
    return NGHTTP3_ERR_QPACK_FATAL;
  }

  if (srclen == 0) {
    return 0;
  }

  encoder->uninterrupted_decoderlen += srclen;
  if (encoder->uninterrupted_decoderlen > NGHTTP3_QPACK_MAX_DECODERLEN) {
    return NGHTTP3_ERR_QPACK_DECODER_STREAM_ERROR;
  }

  end = src + srclen;

  for (; p != end;) {
    switch (encoder->state) {
    case NGHTTP3_QPACK_DS_STATE_OPCODE:
      switch ((*p) & 0xc0) {
      case 0x80:
      case 0xc0:
        DEBUGF("qpack::encode: OPCODE_SECTION_ACK\n");
        encoder->opcode = NGHTTP3_QPACK_DS_OPCODE_SECTION_ACK;
        encoder->rstate.prefix = 7;

        break;
      case 0x40:
        DEBUGF("qpack::encode: OPCODE_STREAM_CANCEL\n");
        encoder->opcode = NGHTTP3_QPACK_DS_OPCODE_STREAM_CANCEL;
        encoder->rstate.prefix = 6;

        break;
      default:
        DEBUGF("qpack::encode: OPCODE_ICNT_INCREMENT\n");
        encoder->opcode = NGHTTP3_QPACK_DS_OPCODE_ICNT_INCREMENT;
        encoder->rstate.prefix = 6;
      }
      encoder->state = NGHTTP3_QPACK_DS_STATE_READ_NUMBER;
      /* fall through */
    case NGHTTP3_QPACK_DS_STATE_READ_NUMBER:
      nread = qpack_read_varint(&rfin, &encoder->rstate, p, end);
      if (nread < 0) {
        assert(nread == NGHTTP3_ERR_QPACK_FATAL);
        rv = NGHTTP3_ERR_QPACK_DECODER_STREAM_ERROR;
        goto fail;
      }

      p += nread;

      if (!rfin) {
        return p - src;
      }

      switch (encoder->opcode) {
      case NGHTTP3_QPACK_DS_OPCODE_ICNT_INCREMENT:
        rv = nghttp3_qpack_encoder_add_icnt(encoder, encoder->rstate.left);
        if (rv != 0) {
          goto fail;
        }
        break;
      case NGHTTP3_QPACK_DS_OPCODE_SECTION_ACK:
        rv = nghttp3_qpack_encoder_ack_header(encoder,
                                              (int64_t)encoder->rstate.left);
        if (rv != 0) {
          goto fail;
        }
        break;
      case NGHTTP3_QPACK_DS_OPCODE_STREAM_CANCEL:
        nghttp3_qpack_encoder_cancel_stream(encoder,
                                            (int64_t)encoder->rstate.left);
        break;
      default:
        nghttp3_unreachable();
      }

      encoder->state = NGHTTP3_QPACK_DS_STATE_OPCODE;
      nghttp3_qpack_read_state_reset(&encoder->rstate);
      break;
    default:
      nghttp3_unreachable();
    }
  }

  return p - src;

fail:
  encoder->ctx.bad = 1;
  return rv;
}

size_t nghttp3_qpack_put_varint_len(uint64_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;
}

uint8_t *nghttp3_qpack_put_varint(uint8_t *buf, uint64_t n, size_t prefix) {
  size_t k = (size_t)((1 << prefix) - 1);

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

  if (n < k) {
    *buf = (uint8_t)(*buf | n);
    return buf + 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 buf;
}

void nghttp3_qpack_read_state_free(nghttp3_qpack_read_state *rstate) {
  nghttp3_rcbuf_decref(rstate->value);
  nghttp3_rcbuf_decref(rstate->name);
}

void nghttp3_qpack_read_state_reset(nghttp3_qpack_read_state *rstate) {
  rstate->name = NULL;
  rstate->value = NULL;
  nghttp3_buf_init(&rstate->namebuf);
  nghttp3_buf_init(&rstate->valuebuf);
  rstate->left = 0;
  rstate->prefix = 0;
  rstate->shift = 0;
  rstate->absidx = 0;
  rstate->never = 0;
  rstate->dynamic = 0;
  rstate->huffman_encoded = 0;
}

int nghttp3_qpack_decoder_init(nghttp3_qpack_decoder *decoder,
                               size_t hard_max_dtable_capacity,
                               size_t max_blocked_streams,
                               const nghttp3_mem *mem) {
  int rv;

  rv = qpack_context_init(&decoder->ctx, hard_max_dtable_capacity,
                          max_blocked_streams, mem);
  if (rv != 0) {
    return rv;
  }

  decoder->state = NGHTTP3_QPACK_ES_STATE_OPCODE;
  decoder->opcode = 0;
  decoder->written_icnt = 0;
  decoder->max_concurrent_streams = 0;
  decoder->uninterrupted_encoderlen = 0;

  nghttp3_qpack_read_state_reset(&decoder->rstate);
  nghttp3_buf_init(&decoder->dbuf);

  return 0;
}

void nghttp3_qpack_decoder_free(nghttp3_qpack_decoder *decoder) {
  nghttp3_buf_free(&decoder->dbuf, decoder->ctx.mem);
  nghttp3_qpack_read_state_free(&decoder->rstate);
  qpack_context_free(&decoder->ctx);
}

/*
 * qpack_read_huffman_string decodes huffman string in buffer [begin,
 * end) and writes the decoded string to |dest|.  This function
 * assumes the buffer pointed by |dest| has enough space.
 *
 * This function returns 0 if it succeeds, or one of the following
 * negative error codes:
 *
 * NGHTTP3_ERR_QPACK_FATAL
 *     Could not decode huffman string.
 */
static nghttp3_ssize qpack_read_huffman_string(nghttp3_qpack_read_state *rstate,
                                               nghttp3_buf *dest,
                                               const uint8_t *begin,
                                               const uint8_t *end) {
  nghttp3_ssize nwrite;
  size_t len = (size_t)(end - begin);
  int fin = 0;

  if (len >= rstate->left) {
    len = (size_t)rstate->left;
    fin = 1;
  }

  nwrite = nghttp3_qpack_huffman_decode(&rstate->huffman_ctx, dest->last, begin,
                                        len, fin);
  if (nwrite < 0) {
    return nwrite;
  }

  if (nghttp3_qpack_huffman_decode_failure_state(&rstate->huffman_ctx)) {
    return NGHTTP3_ERR_QPACK_FATAL;
  }

  dest->last += nwrite;
  rstate->left -= len;
  return (nghttp3_ssize)len;
}

static nghttp3_ssize qpack_read_string(nghttp3_qpack_read_state *rstate,
                                       nghttp3_buf *dest, const uint8_t *begin,
                                       const uint8_t *end) {
  size_t len = (size_t)(end - begin);
  size_t n = (size_t)nghttp3_min_uint64((uint64_t)len, rstate->left);

  dest->last = nghttp3_cpymem(dest->last, begin, n);

  rstate->left -= n;
  return (nghttp3_ssize)n;
}

/*
 * qpack_decoder_validate_index checks rstate->absidx is acceptable.
 *
 * It returns 0 if it succeeds, or one of the following negative error
 * codes:
 *
 * NGHTTP3_ERR_QPACK_FATAL
 *     rstate->absidx is invalid.
 */
static int qpack_decoder_validate_index(nghttp3_qpack_decoder *decoder,
                                        nghttp3_qpack_read_state *rstate) {
  if (rstate->dynamic) {
    return rstate->absidx < decoder->ctx.next_absidx &&
               decoder->ctx.next_absidx - rstate->absidx - 1 <
                 nghttp3_ringbuf_len(&decoder->ctx.dtable)
             ? 0
             : NGHTTP3_ERR_QPACK_FATAL;
  }
  return rstate->absidx < nghttp3_arraylen(stable) ? 0
                                                   : NGHTTP3_ERR_QPACK_FATAL;
}

static void qpack_read_state_check_huffman(nghttp3_qpack_read_state *rstate,
                                           const uint8_t b) {
  rstate->huffman_encoded = (b & (1 << rstate->prefix)) != 0;
}

static void qpack_read_state_terminate_name(nghttp3_qpack_read_state *rstate) {
  *rstate->namebuf.last = '\0';
  rstate->name->len = nghttp3_buf_len(&rstate->namebuf);
}

static void qpack_read_state_terminate_value(nghttp3_qpack_read_state *rstate) {
  *rstate->valuebuf.last = '\0';
  rstate->value->len = nghttp3_buf_len(&rstate->valuebuf);
}

nghttp3_ssize nghttp3_qpack_decoder_read_encoder(nghttp3_qpack_decoder *decoder,
                                                 const uint8_t *src,
                                                 size_t srclen) {
  const uint8_t *p = src, *end;
  int rv;
  int busy = 0;
  const nghttp3_mem *mem = decoder->ctx.mem;
  nghttp3_ssize nread;
  int rfin;

  if (decoder->ctx.bad) {
    return NGHTTP3_ERR_QPACK_FATAL;
  }

  if (srclen == 0) {
    return 0;
  }

  decoder->uninterrupted_encoderlen += srclen;
  if (decoder->uninterrupted_encoderlen > NGHTTP3_QPACK_MAX_ENCODERLEN) {
    return NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR;
  }

  end = src + srclen;

  for (; p != end || busy;) {
    busy = 0;
    switch (decoder->state) {
    case NGHTTP3_QPACK_ES_STATE_OPCODE:
      switch ((*p) & 0xe0) {
      case 0x80:
      case 0xa0:
      case 0xc0:
      case 0xe0:
        DEBUGF("qpack::decode: OPCODE_INSERT_INDEXED\n");
        decoder->opcode = NGHTTP3_QPACK_ES_OPCODE_INSERT_INDEXED;
        decoder->rstate.dynamic = !((*p) & 0x40);
        decoder->rstate.prefix = 6;
        decoder->state = NGHTTP3_QPACK_ES_STATE_READ_INDEX;

        break;
      case 0x40:
      case 0x60:
        DEBUGF("qpack::decode: OPCODE_INSERT\n");
        decoder->opcode = NGHTTP3_QPACK_ES_OPCODE_INSERT;
        decoder->rstate.dynamic = 0;
        decoder->rstate.prefix = 5;
        decoder->state = NGHTTP3_QPACK_ES_STATE_CHECK_NAME_HUFFMAN;

        break;
      case 0x20:
        DEBUGF("qpack::decode: OPCODE_SET_DTABLE_TABLE_CAP\n");
        decoder->opcode = NGHTTP3_QPACK_ES_OPCODE_SET_DTABLE_CAP;
        decoder->rstate.prefix = 5;
        decoder->state = NGHTTP3_QPACK_ES_STATE_READ_INDEX;

        break;
      default:
        DEBUGF("qpack::decode: OPCODE_DUPLICATE\n");
        decoder->opcode = NGHTTP3_QPACK_ES_OPCODE_DUPLICATE;
        decoder->rstate.dynamic = 1;
        decoder->rstate.prefix = 5;
        decoder->state = NGHTTP3_QPACK_ES_STATE_READ_INDEX;
      }
      break;
    case NGHTTP3_QPACK_ES_STATE_READ_INDEX:
      nread = qpack_read_varint(&rfin, &decoder->rstate, p, end);
      if (nread < 0) {
        assert(NGHTTP3_ERR_QPACK_FATAL == nread);
        rv = NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR;
        goto fail;
      }

      p += nread;

      if (!rfin) {
        return p - src;
      }

      if (decoder->opcode == NGHTTP3_QPACK_ES_OPCODE_SET_DTABLE_CAP) {
        DEBUGF("qpack::decode: Set dtable capacity to %" PRIu64 "\n",
               decoder->rstate.left);
        rv = nghttp3_qpack_decoder_set_max_dtable_capacity(
          decoder, (size_t)decoder->rstate.left);
        if (rv != 0) {
          rv = NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR;
          goto fail;
        }

        decoder->state = NGHTTP3_QPACK_ES_STATE_OPCODE;
        nghttp3_qpack_read_state_reset(&decoder->rstate);
        break;
      }

      rv = nghttp3_qpack_decoder_rel2abs(decoder, &decoder->rstate);
      if (rv < 0) {
        goto fail;
      }

      switch (decoder->opcode) {
      case NGHTTP3_QPACK_ES_OPCODE_DUPLICATE:
        rv = nghttp3_qpack_decoder_dtable_duplicate_add(decoder);
        if (rv != 0) {
          goto fail;
        }

        decoder->state = NGHTTP3_QPACK_ES_STATE_OPCODE;
        nghttp3_qpack_read_state_reset(&decoder->rstate);

        break;
      case NGHTTP3_QPACK_ES_OPCODE_INSERT_INDEXED:
        decoder->rstate.prefix = 7;
        decoder->state = NGHTTP3_QPACK_ES_STATE_CHECK_VALUE_HUFFMAN;

        break;
      default:
        nghttp3_unreachable();
      }

      break;
    case NGHTTP3_QPACK_ES_STATE_CHECK_NAME_HUFFMAN:
      qpack_read_state_check_huffman(&decoder->rstate, *p);
      decoder->state = NGHTTP3_QPACK_ES_STATE_READ_NAMELEN;
      decoder->rstate.left = 0;
      decoder->rstate.shift = 0;
      /* Fall through */
    case NGHTTP3_QPACK_ES_STATE_READ_NAMELEN:
      nread = qpack_read_varint(&rfin, &decoder->rstate, p, end);
      if (nread < 0) {
        assert(NGHTTP3_ERR_QPACK_FATAL == nread);
        rv = NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR;
        goto fail;
      }

      p += nread;

      if (!rfin) {
        return p - src;
      }

      if (decoder->rstate.left > NGHTTP3_QPACK_MAX_NAMELEN) {
        rv = NGHTTP3_ERR_QPACK_HEADER_TOO_LARGE;
        goto fail;
      }

      if (decoder->rstate.huffman_encoded) {
        decoder->state = NGHTTP3_QPACK_ES_STATE_READ_NAME_HUFFMAN;
        nghttp3_qpack_huffman_decode_context_init(&decoder->rstate.huffman_ctx);
        rv = nghttp3_rcbuf_new(&decoder->rstate.name,
                               (size_t)decoder->rstate.left * 2 + 1, mem);
      } else {
        decoder->state = NGHTTP3_QPACK_ES_STATE_READ_NAME;
        rv = nghttp3_rcbuf_new(&decoder->rstate.name,
                               (size_t)decoder->rstate.left + 1, mem);
      }
      if (rv != 0) {
        goto fail;
      }

      nghttp3_buf_wrap_init(&decoder->rstate.namebuf,
                            decoder->rstate.name->base,
                            decoder->rstate.name->len);
      break;
    case NGHTTP3_QPACK_ES_STATE_READ_NAME_HUFFMAN:
      nread = qpack_read_huffman_string(&decoder->rstate,
                                        &decoder->rstate.namebuf, p, end);
      if (nread < 0) {
        assert(NGHTTP3_ERR_QPACK_FATAL == nread);
        rv = NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR;
        goto fail;
      }

      p += nread;

      if (decoder->rstate.left) {
        return p - src;
      }

      qpack_read_state_terminate_name(&decoder->rstate);

      decoder->state = NGHTTP3_QPACK_ES_STATE_CHECK_VALUE_HUFFMAN;
      decoder->rstate.prefix = 7;
      break;
    case NGHTTP3_QPACK_ES_STATE_READ_NAME:
      nread =
        qpack_read_string(&decoder->rstate, &decoder->rstate.namebuf, p, end);
      if (nread < 0) {
        rv = (int)nread;
        goto fail;
      }

      p += nread;

      if (decoder->rstate.left) {
        return p - src;
      }

      qpack_read_state_terminate_name(&decoder->rstate);

      decoder->state = NGHTTP3_QPACK_ES_STATE_CHECK_VALUE_HUFFMAN;
      decoder->rstate.prefix = 7;
      break;
    case NGHTTP3_QPACK_ES_STATE_CHECK_VALUE_HUFFMAN:
      qpack_read_state_check_huffman(&decoder->rstate, *p);
      decoder->state = NGHTTP3_QPACK_ES_STATE_READ_VALUELEN;
      decoder->rstate.left = 0;
      decoder->rstate.shift = 0;
      /* Fall through */
    case NGHTTP3_QPACK_ES_STATE_READ_VALUELEN:
      nread = qpack_read_varint(&rfin, &decoder->rstate, p, end);
      if (nread < 0) {
        assert(NGHTTP3_ERR_QPACK_FATAL == nread);
        rv = NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR;
        goto fail;
      }

      p += nread;

      if (!rfin) {
        return p - src;
      }

      if (decoder->rstate.left > NGHTTP3_QPACK_MAX_VALUELEN) {
        rv = NGHTTP3_ERR_QPACK_HEADER_TOO_LARGE;
        goto fail;
      }

      if (decoder->rstate.huffman_encoded) {
        decoder->state = NGHTTP3_QPACK_ES_STATE_READ_VALUE_HUFFMAN;
        nghttp3_qpack_huffman_decode_context_init(&decoder->rstate.huffman_ctx);
        rv = nghttp3_rcbuf_new(&decoder->rstate.value,
                               (size_t)decoder->rstate.left * 2 + 1, mem);
      } else {
        decoder->state = NGHTTP3_QPACK_ES_STATE_READ_VALUE;
        rv = nghttp3_rcbuf_new(&decoder->rstate.value,
                               (size_t)decoder->rstate.left + 1, mem);
      }
      if (rv != 0) {
        goto fail;
      }

      nghttp3_buf_wrap_init(&decoder->rstate.valuebuf,
                            decoder->rstate.value->base,
                            decoder->rstate.value->len);

      /* value might be 0 length */
      busy = 1;
      break;
    case NGHTTP3_QPACK_ES_STATE_READ_VALUE_HUFFMAN:
      nread = qpack_read_huffman_string(&decoder->rstate,
                                        &decoder->rstate.valuebuf, p, end);
      if (nread < 0) {
        assert(NGHTTP3_ERR_QPACK_FATAL == nread);
        rv = NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR;
        goto fail;
      }

      p += nread;

      if (decoder->rstate.left) {
        return p - src;
      }

      qpack_read_state_terminate_value(&decoder->rstate);

      switch (decoder->opcode) {
      case NGHTTP3_QPACK_ES_OPCODE_INSERT_INDEXED:
        rv = nghttp3_qpack_decoder_dtable_indexed_add(decoder);
        break;
      case NGHTTP3_QPACK_ES_OPCODE_INSERT:
        rv = nghttp3_qpack_decoder_dtable_literal_add(decoder);
        break;
      default:
        nghttp3_unreachable();
      }
      if (rv != 0) {
        goto fail;
      }

      decoder->state = NGHTTP3_QPACK_ES_STATE_OPCODE;
      nghttp3_qpack_read_state_reset(&decoder->rstate);
      break;
    case NGHTTP3_QPACK_ES_STATE_READ_VALUE:
      nread =
        qpack_read_string(&decoder->rstate, &decoder->rstate.valuebuf, p, end);
      if (nread < 0) {
        rv = (int)nread;
        goto fail;
      }

      p += nread;

      if (decoder->rstate.left) {
        return p - src;
      }

      qpack_read_state_terminate_value(&decoder->rstate);

      switch (decoder->opcode) {
      case NGHTTP3_QPACK_ES_OPCODE_INSERT_INDEXED:
        rv = nghttp3_qpack_decoder_dtable_indexed_add(decoder);
        break;
      case NGHTTP3_QPACK_ES_OPCODE_INSERT:
        rv = nghttp3_qpack_decoder_dtable_literal_add(decoder);
        break;
      default:
        nghttp3_unreachable();
      }
      if (rv != 0) {
        goto fail;
      }

      decoder->state = NGHTTP3_QPACK_ES_STATE_OPCODE;
      nghttp3_qpack_read_state_reset(&decoder->rstate);
      break;
    }
  }

  return p - src;

fail:
  decoder->ctx.bad = 1;
  return rv;
}

int nghttp3_qpack_decoder_set_max_dtable_capacity(
  nghttp3_qpack_decoder *decoder, size_t max_dtable_capacity) {
  nghttp3_qpack_entry *ent;
  size_t i;
  nghttp3_qpack_context *ctx = &decoder->ctx;
  const nghttp3_mem *mem = ctx->mem;

  if (max_dtable_capacity > decoder->ctx.hard_max_dtable_capacity) {
    return NGHTTP3_ERR_INVALID_ARGUMENT;
  }

  ctx->max_dtable_capacity = max_dtable_capacity;

  while (ctx->dtable_size > max_dtable_capacity) {
    i = nghttp3_ringbuf_len(&ctx->dtable);
    assert(i);
    ent = *(nghttp3_qpack_entry **)nghttp3_ringbuf_get(&ctx->dtable, i - 1);

    ctx->dtable_size -= table_space(ent->nv.name->len, ent->nv.value->len);

    nghttp3_ringbuf_pop_back(&ctx->dtable);
    nghttp3_qpack_entry_free(ent);
    nghttp3_mem_free(mem, ent);
  }

  return 0;
}

int nghttp3_qpack_decoder_dtable_indexed_add(nghttp3_qpack_decoder *decoder) {
  DEBUGF("qpack::decode: Insert With Name Reference (%s) absidx=%" PRIu64 ": "
         "value=%*s\n",
         decoder->rstate.dynamic ? "dynamic" : "static", decoder->rstate.absidx,
         (int)decoder->rstate.value->len, decoder->rstate.value->base);

  if (decoder->rstate.dynamic) {
    return nghttp3_qpack_decoder_dtable_dynamic_add(decoder);
  }

  return nghttp3_qpack_decoder_dtable_static_add(decoder);
}

int nghttp3_qpack_decoder_dtable_static_add(nghttp3_qpack_decoder *decoder) {
  nghttp3_qpack_nv qnv;
  int rv;
  const nghttp3_qpack_static_header *shd;

  shd = &stable[decoder->rstate.absidx];

  if (table_space(shd->name.len, decoder->rstate.value->len) >
      decoder->ctx.max_dtable_capacity) {
    return NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR;
  }

  qnv.name = (nghttp3_rcbuf *)&shd->name;
  qnv.value = decoder->rstate.value;
  qnv.token = shd->token;
  qnv.flags = NGHTTP3_NV_FLAG_NONE;

  rv = nghttp3_qpack_context_dtable_add(&decoder->ctx, &qnv, NULL, 0);

  nghttp3_rcbuf_decref(qnv.value);

  return rv;
}

int nghttp3_qpack_decoder_dtable_dynamic_add(nghttp3_qpack_decoder *decoder) {
  nghttp3_qpack_nv qnv;
  int rv;
  nghttp3_qpack_entry *ent;

  ent = nghttp3_qpack_context_dtable_get(&decoder->ctx, decoder->rstate.absidx);

  if (table_space(ent->nv.name->len, decoder->rstate.value->len) >
      decoder->ctx.max_dtable_capacity) {
    return NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR;
  }

  qnv.name = ent->nv.name;
  qnv.value = decoder->rstate.value;
  qnv.token = ent->nv.token;
  qnv.flags = NGHTTP3_NV_FLAG_NONE;

  nghttp3_rcbuf_incref(qnv.name);

  rv = nghttp3_qpack_context_dtable_add(&decoder->ctx, &qnv, NULL, 0);

  nghttp3_rcbuf_decref(qnv.value);
  nghttp3_rcbuf_decref(qnv.name);

  return rv;
}

int nghttp3_qpack_decoder_dtable_duplicate_add(nghttp3_qpack_decoder *decoder) {
  int rv;
  nghttp3_qpack_entry *ent;
  nghttp3_qpack_nv qnv;

  DEBUGF("qpack::decode: Insert duplicate absidx=%" PRIu64 "\n",
         decoder->rstate.absidx);

  ent = nghttp3_qpack_context_dtable_get(&decoder->ctx, decoder->rstate.absidx);

  if (table_space(ent->nv.name->len, ent->nv.value->len) >
      decoder->ctx.max_dtable_capacity) {
    return NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR;
  }

  qnv = ent->nv;
  nghttp3_rcbuf_incref(qnv.name);
  nghttp3_rcbuf_incref(qnv.value);

  rv = nghttp3_qpack_context_dtable_add(&decoder->ctx, &qnv, NULL, 0);

  nghttp3_rcbuf_decref(qnv.value);
  nghttp3_rcbuf_decref(qnv.name);

  return rv;
}

int nghttp3_qpack_decoder_dtable_literal_add(nghttp3_qpack_decoder *decoder) {
  nghttp3_qpack_nv qnv;
  int rv;

  DEBUGF("qpack::decode: Insert With Literal Name: name=%*s value=%*s\n",
         (int)decoder->rstate.name->len, decoder->rstate.name->base,
         (int)decoder->rstate.value->len, decoder->rstate.value->base);

  if (table_space(decoder->rstate.name->len, decoder->rstate.value->len) >
      decoder->ctx.max_dtable_capacity) {
    return NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR;
  }

  qnv.name = decoder->rstate.name;
  qnv.value = decoder->rstate.value;
  qnv.token = qpack_lookup_token(qnv.name->base, qnv.name->len);
  qnv.flags = NGHTTP3_NV_FLAG_NONE;

  rv = nghttp3_qpack_context_dtable_add(&decoder->ctx, &qnv, NULL, 0);

  nghttp3_rcbuf_decref(qnv.value);
  nghttp3_rcbuf_decref(qnv.name);

  return rv;
}

void nghttp3_qpack_decoder_set_max_concurrent_streams(
  nghttp3_qpack_decoder *decoder, size_t max_concurrent_streams) {
  decoder->max_concurrent_streams =
    nghttp3_max_size(decoder->max_concurrent_streams, max_concurrent_streams);
}

void nghttp3_qpack_stream_context_init(nghttp3_qpack_stream_context *sctx,
                                       int64_t stream_id,
                                       const nghttp3_mem *mem) {
  nghttp3_qpack_read_state_reset(&sctx->rstate);

  sctx->mem = mem;
  sctx->rstate.prefix = 8;
  sctx->state = NGHTTP3_QPACK_RS_STATE_RICNT;
  sctx->opcode = 0;
  sctx->stream_id = stream_id;
  sctx->ricnt = 0;
  sctx->dbase_sign = 0;
  sctx->base = 0;
}

void nghttp3_qpack_stream_context_free(nghttp3_qpack_stream_context *sctx) {
  nghttp3_qpack_read_state_free(&sctx->rstate);
}

void nghttp3_qpack_stream_context_reset(nghttp3_qpack_stream_context *sctx) {
  nghttp3_qpack_stream_context_init(sctx, sctx->stream_id, sctx->mem);
}

uint64_t
nghttp3_qpack_stream_context_get_ricnt(nghttp3_qpack_stream_context *sctx) {
  return sctx->ricnt;
}

nghttp3_ssize
nghttp3_qpack_decoder_read_request(nghttp3_qpack_decoder *decoder,
                                   nghttp3_qpack_stream_context *sctx,
                                   nghttp3_qpack_nv *nv, uint8_t *pflags,
                                   const uint8_t *src, size_t srclen, int fin) {
  const uint8_t *p = src, *end = src ? src + srclen : src;
  int rv;
  int busy = 0;
  nghttp3_ssize nread;
  int rfin;
  const nghttp3_mem *mem = decoder->ctx.mem;

  if (decoder->ctx.bad) {
    return NGHTTP3_ERR_QPACK_FATAL;
  }

  *pflags = NGHTTP3_QPACK_DECODE_FLAG_NONE;

  for (; p != end || busy;) {
    busy = 0;
    switch (sctx->state) {
    case NGHTTP3_QPACK_RS_STATE_RICNT:
      nread = qpack_read_varint(&rfin, &sctx->rstate, p, end);
      if (nread < 0) {
        assert(NGHTTP3_ERR_QPACK_FATAL == nread);
        rv = NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED;
        goto fail;
      }

      p += nread;

      if (!rfin) {
        goto almost_ok;
      }

      rv = nghttp3_qpack_decoder_reconstruct_ricnt(decoder, &sctx->ricnt,
                                                   sctx->rstate.left);
      if (rv != 0) {
        goto fail;
      }

      sctx->state = NGHTTP3_QPACK_RS_STATE_DBASE_SIGN;
      break;
    case NGHTTP3_QPACK_RS_STATE_DBASE_SIGN:
      if ((*p) & 0x80) {
        sctx->dbase_sign = 1;
      }
      sctx->state = NGHTTP3_QPACK_RS_STATE_DBASE;
      sctx->rstate.left = 0;
      sctx->rstate.prefix = 7;
      sctx->rstate.shift = 0;
      /* Fall through */
    case NGHTTP3_QPACK_RS_STATE_DBASE:
      nread = qpack_read_varint(&rfin, &sctx->rstate, p, end);
      if (nread < 0) {
        assert(NGHTTP3_ERR_QPACK_FATAL == nread);
        rv = NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED;
        goto fail;
      }

      p += nread;

      if (!rfin) {
        goto almost_ok;
      }

      if (sctx->dbase_sign) {
        if (sctx->ricnt <= sctx->rstate.left) {
          rv = NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED;
          goto fail;
        }
        sctx->base = sctx->ricnt - sctx->rstate.left - 1;
      } else {
        sctx->base = sctx->ricnt + sctx->rstate.left;
      }

      DEBUGF("qpack::decode: ricnt=%" PRIu64 " base=%" PRIu64 " icnt=%" PRIu64
             "\n",
             sctx->ricnt, sctx->base, decoder->ctx.next_absidx);

      if (sctx->ricnt > decoder->ctx.next_absidx) {
        DEBUGF("qpack::decode: stream blocked\n");
        sctx->state = NGHTTP3_QPACK_RS_STATE_BLOCKED;
        *pflags |= NGHTTP3_QPACK_DECODE_FLAG_BLOCKED;
        return p - src;
      }

      sctx->state = NGHTTP3_QPACK_RS_STATE_OPCODE;
      sctx->rstate.left = 0;
      sctx->rstate.shift = 0;
      break;
    case NGHTTP3_QPACK_RS_STATE_OPCODE:
      assert(sctx->rstate.left == 0);
      assert(sctx->rstate.shift == 0);
      switch ((*p) & 0xf0) {
      case 0x80:
      case 0x90:
      case 0xa0:
      case 0xb0:
      case 0xc0:
      case 0xd0:
      case 0xe0:
      case 0xf0:
        DEBUGF("qpack::decode: OPCODE_INDEXED\n");
        sctx->opcode = NGHTTP3_QPACK_RS_OPCODE_INDEXED;
        sctx->rstate.dynamic = !((*p) & 0x40);
        sctx->rstate.prefix = 6;
        sctx->state = NGHTTP3_QPACK_RS_STATE_READ_INDEX;

        break;
      case 0x40:
      case 0x50:
      case 0x60:
      case 0x70:
        DEBUGF("qpack::decode: OPCODE_INDEXED_NAME\n");
        sctx->opcode = NGHTTP3_QPACK_RS_OPCODE_INDEXED_NAME;
        sctx->rstate.never = (*p) & 0x20;
        sctx->rstate.dynamic = !((*p) & 0x10);
        sctx->rstate.prefix = 4;
        sctx->state = NGHTTP3_QPACK_RS_STATE_READ_INDEX;

        break;
      case 0x20:
      case 0x30:
        DEBUGF("qpack::decode: OPCODE_LITERAL\n");
        sctx->opcode = NGHTTP3_QPACK_RS_OPCODE_LITERAL;
        sctx->rstate.never = (*p) & 0x10;
        sctx->rstate.dynamic = 0;
        sctx->rstate.prefix = 3;
        sctx->state = NGHTTP3_QPACK_RS_STATE_CHECK_NAME_HUFFMAN;

        break;
      case 0x10:
        DEBUGF("qpack::decode: OPCODE_INDEXED_PB\n");
        sctx->opcode = NGHTTP3_QPACK_RS_OPCODE_INDEXED_PB;
        sctx->rstate.dynamic = 1;
        sctx->rstate.prefix = 4;
        sctx->state = NGHTTP3_QPACK_RS_STATE_READ_INDEX;

        break;
      default:
        DEBUGF("qpack::decode: OPCODE_INDEXED_NAME_PB\n");
        sctx->opcode = NGHTTP3_QPACK_RS_OPCODE_INDEXED_NAME_PB;
        sctx->rstate.never = (*p) & 0x08;
        sctx->rstate.dynamic = 1;
        sctx->rstate.prefix = 3;
        sctx->state = NGHTTP3_QPACK_RS_STATE_READ_INDEX;
      }
      break;
    case NGHTTP3_QPACK_RS_STATE_READ_INDEX:
      nread = qpack_read_varint(&rfin, &sctx->rstate, p, end);
      if (nread < 0) {
        assert(NGHTTP3_ERR_QPACK_FATAL == nread);
        rv = NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED;
        goto fail;
      }

      p += nread;

      if (!rfin) {
        goto almost_ok;
      }

      switch (sctx->opcode) {
      case NGHTTP3_QPACK_RS_OPCODE_INDEXED:
        rv = nghttp3_qpack_decoder_brel2abs(decoder, sctx);
        if (rv != 0) {
          goto fail;
        }
        nghttp3_qpack_decoder_emit_indexed(decoder, sctx, nv);
        *pflags |= NGHTTP3_QPACK_DECODE_FLAG_EMIT;

        sctx->state = NGHTTP3_QPACK_RS_STATE_OPCODE;
        nghttp3_qpack_read_state_reset(&sctx->rstate);

        return p - src;
      case NGHTTP3_QPACK_RS_OPCODE_INDEXED_PB:
        rv = nghttp3_qpack_decoder_pbrel2abs(decoder, sctx);
        if (rv != 0) {
          goto fail;
        }
        nghttp3_qpack_decoder_emit_indexed(decoder, sctx, nv);
        *pflags |= NGHTTP3_QPACK_DECODE_FLAG_EMIT;

        sctx->state = NGHTTP3_QPACK_RS_STATE_OPCODE;
        nghttp3_qpack_read_state_reset(&sctx->rstate);

        return p - src;
      case NGHTTP3_QPACK_RS_OPCODE_INDEXED_NAME:
        rv = nghttp3_qpack_decoder_brel2abs(decoder, sctx);
        if (rv != 0) {
          goto fail;
        }
        sctx->rstate.prefix = 7;
        sctx->state = NGHTTP3_QPACK_RS_STATE_CHECK_VALUE_HUFFMAN;
        break;
      case NGHTTP3_QPACK_RS_OPCODE_INDEXED_NAME_PB:
        rv = nghttp3_qpack_decoder_pbrel2abs(decoder, sctx);
        if (rv != 0) {
          goto fail;
        }
        sctx->rstate.prefix = 7;
        sctx->state = NGHTTP3_QPACK_RS_STATE_CHECK_VALUE_HUFFMAN;
        break;
      default:
        nghttp3_unreachable();
      }
      break;
    case NGHTTP3_QPACK_RS_STATE_CHECK_NAME_HUFFMAN:
      qpack_read_state_check_huffman(&sctx->rstate, *p);
      sctx->state = NGHTTP3_QPACK_RS_STATE_READ_NAMELEN;
      sctx->rstate.left = 0;
      sctx->rstate.shift = 0;
      /* Fall through */
    case NGHTTP3_QPACK_RS_STATE_READ_NAMELEN:
      nread = qpack_read_varint(&rfin, &sctx->rstate, p, end);
      if (nread < 0) {
        assert(NGHTTP3_ERR_QPACK_FATAL == nread);
        rv = NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED;
        goto fail;
      }

      p += nread;

      if (!rfin) {
        goto almost_ok;
      }

      if (sctx->rstate.left > NGHTTP3_QPACK_MAX_NAMELEN) {
        rv = NGHTTP3_ERR_QPACK_HEADER_TOO_LARGE;
        goto fail;
      }

      if (sctx->rstate.huffman_encoded) {
        sctx->state = NGHTTP3_QPACK_RS_STATE_READ_NAME_HUFFMAN;
        nghttp3_qpack_huffman_decode_context_init(&sctx->rstate.huffman_ctx);
        rv = nghttp3_rcbuf_new(&sctx->rstate.name,
                               (size_t)sctx->rstate.left * 2 + 1, mem);
      } else {
        sctx->state = NGHTTP3_QPACK_RS_STATE_READ_NAME;
        rv = nghttp3_rcbuf_new(&sctx->rstate.name,
                               (size_t)sctx->rstate.left + 1, mem);
      }
      if (rv != 0) {
        goto fail;
      }

      nghttp3_buf_wrap_init(&sctx->rstate.namebuf, sctx->rstate.name->base,
                            sctx->rstate.name->len);
      break;
    case NGHTTP3_QPACK_RS_STATE_READ_NAME_HUFFMAN:
      nread =
        qpack_read_huffman_string(&sctx->rstate, &sctx->rstate.namebuf, p, end);
      if (nread < 0) {
        assert(NGHTTP3_ERR_QPACK_FATAL == nread);
        rv = NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED;
        goto fail;
      }

      p += nread;

      if (sctx->rstate.left) {
        goto almost_ok;
      }

      qpack_read_state_terminate_name(&sctx->rstate);

      sctx->state = NGHTTP3_QPACK_RS_STATE_CHECK_VALUE_HUFFMAN;
      sctx->rstate.prefix = 7;
      break;
    case NGHTTP3_QPACK_RS_STATE_READ_NAME:
      nread = qpack_read_string(&sctx->rstate, &sctx->rstate.namebuf, p, end);
      if (nread < 0) {
        rv = (int)nread;
        goto fail;
      }

      p += nread;

      if (sctx->rstate.left) {
        goto almost_ok;
      }

      qpack_read_state_terminate_name(&sctx->rstate);

      sctx->state = NGHTTP3_QPACK_RS_STATE_CHECK_VALUE_HUFFMAN;
      sctx->rstate.prefix = 7;
      break;
    case NGHTTP3_QPACK_RS_STATE_CHECK_VALUE_HUFFMAN:
      qpack_read_state_check_huffman(&sctx->rstate, *p);
      sctx->state = NGHTTP3_QPACK_RS_STATE_READ_VALUELEN;
      sctx->rstate.left = 0;
      sctx->rstate.shift = 0;
      /* Fall through */
    case NGHTTP3_QPACK_RS_STATE_READ_VALUELEN:
      nread = qpack_read_varint(&rfin, &sctx->rstate, p, end);
      if (nread < 0) {
        assert(NGHTTP3_ERR_QPACK_FATAL == nread);
        rv = NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED;
        goto fail;
      }

      p += nread;

      if (!rfin) {
        goto almost_ok;
      }

      if (sctx->rstate.left > NGHTTP3_QPACK_MAX_VALUELEN) {
        rv = NGHTTP3_ERR_QPACK_HEADER_TOO_LARGE;
        goto fail;
      }

      if (sctx->rstate.huffman_encoded) {
        sctx->state = NGHTTP3_QPACK_RS_STATE_READ_VALUE_HUFFMAN;
        nghttp3_qpack_huffman_decode_context_init(&sctx->rstate.huffman_ctx);
        rv = nghttp3_rcbuf_new(&sctx->rstate.value,
                               (size_t)sctx->rstate.left * 2 + 1, mem);
      } else {
        sctx->state = NGHTTP3_QPACK_RS_STATE_READ_VALUE;
        rv = nghttp3_rcbuf_new(&sctx->rstate.value,
                               (size_t)sctx->rstate.left + 1, mem);
      }
      if (rv != 0) {
        goto fail;
      }

      nghttp3_buf_wrap_init(&sctx->rstate.valuebuf, sctx->rstate.value->base,
                            sctx->rstate.value->len);

      /* value might be 0 length */
      busy = 1;
      break;
    case NGHTTP3_QPACK_RS_STATE_READ_VALUE_HUFFMAN:
      nread = qpack_read_huffman_string(&sctx->rstate, &sctx->rstate.valuebuf,
                                        p, end);
      if (nread < 0) {
        assert(NGHTTP3_ERR_QPACK_FATAL == nread);
        rv = NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED;
        goto fail;
      }

      p += nread;

      if (sctx->rstate.left) {
        goto almost_ok;
      }

      qpack_read_state_terminate_value(&sctx->rstate);

      switch (sctx->opcode) {
      case NGHTTP3_QPACK_RS_OPCODE_INDEXED_NAME:
      case NGHTTP3_QPACK_RS_OPCODE_INDEXED_NAME_PB:
        rv = nghttp3_qpack_decoder_emit_indexed_name(decoder, sctx, nv);
        if (rv != 0) {
          goto fail;
        }

        break;
      case NGHTTP3_QPACK_RS_OPCODE_LITERAL:
        nghttp3_qpack_decoder_emit_literal(decoder, sctx, nv);
        break;
      default:
        nghttp3_unreachable();
      }

      *pflags |= NGHTTP3_QPACK_DECODE_FLAG_EMIT;

      sctx->state = NGHTTP3_QPACK_RS_STATE_OPCODE;
      nghttp3_qpack_read_state_reset(&sctx->rstate);

      return p - src;
    case NGHTTP3_QPACK_RS_STATE_READ_VALUE:
      nread = qpack_read_string(&sctx->rstate, &sctx->rstate.valuebuf, p, end);
      if (nread < 0) {
        rv = (int)nread;
        goto fail;
      }

      p += nread;

      if (sctx->rstate.left) {
        goto almost_ok;
      }

      qpack_read_state_terminate_value(&sctx->rstate);

      switch (sctx->opcode) {
      case NGHTTP3_QPACK_RS_OPCODE_INDEXED_NAME:
      case NGHTTP3_QPACK_RS_OPCODE_INDEXED_NAME_PB:
        rv = nghttp3_qpack_decoder_emit_indexed_name(decoder, sctx, nv);
        if (rv != 0) {
          goto fail;
        }

        break;
      case NGHTTP3_QPACK_RS_OPCODE_LITERAL:
        nghttp3_qpack_decoder_emit_literal(decoder, sctx, nv);
        break;
      default:
        nghttp3_unreachable();
      }

      *pflags |= NGHTTP3_QPACK_DECODE_FLAG_EMIT;

      sctx->state = NGHTTP3_QPACK_RS_STATE_OPCODE;
      nghttp3_qpack_read_state_reset(&sctx->rstate);

      return p - src;
    case NGHTTP3_QPACK_RS_STATE_BLOCKED:
      if (sctx->ricnt > decoder->ctx.next_absidx) {
        DEBUGF("qpack::decode: stream still blocked\n");
        *pflags |= NGHTTP3_QPACK_DECODE_FLAG_BLOCKED;
        return p - src;
      }
      sctx->state = NGHTTP3_QPACK_RS_STATE_OPCODE;
      nghttp3_qpack_read_state_reset(&sctx->rstate);
      break;
    }
  }

almost_ok:
  if (fin) {
    if (sctx->state != NGHTTP3_QPACK_RS_STATE_OPCODE) {
      rv = NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED;
      goto fail;
    }

    *pflags |= NGHTTP3_QPACK_DECODE_FLAG_FINAL;

    if (sctx->ricnt) {
      rv = nghttp3_qpack_decoder_write_section_ack(decoder, sctx);
      if (rv != 0) {
        goto fail;
      }
    }

    decoder->uninterrupted_encoderlen = 0;
  }

  return p - src;

fail:
  decoder->ctx.bad = 1;
  return rv;
}

static int qpack_decoder_dbuf_overflow(nghttp3_qpack_decoder *decoder) {
  size_t limit = nghttp3_max_size(decoder->max_concurrent_streams, 100);
  /* 10 = nghttp3_qpack_put_varint_len((1ULL << 62) - 1, 2)) */
  return nghttp3_buf_len(&decoder->dbuf) > limit * 2 * 10;
}

int nghttp3_qpack_decoder_write_section_ack(
  nghttp3_qpack_decoder *decoder, const nghttp3_qpack_stream_context *sctx) {
  nghttp3_buf *dbuf = &decoder->dbuf;
  uint8_t *p;
  int rv;

  if (qpack_decoder_dbuf_overflow(decoder)) {
    return NGHTTP3_ERR_QPACK_FATAL;
  }

  rv = reserve_buf(dbuf,
                   nghttp3_qpack_put_varint_len((uint64_t)sctx->stream_id, 7),
                   decoder->ctx.mem);
  if (rv != 0) {
    return rv;
  }

  p = dbuf->last;
  *p = 0x80;
  dbuf->last = nghttp3_qpack_put_varint(p, (uint64_t)sctx->stream_id, 7);

  if (decoder->written_icnt < sctx->ricnt) {
    decoder->written_icnt = sctx->ricnt;
  }

  return 0;
}

size_t
nghttp3_qpack_decoder_get_decoder_streamlen(nghttp3_qpack_decoder *decoder) {
  uint64_t n;
  size_t len = 0;

  if (decoder->written_icnt < decoder->ctx.next_absidx) {
    n = decoder->ctx.next_absidx - decoder->written_icnt;
    len = nghttp3_qpack_put_varint_len(n, 6);
  }

  return nghttp3_buf_len(&decoder->dbuf) + len;
}

void nghttp3_qpack_decoder_write_decoder(nghttp3_qpack_decoder *decoder,
                                         nghttp3_buf *dbuf) {
  uint8_t *p;
  uint64_t n = 0;
  size_t len = 0;
  (void)len;

  if (decoder->written_icnt < decoder->ctx.next_absidx) {
    n = decoder->ctx.next_absidx - decoder->written_icnt;
    len = nghttp3_qpack_put_varint_len(n, 6);
  }

  assert(nghttp3_buf_left(dbuf) >= nghttp3_buf_len(&decoder->dbuf) + len);

  if (nghttp3_buf_len(&decoder->dbuf)) {
    dbuf->last = nghttp3_cpymem(dbuf->last, decoder->dbuf.pos,
                                nghttp3_buf_len(&decoder->dbuf));
  }

  if (n) {
    p = dbuf->last;
    *p = 0;
    dbuf->last = nghttp3_qpack_put_varint(p, n, 6);

    decoder->written_icnt = decoder->ctx.next_absidx;
  }

  nghttp3_buf_reset(&decoder->dbuf);
}

int nghttp3_qpack_decoder_cancel_stream(nghttp3_qpack_decoder *decoder,
                                        int64_t stream_id) {
  uint8_t *p;
  int rv;

  if (qpack_decoder_dbuf_overflow(decoder)) {
    return NGHTTP3_ERR_QPACK_FATAL;
  }

  rv = reserve_buf(&decoder->dbuf,
                   nghttp3_qpack_put_varint_len((uint64_t)stream_id, 6),
                   decoder->ctx.mem);
  if (rv != 0) {
    return rv;
  }

  p = decoder->dbuf.last;
  *p = 0x40;
  decoder->dbuf.last = nghttp3_qpack_put_varint(p, (uint64_t)stream_id, 6);

  return 0;
}

int nghttp3_qpack_decoder_reconstruct_ricnt(nghttp3_qpack_decoder *decoder,
                                            uint64_t *dest, uint64_t encricnt) {
  uint64_t max_ents, full, max, max_wrapped, ricnt;

  if (encricnt == 0) {
    *dest = 0;
    return 0;
  }

  max_ents =
    decoder->ctx.hard_max_dtable_capacity / NGHTTP3_QPACK_ENTRY_OVERHEAD;
  full = 2 * max_ents;

  if (encricnt > full) {
    return NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED;
  }

  max = decoder->ctx.next_absidx + max_ents;
  max_wrapped = max / full * full;
  ricnt = max_wrapped + encricnt - 1;

  if (ricnt > max) {
    if (ricnt <= full) {
      return NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED;
    }
    ricnt -= full;
  }

  if (ricnt == 0) {
    return NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED;
  }

  *dest = ricnt;

  return 0;
}

int nghttp3_qpack_decoder_rel2abs(nghttp3_qpack_decoder *decoder,
                                  nghttp3_qpack_read_state *rstate) {
  DEBUGF("qpack::decode: dynamic=%d relidx=%" PRIu64 " icnt=%" PRIu64 "\n",
         rstate->dynamic, rstate->left, decoder->ctx.next_absidx);

  if (rstate->dynamic) {
    if (decoder->ctx.next_absidx < rstate->left + 1) {
      return NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR;
    }
    rstate->absidx = decoder->ctx.next_absidx - rstate->left - 1;
  } else {
    rstate->absidx = rstate->left;
  }
  if (qpack_decoder_validate_index(decoder, rstate) != 0) {
    return NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR;
  }
  return 0;
}

int nghttp3_qpack_decoder_brel2abs(nghttp3_qpack_decoder *decoder,
                                   nghttp3_qpack_stream_context *sctx) {
  nghttp3_qpack_read_state *rstate = &sctx->rstate;

  DEBUGF("qpack::decode: dynamic=%d relidx=%" PRIu64 " base=%" PRIu64
         " icnt=%" PRIu64 "\n",
         rstate->dynamic, rstate->left, sctx->base, decoder->ctx.next_absidx);

  if (rstate->dynamic) {
    if (sctx->base < rstate->left + 1) {
      return NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED;
    }
    rstate->absidx = sctx->base - rstate->left - 1;

    if (rstate->absidx >= sctx->ricnt) {
      return NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED;
    }
  } else {
    rstate->absidx = rstate->left;
  }

  if (qpack_decoder_validate_index(decoder, rstate) != 0) {
    return NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED;
  }
  return 0;
}

int nghttp3_qpack_decoder_pbrel2abs(nghttp3_qpack_decoder *decoder,
                                    nghttp3_qpack_stream_context *sctx) {
  nghttp3_qpack_read_state *rstate = &sctx->rstate;

  DEBUGF("qpack::decode: pbidx=%" PRIu64 " base=%" PRIu64 " icnt=%" PRIu64 "\n",
         rstate->left, sctx->base, decoder->ctx.next_absidx);

  assert(rstate->dynamic);

  rstate->absidx = rstate->left + sctx->base;

  if (rstate->absidx >= sctx->ricnt) {
    return NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED;
  }

  if (qpack_decoder_validate_index(decoder, rstate) != 0) {
    return NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED;
  }
  return 0;
}

static void
qpack_decoder_emit_static_indexed(nghttp3_qpack_decoder *decoder,
                                  nghttp3_qpack_stream_context *sctx,
                                  nghttp3_qpack_nv *nv) {
  const nghttp3_qpack_static_header *shd = &stable[sctx->rstate.absidx];
  (void)decoder;

  nv->name = (nghttp3_rcbuf *)&shd->name;
  nv->value = (nghttp3_rcbuf *)&shd->value;
  nv->token = shd->token;
  nv->flags = NGHTTP3_NV_FLAG_NONE;
}

static void
qpack_decoder_emit_dynamic_indexed(nghttp3_qpack_decoder *decoder,
                                   nghttp3_qpack_stream_context *sctx,
                                   nghttp3_qpack_nv *nv) {
  nghttp3_qpack_entry *ent =
    nghttp3_qpack_context_dtable_get(&decoder->ctx, sctx->rstate.absidx);

  *nv = ent->nv;

  nghttp3_rcbuf_incref(nv->name);
  nghttp3_rcbuf_incref(nv->value);
}

void nghttp3_qpack_decoder_emit_indexed(nghttp3_qpack_decoder *decoder,
                                        nghttp3_qpack_stream_context *sctx,
                                        nghttp3_qpack_nv *nv) {
  DEBUGF("qpack::decode: Indexed (%s) absidx=%" PRIu64 "\n",
         sctx->rstate.dynamic ? "dynamic" : "static", sctx->rstate.absidx);

  if (sctx->rstate.dynamic) {
    qpack_decoder_emit_dynamic_indexed(decoder, sctx, nv);
  } else {
    qpack_decoder_emit_static_indexed(decoder, sctx, nv);
  }
}

static void
qpack_decoder_emit_static_indexed_name(nghttp3_qpack_decoder *decoder,
                                       nghttp3_qpack_stream_context *sctx,
                                       nghttp3_qpack_nv *nv) {
  const nghttp3_qpack_static_header *shd = &stable[sctx->rstate.absidx];
  (void)decoder;

  nv->name = (nghttp3_rcbuf *)&shd->name;
  nv->value = sctx->rstate.value;
  nv->token = shd->token;
  nv->flags =
    sctx->rstate.never ? NGHTTP3_NV_FLAG_NEVER_INDEX : NGHTTP3_NV_FLAG_NONE;

  sctx->rstate.value = NULL;
}

static int
qpack_decoder_emit_dynamic_indexed_name(nghttp3_qpack_decoder *decoder,
                                        nghttp3_qpack_stream_context *sctx,
                                        nghttp3_qpack_nv *nv) {
  nghttp3_qpack_entry *ent;

  /* A broken encoder might change dtable capacity while processing
     request stream instruction.  Check the absidx again. */
  if (qpack_decoder_validate_index(decoder, &sctx->rstate) != 0) {
    return NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED;
  }

  ent = nghttp3_qpack_context_dtable_get(&decoder->ctx, sctx->rstate.absidx);

  nv->name = ent->nv.name;
  nv->value = sctx->rstate.value;
  nv->token = ent->nv.token;
  nv->flags =
    sctx->rstate.never ? NGHTTP3_NV_FLAG_NEVER_INDEX : NGHTTP3_NV_FLAG_NONE;

  nghttp3_rcbuf_incref(nv->name);

  sctx->rstate.value = NULL;

  return 0;
}

int nghttp3_qpack_decoder_emit_indexed_name(nghttp3_qpack_decoder *decoder,
                                            nghttp3_qpack_stream_context *sctx,
                                            nghttp3_qpack_nv *nv) {
  (void)decoder;

  DEBUGF("qpack::decode: Indexed name (%s) absidx=%" PRIu64 " value=%*s\n",
         sctx->rstate.dynamic ? "dynamic" : "static", sctx->rstate.absidx,
         (int)sctx->rstate.value->len, sctx->rstate.value->base);

  if (sctx->rstate.dynamic) {
    return qpack_decoder_emit_dynamic_indexed_name(decoder, sctx, nv);
  }

  qpack_decoder_emit_static_indexed_name(decoder, sctx, nv);

  return 0;
}

void nghttp3_qpack_decoder_emit_literal(nghttp3_qpack_decoder *decoder,
                                        nghttp3_qpack_stream_context *sctx,
                                        nghttp3_qpack_nv *nv) {
  (void)decoder;

  DEBUGF("qpack::decode: Emit literal name=%*s value=%*s\n",
         (int)sctx->rstate.name->len, sctx->rstate.name->base,
         (int)sctx->rstate.value->len, sctx->rstate.value->base);

  nv->name = sctx->rstate.name;
  nv->value = sctx->rstate.value;
  nv->token = qpack_lookup_token(nv->name->base, nv->name->len);
  nv->flags =
    sctx->rstate.never ? NGHTTP3_NV_FLAG_NEVER_INDEX : NGHTTP3_NV_FLAG_NONE;

  sctx->rstate.name = NULL;
  sctx->rstate.value = NULL;
}

int nghttp3_qpack_encoder_new(nghttp3_qpack_encoder **pencoder,
                              size_t hard_max_dtable_capacity,
                              const nghttp3_mem *mem) {
  int rv;
  nghttp3_qpack_encoder *p;

  p = nghttp3_mem_malloc(mem, sizeof(nghttp3_qpack_encoder));
  if (p == NULL) {
    return NGHTTP3_ERR_NOMEM;
  }

  rv = nghttp3_qpack_encoder_init(p, hard_max_dtable_capacity, mem);
  if (rv != 0) {
    return rv;
  }

  *pencoder = p;

  return 0;
}

void nghttp3_qpack_encoder_del(nghttp3_qpack_encoder *encoder) {
  const nghttp3_mem *mem;

  if (encoder == NULL) {
    return;
  }

  mem = encoder->ctx.mem;

  nghttp3_qpack_encoder_free(encoder);
  nghttp3_mem_free(mem, encoder);
}

int nghttp3_qpack_stream_context_new(nghttp3_qpack_stream_context **psctx,
                                     int64_t stream_id,
                                     const nghttp3_mem *mem) {
  nghttp3_qpack_stream_context *p;

  p = nghttp3_mem_malloc(mem, sizeof(nghttp3_qpack_stream_context));
  if (p == NULL) {
    return NGHTTP3_ERR_NOMEM;
  }

  nghttp3_qpack_stream_context_init(p, stream_id, mem);

  *psctx = p;

  return 0;
}

void nghttp3_qpack_stream_context_del(nghttp3_qpack_stream_context *sctx) {
  const nghttp3_mem *mem;

  if (sctx == NULL) {
    return;
  }

  mem = sctx->mem;

  nghttp3_qpack_stream_context_free(sctx);
  nghttp3_mem_free(mem, sctx);
}

int nghttp3_qpack_decoder_new(nghttp3_qpack_decoder **pdecoder,
                              size_t hard_max_dtable_capacity,
                              size_t max_blocked_streams,
                              const nghttp3_mem *mem) {
  int rv;
  nghttp3_qpack_decoder *p;

  p = nghttp3_mem_malloc(mem, sizeof(nghttp3_qpack_decoder));
  if (p == NULL) {
    return NGHTTP3_ERR_NOMEM;
  }

  rv = nghttp3_qpack_decoder_init(p, hard_max_dtable_capacity,
                                  max_blocked_streams, mem);
  if (rv != 0) {
    return rv;
  }

  *pdecoder = p;

  return 0;
}

void nghttp3_qpack_decoder_del(nghttp3_qpack_decoder *decoder) {
  const nghttp3_mem *mem;

  if (decoder == NULL) {
    return;
  }

  mem = decoder->ctx.mem;

  nghttp3_qpack_decoder_free(decoder);
  nghttp3_mem_free(mem, decoder);
}

uint64_t nghttp3_qpack_decoder_get_icnt(const nghttp3_qpack_decoder *decoder) {
  return decoder->ctx.next_absidx;
}