// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie // SPDX-License-Identifier: MIT //! RFC 9204: QPACK, which is HPACK rearranged around the fact that QUIC //! streams arrive in any order. //! //! HPACK's dynamic table is a shared, ordered thing: an encoder inserts, and //! every later field section is decoded against a table that has that //! insertion in it. Over TCP that is safe, because TCP delivers in order. //! Over QUIC it is not — a field section referring to an insertion that has //! not arrived yet cannot be decoded, and the stream carrying it is //! *blocked*, which is exactly the head-of-line blocking HTTP/3 exists to //! remove. So QPACK moves the insertions onto a stream of their own, makes a //! field section say how much of that stream it depends on (§4.5.1's Required //! Insert Count), and lets a decoder bound how many streams may be blocked at //! once. //! //! ## What is here, and what is deliberately not //! //! This implements the static table and every literal representation, and //! advertises `SETTINGS_QPACK_MAX_TABLE_CAPACITY` of zero. §3.2.2: "the //! encoder MUST NOT insert entries into the dynamic table... if the value is //! zero" — so a conforming peer never inserts, no field section can ever //! depend on an insertion, and none of the machinery above exists to be got //! wrong. An insertion anyway is a QPACK_ENCODER_STREAM_ERROR. //! //! That is the same decision HPACK's encoder here made for the same reason, //! and it costs compression rather than correctness: a repeated header field //! is sent as a literal every time instead of as an index. What it buys is //! that Required Insert Count arithmetic, eviction, the Known Received Count //! and blocked streams are all absent rather than approximate. //! //! ## Lifetimes //! //! Nothing a decoder returns points into its own state, because it has no //! state to point into: a name or value is either a slice of the caller's //! field section, a slice of the caller's scratch buffer, or `.rodata` from //! the static table. The caller copies what it wants to keep. const std = @import("std"); const Writer = std.Io.Writer; const hpack = @import("../http2/hpack.zig"); pub const table = @import("qpack/table.zig"); /// Everything that can go wrong reading a field section. /// /// §6 of RFC 9204 gives all of these one error code, QPACK_DECOMPRESSION_ /// FAILED, and the distinctions here are for the reader of this code rather /// than for the peer -- which gets told only that the section could not be /// decoded, because telling it more would be describing this decoder's /// internals to somebody who may be probing them. pub const Error = error{ /// The section ended in the middle of a representation. Truncated, /// A static table index past the end of the table. BadIndex, /// A reference to the dynamic table, which cannot exist because this /// decoder advertised no capacity for one (§3.2.2). DynamicTableReference, /// An integer too large to represent, or a Huffman string that does not /// decode. Malformed, /// More field lines than the caller left room for. TooManyFields, /// A name or value longer than the caller's scratch. TooLong, /// More decoded field section than the caller said it would take, as /// RFC 9114 §4.2.2 sizes it -- see `decodeBounded`. TooLarge, }; /// RFC 9114 §4.2.2: what each field line costs on top of its name and value /// when a field section is sized against `SETTINGS_MAX_FIELD_SECTION_SIZE`. pub const field_overhead = 32; /// One decoded field line. pub const Field = struct { name: []const u8, value: []const u8, /// §4.5.4: the N bit. "An intermediary MUST NOT put this field in the /// dynamic table" -- which means nothing to a decoder with no dynamic /// table, and is kept because it has to survive a proxy re-encoding the /// section and this is where it would be read from. never_indexed: bool = false, }; /// Reads an encoded field section (§4.5). /// /// `scratch` holds whatever has to be decoded rather than pointed at, which /// is every Huffman-coded name and value. `out` is filled with field lines /// whose slices point into `section`, into `scratch`, or into the static /// table. Returns how many of `out` were filled. /// /// The section is not sized against any limit; a decoder answering to a /// `SETTINGS_MAX_FIELD_SECTION_SIZE` it advertised wants `decodeBounded`. pub fn decode( section: []const u8, out: []Field, scratch: []u8, ) Error!usize { return decodeBounded(section, out, scratch, std.math.maxInt(u64)); } test decode { // The two-octet prefix, then `:method GET` (static index 17) and // `:path /index.html` as a literal with a reference to `:path` (index 1). const section = [_]u8{ 0, 0, 0xc0 | 17, 0x50 | 1, 11 } ++ "/index.html".*; var fields: [4]Field = undefined; var scratch: [64]u8 = undefined; const n = try decode(§ion, &fields, &scratch); try std.testing.expectEqual(@as(usize, 2), n); try std.testing.expectEqualStrings(":method", fields[0].name); try std.testing.expectEqualStrings("GET", fields[0].value); try std.testing.expectEqualStrings(":path", fields[1].name); try std.testing.expectEqualStrings("/index.html", fields[1].value); } /// `decode`, stopping with `error.TooLarge` the moment the decoded section /// grows past `max_size`. /// /// RFC 9114 §4.2.2 sizes a field section "on the uncompressed size of field /// lines, including the length of the name and value in bytes plus an /// overhead of 32 bytes for each field line", and that is the size /// `SETTINGS_MAX_FIELD_SECTION_SIZE` promises a peer is enforced -- not the /// length of the HEADERS frame. The two differ by as much as the static table /// can expand an octet into: index 58 is a single octet on the wire and 101 /// octets of field section once decoded -- sixty-nine of name and value and /// the thirty-two of overhead -- which is the "header accordion" of the QPACK /// amplification attacks. Counting as each line is decoded, /// rather than after the whole section, is what keeps the check from being /// paid for by the thing it is checking. pub fn decodeBounded( section: []const u8, out: []Field, scratch: []u8, max_size: u64, ) Error!usize { var c: hpack.Cursor = .{ .bytes = section }; var used: usize = 0; var count: usize = 0; var size: u64 = 0; // §4.5.1: the Required Insert Count, and §4.5.2's Delta Base after it. // With no dynamic table both are zero, and a peer that sends anything // else is describing a table this decoder said it would not keep. const required = c.int(8) catch return error.Malformed; if (required != 0) return error.DynamicTableReference; _ = c.peekByte() catch return error.Truncated; const base = c.int(7) catch return error.Malformed; if (base != 0) return error.DynamicTableReference; while (!c.atEnd()) { const first = c.peekByte() catch return error.Truncated; if (first & 0x80 != 0) { // §4.5.2, Indexed Field Line: `1TXXXXXX`. T set means the static // table; clear means the dynamic one, which is not here. const static = first & 0x40 != 0; const index = c.int(6) catch return error.Malformed; if (!static) return error.DynamicTableReference; const entry = table.get(index) orelse return error.BadIndex; try append(out, &count, &size, max_size, .{ .name = entry.name, .value = entry.value }); continue; } if (first & 0x40 != 0) { // §4.5.4, Literal Field Line with Name Reference: `01NTXXXX`. const never = first & 0x20 != 0; const static = first & 0x10 != 0; const index = c.int(4) catch return error.Malformed; if (!static) return error.DynamicTableReference; const entry = table.get(index) orelse return error.BadIndex; const value = try take(&c, 7, scratch, &used); try append(out, &count, &size, max_size, .{ .name = entry.name, .value = value, .never_indexed = never, }); continue; } if (first & 0x20 != 0) { // §4.5.6, Literal Field Line with Literal Name: `001NHXXX`. The // name's length has three bits of prefix, not seven, because the // representation has already spent five. const never = first & 0x10 != 0; const name = try take(&c, 3, scratch, &used); const value = try take(&c, 7, scratch, &used); try append(out, &count, &size, max_size, .{ .name = name, .value = value, .never_indexed = never, }); continue; } // §4.5.3 `0001XXXX` and §4.5.5 `0000NXXX` are both post-base, which // is to say both are about the dynamic table. return error.DynamicTableReference; } return count; } test decodeBounded { // Index 58, `strict-transport-security: max-age=31536000; // includesubdomains; preload`: one octet here, and 25 + 44 + 32 = 101 // octets as §4.2.2 counts it. const section = [_]u8{ 0, 0, 0xc0 | 58 }; var fields: [4]Field = undefined; var scratch: [64]u8 = undefined; try std.testing.expectEqual(@as(usize, 1), try decodeBounded(§ion, &fields, &scratch, 101)); try std.testing.expectError(error.TooLarge, decodeBounded(§ion, &fields, &scratch, 100)); } fn append(out: []Field, count: *usize, size: *u64, max_size: u64, field: Field) Error!void { // Both lengths are bounded by a section held in memory or by the static // table, so this sum cannot overflow a u64. size.* += field.name.len + field.value.len + field_overhead; if (size.* > max_size) return error.TooLarge; if (count.* >= out.len) return error.TooManyFields; out[count.*] = field; count.* += 1; } /// Reads one string literal into `scratch` when it is Huffman-coded, or /// points at the section when it is not. fn take(c: *hpack.Cursor, prefix_bits: u4, scratch: []u8, used: *usize) Error![]const u8 { const room = scratch[used.*..]; const s = c.stringPrefixed(prefix_bits, room) catch |err| switch (err) { error.Truncated => return error.Truncated, error.StringTooLong => return error.TooLong, // §6 gives every one of these the same code on the wire -- // QPACK_DECOMPRESSION_FAILED -- so the distinction is for whoever // reads this code rather than for the peer, which is told only that // the section could not be decoded. error.IntegerOverflow, error.BadPadding, error.EosInInput, error.PaddingTooLong, => return error.Malformed, }; // A slice of `room` was decoded in place and has to be reserved; a slice // of the section itself costs nothing. if (s.len > 0 and s.ptr == room.ptr) used.* += s.len; return s; } /// Writes an encoded field section (§4.5). /// /// Every field goes out as an index into the static table when the name and /// value both match, as a literal with a name reference when only the name /// does, and as a literal otherwise. Nothing is inserted anywhere, because /// this encoder has no dynamic table -- see the note at the top. /// /// A name written out as a literal is lowercased on the way, as §4.2 of RFC /// 9114 requires; the match against the static table is exact, so a name /// that is not already lowercase finds no entry and goes out as a literal. /// A field marked `never_indexed` is never sent as a full index, so the bit /// reaches the peer. pub fn encode(out: *Writer, fields: []const Field) Writer.Error!void { // §4.5.1: with no dynamic table the Required Insert Count is zero and the // Base is zero, which is two zero octets and always the same two. try out.writeByte(0); try out.writeByte(0); for (fields) |f| { if (!f.never_indexed) { if (table.find(f.name, f.value)) |index| { // §4.5.2: `1TXXXXXX` with T set for the static table. try hpack.writeInt(out, 6, 0xc0, @intCast(index)); continue; } } if (table.findName(f.name)) |index| { // §4.5.4: `01NTXXXX`, T set, N from the field. const high: u8 = if (f.never_indexed) 0x70 else 0x50; try hpack.writeInt(out, 4, high, @intCast(index)); try hpack.writeString(out, f.value, false); continue; } // §4.5.6: `001NHXXX`, and the name's length has three bits of prefix. const high: u8 = if (f.never_indexed) 0x30 else 0x20; try hpack.writeStringPrefixed(out, 3, high, f.name, true); try hpack.writeString(out, f.value, false); } } test encode { var buffer: [64]u8 = undefined; var w: Writer = .fixed(&buffer); try encode(&w, &.{ .{ .name = ":method", .value = "GET" }, .{ .name = ":path", .value = "/index.html" }, }); // Two zero octets of prefix, `:method GET` as static index 17, then // `:path` by reference to index 1 and its value as a literal. try std.testing.expectEqualSlices(u8, &.{ 0, 0, 0xc0 | 17, 0x51 }, w.buffered()[0..4]); var fields: [4]Field = undefined; var scratch: [64]u8 = undefined; try std.testing.expectEqual(@as(usize, 2), try decode(w.buffered(), &fields, &scratch)); try std.testing.expectEqualStrings("/index.html", fields[1].value); } test { std.testing.refAllDecls(@This()); } const testing = std.testing; test "RFC 9204 4.5: a section is a prefix and then representations" { // The prefix is two zero octets here and always will be: §4.5.1's // Required Insert Count is zero when no field section depends on an // insertion, and none can, because this decoder advertises no capacity // for a dynamic table to insert into. var buffer: [256]u8 = undefined; var w: Writer = .fixed(&buffer); try encode(&w, &.{ .{ .name = ":method", .value = "GET" }, .{ .name = ":scheme", .value = "https" }, .{ .name = ":path", .value = "/" }, .{ .name = ":authority", .value = "example.com" }, }); const section = w.buffered(); try testing.expectEqual(@as(u8, 0), section[0]); try testing.expectEqual(@as(u8, 0), section[1]); var fields: [8]Field = undefined; var scratch: [256]u8 = undefined; const n = try decode(section, &fields, &scratch); try testing.expectEqual(@as(usize, 4), n); try testing.expectEqualStrings(":method", fields[0].name); try testing.expectEqualStrings("GET", fields[0].value); try testing.expectEqualStrings(":scheme", fields[1].name); try testing.expectEqualStrings("https", fields[1].value); try testing.expectEqualStrings(":path", fields[2].name); try testing.expectEqualStrings("/", fields[2].value); try testing.expectEqualStrings(":authority", fields[3].name); try testing.expectEqualStrings("example.com", fields[3].value); } test "RFC 9204 4.5.2: a field the table holds exactly costs one octet" { // Which is the whole of what the static table buys, and the reason it was // rebuilt from traffic rather than inherited from HPACK: the entries are // the field lines that actually turn up. var buffer: [64]u8 = undefined; var w: Writer = .fixed(&buffer); try encode(&w, &.{.{ .name = ":method", .value = "GET" }}); // Two octets of prefix and one of representation. try testing.expectEqual(@as(usize, 3), w.buffered().len); // §4.5.2: `1TXXXXXX` with T set and the index in six bits. `:method GET` // is 17. try testing.expectEqual(@as(u8, 0xc0 | 17), w.buffered()[2]); } test "RFC 9204 4.5.4: a name the table holds costs the value only" { var buffer: [64]u8 = undefined; var w: Writer = .fixed(&buffer); try encode(&w, &.{.{ .name = ":status", .value = "418" }}); // `01NTXXXX` with T set and N clear, so four bits of prefix for the // index -- and `:status` is at 24, which does not fit in four bits. A // prefix at its maximum means the value continues, so the octet is // 0x50 | 0x0f and the remainder 24 - 15 follows it. Worth pinning // exactly: the narrow prefixes are where QPACK differs from HPACK most // and where an encoder that assumed seven bits would write a number the // peer reads as something else entirely. try testing.expectEqual(@as(u8, 0x5f), w.buffered()[2]); try testing.expectEqual(@as(u8, 24 - 15), w.buffered()[3]); var fields: [4]Field = undefined; var scratch: [64]u8 = undefined; try testing.expectEqual(@as(usize, 1), try decode(w.buffered(), &fields, &scratch)); try testing.expectEqualStrings(":status", fields[0].name); try testing.expectEqualStrings("418", fields[0].value); } test "RFC 9204 4.5.6: a name the table does not hold is written out" { // And is lower-cased on the way, because §4.1.1 of RFC 9114 requires it // and this is the last place that can be true. var buffer: [128]u8 = undefined; var w: Writer = .fixed(&buffer); try encode(&w, &.{.{ .name = "X-Made-Up", .value = "yes" }}); var fields: [4]Field = undefined; var scratch: [128]u8 = undefined; try testing.expectEqual(@as(usize, 1), try decode(w.buffered(), &fields, &scratch)); try testing.expectEqualStrings("x-made-up", fields[0].name); try testing.expectEqualStrings("yes", fields[0].value); } test "RFC 9204 4.5.4: the never-indexed bit survives a round trip" { // It means nothing to a decoder with no dynamic table, and is kept // because it has to survive a proxy re-encoding the section -- §4.5.4: // "an intermediary MUST NOT put this field in the dynamic table". var buffer: [128]u8 = undefined; var w: Writer = .fixed(&buffer); try encode(&w, &.{ .{ .name = "authorization", .value = "secret", .never_indexed = true }, }); var fields: [4]Field = undefined; var scratch: [128]u8 = undefined; try testing.expectEqual(@as(usize, 1), try decode(w.buffered(), &fields, &scratch)); try testing.expectEqualStrings("authorization", fields[0].name); try testing.expectEqualStrings("secret", fields[0].value); try testing.expect(fields[0].never_indexed); } test "RFC 9204 3.2.2: a reference to a dynamic table that was refused is an error" { // "The encoder MUST NOT insert entries into the dynamic table... if the // value is zero." A peer that does it anyway has described a table this // decoder said it would not keep, and there is nothing to decode against. var fields: [4]Field = undefined; var scratch: [64]u8 = undefined; // §4.5.2 with T clear: an indexed field line against the dynamic table. try testing.expectError( error.DynamicTableReference, decode(&.{ 0, 0, 0x80 }, &fields, &scratch), ); // §4.5.3: a post-base index, which is dynamic by definition. try testing.expectError( error.DynamicTableReference, decode(&.{ 0, 0, 0x10 }, &fields, &scratch), ); // §4.5.1: a Required Insert Count that is not zero. try testing.expectError( error.DynamicTableReference, decode(&.{ 1, 0 }, &fields, &scratch), ); } test "RFC 9204 4.5.2: an index past the end of the table" { var fields: [4]Field = undefined; var scratch: [64]u8 = undefined; // 0xff is a six-bit prefix at its maximum, so the index continues into // the next octet: 63 + 100 = 163, well past ninety-nine. try testing.expectError( error.BadIndex, decode(&.{ 0, 0, 0xff, 100 }, &fields, &scratch), ); } test "RFC 9114 4.2.2: a section is sized decoded, at 32 octets a line over its name and value" { // `strict-transport-security: max-age=31536000; includesubdomains; // preload` is static index 58: one octet of representation, and // 25 + 44 + 32 = 101 octets of field section by §4.2.2's arithmetic. // A section of a few octets on the wire can therefore be many times its // own size decoded, and a limit that measured the frame would let it in. const one = [_]u8{ 0, 0, 0xc0 | 58 }; const three = [_]u8{ 0, 0, 0xc0 | 58, 0xc0 | 58, 0xc0 | 58 }; var fields: [8]Field = undefined; var scratch: [64]u8 = undefined; try testing.expectEqual(@as(usize, 1), try decodeBounded(&one, &fields, &scratch, 101)); try testing.expectError(error.TooLarge, decodeBounded(&one, &fields, &scratch, 100)); // Stopped at the line that crosses the limit, not after decoding them all. try testing.expectEqual(@as(usize, 3), try decodeBounded(&three, &fields, &scratch, 303)); try testing.expectError(error.TooLarge, decodeBounded(&three, &fields, &scratch, 302)); // And the overhead is charged on an empty line too, which is what keeps a // section of one-octet empty literals from being free. const empty = [_]u8{ 0, 0, 0x20 | 1, 'a', 0 }; try testing.expectError(error.TooLarge, decodeBounded(&empty, &fields, &scratch, 32)); try testing.expectEqual(@as(usize, 1), try decodeBounded(&empty, &fields, &scratch, 33)); } test "RFC 9114 4.2.2: the limit is checked as each line is decoded, not after the section" { // Several of the servers the QPACK amplification attacks reached decoded // a whole section and then measured it, which is paying the full cost of // the thing the limit exists to refuse. Here the line that crosses the // limit is the last one decoded: what follows it is a truncated literal, // and a decoder that read on would report that instead. const section = [_]u8{ 0, 0, 0xc0 | 58, 0xc0 | 58, 0x50 | 8, 0x7f }; var fields: [8]Field = undefined; var scratch: [64]u8 = undefined; try testing.expectError(error.TooLarge, decodeBounded(§ion, &fields, &scratch, 150)); try testing.expectError(error.Truncated, decodeBounded(§ion, &fields, &scratch, 1000)); } test "a section that stops in the middle of a representation" { var fields: [4]Field = undefined; var scratch: [64]u8 = undefined; try testing.expectError(error.Truncated, decode(&.{0}, &fields, &scratch)); // A literal whose value length says more than is there. try testing.expectError( error.Truncated, decode(&.{ 0, 0, 0x50 | 8, 0x7f }, &fields, &scratch), ); }