text: /*
   * 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"
  
  /* 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, NULL, (uint8_t *)(N), sizeof((N)) - 1, -1},                         \
          {NULL, 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_size.
   */
  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_size;
  }
  
  /* |*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|.  |max_dtable_size| is the
   * maximum size of dynamic table.  |mem| is a memory allocator.
   *
   * 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 max_dtable_size, size_t max_blocked,
                                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_size = max_dtable_size;
    ctx->max_dtable_size = 0;
    ctx->max_blocked = max_blocked;
    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);
  }
  
  int nghttp3_qpack_encoder_init(nghttp3_qpack_encoder *encoder,
                                 size_t max_dtable_size, size_t max_blocked,
                                 const nghttp3_mem *mem) {
    int rv;
  
    rv = qpack_context_init(&encoder->ctx, max_dtable_size, max_blocked, mem);
    if (rv != 0) {
      return rv;
    }
  
    rv = nghttp3_map_init(&encoder->streams, mem);
    if (rv != 0) {
      goto streams_init_fail;
    }
  
    rv = nghttp3_ksl_init(&encoder->blocked_streams, max_cnt_greater,
                          sizeof(nghttp3_blocked_streams_key), mem);
    if (rv != 0) {
      goto blocked_streams_init_fail;
    }
  
    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->flags = NGHTTP3_QPACK_ENCODER_FLAG_NONE;
  
    nghttp3_qpack_read_state_reset(&encoder->rstate);
  
    return 0;
  
  blocked_streams_init_fail:
    nghttp3_map_free(&encoder->streams);
  streams_init_fail:
    qpack_context_free(&encoder->ctx);
  
    return rv;
  }
  
  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_free(&encoder->streams, map_stream_free,
                          (void *)encoder->ctx.mem);
    nghttp3_map_free(&encoder->streams);
    qpack_context_free(&encoder->ctx);
  }
  
  int nghttp3_qpack_encoder_set_max_dtable_size(nghttp3_qpack_encoder *encoder,
                                                size_t max_dtable_size) {
    if (encoder->ctx.hard_max_dtable_size < max_dtable_size) {
      return NGHTTP3_ERR_INVALID_ARGUMENT;
    }
  
    if (encoder->ctx.max_dtable_size == max_dtable_size) {
      return 0;
    }
  
    encoder->flags |= NGHTTP3_QPACK_ENCODER_FLAG_PENDING_SET_DTABLE_CAP;
  
    if (encoder->min_dtable_update > max_dtable_size) {
      encoder->min_dtable_update = max_dtable_size;
      encoder->ctx.max_dtable_size = max_dtable_size;
    }
    encoder->last_max_dtable_update = max_dtable_size;
  
    return 0;
  }
  
  int nghttp3_qpack_encoder_set_hard_max_dtable_size(
      nghttp3_qpack_encoder *encoder, size_t hard_max_dtable_size) {
    /* TODO This is not ideal. */
    if (encoder->ctx.hard_max_dtable_size) {
      return NGHTTP3_ERR_INVALID_STATE;
    }
  
    encoder->ctx.hard_max_dtable_size = hard_max_dtable_size;
  
    return 0;
  }
  
  int nghttp3_qpack_encoder_set_max_blocked(nghttp3_qpack_encoder *encoder,
                                            size_t max_blocked) {
    /* TODO This is not ideal. */
    if (encoder->ctx.max_blocked) {
      return NGHTTP3_ERR_INVALID_STATE;
    }
  
    encoder->ctx.max_blocked = max_blocked;
  
    return 0;
  }
  
  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_size) {
      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_size;) {
      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_internal ensures that |buf| contains at least
   * |extra_size| of free space.  In other words, if this function
   * succeeds, nghttp2_buf_left(buf) >= extra_size holds.  |min_size| is
   * the minimum size of buffer.  The allocated buffer has at least
   * |min_size| bytes.
   *
   * 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_internal(nghttp3_buf *buf, size_t extra_size,
                                  size_t min_size, const nghttp3_mem *mem) {
    size_t left = nghttp3_buf_left(buf);
    size_t n = min_size, need;
  
    if (left >= extra_size) {
      return 0;
    }
  
    need = nghttp3_buf_cap(buf) + extra_size - left;
  
    for (; n < need; n *= 2)
      ;
  
    return nghttp3_buf_reserve(buf, n, mem);
  }
  
  static int reserve_buf_small(nghttp3_buf *buf, size_t extra_size,
                               const nghttp3_mem *mem) {
    return reserve_buf_internal(buf, extra_size, 32, mem);
  }
  
  static int reserve_buf(nghttp3_buf *buf, size_t extra_size,
                         const nghttp3_mem *mem) {
    return reserve_buf_internal(buf, extra_size, 32, 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 > 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);
  
    /* 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_size < 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_size = 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);
  }
  
  /*
   * 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:
      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 (token >= 1000) {
        return NGHTTP3_QPACK_INDEXING_MODE_LITERAL;
      }
    }
  
    if (table_space(nv->namelen, nv->valuelen) >
        encoder->ctx.max_dtable_size * 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_size > encoder->ctx.dtable_size) {
      avail = encoder->ctx.max_dtable_size - 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(min_cnt, gmin_cnt);
    }
  
    if (min_cnt == UINT64_MAX) {
      return encoder->ctx.max_dtable_size >= 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_size - nghttp3_min(512, ctx->max_dtable_size * 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);
    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;
      }
    }
  
    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 (hash &&
        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(*pmax_cnt, (size_t)(dres.index + 1));
      *pmin_cnt = nghttp3_min(*pmin_cnt, (size_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(*pmax_cnt, new_ent->absidx + 1);
          *pmin_cnt = nghttp3_min(*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((size_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(*pmin_cnt, (size_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(*pmax_cnt, new_ent->absidx + 1);
          *pmin_cnt = nghttp3_min(*pmin_cnt, new_ent->absidx + 1);
  
          return nghttp3_qpack_encoder_write_dynamic_indexed(
              encoder, rbuf, new_ent->absidx, base);
        }
      }
  
      *pmax_cnt = nghttp3_max(*pmax_cnt, (size_t)(dres.index + 1));
      *pmin_cnt = nghttp3_min(*pmin_cnt, (size_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(*pmax_cnt, new_ent->absidx + 1);
        *pmin_cnt = nghttp3_min(*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_size);
  
    while (ctx->dtable_size + space > ctx->max_dtable_size) {
      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_insert_count(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_free(&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(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_size / 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;
    }
  
    end = src + srclen;
  
    for (; p != end;) {
      switch (encoder->state) {
      case NGHTTP3_QPACK_DS_STATE_OPCODE:
        if ((*p) & 0x80) {
          DEBUGF("qpack::encode: OPCODE_SECTION_ACK\n");
          encoder->opcode = NGHTTP3_QPACK_DS_OPCODE_SECTION_ACK;
          encoder->rstate.prefix = 7;
        } else if ((*p) & 0x40) {
          DEBUGF("qpack::encode: OPCODE_STREAM_CANCEL\n");
          encoder->opcode = NGHTTP3_QPACK_DS_OPCODE_STREAM_CANCEL;
          encoder->rstate.prefix = 6;
        } else {
          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_insert_count(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:
          /* unreachable */
          assert(0);
          break;
        }
  
        encoder->state = NGHTTP3_QPACK_DS_STATE_OPCODE;
        nghttp3_qpack_read_state_reset(&encoder->rstate);
        break;
      default:
        /* unreachable */
        assert(0);
        break;
      }
    }
  
    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 max_dtable_size, size_t max_blocked,
                                 const nghttp3_mem *mem) {
    int rv;
  
    rv = qpack_context_init(&decoder->ctx, max_dtable_size, max_blocked, 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;
  
    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_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 suceeds, 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;
    }
  
    end = src + srclen;
  
    for (; p != end || busy;) {
      busy = 0;
      switch (decoder->state) {
      case NGHTTP3_QPACK_ES_STATE_OPCODE:
        if ((*p) & 0x80) {
          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;
        } else if ((*p) & 0x40) {
          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;
        } else if ((*p) & 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;
        } else if (!((*p) & 0x20)) {
          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;
        } else {
          DEBUGF("qpack::decode: unknown opcode %02x\n", *p);
          rv = NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR;
          goto fail;
        }
        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) {
          if (decoder->rstate.left > decoder->ctx.hard_max_dtable_size) {
            rv = NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR;
            goto fail;
          }
          DEBUGF("qpack::decode: Set dtable capacity to %" PRIu64 "\n",
                 decoder->rstate.left);
          nghttp3_qpack_decoder_set_dtable_cap(decoder,
                                               (size_t)decoder->rstate.left);
  
          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;
        }
  
        if (decoder->opcode == 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;
        }
  
        if (decoder->opcode == NGHTTP3_QPACK_ES_OPCODE_INSERT_INDEXED) {
          decoder->rstate.prefix = 7;
          decoder->state = NGHTTP3_QPACK_ES_STATE_CHECK_VALUE_HUFFMAN;
          break;
        }
  
        /* Unreachable */
        assert(0);
        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:
          /* Unreachable */
          assert(0);
        }
        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:
          /* Unreachable */
          assert(0);
        }
        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;
  }
  
  void nghttp3_qpack_decoder_set_dtable_cap(nghttp3_qpack_decoder *decoder,
                                            size_t cap) {
    nghttp3_qpack_entry *ent;
    size_t i;
    nghttp3_qpack_context *ctx = &decoder->ctx;
    const nghttp3_mem *mem = ctx->mem;
  
    ctx->max_dtable_size = cap;
  
    while (ctx->dtable_size > cap) {
      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);
    }
  }
  
  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_size) {
      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_size) {
      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_size) {
      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_size) {
      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(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);
        if ((*p) & 0x80) {
          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;
        } else if ((*p) & 0x40) {
          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;
        } else if ((*p) & 0x20) {
          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;
        } else if ((*p) & 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;
        } else {
          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:
          /* Unreachable */
          assert(0);
        }
        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:
          nghttp3_qpack_decoder_emit_indexed_name(decoder, sctx, nv);
          break;
        case NGHTTP3_QPACK_RS_OPCODE_LITERAL:
          nghttp3_qpack_decoder_emit_literal(decoder, sctx, nv);
          break;
        default:
          /* Unreachable */
          assert(0);
        }
  
        *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:
          nghttp3_qpack_decoder_emit_indexed_name(decoder, sctx, nv);
          break;
        case NGHTTP3_QPACK_RS_OPCODE_LITERAL:
          nghttp3_qpack_decoder_emit_literal(decoder, sctx, nv);
          break;
        default:
          /* Unreachable */
          assert(0);
        }
  
        *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;
        }
      }
    }
  
    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(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_small(
        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;
  
    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_size / 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 void
  qpack_decoder_emit_dynamic_indexed_name(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);
    (void)decoder;
  
    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;
  }
  
  void 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) {
      qpack_decoder_emit_dynamic_indexed_name(decoder, sctx, nv);
    } else {
      qpack_decoder_emit_static_indexed_name(decoder, sctx, nv);
    }
  }
  
  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 max_dtable_size, size_t max_blocked,
                                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, max_dtable_size, max_blocked, 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 max_dtable_size, size_t max_blocked,
                                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, max_dtable_size, max_blocked, 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;
  }
  