diff options
Diffstat (limited to 'lib/nghttp3_qpack.c')
| -rw-r--r-- | lib/nghttp3_qpack.c | 4093 |
1 files changed, 4093 insertions, 0 deletions
diff --git a/lib/nghttp3_qpack.c b/lib/nghttp3_qpack.c new file mode 100644 index 0000000..fece8f1 --- /dev/null +++ b/lib/nghttp3_qpack.c @@ -0,0 +1,4093 @@ +/* + * nghttp3 + * + * Copyright (c) 2019 nghttp3 contributors + * Copyright (c) 2013 nghttp2 contributors + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE + * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION + * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION + * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + */ +#include "nghttp3_qpack.h" + +#include <string.h> +#include <assert.h> +#include <stdio.h> + +#include "nghttp3_str.h" +#include "nghttp3_macro.h" +#include "nghttp3_debug.h" +#include "nghttp3_unreachable.h" + +/* NGHTTP3_QPACK_MAX_QPACK_STREAMS is the maximum number of concurrent + nghttp3_qpack_stream object to handle a client which never cancel + or acknowledge header block. After this limit, encoder stops using + dynamic table. */ +#define NGHTTP3_QPACK_MAX_QPACK_STREAMS 2000 + +/* Make scalar initialization form of nghttp3_qpack_static_entry */ +#define MAKE_STATIC_ENT(I, T, H) \ + { I, T, H } + +/* Generated by mkstatichdtbl.py */ +static nghttp3_qpack_static_entry token_stable[] = { + MAKE_STATIC_ENT(0, NGHTTP3_QPACK_TOKEN__AUTHORITY, 3153725150u), + MAKE_STATIC_ENT(15, NGHTTP3_QPACK_TOKEN__METHOD, 695666056u), + MAKE_STATIC_ENT(16, NGHTTP3_QPACK_TOKEN__METHOD, 695666056u), + MAKE_STATIC_ENT(17, NGHTTP3_QPACK_TOKEN__METHOD, 695666056u), + MAKE_STATIC_ENT(18, NGHTTP3_QPACK_TOKEN__METHOD, 695666056u), + MAKE_STATIC_ENT(19, NGHTTP3_QPACK_TOKEN__METHOD, 695666056u), + MAKE_STATIC_ENT(20, NGHTTP3_QPACK_TOKEN__METHOD, 695666056u), + MAKE_STATIC_ENT(21, NGHTTP3_QPACK_TOKEN__METHOD, 695666056u), + MAKE_STATIC_ENT(1, NGHTTP3_QPACK_TOKEN__PATH, 3292848686u), + MAKE_STATIC_ENT(22, NGHTTP3_QPACK_TOKEN__SCHEME, 2510477674u), + MAKE_STATIC_ENT(23, NGHTTP3_QPACK_TOKEN__SCHEME, 2510477674u), + MAKE_STATIC_ENT(24, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), + MAKE_STATIC_ENT(25, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), + MAKE_STATIC_ENT(26, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), + MAKE_STATIC_ENT(27, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), + MAKE_STATIC_ENT(28, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), + MAKE_STATIC_ENT(63, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), + MAKE_STATIC_ENT(64, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), + MAKE_STATIC_ENT(65, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), + MAKE_STATIC_ENT(66, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), + MAKE_STATIC_ENT(67, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), + MAKE_STATIC_ENT(68, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), + MAKE_STATIC_ENT(69, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), + MAKE_STATIC_ENT(70, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), + MAKE_STATIC_ENT(71, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), + MAKE_STATIC_ENT(29, NGHTTP3_QPACK_TOKEN_ACCEPT, 136609321u), + MAKE_STATIC_ENT(30, NGHTTP3_QPACK_TOKEN_ACCEPT, 136609321u), + MAKE_STATIC_ENT(31, NGHTTP3_QPACK_TOKEN_ACCEPT_ENCODING, 3379649177u), + MAKE_STATIC_ENT(72, NGHTTP3_QPACK_TOKEN_ACCEPT_LANGUAGE, 1979086614u), + MAKE_STATIC_ENT(32, NGHTTP3_QPACK_TOKEN_ACCEPT_RANGES, 1713753958u), + MAKE_STATIC_ENT(73, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_CREDENTIALS, + 901040780u), + MAKE_STATIC_ENT(74, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_CREDENTIALS, + 901040780u), + MAKE_STATIC_ENT(33, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_HEADERS, + 1524311232u), + MAKE_STATIC_ENT(34, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_HEADERS, + 1524311232u), + MAKE_STATIC_ENT(75, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_HEADERS, + 1524311232u), + MAKE_STATIC_ENT(76, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_METHODS, + 2175229868u), + MAKE_STATIC_ENT(77, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_METHODS, + 2175229868u), + MAKE_STATIC_ENT(78, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_METHODS, + 2175229868u), + MAKE_STATIC_ENT(35, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_ORIGIN, + 2710797292u), + MAKE_STATIC_ENT(79, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_EXPOSE_HEADERS, + 2449824425u), + MAKE_STATIC_ENT(80, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_REQUEST_HEADERS, + 3599549072u), + MAKE_STATIC_ENT(81, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_REQUEST_METHOD, + 2417078055u), + MAKE_STATIC_ENT(82, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_REQUEST_METHOD, + 2417078055u), + MAKE_STATIC_ENT(2, NGHTTP3_QPACK_TOKEN_AGE, 742476188u), + MAKE_STATIC_ENT(83, NGHTTP3_QPACK_TOKEN_ALT_SVC, 2148877059u), + MAKE_STATIC_ENT(84, NGHTTP3_QPACK_TOKEN_AUTHORIZATION, 2436257726u), + MAKE_STATIC_ENT(36, NGHTTP3_QPACK_TOKEN_CACHE_CONTROL, 1355326669u), + MAKE_STATIC_ENT(37, NGHTTP3_QPACK_TOKEN_CACHE_CONTROL, 1355326669u), + MAKE_STATIC_ENT(38, NGHTTP3_QPACK_TOKEN_CACHE_CONTROL, 1355326669u), + MAKE_STATIC_ENT(39, NGHTTP3_QPACK_TOKEN_CACHE_CONTROL, 1355326669u), + MAKE_STATIC_ENT(40, NGHTTP3_QPACK_TOKEN_CACHE_CONTROL, 1355326669u), + MAKE_STATIC_ENT(41, NGHTTP3_QPACK_TOKEN_CACHE_CONTROL, 1355326669u), + MAKE_STATIC_ENT(3, NGHTTP3_QPACK_TOKEN_CONTENT_DISPOSITION, 3889184348u), + MAKE_STATIC_ENT(42, NGHTTP3_QPACK_TOKEN_CONTENT_ENCODING, 65203592u), + MAKE_STATIC_ENT(43, NGHTTP3_QPACK_TOKEN_CONTENT_ENCODING, 65203592u), + MAKE_STATIC_ENT(4, NGHTTP3_QPACK_TOKEN_CONTENT_LENGTH, 1308181789u), + MAKE_STATIC_ENT(85, NGHTTP3_QPACK_TOKEN_CONTENT_SECURITY_POLICY, + 1569039836u), + MAKE_STATIC_ENT(44, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u), + MAKE_STATIC_ENT(45, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u), + MAKE_STATIC_ENT(46, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u), + MAKE_STATIC_ENT(47, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u), + MAKE_STATIC_ENT(48, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u), + MAKE_STATIC_ENT(49, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u), + MAKE_STATIC_ENT(50, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u), + MAKE_STATIC_ENT(51, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u), + MAKE_STATIC_ENT(52, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u), + MAKE_STATIC_ENT(53, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u), + MAKE_STATIC_ENT(54, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u), + MAKE_STATIC_ENT(5, NGHTTP3_QPACK_TOKEN_COOKIE, 2007449791u), + MAKE_STATIC_ENT(6, NGHTTP3_QPACK_TOKEN_DATE, 3564297305u), + MAKE_STATIC_ENT(86, NGHTTP3_QPACK_TOKEN_EARLY_DATA, 4080895051u), + MAKE_STATIC_ENT(7, NGHTTP3_QPACK_TOKEN_ETAG, 113792960u), + MAKE_STATIC_ENT(87, NGHTTP3_QPACK_TOKEN_EXPECT_CT, 1183214960u), + MAKE_STATIC_ENT(88, NGHTTP3_QPACK_TOKEN_FORWARDED, 1485178027u), + MAKE_STATIC_ENT(8, NGHTTP3_QPACK_TOKEN_IF_MODIFIED_SINCE, 2213050793u), + MAKE_STATIC_ENT(9, NGHTTP3_QPACK_TOKEN_IF_NONE_MATCH, 2536202615u), + MAKE_STATIC_ENT(89, NGHTTP3_QPACK_TOKEN_IF_RANGE, 2340978238u), + MAKE_STATIC_ENT(10, NGHTTP3_QPACK_TOKEN_LAST_MODIFIED, 3226950251u), + MAKE_STATIC_ENT(11, NGHTTP3_QPACK_TOKEN_LINK, 232457833u), + MAKE_STATIC_ENT(12, NGHTTP3_QPACK_TOKEN_LOCATION, 200649126u), + MAKE_STATIC_ENT(90, NGHTTP3_QPACK_TOKEN_ORIGIN, 3649018447u), + MAKE_STATIC_ENT(91, NGHTTP3_QPACK_TOKEN_PURPOSE, 4212263681u), + MAKE_STATIC_ENT(55, NGHTTP3_QPACK_TOKEN_RANGE, 4208725202u), + MAKE_STATIC_ENT(13, NGHTTP3_QPACK_TOKEN_REFERER, 3969579366u), + MAKE_STATIC_ENT(92, NGHTTP3_QPACK_TOKEN_SERVER, 1085029842u), + MAKE_STATIC_ENT(14, NGHTTP3_QPACK_TOKEN_SET_COOKIE, 1848371000u), + MAKE_STATIC_ENT(56, NGHTTP3_QPACK_TOKEN_STRICT_TRANSPORT_SECURITY, + 4138147361u), + MAKE_STATIC_ENT(57, NGHTTP3_QPACK_TOKEN_STRICT_TRANSPORT_SECURITY, + 4138147361u), + MAKE_STATIC_ENT(58, NGHTTP3_QPACK_TOKEN_STRICT_TRANSPORT_SECURITY, + 4138147361u), + MAKE_STATIC_ENT(93, NGHTTP3_QPACK_TOKEN_TIMING_ALLOW_ORIGIN, 2432297564u), + MAKE_STATIC_ENT(94, NGHTTP3_QPACK_TOKEN_UPGRADE_INSECURE_REQUESTS, + 2479169413u), + MAKE_STATIC_ENT(95, NGHTTP3_QPACK_TOKEN_USER_AGENT, 606444526u), + MAKE_STATIC_ENT(59, NGHTTP3_QPACK_TOKEN_VARY, 1085005381u), + MAKE_STATIC_ENT(60, NGHTTP3_QPACK_TOKEN_VARY, 1085005381u), + MAKE_STATIC_ENT(61, NGHTTP3_QPACK_TOKEN_X_CONTENT_TYPE_OPTIONS, + 3644557769u), + MAKE_STATIC_ENT(96, NGHTTP3_QPACK_TOKEN_X_FORWARDED_FOR, 2914187656u), + MAKE_STATIC_ENT(97, NGHTTP3_QPACK_TOKEN_X_FRAME_OPTIONS, 3993834824u), + MAKE_STATIC_ENT(98, NGHTTP3_QPACK_TOKEN_X_FRAME_OPTIONS, 3993834824u), + MAKE_STATIC_ENT(62, NGHTTP3_QPACK_TOKEN_X_XSS_PROTECTION, 2501058888u), +}; + +/* Make scalar initialization form of nghttp3_qpack_static_entry */ +#define MAKE_STATIC_HD(N, V, T) \ + { \ + {NULL, (uint8_t *)(N), sizeof((N)) - 1, -1}, \ + {NULL, (uint8_t *)(V), sizeof((V)) - 1, -1}, T \ + } + +static nghttp3_qpack_static_header stable[] = { + MAKE_STATIC_HD(":authority", "", NGHTTP3_QPACK_TOKEN__AUTHORITY), + MAKE_STATIC_HD(":path", "/", NGHTTP3_QPACK_TOKEN__PATH), + MAKE_STATIC_HD("age", "0", NGHTTP3_QPACK_TOKEN_AGE), + MAKE_STATIC_HD("content-disposition", "", + NGHTTP3_QPACK_TOKEN_CONTENT_DISPOSITION), + MAKE_STATIC_HD("content-length", "0", NGHTTP3_QPACK_TOKEN_CONTENT_LENGTH), + MAKE_STATIC_HD("cookie", "", NGHTTP3_QPACK_TOKEN_COOKIE), + MAKE_STATIC_HD("date", "", NGHTTP3_QPACK_TOKEN_DATE), + MAKE_STATIC_HD("etag", "", NGHTTP3_QPACK_TOKEN_ETAG), + MAKE_STATIC_HD("if-modified-since", "", + NGHTTP3_QPACK_TOKEN_IF_MODIFIED_SINCE), + MAKE_STATIC_HD("if-none-match", "", NGHTTP3_QPACK_TOKEN_IF_NONE_MATCH), + MAKE_STATIC_HD("last-modified", "", NGHTTP3_QPACK_TOKEN_LAST_MODIFIED), + MAKE_STATIC_HD("link", "", NGHTTP3_QPACK_TOKEN_LINK), + MAKE_STATIC_HD("location", "", NGHTTP3_QPACK_TOKEN_LOCATION), + MAKE_STATIC_HD("referer", "", NGHTTP3_QPACK_TOKEN_REFERER), + MAKE_STATIC_HD("set-cookie", "", NGHTTP3_QPACK_TOKEN_SET_COOKIE), + MAKE_STATIC_HD(":method", "CONNECT", NGHTTP3_QPACK_TOKEN__METHOD), + MAKE_STATIC_HD(":method", "DELETE", NGHTTP3_QPACK_TOKEN__METHOD), + MAKE_STATIC_HD(":method", "GET", NGHTTP3_QPACK_TOKEN__METHOD), + MAKE_STATIC_HD(":method", "HEAD", NGHTTP3_QPACK_TOKEN__METHOD), + MAKE_STATIC_HD(":method", "OPTIONS", NGHTTP3_QPACK_TOKEN__METHOD), + MAKE_STATIC_HD(":method", "POST", NGHTTP3_QPACK_TOKEN__METHOD), + MAKE_STATIC_HD(":method", "PUT", NGHTTP3_QPACK_TOKEN__METHOD), + MAKE_STATIC_HD(":scheme", "http", NGHTTP3_QPACK_TOKEN__SCHEME), + MAKE_STATIC_HD(":scheme", "https", NGHTTP3_QPACK_TOKEN__SCHEME), + MAKE_STATIC_HD(":status", "103", NGHTTP3_QPACK_TOKEN__STATUS), + MAKE_STATIC_HD(":status", "200", NGHTTP3_QPACK_TOKEN__STATUS), + MAKE_STATIC_HD(":status", "304", NGHTTP3_QPACK_TOKEN__STATUS), + MAKE_STATIC_HD(":status", "404", NGHTTP3_QPACK_TOKEN__STATUS), + MAKE_STATIC_HD(":status", "503", NGHTTP3_QPACK_TOKEN__STATUS), + MAKE_STATIC_HD("accept", "*/*", NGHTTP3_QPACK_TOKEN_ACCEPT), + MAKE_STATIC_HD("accept", "application/dns-message", + NGHTTP3_QPACK_TOKEN_ACCEPT), + MAKE_STATIC_HD("accept-encoding", "gzip, deflate, br", + NGHTTP3_QPACK_TOKEN_ACCEPT_ENCODING), + MAKE_STATIC_HD("accept-ranges", "bytes", NGHTTP3_QPACK_TOKEN_ACCEPT_RANGES), + MAKE_STATIC_HD("access-control-allow-headers", "cache-control", + NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_HEADERS), + MAKE_STATIC_HD("access-control-allow-headers", "content-type", + NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_HEADERS), + MAKE_STATIC_HD("access-control-allow-origin", "*", + NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_ORIGIN), + MAKE_STATIC_HD("cache-control", "max-age=0", + NGHTTP3_QPACK_TOKEN_CACHE_CONTROL), + MAKE_STATIC_HD("cache-control", "max-age=2592000", + NGHTTP3_QPACK_TOKEN_CACHE_CONTROL), + MAKE_STATIC_HD("cache-control", "max-age=604800", + NGHTTP3_QPACK_TOKEN_CACHE_CONTROL), + MAKE_STATIC_HD("cache-control", "no-cache", + NGHTTP3_QPACK_TOKEN_CACHE_CONTROL), + MAKE_STATIC_HD("cache-control", "no-store", + NGHTTP3_QPACK_TOKEN_CACHE_CONTROL), + MAKE_STATIC_HD("cache-control", "public, max-age=31536000", + NGHTTP3_QPACK_TOKEN_CACHE_CONTROL), + MAKE_STATIC_HD("content-encoding", "br", + NGHTTP3_QPACK_TOKEN_CONTENT_ENCODING), + MAKE_STATIC_HD("content-encoding", "gzip", + NGHTTP3_QPACK_TOKEN_CONTENT_ENCODING), + MAKE_STATIC_HD("content-type", "application/dns-message", + NGHTTP3_QPACK_TOKEN_CONTENT_TYPE), + MAKE_STATIC_HD("content-type", "application/javascript", + NGHTTP3_QPACK_TOKEN_CONTENT_TYPE), + MAKE_STATIC_HD("content-type", "application/json", + NGHTTP3_QPACK_TOKEN_CONTENT_TYPE), + MAKE_STATIC_HD("content-type", "application/x-www-form-urlencoded", + NGHTTP3_QPACK_TOKEN_CONTENT_TYPE), + MAKE_STATIC_HD("content-type", "image/gif", + NGHTTP3_QPACK_TOKEN_CONTENT_TYPE), + MAKE_STATIC_HD("content-type", "image/jpeg", + NGHTTP3_QPACK_TOKEN_CONTENT_TYPE), + MAKE_STATIC_HD("content-type", "image/png", + NGHTTP3_QPACK_TOKEN_CONTENT_TYPE), + MAKE_STATIC_HD("content-type", "text/css", + NGHTTP3_QPACK_TOKEN_CONTENT_TYPE), + MAKE_STATIC_HD("content-type", "text/html; charset=utf-8", + NGHTTP3_QPACK_TOKEN_CONTENT_TYPE), + MAKE_STATIC_HD("content-type", "text/plain", + NGHTTP3_QPACK_TOKEN_CONTENT_TYPE), + MAKE_STATIC_HD("content-type", "text/plain;charset=utf-8", + NGHTTP3_QPACK_TOKEN_CONTENT_TYPE), + MAKE_STATIC_HD("range", "bytes=0-", NGHTTP3_QPACK_TOKEN_RANGE), + MAKE_STATIC_HD("strict-transport-security", "max-age=31536000", + NGHTTP3_QPACK_TOKEN_STRICT_TRANSPORT_SECURITY), + MAKE_STATIC_HD("strict-transport-security", + "max-age=31536000; includesubdomains", + NGHTTP3_QPACK_TOKEN_STRICT_TRANSPORT_SECURITY), + MAKE_STATIC_HD("strict-transport-security", + "max-age=31536000; includesubdomains; preload", + NGHTTP3_QPACK_TOKEN_STRICT_TRANSPORT_SECURITY), + MAKE_STATIC_HD("vary", "accept-encoding", NGHTTP3_QPACK_TOKEN_VARY), + MAKE_STATIC_HD("vary", "origin", NGHTTP3_QPACK_TOKEN_VARY), + MAKE_STATIC_HD("x-content-type-options", "nosniff", + NGHTTP3_QPACK_TOKEN_X_CONTENT_TYPE_OPTIONS), + MAKE_STATIC_HD("x-xss-protection", "1; mode=block", + NGHTTP3_QPACK_TOKEN_X_XSS_PROTECTION), + MAKE_STATIC_HD(":status", "100", NGHTTP3_QPACK_TOKEN__STATUS), + MAKE_STATIC_HD(":status", "204", NGHTTP3_QPACK_TOKEN__STATUS), + MAKE_STATIC_HD(":status", "206", NGHTTP3_QPACK_TOKEN__STATUS), + MAKE_STATIC_HD(":status", "302", NGHTTP3_QPACK_TOKEN__STATUS), + MAKE_STATIC_HD(":status", "400", NGHTTP3_QPACK_TOKEN__STATUS), + MAKE_STATIC_HD(":status", "403", NGHTTP3_QPACK_TOKEN__STATUS), + MAKE_STATIC_HD(":status", "421", NGHTTP3_QPACK_TOKEN__STATUS), + MAKE_STATIC_HD(":status", "425", NGHTTP3_QPACK_TOKEN__STATUS), + MAKE_STATIC_HD(":status", "500", NGHTTP3_QPACK_TOKEN__STATUS), + MAKE_STATIC_HD("accept-language", "", NGHTTP3_QPACK_TOKEN_ACCEPT_LANGUAGE), + MAKE_STATIC_HD("access-control-allow-credentials", "FALSE", + NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_CREDENTIALS), + MAKE_STATIC_HD("access-control-allow-credentials", "TRUE", + NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_CREDENTIALS), + MAKE_STATIC_HD("access-control-allow-headers", "*", + NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_HEADERS), + MAKE_STATIC_HD("access-control-allow-methods", "get", + NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_METHODS), + MAKE_STATIC_HD("access-control-allow-methods", "get, post, options", + NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_METHODS), + MAKE_STATIC_HD("access-control-allow-methods", "options", + NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_METHODS), + MAKE_STATIC_HD("access-control-expose-headers", "content-length", + NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_EXPOSE_HEADERS), + MAKE_STATIC_HD("access-control-request-headers", "content-type", + NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_REQUEST_HEADERS), + MAKE_STATIC_HD("access-control-request-method", "get", + NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_REQUEST_METHOD), + MAKE_STATIC_HD("access-control-request-method", "post", + NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_REQUEST_METHOD), + MAKE_STATIC_HD("alt-svc", "clear", NGHTTP3_QPACK_TOKEN_ALT_SVC), + MAKE_STATIC_HD("authorization", "", NGHTTP3_QPACK_TOKEN_AUTHORIZATION), + MAKE_STATIC_HD("content-security-policy", + "script-src 'none'; object-src 'none'; base-uri 'none'", + NGHTTP3_QPACK_TOKEN_CONTENT_SECURITY_POLICY), + MAKE_STATIC_HD("early-data", "1", NGHTTP3_QPACK_TOKEN_EARLY_DATA), + MAKE_STATIC_HD("expect-ct", "", NGHTTP3_QPACK_TOKEN_EXPECT_CT), + MAKE_STATIC_HD("forwarded", "", NGHTTP3_QPACK_TOKEN_FORWARDED), + MAKE_STATIC_HD("if-range", "", NGHTTP3_QPACK_TOKEN_IF_RANGE), + MAKE_STATIC_HD("origin", "", NGHTTP3_QPACK_TOKEN_ORIGIN), + MAKE_STATIC_HD("purpose", "prefetch", NGHTTP3_QPACK_TOKEN_PURPOSE), + MAKE_STATIC_HD("server", "", NGHTTP3_QPACK_TOKEN_SERVER), + MAKE_STATIC_HD("timing-allow-origin", "*", + NGHTTP3_QPACK_TOKEN_TIMING_ALLOW_ORIGIN), + MAKE_STATIC_HD("upgrade-insecure-requests", "1", + NGHTTP3_QPACK_TOKEN_UPGRADE_INSECURE_REQUESTS), + MAKE_STATIC_HD("user-agent", "", NGHTTP3_QPACK_TOKEN_USER_AGENT), + MAKE_STATIC_HD("x-forwarded-for", "", NGHTTP3_QPACK_TOKEN_X_FORWARDED_FOR), + MAKE_STATIC_HD("x-frame-options", "deny", + NGHTTP3_QPACK_TOKEN_X_FRAME_OPTIONS), + MAKE_STATIC_HD("x-frame-options", "sameorigin", + NGHTTP3_QPACK_TOKEN_X_FRAME_OPTIONS), +}; + +static int memeq(const void *s1, const void *s2, size_t n) { + return n == 0 || memcmp(s1, s2, n) == 0; +} + +/* Generated by genlibtokenlookup.py */ +static int32_t qpack_lookup_token(const uint8_t *name, size_t namelen) { + switch (namelen) { + case 2: + switch (name[1]) { + case 'e': + if (memeq("t", name, 1)) { + return NGHTTP3_QPACK_TOKEN_TE; + } + break; + } + break; + case 3: + switch (name[2]) { + case 'e': + if (memeq("ag", name, 2)) { + return NGHTTP3_QPACK_TOKEN_AGE; + } + break; + } + break; + case 4: + switch (name[3]) { + case 'e': + if (memeq("dat", name, 3)) { + return NGHTTP3_QPACK_TOKEN_DATE; + } + break; + case 'g': + if (memeq("eta", name, 3)) { + return NGHTTP3_QPACK_TOKEN_ETAG; + } + break; + case 'k': + if (memeq("lin", name, 3)) { + return NGHTTP3_QPACK_TOKEN_LINK; + } + break; + case 't': + if (memeq("hos", name, 3)) { + return NGHTTP3_QPACK_TOKEN_HOST; + } + break; + case 'y': + if (memeq("var", name, 3)) { + return NGHTTP3_QPACK_TOKEN_VARY; + } + break; + } + break; + case 5: + switch (name[4]) { + case 'e': + if (memeq("rang", name, 4)) { + return NGHTTP3_QPACK_TOKEN_RANGE; + } + break; + case 'h': + if (memeq(":pat", name, 4)) { + return NGHTTP3_QPACK_TOKEN__PATH; + } + break; + } + break; + case 6: + switch (name[5]) { + case 'e': + if (memeq("cooki", name, 5)) { + return NGHTTP3_QPACK_TOKEN_COOKIE; + } + break; + case 'n': + if (memeq("origi", name, 5)) { + return NGHTTP3_QPACK_TOKEN_ORIGIN; + } + break; + case 'r': + if (memeq("serve", name, 5)) { + return NGHTTP3_QPACK_TOKEN_SERVER; + } + break; + case 't': + if (memeq("accep", name, 5)) { + return NGHTTP3_QPACK_TOKEN_ACCEPT; + } + break; + } + break; + case 7: + switch (name[6]) { + case 'c': + if (memeq("alt-sv", name, 6)) { + return NGHTTP3_QPACK_TOKEN_ALT_SVC; + } + break; + case 'd': + if (memeq(":metho", name, 6)) { + return NGHTTP3_QPACK_TOKEN__METHOD; + } + break; + case 'e': + if (memeq(":schem", name, 6)) { + return NGHTTP3_QPACK_TOKEN__SCHEME; + } + if (memeq("purpos", name, 6)) { + return NGHTTP3_QPACK_TOKEN_PURPOSE; + } + if (memeq("upgrad", name, 6)) { + return NGHTTP3_QPACK_TOKEN_UPGRADE; + } + break; + case 'r': + if (memeq("refere", name, 6)) { + return NGHTTP3_QPACK_TOKEN_REFERER; + } + break; + case 's': + if (memeq(":statu", name, 6)) { + return NGHTTP3_QPACK_TOKEN__STATUS; + } + break; + } + break; + case 8: + switch (name[7]) { + case 'e': + if (memeq("if-rang", name, 7)) { + return NGHTTP3_QPACK_TOKEN_IF_RANGE; + } + break; + case 'n': + if (memeq("locatio", name, 7)) { + return NGHTTP3_QPACK_TOKEN_LOCATION; + } + break; + case 'y': + if (memeq("priorit", name, 7)) { + return NGHTTP3_QPACK_TOKEN_PRIORITY; + } + break; + } + break; + case 9: + switch (name[8]) { + case 'd': + if (memeq("forwarde", name, 8)) { + return NGHTTP3_QPACK_TOKEN_FORWARDED; + } + break; + case 'l': + if (memeq(":protoco", name, 8)) { + return NGHTTP3_QPACK_TOKEN__PROTOCOL; + } + break; + case 't': + if (memeq("expect-c", name, 8)) { + return NGHTTP3_QPACK_TOKEN_EXPECT_CT; + } + break; + } + break; + case 10: + switch (name[9]) { + case 'a': + if (memeq("early-dat", name, 9)) { + return NGHTTP3_QPACK_TOKEN_EARLY_DATA; + } + break; + case 'e': + if (memeq("keep-aliv", name, 9)) { + return NGHTTP3_QPACK_TOKEN_KEEP_ALIVE; + } + if (memeq("set-cooki", name, 9)) { + return NGHTTP3_QPACK_TOKEN_SET_COOKIE; + } + break; + case 'n': + if (memeq("connectio", name, 9)) { + return NGHTTP3_QPACK_TOKEN_CONNECTION; + } + break; + case 't': + if (memeq("user-agen", name, 9)) { + return NGHTTP3_QPACK_TOKEN_USER_AGENT; + } + break; + case 'y': + if (memeq(":authorit", name, 9)) { + return NGHTTP3_QPACK_TOKEN__AUTHORITY; + } + break; + } + break; + case 12: + switch (name[11]) { + case 'e': + if (memeq("content-typ", name, 11)) { + return NGHTTP3_QPACK_TOKEN_CONTENT_TYPE; + } + break; + } + break; + case 13: + switch (name[12]) { + case 'd': + if (memeq("last-modifie", name, 12)) { + return NGHTTP3_QPACK_TOKEN_LAST_MODIFIED; + } + break; + case 'h': + if (memeq("if-none-matc", name, 12)) { + return NGHTTP3_QPACK_TOKEN_IF_NONE_MATCH; + } + break; + case 'l': + if (memeq("cache-contro", name, 12)) { + return NGHTTP3_QPACK_TOKEN_CACHE_CONTROL; + } + break; + case 'n': + if (memeq("authorizatio", name, 12)) { + return NGHTTP3_QPACK_TOKEN_AUTHORIZATION; + } + break; + case 's': + if (memeq("accept-range", name, 12)) { + return NGHTTP3_QPACK_TOKEN_ACCEPT_RANGES; + } + break; + } + break; + case 14: + switch (name[13]) { + case 'h': + if (memeq("content-lengt", name, 13)) { + return NGHTTP3_QPACK_TOKEN_CONTENT_LENGTH; + } + break; + } + break; + case 15: + switch (name[14]) { + case 'e': + if (memeq("accept-languag", name, 14)) { + return NGHTTP3_QPACK_TOKEN_ACCEPT_LANGUAGE; + } + break; + case 'g': + if (memeq("accept-encodin", name, 14)) { + return NGHTTP3_QPACK_TOKEN_ACCEPT_ENCODING; + } + break; + case 'r': + if (memeq("x-forwarded-fo", name, 14)) { + return NGHTTP3_QPACK_TOKEN_X_FORWARDED_FOR; + } + break; + case 's': + if (memeq("x-frame-option", name, 14)) { + return NGHTTP3_QPACK_TOKEN_X_FRAME_OPTIONS; + } + break; + } + break; + case 16: + switch (name[15]) { + case 'g': + if (memeq("content-encodin", name, 15)) { + return NGHTTP3_QPACK_TOKEN_CONTENT_ENCODING; + } + break; + case 'n': + if (memeq("proxy-connectio", name, 15)) { + return NGHTTP3_QPACK_TOKEN_PROXY_CONNECTION; + } + if (memeq("x-xss-protectio", name, 15)) { + return NGHTTP3_QPACK_TOKEN_X_XSS_PROTECTION; + } + break; + } + break; + case 17: + switch (name[16]) { + case 'e': + if (memeq("if-modified-sinc", name, 16)) { + return NGHTTP3_QPACK_TOKEN_IF_MODIFIED_SINCE; + } + break; + case 'g': + if (memeq("transfer-encodin", name, 16)) { + return NGHTTP3_QPACK_TOKEN_TRANSFER_ENCODING; + } + break; + } + break; + case 19: + switch (name[18]) { + case 'n': + if (memeq("content-dispositio", name, 18)) { + return NGHTTP3_QPACK_TOKEN_CONTENT_DISPOSITION; + } + if (memeq("timing-allow-origi", name, 18)) { + return NGHTTP3_QPACK_TOKEN_TIMING_ALLOW_ORIGIN; + } + break; + } + break; + case 22: + switch (name[21]) { + case 's': + if (memeq("x-content-type-option", name, 21)) { + return NGHTTP3_QPACK_TOKEN_X_CONTENT_TYPE_OPTIONS; + } + break; + } + break; + case 23: + switch (name[22]) { + case 'y': + if (memeq("content-security-polic", name, 22)) { + return NGHTTP3_QPACK_TOKEN_CONTENT_SECURITY_POLICY; + } + break; + } + break; + case 25: + switch (name[24]) { + case 's': + if (memeq("upgrade-insecure-request", name, 24)) { + return NGHTTP3_QPACK_TOKEN_UPGRADE_INSECURE_REQUESTS; + } + break; + case 'y': + if (memeq("strict-transport-securit", name, 24)) { + return NGHTTP3_QPACK_TOKEN_STRICT_TRANSPORT_SECURITY; + } + break; + } + break; + case 27: + switch (name[26]) { + case 'n': + if (memeq("access-control-allow-origi", name, 26)) { + return NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_ORIGIN; + } + break; + } + break; + case 28: + switch (name[27]) { + case 's': + if (memeq("access-control-allow-header", name, 27)) { + return NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_HEADERS; + } + if (memeq("access-control-allow-method", name, 27)) { + return NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_METHODS; + } + break; + } + break; + case 29: + switch (name[28]) { + case 'd': + if (memeq("access-control-request-metho", name, 28)) { + return NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_REQUEST_METHOD; + } + break; + case 's': + if (memeq("access-control-expose-header", name, 28)) { + return NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_EXPOSE_HEADERS; + } + break; + } + break; + case 30: + switch (name[29]) { + case 's': + if (memeq("access-control-request-header", name, 29)) { + return NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_REQUEST_HEADERS; + } + break; + } + break; + case 32: + switch (name[31]) { + case 's': + if (memeq("access-control-allow-credential", name, 31)) { + return NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_CREDENTIALS; + } + break; + } + break; + } + return -1; +} + +static size_t table_space(size_t namelen, size_t valuelen) { + return NGHTTP3_QPACK_ENTRY_OVERHEAD + namelen + valuelen; +} + +static int qpack_nv_name_eq(const nghttp3_qpack_nv *a, const nghttp3_nv *b) { + return a->name->len == b->namelen && + memeq(a->name->base, b->name, b->namelen); +} + +static int qpack_nv_value_eq(const nghttp3_qpack_nv *a, const nghttp3_nv *b) { + return a->value->len == b->valuelen && + memeq(a->value->base, b->value, b->valuelen); +} + +static void qpack_map_init(nghttp3_qpack_map *map) { + memset(map, 0, sizeof(nghttp3_qpack_map)); +} + +static void qpack_map_insert(nghttp3_qpack_map *map, nghttp3_qpack_entry *ent) { + nghttp3_qpack_entry **bucket; + + bucket = &map->table[ent->hash & (NGHTTP3_QPACK_MAP_SIZE - 1)]; + + if (*bucket == NULL) { + *bucket = ent; + return; + } + + /* larger absidx is linked near the root */ + ent->map_next = *bucket; + *bucket = ent; +} + +static void qpack_map_remove(nghttp3_qpack_map *map, nghttp3_qpack_entry *ent) { + nghttp3_qpack_entry **dst; + + dst = &map->table[ent->hash & (NGHTTP3_QPACK_MAP_SIZE - 1)]; + + for (; *dst; dst = &(*dst)->map_next) { + if (*dst != ent) { + continue; + } + + *dst = ent->map_next; + ent->map_next = NULL; + return; + } +} + +/* + * qpack_context_can_reference returns nonzero if dynamic table entry + * at |absidx| can be referenced. In other words, it is within + * ctx->max_dtable_capacity. + */ +static int qpack_context_can_reference(nghttp3_qpack_context *ctx, + uint64_t absidx) { + nghttp3_qpack_entry *ent = nghttp3_qpack_context_dtable_get(ctx, absidx); + return ctx->dtable_sum - ent->sum <= ctx->max_dtable_capacity; +} + +/* |*ppb_match| (post-base match), if it is not NULL, is always exact + match. */ +static void encoder_qpack_map_find(nghttp3_qpack_encoder *encoder, + int *exact_match, + nghttp3_qpack_entry **pmatch, + nghttp3_qpack_entry **ppb_match, + const nghttp3_nv *nv, int32_t token, + uint32_t hash, uint64_t krcnt, + int allow_blocking, int name_only) { + nghttp3_qpack_entry *p; + + *exact_match = 0; + *pmatch = NULL; + *ppb_match = NULL; + + for (p = encoder->dtable_map.table[hash & (NGHTTP3_QPACK_MAP_SIZE - 1)]; p; + p = p->map_next) { + if (token != p->nv.token || + (token == -1 && (hash != p->hash || !qpack_nv_name_eq(&p->nv, nv))) || + !qpack_context_can_reference(&encoder->ctx, p->absidx)) { + continue; + } + if (allow_blocking || p->absidx + 1 <= krcnt) { + if (!*pmatch) { + *pmatch = p; + if (name_only) { + return; + } + } + if (qpack_nv_value_eq(&p->nv, nv)) { + *pmatch = p; + *exact_match = 1; + return; + } + } else if (!*ppb_match && qpack_nv_value_eq(&p->nv, nv)) { + *ppb_match = p; + } + } +} + +/* + * qpack_context_init initializes |ctx|. |hard_max_dtable_capacity| + * is the upper bound of the dynamic table capacity. |mem| is a + * memory allocator. + * + * The maximum dynamic table size is governed by + * ctx->max_dtable_capacity and it is initialized to 0. + * |hard_max_dtable_capacity| is the upper bound of + * ctx->max_dtable_capacity. + * + * This function returns 0 if it succeeds, or one of the following + * negative error codes: + * + * NGHTTP3_ERR_NOMEM + * Out of memory. + */ +static int qpack_context_init(nghttp3_qpack_context *ctx, + size_t hard_max_dtable_capacity, + size_t max_blocked_streams, + const nghttp3_mem *mem) { + int rv; + size_t len = 4096 / NGHTTP3_QPACK_ENTRY_OVERHEAD; + size_t len2; + + for (len2 = 1; len2 < len; len2 <<= 1) + ; + + rv = nghttp3_ringbuf_init(&ctx->dtable, len2, sizeof(nghttp3_qpack_entry *), + mem); + if (rv != 0) { + return rv; + } + + ctx->mem = mem; + ctx->dtable_size = 0; + ctx->dtable_sum = 0; + ctx->hard_max_dtable_capacity = hard_max_dtable_capacity; + ctx->max_dtable_capacity = 0; + ctx->max_blocked_streams = max_blocked_streams; + ctx->next_absidx = 0; + ctx->bad = 0; + + return 0; +} + +static void qpack_context_free(nghttp3_qpack_context *ctx) { + nghttp3_qpack_entry *ent; + size_t i, len = nghttp3_ringbuf_len(&ctx->dtable); + + for (i = 0; i < len; ++i) { + ent = *(nghttp3_qpack_entry **)nghttp3_ringbuf_get(&ctx->dtable, i); + nghttp3_qpack_entry_free(ent); + nghttp3_mem_free(ctx->mem, ent); + } + nghttp3_ringbuf_free(&ctx->dtable); +} + +static int ref_min_cnt_less(const nghttp3_pq_entry *lhsx, + const nghttp3_pq_entry *rhsx) { + nghttp3_qpack_header_block_ref *lhs = + nghttp3_struct_of(lhsx, nghttp3_qpack_header_block_ref, min_cnts_pe); + nghttp3_qpack_header_block_ref *rhs = + nghttp3_struct_of(rhsx, nghttp3_qpack_header_block_ref, min_cnts_pe); + + return lhs->min_cnt < rhs->min_cnt; +} + +typedef struct nghttp3_blocked_streams_key { + uint64_t max_cnt; + uint64_t id; +} nghttp3_blocked_streams_key; + +static int max_cnt_greater(const nghttp3_ksl_key *lhs, + const nghttp3_ksl_key *rhs) { + const nghttp3_blocked_streams_key *a = lhs; + const nghttp3_blocked_streams_key *b = rhs; + return a->max_cnt > b->max_cnt || (a->max_cnt == b->max_cnt && a->id < b->id); +} + +int nghttp3_qpack_encoder_init(nghttp3_qpack_encoder *encoder, + size_t hard_max_dtable_capacity, + const nghttp3_mem *mem) { + int rv; + + rv = qpack_context_init(&encoder->ctx, hard_max_dtable_capacity, 0, mem); + if (rv != 0) { + return rv; + } + + nghttp3_map_init(&encoder->streams, mem); + + nghttp3_ksl_init(&encoder->blocked_streams, max_cnt_greater, + sizeof(nghttp3_blocked_streams_key), mem); + + qpack_map_init(&encoder->dtable_map); + nghttp3_pq_init(&encoder->min_cnts, ref_min_cnt_less, mem); + + encoder->krcnt = 0; + encoder->state = NGHTTP3_QPACK_DS_STATE_OPCODE; + encoder->opcode = 0; + encoder->min_dtable_update = SIZE_MAX; + encoder->last_max_dtable_update = 0; + encoder->flags = NGHTTP3_QPACK_ENCODER_FLAG_NONE; + + nghttp3_qpack_read_state_reset(&encoder->rstate); + + return 0; +} + +static int map_stream_free(void *data, void *ptr) { + const nghttp3_mem *mem = ptr; + nghttp3_qpack_stream *stream = data; + nghttp3_qpack_stream_del(stream, mem); + return 0; +} + +void nghttp3_qpack_encoder_free(nghttp3_qpack_encoder *encoder) { + nghttp3_pq_free(&encoder->min_cnts); + nghttp3_ksl_free(&encoder->blocked_streams); + nghttp3_map_each_free(&encoder->streams, map_stream_free, + (void *)encoder->ctx.mem); + nghttp3_map_free(&encoder->streams); + qpack_context_free(&encoder->ctx); +} + +void nghttp3_qpack_encoder_set_max_dtable_capacity( + nghttp3_qpack_encoder *encoder, size_t max_dtable_capacity) { + max_dtable_capacity = + nghttp3_min(max_dtable_capacity, encoder->ctx.hard_max_dtable_capacity); + + if (encoder->ctx.max_dtable_capacity == max_dtable_capacity) { + return; + } + + encoder->flags |= NGHTTP3_QPACK_ENCODER_FLAG_PENDING_SET_DTABLE_CAP; + + if (encoder->min_dtable_update > max_dtable_capacity) { + encoder->min_dtable_update = max_dtable_capacity; + encoder->ctx.max_dtable_capacity = max_dtable_capacity; + } + encoder->last_max_dtable_update = max_dtable_capacity; +} + +void nghttp3_qpack_encoder_set_max_blocked_streams( + nghttp3_qpack_encoder *encoder, size_t max_blocked_streams) { + encoder->ctx.max_blocked_streams = max_blocked_streams; +} + +uint64_t nghttp3_qpack_encoder_get_min_cnt(nghttp3_qpack_encoder *encoder) { + assert(!nghttp3_pq_empty(&encoder->min_cnts)); + + return nghttp3_struct_of(nghttp3_pq_top(&encoder->min_cnts), + nghttp3_qpack_header_block_ref, min_cnts_pe) + ->min_cnt; +} + +void nghttp3_qpack_encoder_shrink_dtable(nghttp3_qpack_encoder *encoder) { + nghttp3_ringbuf *dtable = &encoder->ctx.dtable; + const nghttp3_mem *mem = encoder->ctx.mem; + uint64_t min_cnt = UINT64_MAX; + size_t len; + nghttp3_qpack_entry *ent; + + if (encoder->ctx.dtable_size <= encoder->ctx.max_dtable_capacity) { + return; + } + + if (!nghttp3_pq_empty(&encoder->min_cnts)) { + min_cnt = nghttp3_qpack_encoder_get_min_cnt(encoder); + } + + for (; encoder->ctx.dtable_size > encoder->ctx.max_dtable_capacity;) { + len = nghttp3_ringbuf_len(dtable); + ent = *(nghttp3_qpack_entry **)nghttp3_ringbuf_get(dtable, len - 1); + if (ent->absidx + 1 == min_cnt) { + return; + } + + encoder->ctx.dtable_size -= + table_space(ent->nv.name->len, ent->nv.value->len); + + nghttp3_ringbuf_pop_back(dtable); + qpack_map_remove(&encoder->dtable_map, ent); + + nghttp3_qpack_entry_free(ent); + nghttp3_mem_free(mem, ent); + } +} + +/* + * qpack_encoder_add_stream_ref adds another dynamic table reference + * to a stream denoted by |stream_id|. |stream| must be NULL if no + * stream object is not found for the given stream ID. |max_cnt| and + * |min_cnt| is the maximum and minimum insert count it references + * respectively. + * + * This function returns 0 if it succeeds, or one of the following + * negative error codes: + * + * NGHTTP3_ERR_NOMEM + * Out of memory. + */ +static int qpack_encoder_add_stream_ref(nghttp3_qpack_encoder *encoder, + int64_t stream_id, + nghttp3_qpack_stream *stream, + uint64_t max_cnt, uint64_t min_cnt) { + nghttp3_qpack_header_block_ref *ref; + const nghttp3_mem *mem = encoder->ctx.mem; + uint64_t prev_max_cnt = 0; + int rv; + + if (stream == NULL) { + rv = nghttp3_qpack_stream_new(&stream, stream_id, mem); + if (rv != 0) { + assert(rv == NGHTTP3_ERR_NOMEM); + return rv; + } + rv = nghttp3_map_insert(&encoder->streams, + (nghttp3_map_key_type)stream->stream_id, stream); + if (rv != 0) { + assert(rv == NGHTTP3_ERR_NOMEM); + nghttp3_qpack_stream_del(stream, mem); + return rv; + } + } else { + prev_max_cnt = nghttp3_qpack_stream_get_max_cnt(stream); + if (nghttp3_qpack_encoder_stream_is_blocked(encoder, stream) && + max_cnt > prev_max_cnt) { + nghttp3_qpack_encoder_unblock_stream(encoder, stream); + } + } + + rv = nghttp3_qpack_header_block_ref_new(&ref, max_cnt, min_cnt, mem); + if (rv != 0) { + return rv; + } + + rv = nghttp3_qpack_stream_add_ref(stream, ref); + if (rv != 0) { + nghttp3_qpack_header_block_ref_del(ref, mem); + return rv; + } + + if (max_cnt > prev_max_cnt && + nghttp3_qpack_encoder_stream_is_blocked(encoder, stream)) { + rv = nghttp3_qpack_encoder_block_stream(encoder, stream); + if (rv != 0) { + return rv; + } + } + + return nghttp3_pq_push(&encoder->min_cnts, &ref->min_cnts_pe); +} + +static void qpack_encoder_remove_stream(nghttp3_qpack_encoder *encoder, + nghttp3_qpack_stream *stream) { + size_t i, len; + nghttp3_qpack_header_block_ref *ref; + + nghttp3_map_remove(&encoder->streams, + (nghttp3_map_key_type)stream->stream_id); + + len = nghttp3_ringbuf_len(&stream->refs); + for (i = 0; i < len; ++i) { + ref = *(nghttp3_qpack_header_block_ref **)nghttp3_ringbuf_get(&stream->refs, + i); + + assert(ref->min_cnts_pe.index != NGHTTP3_PQ_BAD_INDEX); + + nghttp3_pq_remove(&encoder->min_cnts, &ref->min_cnts_pe); + } +} + +/* + * reserve_buf_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_streams > + nghttp3_ksl_len(&encoder->blocked_streams); + + DEBUGF("qpack::encode: stream %ld blocked=%d allow_blocking=%d\n", stream_id, + blocked_stream, allow_blocking); + + for (i = 0; i < nvlen; ++i) { + rv = nghttp3_qpack_encoder_encode_nv(encoder, &max_cnt, &min_cnt, rbuf, + ebuf, &nva[i], base, allow_blocking); + if (rv != 0) { + goto fail; + } + } + + nghttp3_qpack_encoder_write_field_section_prefix(encoder, pbuf, max_cnt, + base); + + /* TODO If max_cnt == 0, no reference is made to dtable. */ + if (!max_cnt) { + return 0; + } + + rv = qpack_encoder_add_stream_ref(encoder, stream_id, stream, max_cnt, + min_cnt); + if (rv != 0) { + goto fail; + } + + return 0; + +fail: + encoder->ctx.bad = 1; + return rv; +} + +/* + * qpack_write_number writes variable integer to |rbuf|. |num| is an + * integer to write. |prefix| is a prefix of variable integer + * encoding. + * + * This function returns 0 if it succeeds, or one of the following + * negative error codes: + * + * NGHTTP3_ERR_NOMEM + * Out of memory. + */ +static int qpack_write_number(nghttp3_buf *rbuf, uint8_t fb, uint64_t num, + size_t prefix, const nghttp3_mem *mem) { + int rv; + size_t len = nghttp3_qpack_put_varint_len(num, prefix); + uint8_t *p; + + rv = reserve_buf(rbuf, len, mem); + if (rv != 0) { + return rv; + } + + p = rbuf->last; + + *p = fb; + p = nghttp3_qpack_put_varint(p, num, prefix); + + assert((size_t)(p - rbuf->last) == len); + + rbuf->last = p; + + return 0; +} + +int nghttp3_qpack_encoder_process_dtable_update(nghttp3_qpack_encoder *encoder, + nghttp3_buf *ebuf) { + int rv; + + nghttp3_qpack_encoder_shrink_dtable(encoder); + + if (encoder->ctx.max_dtable_capacity < encoder->ctx.dtable_size || + !(encoder->flags & NGHTTP3_QPACK_ENCODER_FLAG_PENDING_SET_DTABLE_CAP)) { + return 0; + } + + if (encoder->min_dtable_update < encoder->last_max_dtable_update) { + rv = nghttp3_qpack_encoder_write_set_dtable_cap(encoder, ebuf, + encoder->min_dtable_update); + if (rv != 0) { + return rv; + } + } + + rv = nghttp3_qpack_encoder_write_set_dtable_cap( + encoder, ebuf, encoder->last_max_dtable_update); + if (rv != 0) { + return rv; + } + + encoder->flags &= (uint8_t)~NGHTTP3_QPACK_ENCODER_FLAG_PENDING_SET_DTABLE_CAP; + encoder->min_dtable_update = SIZE_MAX; + encoder->ctx.max_dtable_capacity = encoder->last_max_dtable_update; + + return 0; +} + +int nghttp3_qpack_encoder_write_set_dtable_cap(nghttp3_qpack_encoder *encoder, + nghttp3_buf *ebuf, size_t cap) { + DEBUGF("qpack::encode: Set Dynamic Table Capacity capacity=%zu\n", cap); + return qpack_write_number(ebuf, 0x20, cap, 5, encoder->ctx.mem); +} + +nghttp3_qpack_stream * +nghttp3_qpack_encoder_find_stream(nghttp3_qpack_encoder *encoder, + int64_t stream_id) { + return nghttp3_map_find(&encoder->streams, (nghttp3_map_key_type)stream_id); +} + +int nghttp3_qpack_encoder_stream_is_blocked(nghttp3_qpack_encoder *encoder, + nghttp3_qpack_stream *stream) { + return stream && encoder->krcnt < nghttp3_qpack_stream_get_max_cnt(stream); +} + +/* + * 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_capacity * 3 / 4) { + return NGHTTP3_QPACK_INDEXING_MODE_LITERAL; + } + + return NGHTTP3_QPACK_INDEXING_MODE_STORE; +} + +/* + * qpack_encoder_can_index returns nonzero if an entry which occupies + * |need| bytes can be inserted into dynamic table. |min_cnt| is the + * minimum insert count which blocked stream requires. + */ +static int qpack_encoder_can_index(nghttp3_qpack_encoder *encoder, size_t need, + uint64_t min_cnt) { + size_t avail = 0; + size_t len; + uint64_t gmin_cnt; + nghttp3_qpack_entry *min_ent, *last_ent; + nghttp3_ringbuf *dtable = &encoder->ctx.dtable; + + if (encoder->ctx.max_dtable_capacity > encoder->ctx.dtable_size) { + avail = encoder->ctx.max_dtable_capacity - encoder->ctx.dtable_size; + if (need <= avail) { + return 1; + } + } + + if (!nghttp3_pq_empty(&encoder->min_cnts)) { + gmin_cnt = nghttp3_qpack_encoder_get_min_cnt(encoder); + min_cnt = nghttp3_min(min_cnt, gmin_cnt); + } + + if (min_cnt == UINT64_MAX) { + return encoder->ctx.max_dtable_capacity >= need; + } + + min_ent = nghttp3_qpack_context_dtable_get(&encoder->ctx, min_cnt - 1); + + len = nghttp3_ringbuf_len(&encoder->ctx.dtable); + assert(len); + last_ent = *(nghttp3_qpack_entry **)nghttp3_ringbuf_get(dtable, len - 1); + + if (min_ent == last_ent) { + return 0; + } + + return avail + min_ent->sum - last_ent->sum >= need; +} + +/* + * qpack_encoder_can_index_nv returns nonzero if header field |nv| can + * be inserted into dynamic table. |min_cnt| is the minimum insert + * count which blocked stream requires. + */ +static int qpack_encoder_can_index_nv(nghttp3_qpack_encoder *encoder, + const nghttp3_nv *nv, uint64_t min_cnt) { + return qpack_encoder_can_index( + encoder, table_space(nv->namelen, nv->valuelen), min_cnt); +} + +/* + * qpack_encoder_can_index_duplicate returns nonzero if an entry at + * |absidx| in dynamic table can be inserted to dynamic table as + * duplicate. |min_cnt| is the minimum insert count which blocked + * stream requires. + */ +static int qpack_encoder_can_index_duplicate(nghttp3_qpack_encoder *encoder, + uint64_t absidx, + uint64_t min_cnt) { + nghttp3_qpack_entry *ent = + nghttp3_qpack_context_dtable_get(&encoder->ctx, absidx); + + return qpack_encoder_can_index( + encoder, table_space(ent->nv.name->len, ent->nv.value->len), min_cnt); +} + +/* + * qpack_context_check_draining returns nonzero if an entry at + * |absidx| in dynamic table is one of draining entries. + */ +static int qpack_context_check_draining(nghttp3_qpack_context *ctx, + uint64_t absidx) { + const size_t safe = ctx->max_dtable_capacity - + nghttp3_min(512, ctx->max_dtable_capacity * 1 / 8); + nghttp3_qpack_entry *ent = nghttp3_qpack_context_dtable_get(ctx, absidx); + + return ctx->dtable_sum - ent->sum > safe; +} + +int nghttp3_qpack_encoder_encode_nv(nghttp3_qpack_encoder *encoder, + uint64_t *pmax_cnt, uint64_t *pmin_cnt, + nghttp3_buf *rbuf, nghttp3_buf *ebuf, + const nghttp3_nv *nv, uint64_t base, + int allow_blocking) { + uint32_t hash = 0; + int32_t token; + nghttp3_qpack_indexing_mode indexing_mode; + nghttp3_qpack_lookup_result sres = {-1, 0, -1}, dres = {-1, 0, -1}; + nghttp3_qpack_entry *new_ent = NULL; + int static_entry; + int just_index = 0; + int rv; + + token = qpack_lookup_token(nv->name, nv->namelen); + static_entry = token != -1 && (size_t)token < nghttp3_arraylen(token_stable); + 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_capacity); + + while (ctx->dtable_size + space > ctx->max_dtable_capacity) { + i = nghttp3_ringbuf_len(&ctx->dtable); + assert(i); + ent = *(nghttp3_qpack_entry **)nghttp3_ringbuf_get(&ctx->dtable, i - 1); + + ctx->dtable_size -= table_space(ent->nv.name->len, ent->nv.value->len); + + nghttp3_ringbuf_pop_back(&ctx->dtable); + if (dtable_map) { + qpack_map_remove(dtable_map, ent); + } + + nghttp3_qpack_entry_free(ent); + nghttp3_mem_free(mem, ent); + } + + new_ent = nghttp3_mem_malloc(mem, sizeof(nghttp3_qpack_entry)); + if (new_ent == NULL) { + return NGHTTP3_ERR_NOMEM; + } + + nghttp3_qpack_entry_init(new_ent, qnv, ctx->dtable_sum, ctx->next_absidx++, + hash); + + if (nghttp3_ringbuf_full(&ctx->dtable)) { + rv = nghttp3_ringbuf_reserve(&ctx->dtable, + nghttp3_ringbuf_len(&ctx->dtable) * 2); + if (rv != 0) { + goto fail; + } + } + + p = nghttp3_ringbuf_push_front(&ctx->dtable); + *p = new_ent; + + if (dtable_map) { + qpack_map_insert(dtable_map, new_ent); + } + + ctx->dtable_size += space; + ctx->dtable_sum += space; + + return 0; + +fail: + nghttp3_qpack_entry_free(new_ent); + nghttp3_mem_free(mem, new_ent); + + return rv; +} + +int nghttp3_qpack_encoder_dtable_static_add(nghttp3_qpack_encoder *encoder, + uint64_t absidx, + const nghttp3_nv *nv, + uint32_t hash) { + const nghttp3_qpack_static_header *shd; + nghttp3_qpack_nv qnv; + const nghttp3_mem *mem = encoder->ctx.mem; + int rv; + + rv = nghttp3_rcbuf_new2(&qnv.value, nv->value, nv->valuelen, mem); + if (rv != 0) { + return rv; + } + + assert(nghttp3_arraylen(stable) > absidx); + + shd = &stable[absidx]; + + qnv.name = (nghttp3_rcbuf *)&shd->name; + qnv.token = shd->token; + qnv.flags = NGHTTP3_NV_FLAG_NONE; + + rv = nghttp3_qpack_context_dtable_add(&encoder->ctx, &qnv, + &encoder->dtable_map, hash); + + nghttp3_rcbuf_decref(qnv.value); + + return rv; +} + +int nghttp3_qpack_encoder_dtable_dynamic_add(nghttp3_qpack_encoder *encoder, + uint64_t absidx, + const nghttp3_nv *nv, + uint32_t hash) { + nghttp3_qpack_nv qnv; + nghttp3_qpack_entry *ent; + const nghttp3_mem *mem = encoder->ctx.mem; + int rv; + + rv = nghttp3_rcbuf_new2(&qnv.value, nv->value, nv->valuelen, mem); + if (rv != 0) { + return rv; + } + + ent = nghttp3_qpack_context_dtable_get(&encoder->ctx, absidx); + + qnv.name = ent->nv.name; + qnv.token = ent->nv.token; + qnv.flags = NGHTTP3_NV_FLAG_NONE; + + nghttp3_rcbuf_incref(qnv.name); + + rv = nghttp3_qpack_context_dtable_add(&encoder->ctx, &qnv, + &encoder->dtable_map, hash); + + nghttp3_rcbuf_decref(qnv.value); + nghttp3_rcbuf_decref(qnv.name); + + return rv; +} + +int nghttp3_qpack_encoder_dtable_duplicate_add(nghttp3_qpack_encoder *encoder, + uint64_t absidx) { + nghttp3_qpack_nv qnv; + nghttp3_qpack_entry *ent; + int rv; + + ent = nghttp3_qpack_context_dtable_get(&encoder->ctx, absidx); + + qnv = ent->nv; + nghttp3_rcbuf_incref(qnv.name); + nghttp3_rcbuf_incref(qnv.value); + + rv = nghttp3_qpack_context_dtable_add(&encoder->ctx, &qnv, + &encoder->dtable_map, ent->hash); + + nghttp3_rcbuf_decref(qnv.name); + nghttp3_rcbuf_decref(qnv.value); + + return rv; +} + +int nghttp3_qpack_encoder_dtable_literal_add(nghttp3_qpack_encoder *encoder, + const nghttp3_nv *nv, + int32_t token, uint32_t hash) { + nghttp3_qpack_nv qnv; + const nghttp3_mem *mem = encoder->ctx.mem; + int rv; + + rv = nghttp3_rcbuf_new2(&qnv.name, nv->name, nv->namelen, mem); + if (rv != 0) { + return rv; + } + + rv = nghttp3_rcbuf_new2(&qnv.value, nv->value, nv->valuelen, mem); + if (rv != 0) { + nghttp3_rcbuf_decref(qnv.name); + return rv; + } + + qnv.token = token; + qnv.flags = NGHTTP3_NV_FLAG_NONE; + + rv = nghttp3_qpack_context_dtable_add(&encoder->ctx, &qnv, + &encoder->dtable_map, hash); + + nghttp3_rcbuf_decref(qnv.value); + nghttp3_rcbuf_decref(qnv.name); + + return rv; +} + +nghttp3_qpack_entry * +nghttp3_qpack_context_dtable_get(nghttp3_qpack_context *ctx, uint64_t absidx) { + size_t relidx; + + assert(ctx->next_absidx > absidx); + assert(ctx->next_absidx - absidx - 1 < nghttp3_ringbuf_len(&ctx->dtable)); + + relidx = (size_t)(ctx->next_absidx - absidx - 1); + + return *(nghttp3_qpack_entry **)nghttp3_ringbuf_get(&ctx->dtable, relidx); +} + +nghttp3_qpack_entry * +nghttp3_qpack_context_dtable_top(nghttp3_qpack_context *ctx) { + assert(nghttp3_ringbuf_len(&ctx->dtable)); + return *(nghttp3_qpack_entry **)nghttp3_ringbuf_get(&ctx->dtable, 0); +} + +void nghttp3_qpack_entry_init(nghttp3_qpack_entry *ent, nghttp3_qpack_nv *qnv, + size_t sum, uint64_t absidx, uint32_t hash) { + ent->nv = *qnv; + ent->map_next = NULL; + ent->sum = sum; + ent->absidx = absidx; + ent->hash = hash; + + nghttp3_rcbuf_incref(ent->nv.name); + nghttp3_rcbuf_incref(ent->nv.value); +} + +void nghttp3_qpack_entry_free(nghttp3_qpack_entry *ent) { + nghttp3_rcbuf_decref(ent->nv.value); + nghttp3_rcbuf_decref(ent->nv.name); +} + +int nghttp3_qpack_encoder_block_stream(nghttp3_qpack_encoder *encoder, + nghttp3_qpack_stream *stream) { + nghttp3_blocked_streams_key bsk = { + nghttp3_struct_of(nghttp3_pq_top(&stream->max_cnts), + nghttp3_qpack_header_block_ref, max_cnts_pe) + ->max_cnt, + (uint64_t)stream->stream_id}; + + return nghttp3_ksl_insert(&encoder->blocked_streams, NULL, &bsk, stream); +} + +void nghttp3_qpack_encoder_unblock_stream(nghttp3_qpack_encoder *encoder, + nghttp3_qpack_stream *stream) { + nghttp3_blocked_streams_key bsk = { + nghttp3_struct_of(nghttp3_pq_top(&stream->max_cnts), + nghttp3_qpack_header_block_ref, max_cnts_pe) + ->max_cnt, + (uint64_t)stream->stream_id}; + nghttp3_ksl_it it; + + /* This is purely debugging purpose only */ + it = nghttp3_ksl_lower_bound(&encoder->blocked_streams, &bsk); + + assert(!nghttp3_ksl_it_end(&it)); + assert(nghttp3_ksl_it_get(&it) == stream); + + nghttp3_ksl_remove_hint(&encoder->blocked_streams, NULL, &it, &bsk); +} + +void nghttp3_qpack_encoder_unblock(nghttp3_qpack_encoder *encoder, + uint64_t max_cnt) { + nghttp3_blocked_streams_key bsk = {max_cnt, 0}; + nghttp3_ksl_it it; + + it = nghttp3_ksl_lower_bound(&encoder->blocked_streams, &bsk); + + for (; !nghttp3_ksl_it_end(&it);) { + bsk = *(nghttp3_blocked_streams_key *)nghttp3_ksl_it_key(&it); + nghttp3_ksl_remove_hint(&encoder->blocked_streams, &it, &it, &bsk); + } +} + +int nghttp3_qpack_encoder_ack_header(nghttp3_qpack_encoder *encoder, + int64_t stream_id) { + nghttp3_qpack_stream *stream = + nghttp3_qpack_encoder_find_stream(encoder, stream_id); + const nghttp3_mem *mem = encoder->ctx.mem; + nghttp3_qpack_header_block_ref *ref; + + if (stream == NULL) { + return NGHTTP3_ERR_QPACK_DECODER_STREAM_ERROR; + } + + assert(nghttp3_ringbuf_len(&stream->refs)); + + ref = + *(nghttp3_qpack_header_block_ref **)nghttp3_ringbuf_get(&stream->refs, 0); + + DEBUGF("qpack::encoder: Header acknowledgement stream=%ld ricnt=%" PRIu64 + " krcnt=%" PRIu64 "\n", + stream_id, ref->max_cnt, encoder->krcnt); + + if (encoder->krcnt < ref->max_cnt) { + encoder->krcnt = ref->max_cnt; + + nghttp3_qpack_encoder_unblock(encoder, ref->max_cnt); + } + + nghttp3_qpack_stream_pop_ref(stream); + + assert(ref->min_cnts_pe.index != NGHTTP3_PQ_BAD_INDEX); + + nghttp3_pq_remove(&encoder->min_cnts, &ref->min_cnts_pe); + + nghttp3_qpack_header_block_ref_del(ref, mem); + + if (nghttp3_ringbuf_len(&stream->refs)) { + return 0; + } + + qpack_encoder_remove_stream(encoder, stream); + + nghttp3_qpack_stream_del(stream, mem); + + return 0; +} + +int nghttp3_qpack_encoder_add_icnt(nghttp3_qpack_encoder *encoder, uint64_t n) { + if (n == 0 || encoder->ctx.next_absidx - encoder->krcnt < n) { + return NGHTTP3_ERR_QPACK_DECODER_STREAM_ERROR; + } + encoder->krcnt += n; + + nghttp3_qpack_encoder_unblock(encoder, encoder->krcnt); + + return 0; +} + +void nghttp3_qpack_encoder_ack_everything(nghttp3_qpack_encoder *encoder) { + encoder->krcnt = encoder->ctx.next_absidx; + + nghttp3_ksl_clear(&encoder->blocked_streams); + nghttp3_pq_clear(&encoder->min_cnts); + nghttp3_map_each_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_streams(nghttp3_qpack_encoder *encoder) { + return nghttp3_ksl_len(&encoder->blocked_streams); +} + +int nghttp3_qpack_encoder_write_field_section_prefix( + nghttp3_qpack_encoder *encoder, nghttp3_buf *pbuf, uint64_t ricnt, + uint64_t base) { + size_t max_ents = + encoder->ctx.hard_max_dtable_capacity / NGHTTP3_QPACK_ENTRY_OVERHEAD; + uint64_t encricnt = ricnt == 0 ? 0 : (ricnt % (2 * max_ents)) + 1; + int sign = base < ricnt; + uint64_t delta_base = sign ? ricnt - base - 1 : base - ricnt; + size_t len = nghttp3_qpack_put_varint_len(encricnt, 8) + + nghttp3_qpack_put_varint_len(delta_base, 7); + uint8_t *p; + int rv; + + DEBUGF("qpack::encode: ricnt=%" PRIu64 " base=%" PRIu64 " icnt=%" PRIu64 "\n", + ricnt, base, encoder->ctx.next_absidx); + + rv = reserve_buf(pbuf, len, encoder->ctx.mem); + if (rv != 0) { + return rv; + } + + p = pbuf->last; + + p = nghttp3_qpack_put_varint(p, encricnt, 8); + if (sign) { + *p = 0x80; + } else { + *p = 0; + } + p = nghttp3_qpack_put_varint(p, delta_base, 7); + + assert((size_t)(p - pbuf->last) == len); + + pbuf->last = p; + + return 0; +} + +/* + * qpack_read_varint reads |rstate->prefix| prefixed integer stored + * from |begin|. The |end| represents the 1 beyond the last of the + * valid contiguous memory region from |begin|. The decoded integer + * must be less than or equal to NGHTTP3_QPACK_INT_MAX. + * + * If the |rstate->left| is nonzero, it is used as an initial value, + * and this function assumes the |begin| starts with intermediate + * data. |rstate->shift| is used as initial integer shift. + * + * If an entire integer is decoded successfully, the |*fin| is set to + * nonzero. + * + * This function stores the decoded integer in |rstate->left| if it + * succeeds, including partial decoding (in this case, number of shift + * to make in the next call will be stored in |rstate->shift|) and + * returns number of bytes processed, or returns negative error code + * NGHTTP3_ERR_QPACK_FATAL, indicating decoding error. + */ +static nghttp3_ssize qpack_read_varint(int *fin, + nghttp3_qpack_read_state *rstate, + const uint8_t *begin, + const uint8_t *end) { + uint64_t k = (uint8_t)((1 << rstate->prefix) - 1); + uint64_t n = rstate->left; + uint64_t add; + const uint8_t *p = begin; + size_t shift = rstate->shift; + + rstate->shift = 0; + *fin = 0; + + if (n == 0) { + if (((*p) & k) != k) { + rstate->left = (*p) & k; + *fin = 1; + return 1; + } + + n = k; + + if (++p == end) { + rstate->left = n; + return (nghttp3_ssize)(p - begin); + } + } + + for (; p != end; ++p, shift += 7) { + add = (*p) & 0x7f; + + if (shift > 62) { + return NGHTTP3_ERR_QPACK_FATAL; + } + + if ((NGHTTP3_QPACK_INT_MAX >> shift) < add) { + return NGHTTP3_ERR_QPACK_FATAL; + } + + add <<= shift; + + if (NGHTTP3_QPACK_INT_MAX - add < n) { + return NGHTTP3_ERR_QPACK_FATAL; + } + + n += add; + + if (((*p) & (1 << 7)) == 0) { + break; + } + } + + rstate->shift = shift; + + if (p == end) { + rstate->left = n; + return (nghttp3_ssize)(p - begin); + } + + rstate->left = n; + *fin = 1; + return (nghttp3_ssize)(p + 1 - begin); +} + +nghttp3_ssize nghttp3_qpack_encoder_read_decoder(nghttp3_qpack_encoder *encoder, + const uint8_t *src, + size_t srclen) { + const uint8_t *p = src, *end; + int rv; + nghttp3_ssize nread; + int rfin; + + if (encoder->ctx.bad) { + return NGHTTP3_ERR_QPACK_FATAL; + } + + if (srclen == 0) { + return 0; + } + + 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_icnt(encoder, encoder->rstate.left); + if (rv != 0) { + goto fail; + } + break; + case NGHTTP3_QPACK_DS_OPCODE_SECTION_ACK: + rv = nghttp3_qpack_encoder_ack_header(encoder, + (int64_t)encoder->rstate.left); + if (rv != 0) { + goto fail; + } + break; + case NGHTTP3_QPACK_DS_OPCODE_STREAM_CANCEL: + nghttp3_qpack_encoder_cancel_stream(encoder, + (int64_t)encoder->rstate.left); + break; + default: + nghttp3_unreachable(); + } + + encoder->state = NGHTTP3_QPACK_DS_STATE_OPCODE; + nghttp3_qpack_read_state_reset(&encoder->rstate); + break; + default: + nghttp3_unreachable(); + } + } + + return p - src; + +fail: + encoder->ctx.bad = 1; + return rv; +} + +size_t nghttp3_qpack_put_varint_len(uint64_t n, size_t prefix) { + size_t k = (size_t)((1 << prefix) - 1); + size_t len = 0; + + if (n < k) { + return 1; + } + + n -= k; + ++len; + + for (; n >= 128; n >>= 7, ++len) + ; + + return len + 1; +} + +uint8_t *nghttp3_qpack_put_varint(uint8_t *buf, uint64_t n, size_t prefix) { + size_t k = (size_t)((1 << prefix) - 1); + + *buf = (uint8_t)(*buf & ~k); + + if (n < k) { + *buf = (uint8_t)(*buf | n); + return buf + 1; + } + + *buf = (uint8_t)(*buf | k); + ++buf; + + n -= k; + + for (; n >= 128; n >>= 7) { + *buf++ = (uint8_t)((1 << 7) | (n & 0x7f)); + } + + *buf++ = (uint8_t)n; + + return buf; +} + +void nghttp3_qpack_read_state_free(nghttp3_qpack_read_state *rstate) { + nghttp3_rcbuf_decref(rstate->value); + nghttp3_rcbuf_decref(rstate->name); +} + +void nghttp3_qpack_read_state_reset(nghttp3_qpack_read_state *rstate) { + rstate->name = NULL; + rstate->value = NULL; + nghttp3_buf_init(&rstate->namebuf); + nghttp3_buf_init(&rstate->valuebuf); + rstate->left = 0; + rstate->prefix = 0; + rstate->shift = 0; + rstate->absidx = 0; + rstate->never = 0; + rstate->dynamic = 0; + rstate->huffman_encoded = 0; +} + +int nghttp3_qpack_decoder_init(nghttp3_qpack_decoder *decoder, + size_t hard_max_dtable_capacity, + size_t max_blocked_streams, + const nghttp3_mem *mem) { + int rv; + + rv = qpack_context_init(&decoder->ctx, hard_max_dtable_capacity, + max_blocked_streams, mem); + if (rv != 0) { + return rv; + } + + decoder->state = NGHTTP3_QPACK_ES_STATE_OPCODE; + decoder->opcode = 0; + decoder->written_icnt = 0; + decoder->max_concurrent_streams = 0; + + 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 succeeds, or one of the following negative error + * codes: + * + * NGHTTP3_ERR_QPACK_FATAL + * rstate->absidx is invalid. + */ +static int qpack_decoder_validate_index(nghttp3_qpack_decoder *decoder, + nghttp3_qpack_read_state *rstate) { + if (rstate->dynamic) { + return rstate->absidx < decoder->ctx.next_absidx && + decoder->ctx.next_absidx - rstate->absidx - 1 < + nghttp3_ringbuf_len(&decoder->ctx.dtable) + ? 0 + : NGHTTP3_ERR_QPACK_FATAL; + } + return rstate->absidx < nghttp3_arraylen(stable) ? 0 + : NGHTTP3_ERR_QPACK_FATAL; +} + +static void qpack_read_state_check_huffman(nghttp3_qpack_read_state *rstate, + const uint8_t b) { + rstate->huffman_encoded = (b & (1 << rstate->prefix)) != 0; +} + +static void qpack_read_state_terminate_name(nghttp3_qpack_read_state *rstate) { + *rstate->namebuf.last = '\0'; + rstate->name->len = nghttp3_buf_len(&rstate->namebuf); +} + +static void qpack_read_state_terminate_value(nghttp3_qpack_read_state *rstate) { + *rstate->valuebuf.last = '\0'; + rstate->value->len = nghttp3_buf_len(&rstate->valuebuf); +} + +nghttp3_ssize nghttp3_qpack_decoder_read_encoder(nghttp3_qpack_decoder *decoder, + const uint8_t *src, + size_t srclen) { + const uint8_t *p = src, *end; + int rv; + int busy = 0; + const nghttp3_mem *mem = decoder->ctx.mem; + nghttp3_ssize nread; + int rfin; + + if (decoder->ctx.bad) { + return NGHTTP3_ERR_QPACK_FATAL; + } + + if (srclen == 0) { + return 0; + } + + 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) { + DEBUGF("qpack::decode: Set dtable capacity to %" PRIu64 "\n", + decoder->rstate.left); + rv = nghttp3_qpack_decoder_set_max_dtable_capacity( + decoder, (size_t)decoder->rstate.left); + if (rv != 0) { + rv = NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR; + goto fail; + } + + decoder->state = NGHTTP3_QPACK_ES_STATE_OPCODE; + nghttp3_qpack_read_state_reset(&decoder->rstate); + break; + } + + rv = nghttp3_qpack_decoder_rel2abs(decoder, &decoder->rstate); + if (rv < 0) { + goto fail; + } + + switch (decoder->opcode) { + case NGHTTP3_QPACK_ES_OPCODE_DUPLICATE: + rv = nghttp3_qpack_decoder_dtable_duplicate_add(decoder); + if (rv != 0) { + goto fail; + } + + decoder->state = NGHTTP3_QPACK_ES_STATE_OPCODE; + nghttp3_qpack_read_state_reset(&decoder->rstate); + + break; + case NGHTTP3_QPACK_ES_OPCODE_INSERT_INDEXED: + decoder->rstate.prefix = 7; + decoder->state = NGHTTP3_QPACK_ES_STATE_CHECK_VALUE_HUFFMAN; + + break; + default: + nghttp3_unreachable(); + } + + break; + case NGHTTP3_QPACK_ES_STATE_CHECK_NAME_HUFFMAN: + qpack_read_state_check_huffman(&decoder->rstate, *p); + decoder->state = NGHTTP3_QPACK_ES_STATE_READ_NAMELEN; + decoder->rstate.left = 0; + decoder->rstate.shift = 0; + /* Fall through */ + case NGHTTP3_QPACK_ES_STATE_READ_NAMELEN: + nread = qpack_read_varint(&rfin, &decoder->rstate, p, end); + if (nread < 0) { + assert(NGHTTP3_ERR_QPACK_FATAL == nread); + rv = NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR; + goto fail; + } + + p += nread; + + if (!rfin) { + return p - src; + } + + if (decoder->rstate.left > NGHTTP3_QPACK_MAX_NAMELEN) { + rv = NGHTTP3_ERR_QPACK_HEADER_TOO_LARGE; + goto fail; + } + + if (decoder->rstate.huffman_encoded) { + decoder->state = NGHTTP3_QPACK_ES_STATE_READ_NAME_HUFFMAN; + nghttp3_qpack_huffman_decode_context_init(&decoder->rstate.huffman_ctx); + rv = nghttp3_rcbuf_new(&decoder->rstate.name, + (size_t)decoder->rstate.left * 2 + 1, mem); + } else { + decoder->state = NGHTTP3_QPACK_ES_STATE_READ_NAME; + rv = nghttp3_rcbuf_new(&decoder->rstate.name, + (size_t)decoder->rstate.left + 1, mem); + } + if (rv != 0) { + goto fail; + } + + nghttp3_buf_wrap_init(&decoder->rstate.namebuf, + decoder->rstate.name->base, + decoder->rstate.name->len); + break; + case NGHTTP3_QPACK_ES_STATE_READ_NAME_HUFFMAN: + nread = qpack_read_huffman_string(&decoder->rstate, + &decoder->rstate.namebuf, p, end); + if (nread < 0) { + assert(NGHTTP3_ERR_QPACK_FATAL == nread); + rv = NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR; + goto fail; + } + + p += nread; + + if (decoder->rstate.left) { + return p - src; + } + + qpack_read_state_terminate_name(&decoder->rstate); + + decoder->state = NGHTTP3_QPACK_ES_STATE_CHECK_VALUE_HUFFMAN; + decoder->rstate.prefix = 7; + break; + case NGHTTP3_QPACK_ES_STATE_READ_NAME: + nread = + qpack_read_string(&decoder->rstate, &decoder->rstate.namebuf, p, end); + if (nread < 0) { + rv = (int)nread; + goto fail; + } + + p += nread; + + if (decoder->rstate.left) { + return p - src; + } + + qpack_read_state_terminate_name(&decoder->rstate); + + decoder->state = NGHTTP3_QPACK_ES_STATE_CHECK_VALUE_HUFFMAN; + decoder->rstate.prefix = 7; + break; + case NGHTTP3_QPACK_ES_STATE_CHECK_VALUE_HUFFMAN: + qpack_read_state_check_huffman(&decoder->rstate, *p); + decoder->state = NGHTTP3_QPACK_ES_STATE_READ_VALUELEN; + decoder->rstate.left = 0; + decoder->rstate.shift = 0; + /* Fall through */ + case NGHTTP3_QPACK_ES_STATE_READ_VALUELEN: + nread = qpack_read_varint(&rfin, &decoder->rstate, p, end); + if (nread < 0) { + assert(NGHTTP3_ERR_QPACK_FATAL == nread); + rv = NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR; + goto fail; + } + + p += nread; + + if (!rfin) { + return p - src; + } + + if (decoder->rstate.left > NGHTTP3_QPACK_MAX_VALUELEN) { + rv = NGHTTP3_ERR_QPACK_HEADER_TOO_LARGE; + goto fail; + } + + if (decoder->rstate.huffman_encoded) { + decoder->state = NGHTTP3_QPACK_ES_STATE_READ_VALUE_HUFFMAN; + nghttp3_qpack_huffman_decode_context_init(&decoder->rstate.huffman_ctx); + rv = nghttp3_rcbuf_new(&decoder->rstate.value, + (size_t)decoder->rstate.left * 2 + 1, mem); + } else { + decoder->state = NGHTTP3_QPACK_ES_STATE_READ_VALUE; + rv = nghttp3_rcbuf_new(&decoder->rstate.value, + (size_t)decoder->rstate.left + 1, mem); + } + if (rv != 0) { + goto fail; + } + + nghttp3_buf_wrap_init(&decoder->rstate.valuebuf, + decoder->rstate.value->base, + decoder->rstate.value->len); + + /* value might be 0 length */ + busy = 1; + break; + case NGHTTP3_QPACK_ES_STATE_READ_VALUE_HUFFMAN: + nread = qpack_read_huffman_string(&decoder->rstate, + &decoder->rstate.valuebuf, p, end); + if (nread < 0) { + assert(NGHTTP3_ERR_QPACK_FATAL == nread); + rv = NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR; + goto fail; + } + + p += nread; + + if (decoder->rstate.left) { + return p - src; + } + + qpack_read_state_terminate_value(&decoder->rstate); + + switch (decoder->opcode) { + case NGHTTP3_QPACK_ES_OPCODE_INSERT_INDEXED: + rv = nghttp3_qpack_decoder_dtable_indexed_add(decoder); + break; + case NGHTTP3_QPACK_ES_OPCODE_INSERT: + rv = nghttp3_qpack_decoder_dtable_literal_add(decoder); + break; + default: + nghttp3_unreachable(); + } + if (rv != 0) { + goto fail; + } + + decoder->state = NGHTTP3_QPACK_ES_STATE_OPCODE; + nghttp3_qpack_read_state_reset(&decoder->rstate); + break; + case NGHTTP3_QPACK_ES_STATE_READ_VALUE: + nread = qpack_read_string(&decoder->rstate, &decoder->rstate.valuebuf, p, + end); + if (nread < 0) { + rv = (int)nread; + goto fail; + } + + p += nread; + + if (decoder->rstate.left) { + return p - src; + } + + qpack_read_state_terminate_value(&decoder->rstate); + + switch (decoder->opcode) { + case NGHTTP3_QPACK_ES_OPCODE_INSERT_INDEXED: + rv = nghttp3_qpack_decoder_dtable_indexed_add(decoder); + break; + case NGHTTP3_QPACK_ES_OPCODE_INSERT: + rv = nghttp3_qpack_decoder_dtable_literal_add(decoder); + break; + default: + nghttp3_unreachable(); + } + if (rv != 0) { + goto fail; + } + + decoder->state = NGHTTP3_QPACK_ES_STATE_OPCODE; + nghttp3_qpack_read_state_reset(&decoder->rstate); + break; + } + } + + return p - src; + +fail: + decoder->ctx.bad = 1; + return rv; +} + +int nghttp3_qpack_decoder_set_max_dtable_capacity( + nghttp3_qpack_decoder *decoder, size_t max_dtable_capacity) { + nghttp3_qpack_entry *ent; + size_t i; + nghttp3_qpack_context *ctx = &decoder->ctx; + const nghttp3_mem *mem = ctx->mem; + + if (max_dtable_capacity > decoder->ctx.hard_max_dtable_capacity) { + return NGHTTP3_ERR_INVALID_ARGUMENT; + } + + ctx->max_dtable_capacity = max_dtable_capacity; + + while (ctx->dtable_size > max_dtable_capacity) { + i = nghttp3_ringbuf_len(&ctx->dtable); + assert(i); + ent = *(nghttp3_qpack_entry **)nghttp3_ringbuf_get(&ctx->dtable, i - 1); + + ctx->dtable_size -= table_space(ent->nv.name->len, ent->nv.value->len); + + nghttp3_ringbuf_pop_back(&ctx->dtable); + nghttp3_qpack_entry_free(ent); + nghttp3_mem_free(mem, ent); + } + + return 0; +} + +int nghttp3_qpack_decoder_dtable_indexed_add(nghttp3_qpack_decoder *decoder) { + DEBUGF("qpack::decode: Insert With Name Reference (%s) absidx=%" PRIu64 ": " + "value=%*s\n", + decoder->rstate.dynamic ? "dynamic" : "static", decoder->rstate.absidx, + (int)decoder->rstate.value->len, decoder->rstate.value->base); + + if (decoder->rstate.dynamic) { + return nghttp3_qpack_decoder_dtable_dynamic_add(decoder); + } + + return nghttp3_qpack_decoder_dtable_static_add(decoder); +} + +int nghttp3_qpack_decoder_dtable_static_add(nghttp3_qpack_decoder *decoder) { + nghttp3_qpack_nv qnv; + int rv; + const nghttp3_qpack_static_header *shd; + + shd = &stable[decoder->rstate.absidx]; + + if (table_space(shd->name.len, decoder->rstate.value->len) > + decoder->ctx.max_dtable_capacity) { + return NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR; + } + + qnv.name = (nghttp3_rcbuf *)&shd->name; + qnv.value = decoder->rstate.value; + qnv.token = shd->token; + qnv.flags = NGHTTP3_NV_FLAG_NONE; + + rv = nghttp3_qpack_context_dtable_add(&decoder->ctx, &qnv, NULL, 0); + + nghttp3_rcbuf_decref(qnv.value); + + return rv; +} + +int nghttp3_qpack_decoder_dtable_dynamic_add(nghttp3_qpack_decoder *decoder) { + nghttp3_qpack_nv qnv; + int rv; + nghttp3_qpack_entry *ent; + + ent = nghttp3_qpack_context_dtable_get(&decoder->ctx, decoder->rstate.absidx); + + if (table_space(ent->nv.name->len, decoder->rstate.value->len) > + decoder->ctx.max_dtable_capacity) { + return NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR; + } + + qnv.name = ent->nv.name; + qnv.value = decoder->rstate.value; + qnv.token = ent->nv.token; + qnv.flags = NGHTTP3_NV_FLAG_NONE; + + nghttp3_rcbuf_incref(qnv.name); + + rv = nghttp3_qpack_context_dtable_add(&decoder->ctx, &qnv, NULL, 0); + + nghttp3_rcbuf_decref(qnv.value); + nghttp3_rcbuf_decref(qnv.name); + + return rv; +} + +int nghttp3_qpack_decoder_dtable_duplicate_add(nghttp3_qpack_decoder *decoder) { + int rv; + nghttp3_qpack_entry *ent; + nghttp3_qpack_nv qnv; + + DEBUGF("qpack::decode: Insert duplicate absidx=%" PRIu64 "\n", + decoder->rstate.absidx); + + ent = nghttp3_qpack_context_dtable_get(&decoder->ctx, decoder->rstate.absidx); + + if (table_space(ent->nv.name->len, ent->nv.value->len) > + decoder->ctx.max_dtable_capacity) { + return NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR; + } + + qnv = ent->nv; + nghttp3_rcbuf_incref(qnv.name); + nghttp3_rcbuf_incref(qnv.value); + + rv = nghttp3_qpack_context_dtable_add(&decoder->ctx, &qnv, NULL, 0); + + nghttp3_rcbuf_decref(qnv.value); + nghttp3_rcbuf_decref(qnv.name); + + return rv; +} + +int nghttp3_qpack_decoder_dtable_literal_add(nghttp3_qpack_decoder *decoder) { + nghttp3_qpack_nv qnv; + int rv; + + DEBUGF("qpack::decode: Insert With Literal Name: name=%*s value=%*s\n", + (int)decoder->rstate.name->len, decoder->rstate.name->base, + (int)decoder->rstate.value->len, decoder->rstate.value->base); + + if (table_space(decoder->rstate.name->len, decoder->rstate.value->len) > + decoder->ctx.max_dtable_capacity) { + return NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR; + } + + qnv.name = decoder->rstate.name; + qnv.value = decoder->rstate.value; + qnv.token = qpack_lookup_token(qnv.name->base, qnv.name->len); + qnv.flags = NGHTTP3_NV_FLAG_NONE; + + rv = nghttp3_qpack_context_dtable_add(&decoder->ctx, &qnv, NULL, 0); + + nghttp3_rcbuf_decref(qnv.value); + nghttp3_rcbuf_decref(qnv.name); + + return rv; +} + +void nghttp3_qpack_decoder_set_max_concurrent_streams( + nghttp3_qpack_decoder *decoder, size_t max_concurrent_streams) { + decoder->max_concurrent_streams = + nghttp3_max(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: + nghttp3_unreachable(); + } + break; + case NGHTTP3_QPACK_RS_STATE_CHECK_NAME_HUFFMAN: + qpack_read_state_check_huffman(&sctx->rstate, *p); + sctx->state = NGHTTP3_QPACK_RS_STATE_READ_NAMELEN; + sctx->rstate.left = 0; + sctx->rstate.shift = 0; + /* Fall through */ + case NGHTTP3_QPACK_RS_STATE_READ_NAMELEN: + nread = qpack_read_varint(&rfin, &sctx->rstate, p, end); + if (nread < 0) { + assert(NGHTTP3_ERR_QPACK_FATAL == nread); + rv = NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; + goto fail; + } + + p += nread; + + if (!rfin) { + goto almost_ok; + } + + if (sctx->rstate.left > NGHTTP3_QPACK_MAX_NAMELEN) { + rv = NGHTTP3_ERR_QPACK_HEADER_TOO_LARGE; + goto fail; + } + + if (sctx->rstate.huffman_encoded) { + sctx->state = NGHTTP3_QPACK_RS_STATE_READ_NAME_HUFFMAN; + nghttp3_qpack_huffman_decode_context_init(&sctx->rstate.huffman_ctx); + rv = nghttp3_rcbuf_new(&sctx->rstate.name, + (size_t)sctx->rstate.left * 2 + 1, mem); + } else { + sctx->state = NGHTTP3_QPACK_RS_STATE_READ_NAME; + rv = nghttp3_rcbuf_new(&sctx->rstate.name, + (size_t)sctx->rstate.left + 1, mem); + } + if (rv != 0) { + goto fail; + } + + nghttp3_buf_wrap_init(&sctx->rstate.namebuf, sctx->rstate.name->base, + sctx->rstate.name->len); + break; + case NGHTTP3_QPACK_RS_STATE_READ_NAME_HUFFMAN: + nread = qpack_read_huffman_string(&sctx->rstate, &sctx->rstate.namebuf, p, + end); + if (nread < 0) { + assert(NGHTTP3_ERR_QPACK_FATAL == nread); + rv = NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; + goto fail; + } + + p += nread; + + if (sctx->rstate.left) { + goto almost_ok; + } + + qpack_read_state_terminate_name(&sctx->rstate); + + sctx->state = NGHTTP3_QPACK_RS_STATE_CHECK_VALUE_HUFFMAN; + sctx->rstate.prefix = 7; + break; + case NGHTTP3_QPACK_RS_STATE_READ_NAME: + nread = qpack_read_string(&sctx->rstate, &sctx->rstate.namebuf, p, end); + if (nread < 0) { + rv = (int)nread; + goto fail; + } + + p += nread; + + if (sctx->rstate.left) { + goto almost_ok; + } + + qpack_read_state_terminate_name(&sctx->rstate); + + sctx->state = NGHTTP3_QPACK_RS_STATE_CHECK_VALUE_HUFFMAN; + sctx->rstate.prefix = 7; + break; + case NGHTTP3_QPACK_RS_STATE_CHECK_VALUE_HUFFMAN: + qpack_read_state_check_huffman(&sctx->rstate, *p); + sctx->state = NGHTTP3_QPACK_RS_STATE_READ_VALUELEN; + sctx->rstate.left = 0; + sctx->rstate.shift = 0; + /* Fall through */ + case NGHTTP3_QPACK_RS_STATE_READ_VALUELEN: + nread = qpack_read_varint(&rfin, &sctx->rstate, p, end); + if (nread < 0) { + assert(NGHTTP3_ERR_QPACK_FATAL == nread); + rv = NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; + goto fail; + } + + p += nread; + + if (!rfin) { + goto almost_ok; + } + + if (sctx->rstate.left > NGHTTP3_QPACK_MAX_VALUELEN) { + rv = NGHTTP3_ERR_QPACK_HEADER_TOO_LARGE; + goto fail; + } + + if (sctx->rstate.huffman_encoded) { + sctx->state = NGHTTP3_QPACK_RS_STATE_READ_VALUE_HUFFMAN; + nghttp3_qpack_huffman_decode_context_init(&sctx->rstate.huffman_ctx); + rv = nghttp3_rcbuf_new(&sctx->rstate.value, + (size_t)sctx->rstate.left * 2 + 1, mem); + } else { + sctx->state = NGHTTP3_QPACK_RS_STATE_READ_VALUE; + rv = nghttp3_rcbuf_new(&sctx->rstate.value, + (size_t)sctx->rstate.left + 1, mem); + } + if (rv != 0) { + goto fail; + } + + nghttp3_buf_wrap_init(&sctx->rstate.valuebuf, sctx->rstate.value->base, + sctx->rstate.value->len); + + /* value might be 0 length */ + busy = 1; + break; + case NGHTTP3_QPACK_RS_STATE_READ_VALUE_HUFFMAN: + nread = qpack_read_huffman_string(&sctx->rstate, &sctx->rstate.valuebuf, + p, end); + if (nread < 0) { + assert(NGHTTP3_ERR_QPACK_FATAL == nread); + rv = NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; + goto fail; + } + + p += nread; + + if (sctx->rstate.left) { + goto almost_ok; + } + + qpack_read_state_terminate_value(&sctx->rstate); + + switch (sctx->opcode) { + case NGHTTP3_QPACK_RS_OPCODE_INDEXED_NAME: + case NGHTTP3_QPACK_RS_OPCODE_INDEXED_NAME_PB: + rv = nghttp3_qpack_decoder_emit_indexed_name(decoder, sctx, nv); + if (rv != 0) { + goto fail; + } + + break; + case NGHTTP3_QPACK_RS_OPCODE_LITERAL: + nghttp3_qpack_decoder_emit_literal(decoder, sctx, nv); + break; + default: + nghttp3_unreachable(); + } + + *pflags |= NGHTTP3_QPACK_DECODE_FLAG_EMIT; + + sctx->state = NGHTTP3_QPACK_RS_STATE_OPCODE; + nghttp3_qpack_read_state_reset(&sctx->rstate); + + return p - src; + case NGHTTP3_QPACK_RS_STATE_READ_VALUE: + nread = qpack_read_string(&sctx->rstate, &sctx->rstate.valuebuf, p, end); + if (nread < 0) { + rv = (int)nread; + goto fail; + } + + p += nread; + + if (sctx->rstate.left) { + goto almost_ok; + } + + qpack_read_state_terminate_value(&sctx->rstate); + + switch (sctx->opcode) { + case NGHTTP3_QPACK_RS_OPCODE_INDEXED_NAME: + case NGHTTP3_QPACK_RS_OPCODE_INDEXED_NAME_PB: + rv = nghttp3_qpack_decoder_emit_indexed_name(decoder, sctx, nv); + if (rv != 0) { + goto fail; + } + + break; + case NGHTTP3_QPACK_RS_OPCODE_LITERAL: + nghttp3_qpack_decoder_emit_literal(decoder, sctx, nv); + break; + default: + nghttp3_unreachable(); + } + + *pflags |= NGHTTP3_QPACK_DECODE_FLAG_EMIT; + + sctx->state = NGHTTP3_QPACK_RS_STATE_OPCODE; + nghttp3_qpack_read_state_reset(&sctx->rstate); + + return p - src; + case NGHTTP3_QPACK_RS_STATE_BLOCKED: + if (sctx->ricnt > decoder->ctx.next_absidx) { + DEBUGF("qpack::decode: stream still blocked\n"); + *pflags |= NGHTTP3_QPACK_DECODE_FLAG_BLOCKED; + return p - src; + } + sctx->state = NGHTTP3_QPACK_RS_STATE_OPCODE; + nghttp3_qpack_read_state_reset(&sctx->rstate); + break; + } + } + +almost_ok: + if (fin) { + if (sctx->state != NGHTTP3_QPACK_RS_STATE_OPCODE) { + rv = NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; + goto fail; + } + + *pflags |= NGHTTP3_QPACK_DECODE_FLAG_FINAL; + + if (sctx->ricnt) { + rv = nghttp3_qpack_decoder_write_section_ack(decoder, sctx); + if (rv != 0) { + goto fail; + } + } + } + + 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; + (void)len; + + if (decoder->written_icnt < decoder->ctx.next_absidx) { + n = decoder->ctx.next_absidx - decoder->written_icnt; + len = nghttp3_qpack_put_varint_len(n, 6); + } + + assert(nghttp3_buf_left(dbuf) >= nghttp3_buf_len(&decoder->dbuf) + len); + + if (nghttp3_buf_len(&decoder->dbuf)) { + dbuf->last = nghttp3_cpymem(dbuf->last, decoder->dbuf.pos, + nghttp3_buf_len(&decoder->dbuf)); + } + + if (n) { + p = dbuf->last; + *p = 0; + dbuf->last = nghttp3_qpack_put_varint(p, n, 6); + + decoder->written_icnt = decoder->ctx.next_absidx; + } + + nghttp3_buf_reset(&decoder->dbuf); +} + +int nghttp3_qpack_decoder_cancel_stream(nghttp3_qpack_decoder *decoder, + int64_t stream_id) { + uint8_t *p; + int rv; + + if (qpack_decoder_dbuf_overflow(decoder)) { + return NGHTTP3_ERR_QPACK_FATAL; + } + + rv = reserve_buf(&decoder->dbuf, + nghttp3_qpack_put_varint_len((uint64_t)stream_id, 6), + decoder->ctx.mem); + if (rv != 0) { + return rv; + } + + p = decoder->dbuf.last; + *p = 0x40; + decoder->dbuf.last = nghttp3_qpack_put_varint(p, (uint64_t)stream_id, 6); + + return 0; +} + +int nghttp3_qpack_decoder_reconstruct_ricnt(nghttp3_qpack_decoder *decoder, + uint64_t *dest, uint64_t encricnt) { + uint64_t max_ents, full, max, max_wrapped, ricnt; + + if (encricnt == 0) { + *dest = 0; + return 0; + } + + max_ents = + decoder->ctx.hard_max_dtable_capacity / NGHTTP3_QPACK_ENTRY_OVERHEAD; + full = 2 * max_ents; + + if (encricnt > full) { + return NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; + } + + max = decoder->ctx.next_absidx + max_ents; + max_wrapped = max / full * full; + ricnt = max_wrapped + encricnt - 1; + + if (ricnt > max) { + if (ricnt <= full) { + return NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; + } + ricnt -= full; + } + + if (ricnt == 0) { + return NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; + } + + *dest = ricnt; + + return 0; +} + +int nghttp3_qpack_decoder_rel2abs(nghttp3_qpack_decoder *decoder, + nghttp3_qpack_read_state *rstate) { + DEBUGF("qpack::decode: dynamic=%d relidx=%" PRIu64 " icnt=%" PRIu64 "\n", + rstate->dynamic, rstate->left, decoder->ctx.next_absidx); + + if (rstate->dynamic) { + if (decoder->ctx.next_absidx < rstate->left + 1) { + return NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR; + } + rstate->absidx = decoder->ctx.next_absidx - rstate->left - 1; + } else { + rstate->absidx = rstate->left; + } + if (qpack_decoder_validate_index(decoder, rstate) != 0) { + return NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR; + } + return 0; +} + +int nghttp3_qpack_decoder_brel2abs(nghttp3_qpack_decoder *decoder, + nghttp3_qpack_stream_context *sctx) { + nghttp3_qpack_read_state *rstate = &sctx->rstate; + + DEBUGF("qpack::decode: dynamic=%d relidx=%" PRIu64 " base=%" PRIu64 + " icnt=%" PRIu64 "\n", + rstate->dynamic, rstate->left, sctx->base, decoder->ctx.next_absidx); + + if (rstate->dynamic) { + if (sctx->base < rstate->left + 1) { + return NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; + } + rstate->absidx = sctx->base - rstate->left - 1; + + if (rstate->absidx >= sctx->ricnt) { + return NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; + } + } else { + rstate->absidx = rstate->left; + } + + if (qpack_decoder_validate_index(decoder, rstate) != 0) { + return NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; + } + return 0; +} + +int nghttp3_qpack_decoder_pbrel2abs(nghttp3_qpack_decoder *decoder, + nghttp3_qpack_stream_context *sctx) { + nghttp3_qpack_read_state *rstate = &sctx->rstate; + + DEBUGF("qpack::decode: pbidx=%" PRIu64 " base=%" PRIu64 " icnt=%" PRIu64 "\n", + rstate->left, sctx->base, decoder->ctx.next_absidx); + + assert(rstate->dynamic); + + rstate->absidx = rstate->left + sctx->base; + + if (rstate->absidx >= sctx->ricnt) { + return NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; + } + + if (qpack_decoder_validate_index(decoder, rstate) != 0) { + return NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; + } + return 0; +} + +static void +qpack_decoder_emit_static_indexed(nghttp3_qpack_decoder *decoder, + nghttp3_qpack_stream_context *sctx, + nghttp3_qpack_nv *nv) { + const nghttp3_qpack_static_header *shd = &stable[sctx->rstate.absidx]; + (void)decoder; + + nv->name = (nghttp3_rcbuf *)&shd->name; + nv->value = (nghttp3_rcbuf *)&shd->value; + nv->token = shd->token; + nv->flags = NGHTTP3_NV_FLAG_NONE; +} + +static void +qpack_decoder_emit_dynamic_indexed(nghttp3_qpack_decoder *decoder, + nghttp3_qpack_stream_context *sctx, + nghttp3_qpack_nv *nv) { + nghttp3_qpack_entry *ent = + nghttp3_qpack_context_dtable_get(&decoder->ctx, sctx->rstate.absidx); + + *nv = ent->nv; + + nghttp3_rcbuf_incref(nv->name); + nghttp3_rcbuf_incref(nv->value); +} + +void nghttp3_qpack_decoder_emit_indexed(nghttp3_qpack_decoder *decoder, + nghttp3_qpack_stream_context *sctx, + nghttp3_qpack_nv *nv) { + DEBUGF("qpack::decode: Indexed (%s) absidx=%" PRIu64 "\n", + sctx->rstate.dynamic ? "dynamic" : "static", sctx->rstate.absidx); + + if (sctx->rstate.dynamic) { + qpack_decoder_emit_dynamic_indexed(decoder, sctx, nv); + } else { + qpack_decoder_emit_static_indexed(decoder, sctx, nv); + } +} + +static void +qpack_decoder_emit_static_indexed_name(nghttp3_qpack_decoder *decoder, + nghttp3_qpack_stream_context *sctx, + nghttp3_qpack_nv *nv) { + const nghttp3_qpack_static_header *shd = &stable[sctx->rstate.absidx]; + (void)decoder; + + nv->name = (nghttp3_rcbuf *)&shd->name; + nv->value = sctx->rstate.value; + nv->token = shd->token; + nv->flags = + sctx->rstate.never ? NGHTTP3_NV_FLAG_NEVER_INDEX : NGHTTP3_NV_FLAG_NONE; + + sctx->rstate.value = NULL; +} + +static int +qpack_decoder_emit_dynamic_indexed_name(nghttp3_qpack_decoder *decoder, + nghttp3_qpack_stream_context *sctx, + nghttp3_qpack_nv *nv) { + nghttp3_qpack_entry *ent; + + /* A broken encoder might change dtable capacity while processing + request stream instruction. Check the absidx again. */ + if (qpack_decoder_validate_index(decoder, &sctx->rstate) != 0) { + return NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; + } + + ent = nghttp3_qpack_context_dtable_get(&decoder->ctx, sctx->rstate.absidx); + + nv->name = ent->nv.name; + nv->value = sctx->rstate.value; + nv->token = ent->nv.token; + nv->flags = + sctx->rstate.never ? NGHTTP3_NV_FLAG_NEVER_INDEX : NGHTTP3_NV_FLAG_NONE; + + nghttp3_rcbuf_incref(nv->name); + + sctx->rstate.value = NULL; + + return 0; +} + +int nghttp3_qpack_decoder_emit_indexed_name(nghttp3_qpack_decoder *decoder, + nghttp3_qpack_stream_context *sctx, + nghttp3_qpack_nv *nv) { + (void)decoder; + + DEBUGF("qpack::decode: Indexed name (%s) absidx=%" PRIu64 " value=%*s\n", + sctx->rstate.dynamic ? "dynamic" : "static", sctx->rstate.absidx, + (int)sctx->rstate.value->len, sctx->rstate.value->base); + + if (sctx->rstate.dynamic) { + return qpack_decoder_emit_dynamic_indexed_name(decoder, sctx, nv); + } + + qpack_decoder_emit_static_indexed_name(decoder, sctx, nv); + + return 0; +} + +void nghttp3_qpack_decoder_emit_literal(nghttp3_qpack_decoder *decoder, + nghttp3_qpack_stream_context *sctx, + nghttp3_qpack_nv *nv) { + (void)decoder; + + DEBUGF("qpack::decode: Emit literal name=%*s value=%*s\n", + (int)sctx->rstate.name->len, sctx->rstate.name->base, + (int)sctx->rstate.value->len, sctx->rstate.value->base); + + nv->name = sctx->rstate.name; + nv->value = sctx->rstate.value; + nv->token = qpack_lookup_token(nv->name->base, nv->name->len); + nv->flags = + sctx->rstate.never ? NGHTTP3_NV_FLAG_NEVER_INDEX : NGHTTP3_NV_FLAG_NONE; + + sctx->rstate.name = NULL; + sctx->rstate.value = NULL; +} + +int nghttp3_qpack_encoder_new(nghttp3_qpack_encoder **pencoder, + size_t hard_max_dtable_capacity, + const nghttp3_mem *mem) { + int rv; + nghttp3_qpack_encoder *p; + + p = nghttp3_mem_malloc(mem, sizeof(nghttp3_qpack_encoder)); + if (p == NULL) { + return NGHTTP3_ERR_NOMEM; + } + + rv = nghttp3_qpack_encoder_init(p, hard_max_dtable_capacity, mem); + if (rv != 0) { + return rv; + } + + *pencoder = p; + + return 0; +} + +void nghttp3_qpack_encoder_del(nghttp3_qpack_encoder *encoder) { + const nghttp3_mem *mem; + + if (encoder == NULL) { + return; + } + + mem = encoder->ctx.mem; + + nghttp3_qpack_encoder_free(encoder); + nghttp3_mem_free(mem, encoder); +} + +int nghttp3_qpack_stream_context_new(nghttp3_qpack_stream_context **psctx, + int64_t stream_id, + const nghttp3_mem *mem) { + nghttp3_qpack_stream_context *p; + + p = nghttp3_mem_malloc(mem, sizeof(nghttp3_qpack_stream_context)); + if (p == NULL) { + return NGHTTP3_ERR_NOMEM; + } + + nghttp3_qpack_stream_context_init(p, stream_id, mem); + + *psctx = p; + + return 0; +} + +void nghttp3_qpack_stream_context_del(nghttp3_qpack_stream_context *sctx) { + const nghttp3_mem *mem; + + if (sctx == NULL) { + return; + } + + mem = sctx->mem; + + nghttp3_qpack_stream_context_free(sctx); + nghttp3_mem_free(mem, sctx); +} + +int nghttp3_qpack_decoder_new(nghttp3_qpack_decoder **pdecoder, + size_t hard_max_dtable_capacity, + size_t max_blocked_streams, + const nghttp3_mem *mem) { + int rv; + nghttp3_qpack_decoder *p; + + p = nghttp3_mem_malloc(mem, sizeof(nghttp3_qpack_decoder)); + if (p == NULL) { + return NGHTTP3_ERR_NOMEM; + } + + rv = nghttp3_qpack_decoder_init(p, hard_max_dtable_capacity, + max_blocked_streams, mem); + if (rv != 0) { + return rv; + } + + *pdecoder = p; + + return 0; +} + +void nghttp3_qpack_decoder_del(nghttp3_qpack_decoder *decoder) { + const nghttp3_mem *mem; + + if (decoder == NULL) { + return; + } + + mem = decoder->ctx.mem; + + nghttp3_qpack_decoder_free(decoder); + nghttp3_mem_free(mem, decoder); +} + +uint64_t nghttp3_qpack_decoder_get_icnt(const nghttp3_qpack_decoder *decoder) { + return decoder->ctx.next_absidx; +} |