// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie // SPDX-License-Identifier: MIT //! HPACK: the header compression HTTP/2 carries its field sections in, RFC //! 7541. //! //! Two primitives underneath everything else — an integer encoding that can //! spill across as many octets as it likes, and a string literal that may or //! may not be Huffman-coded — and then five representations built out of //! them. This file holds the primitives; `hpack/Decoder.zig` and //! `hpack/Encoder.zig` hold the representations, and `hpack/table.zig` holds //! the two tables they index into. //! //! ## Where a decoded string lives //! //! Every name and value the decoder produces is copied into an allocator the //! caller passes for the field section — in this server, the arena belonging //! to the stream the section arrived on. The only exception is a static-table //! hit, whose strings are `.rodata` and outlive everything. //! //! That is the load-bearing decision in this whole module, and it is worth //! the paragraphs because the cheaper-looking alternatives are all wrong: //! //! * **Not the decoder's own buffer.** HPACK state is per *connection*; a //! decoded field section belongs to one *stream* and must stay valid until //! that stream's handler returns. HTTP/2 is multiplexed, so the decoder //! will be decoding another stream's section while the first handler is //! still reading its headers. Anything owned by the decoder is the wrong //! lifetime by construction rather than by accident. //! * **Not the dynamic table**, even though it outlives the section. It is a //! ring that evicts, and it can evict *during the very section that //! references it*: a literal with incremental indexing anywhere in a //! section can push out an entry that an indexed field earlier in the same //! section pointed at. Handing out slices into it is a use-after-free that //! a fuzzer finds and a table of worked examples does not. //! * **Not the field section either.** A section arrives split across a //! HEADERS frame and any number of CONTINUATION frames, so the driver //! reassembles it into a buffer it owns and reuses. Borrowing would make //! the rule "valid until the next field section on this connection", which //! is not a rule a handler can be expected to keep. //! //! So the contract, which the fuzz target states as a property: **no slice //! the decoder returns points into the field section it was given, or into //! the dynamic table.** One `memcpy` of a few hundred octets per request, //! next to a syscall. const std = @import("std"); pub const Decoder = @import("hpack/Decoder.zig"); pub const Encoder = @import("hpack/Encoder.zig"); /// RFC 9204 §5 defines no Huffman code of its own: it points at RFC 7541 /// Appendix B, which is this one. So the table is shared with QPACK rather /// than belonging to HPACK, and lives in `field` -- re-exported here because /// this is where a reader of RFC 7541 will look for it. pub const huffman = @import("../field.zig").huffman; pub const table = @import("hpack/table.zig"); // Test data only, so nothing references it: without this its tests never run. test { _ = @import("hpack/rfc7541.zig"); } const Writer = std.Io.Writer; pub const IntError = error{ /// The integer ran off the end of the field section. Truncated, /// More continuation octets than the result can hold. /// /// RFC 7541 §5.1 leaves the bound to the implementation and warns about /// exactly this: the encoding is not required to be minimal, so /// `1f 80 80 80 80 80 80 ...` is a syntactically fine way to write a /// small number using as many octets as the sender likes, and a decoder /// without a cap loops until the section runs out. /// /// The cap is on the shift rather than on a count of octets, so what is /// refused is the value that would not have fit rather than the one that /// was merely written oddly. IntegerOverflow, }; pub const StringError = IntError || huffman.DecodeError; /// A position in a field section. /// /// Everything the decoder reads goes through one, which is what keeps the /// bounds checks in a single place rather than one per representation — and a /// field section is the input a server is most often handed by somebody who /// means it harm. pub const Cursor = struct { bytes: []const u8, pos: usize = 0, /// Whether every octet of the section has been consumed, which is how a /// decoder knows the section is finished rather than truncated. pub fn atEnd(c: Cursor) bool { return c.pos >= c.bytes.len; } test atEnd { var c: Cursor = .{ .bytes = &.{0x82} }; try testing.expect(!c.atEnd()); _ = try c.byte(); try testing.expect(c.atEnd()); } /// Consumes one octet, or reports that the section ended first. pub fn byte(c: *Cursor) error{Truncated}!u8 { if (c.pos >= c.bytes.len) return error.Truncated; defer c.pos += 1; return c.bytes[c.pos]; } test byte { var c: Cursor = .{ .bytes = &.{ 0x82, 0x86 } }; try testing.expectEqual(@as(u8, 0x82), try c.byte()); try testing.expectEqual(@as(u8, 0x86), try c.byte()); try testing.expectError(error.Truncated, c.byte()); } /// The next octet without consuming it: what a decoder reads a /// representation's pattern bits from before deciding how to parse it. pub fn peekByte(c: Cursor) error{Truncated}!u8 { if (c.pos >= c.bytes.len) return error.Truncated; return c.bytes[c.pos]; } test peekByte { var c: Cursor = .{ .bytes = &.{0x82} }; try testing.expectEqual(@as(u8, 0x82), try c.peekByte()); // Still there. try testing.expectEqual(@as(u8, 0x82), try c.byte()); try testing.expectError(error.Truncated, c.peekByte()); } /// Consumes the next `n` octets and returns them, borrowed from `bytes`. /// Fails without consuming anything if fewer than `n` remain. pub fn slice(c: *Cursor, n: usize) error{Truncated}![]const u8 { if (n > c.bytes.len - c.pos) return error.Truncated; defer c.pos += n; return c.bytes[c.pos..][0..n]; } test slice { var c: Cursor = .{ .bytes = "hello" }; try testing.expectEqualStrings("hel", try c.slice(3)); try testing.expectError(error.Truncated, c.slice(3)); try testing.expectEqualStrings("lo", try c.slice(2)); } /// The prefixed integer of RFC 7541 §5.1, `prefix_bits` wide. /// /// The octet carrying the prefix is consumed here; the flag bits above /// the prefix are the caller's to have peeked at already. pub fn int(c: *Cursor, prefix_bits: u4) IntError!u32 { std.debug.assert(prefix_bits >= 1 and prefix_bits <= 8); const max: u32 = (@as(u32, 1) << prefix_bits) - 1; const first = try c.byte(); const prefix: u32 = first & @as(u8, @intCast(max)); // A prefix below its maximum is the whole value, and there are no // continuation octets to read. if (prefix < max) return prefix; var value: u32 = max; var shift: u5 = 0; while (true) { const b = try c.byte(); const payload: u32 = b & 0x7f; // Seven bits at a time. `shlExact` is the whole overflow check: // it refuses a shift that would push a meaningful bit off the top // of a `u32`, which is exactly the value that cannot fit however // few octets it was written in. const addend = std.math.shlExact(u32, payload, shift) catch return error.IntegerOverflow; value = std.math.add(u32, value, addend) catch return error.IntegerOverflow; if (b & 0x80 == 0) return value; // Running out of shift *is* the cap on the octet count: after the // fifth continuation octet there is nowhere left to put anything. shift = std.math.add(u5, shift, 7) catch return error.IntegerOverflow; } } test int { // RFC 7541 C.1.2: 1337 with a five-bit prefix. The three bits above // the prefix are a representation's pattern, and not part of the value. var c: Cursor = .{ .bytes = &.{ 0xff, 0x9a, 0x0a } }; try testing.expectEqual(@as(u32, 1337), try c.int(5)); try testing.expect(c.atEnd()); } /// The string literal of RFC 7541 §5.2. /// /// The result is either a sub-slice of `bytes` — when the literal was not /// Huffman-coded, in which case nothing is copied — or a prefix of /// `scratch`. Neither is somewhere it may be kept; see the note at the /// top of this file. pub fn string(c: *Cursor, scratch: []u8) StringError![]const u8 { return c.stringPrefixed(7, scratch); } test string { var scratch: [64]u8 = undefined; // RFC 7541 C.4.1: "www.example.com", Huffman-coded into twelve octets. var c: Cursor = .{ .bytes = &.{ 0x8c, 0xf1, 0xe3, 0xc2, 0xe5, 0xf2, 0x3a, 0x6b, 0xa0, 0xab, 0x90, 0xf4, 0xff, } }; try testing.expectEqualStrings("www.example.com", try c.string(&scratch)); try testing.expect(c.atEnd()); } /// The same string literal with a narrower length prefix. /// /// RFC 7541 only ever uses seven bits, because a string literal there is /// always the whole octet. QPACK's are not: §4.5.6 of RFC 9204 puts a /// field line's *name* behind three bits of representation, so the H bit /// is bit 3 and the length has three bits of prefix rather than seven. /// Same algorithm, different width -- which is why this is parameterised /// here rather than written out a second time in `qpack`. pub fn stringPrefixed(c: *Cursor, prefix_bits: u4, scratch: []u8) StringError![]const u8 { std.debug.assert(prefix_bits >= 1 and prefix_bits <= 7); const huffman_bit = @as(u8, 1) << @as(u3, @intCast(prefix_bits)); const first = try c.peekByte(); const coded = first & huffman_bit != 0; const len = try c.int(prefix_bits); const raw = try c.slice(len); if (!coded) return raw; return huffman.decode(raw, scratch); } test stringPrefixed { var scratch: [16]u8 = undefined; // A QPACK-shaped name: a representation's pattern in the high bits, // the H bit at 0x08, and a three-bit length of 3. var c: Cursor = .{ .bytes = &.{ 0x50 | 0x03, 'a', 'g', 'e' } }; try testing.expectEqualStrings("age", try c.stringPrefixed(3, &scratch)); } /// Steps over a string literal without decoding it, which is what a /// decoder does for a field it has already decided is over budget and /// which is not going into the dynamic table. pub fn skipString(c: *Cursor) IntError!void { _ = try c.peekByte(); const len = try c.int(7); _ = try c.slice(len); } test skipString { var c: Cursor = .{ .bytes = &.{ 0x03, 'a', 'g', 'e', 0x82 } }; try c.skipString(); try testing.expectEqual(@as(u8, 0x82), try c.byte()); } }; /// Writes a prefixed integer. `high_bits` is the pattern above the prefix — /// `0x80` for an indexed field, `0x40` for a literal with incremental /// indexing, and so on. pub fn writeInt(out: *Writer, prefix_bits: u4, high_bits: u8, value: u32) Writer.Error!void { std.debug.assert(prefix_bits >= 1 and prefix_bits <= 8); const max: u32 = (@as(u32, 1) << prefix_bits) - 1; if (value < max) return out.writeByte(high_bits | @as(u8, @intCast(value))); try out.writeByte(high_bits | @as(u8, @intCast(max))); var rest = value - max; while (rest >= 128) { try out.writeByte(@as(u8, @truncate(rest & 0x7f)) | 0x80); rest >>= 7; } try out.writeByte(@intCast(rest)); } test writeInt { var buffer: [8]u8 = undefined; var w: Writer = .fixed(&buffer); // RFC 7541 C.1.2, with three pattern bits above the five-bit prefix. try writeInt(&w, 5, 0xe0, 1337); try testing.expectEqualSlices(u8, &.{ 0xff, 0x9a, 0x0a }, w.buffered()); } /// `writeString` with a narrower length prefix and whatever pattern belongs /// above it. See `Cursor.stringPrefixed` for why QPACK needs one. /// /// `prefix_bits` is the width of the length; the Huffman bit sits immediately /// above it, and `high_bits` above that. pub fn writeStringPrefixed( out: *Writer, prefix_bits: u4, high_bits: u8, s: []const u8, lowercase: bool, ) Writer.Error!void { const huffman_bit = @as(u8, 1) << @as(u3, @intCast(prefix_bits)); if (huffman.worthwhile(s, lowercase)) { try writeInt(out, prefix_bits, high_bits | huffman_bit, @intCast(huffman.encodedLen(s, lowercase))); return huffman.encode(out, s, lowercase); } try writeInt(out, prefix_bits, high_bits, @intCast(s.len)); if (lowercase) { for (s) |c| try out.writeByte(std.ascii.toLower(c)); } else { try out.writeAll(s); } } test writeStringPrefixed { var buffer: [16]u8 = undefined; var w: Writer = .fixed(&buffer); // Three octets Huffman coding would not shrink, so they go as they are: // no H bit, and a three-bit length under the pattern 0x50. try writeStringPrefixed(&w, 3, 0x50, "\x00\x01\x02", false); try testing.expectEqualSlices(u8, &.{ 0x53, 0x00, 0x01, 0x02 }, w.buffered()); } /// Writes a string literal, Huffman-coded when that is shorter — which is /// what §5.2 leaves to the encoder, and what every implementation does, /// because a coded string longer than its input is one the decoder has to do /// more work to get back. /// /// `lowercase` is not an optimisation. RFC 9113 §8.2.1 requires field names /// to be lower case on the wire and `protocol.Headers` deliberately stores /// them as the handler wrote them, so somewhere has to fold them. This is the /// right somewhere: the last thing that touches the octets, and the only one /// that can do it without a buffer. pub fn writeString(out: *Writer, s: []const u8, lowercase: bool) Writer.Error!void { if (huffman.worthwhile(s, lowercase)) { try writeInt(out, 7, 0x80, @intCast(huffman.encodedLen(s, lowercase))); return huffman.encode(out, s, lowercase); } try writeInt(out, 7, 0x00, @intCast(s.len)); if (!lowercase) return out.writeAll(s); for (s) |c| try out.writeByte(if (c >= 'A' and c <= 'Z') c + 32 else c); } test writeString { var buffer: [16]u8 = undefined; var w: Writer = .fixed(&buffer); try writeString(&w, "Content-Type", true); // Shorter coded, so the H bit is set -- and folded on the way out. try testing.expect(buffer[0] & 0x80 != 0); var scratch: [16]u8 = undefined; var c: Cursor = .{ .bytes = w.buffered() }; try testing.expectEqualStrings("content-type", try c.string(&scratch)); } test { std.testing.refAllDecls(@This()); } const testing = std.testing; test "RFC 7541 C.1, the three integer examples" { // C.1.1: 10 with a five-bit prefix fits in the prefix. var c: Cursor = .{ .bytes = &.{0x0a} }; try testing.expectEqual(@as(u32, 10), try c.int(5)); // C.1.2: 1337 with a five-bit prefix spills into two continuation octets. c = .{ .bytes = &.{ 0x1f, 0x9a, 0x0a } }; try testing.expectEqual(@as(u32, 1337), try c.int(5)); try testing.expect(c.atEnd()); // C.1.3: 42 starting at an octet boundary, which is a prefix of eight. c = .{ .bytes = &.{0x2a} }; try testing.expectEqual(@as(u32, 42), try c.int(8)); } test "integers round trip at every prefix width" { const values = [_]u32{ 0, 1, 2, 126, 127, 128, 255, 256, 1337, 16383, 16384, 65535, 65536, 1 << 20, (1 << 31) - 1, 1 << 31, std.math.maxInt(u32) - 1, std.math.maxInt(u32), }; var buffer: [16]u8 = undefined; for (1..9) |prefix| { for (values) |value| { var w: Writer = .fixed(&buffer); try writeInt(&w, @intCast(prefix), 0, value); var c: Cursor = .{ .bytes = buffer[0..w.end] }; try testing.expectEqual(value, try c.int(@intCast(prefix))); try testing.expect(c.atEnd()); } } } test "the high bits above a prefix survive" { var buffer: [16]u8 = undefined; var w: Writer = .fixed(&buffer); try writeInt(&w, 7, 0x80, 10); try testing.expectEqual(@as(u8, 0x8a), buffer[0]); // And are not mistaken for part of the value on the way back. var c: Cursor = .{ .bytes = buffer[0..w.end] }; try testing.expectEqual(@as(u32, 10), try c.int(7)); } test "integers that will not fit are refused rather than wrapped" { // A continuation chain that never terminates. var c: Cursor = .{ .bytes = &.{ 0x1f, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80 } }; try testing.expectError(error.IntegerOverflow, c.int(5)); // The non-minimal encoding RFC 7541 §5.1 warns about: a small value // written in as many octets as the sender liked. c = .{ .bytes = &.{ 0x1f, 0x80, 0x80, 0x80, 0x80, 0x80, 0x00 } }; try testing.expectError(error.IntegerOverflow, c.int(5)); // A value one past what a u32 holds. c = .{ .bytes = &.{ 0x1f, 0xe1, 0xff, 0xff, 0xff, 0x0f } }; try testing.expectError(error.IntegerOverflow, c.int(5)); // And one that simply ends. c = .{ .bytes = &.{ 0x1f, 0x80 } }; try testing.expectError(error.Truncated, c.int(5)); } test "string literals, coded and not" { var scratch: [64]u8 = undefined; var buffer: [64]u8 = undefined; // A string Huffman coding would not shrink is written as it is. var w: Writer = .fixed(&buffer); try writeString(&w, "\x00\x01\x02", false); try testing.expectEqual(@as(u8, 0x03), buffer[0]); // no Huffman bit var c: Cursor = .{ .bytes = buffer[0..w.end] }; try testing.expectEqualStrings("\x00\x01\x02", try c.string(&scratch)); // One it would is, and the length prefix carries the Huffman bit. w = .fixed(&buffer); try writeString(&w, "www.example.com", false); try testing.expect(buffer[0] & 0x80 != 0); try testing.expectEqual(@as(u8, 0x8c), buffer[0]); // twelve octets c = .{ .bytes = buffer[0..w.end] }; try testing.expectEqualStrings("www.example.com", try c.string(&scratch)); // A name is folded on the way out and comes back folded. w = .fixed(&buffer); try writeString(&w, "Content-Type", true); c = .{ .bytes = buffer[0..w.end] }; try testing.expectEqualStrings("content-type", try c.string(&scratch)); } test "an uncoded literal is not copied" { var scratch: [64]u8 = undefined; const section = [_]u8{ 0x05, 'h', 'e', 'l', 'l', 'o' }; var c: Cursor = .{ .bytes = §ion }; const s = try c.string(&scratch); try testing.expectEqualStrings("hello", s); // It points into the section, which is exactly why the decoder above this // has to copy before handing it to a handler. try testing.expectEqual(@intFromPtr(§ion[1]), @intFromPtr(s.ptr)); } test "strings that run off the end" { var scratch: [64]u8 = undefined; var c: Cursor = .{ .bytes = &.{ 0x05, 'h', 'i' } }; try testing.expectError(error.Truncated, c.string(&scratch)); // A Huffman string that needs more room than the scratch buffer. var tiny: [2]u8 = undefined; c = .{ .bytes = &.{ 0x8c, 0xf1, 0xe3, 0xc2, 0xe5, 0xf2, 0x3a, 0x6b, 0xa0, 0xab, 0x90, 0xf4, 0xff } }; try testing.expectError(error.StringTooLong, c.string(&tiny)); } test "skipString steps over a literal without decoding it" { var c: Cursor = .{ .bytes = &.{ 0x05, 'h', 'e', 'l', 'l', 'o', 0x99 } }; try c.skipString(); try testing.expectEqual(@as(u8, 0x99), try c.byte()); }