Something went wrong. Try again.
An HTTP library for Zig 0.17, server and client, HTTP/1.0 through HTTP/3, with the protocol in a module that owns no socket.
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>// SPDX-License-Identifier: MIT
//! The Huffman code HPACK string literals may be written in: RFC 7541//! Appendix B.//!//! One table, transcribed from the appendix and laid out so that it can be//! read against it line by line, and everything else in this file computed//! from that table at compile time. That is the whole design, and it is a//! choice about what can go wrong rather than about speed.//!//! ## Why a canonical walk and not a lookup table//!//! The fast way to decode a Huffman code is a multi-level lookup table — an//! eight-bit root and sub-tables for the longer codes — which decodes a//! symbol in one or two array reads. The fastest way is a generated state//! machine, four bits at a time over 256 states, which is what nghttp2 does.//!//! Both are rejected here for the same reason: a reviewer cannot check either//! against the RFC. A state machine is a blob emitted by a program that is not//! in this repository, and a multi-level table is eighty lines of construction//! code whose correctness is not visible from reading it. What is here instead//! keeps the 257 rows looking like the appendix and derives the four small//! arrays the decoder needs beside them, with the derivation asserting the//! properties it depends on — so a mis-transcribed row fails to compile rather//! than at three in the morning.//!//! The cost is up to thirty iterations per output octet instead of one lookup.//! It is worth being precise about the adversarial case rather than waving at//! it: a peer that codes every octet as a thirty-bit symbol makes the decoder//! do thirty iterations per octet, but it had to spend thirty bits to buy//! them. The work is one iteration per *input bit*, and the input is already//! bounded by the frame layer and by `max_header_list_size`. Three//! instructions per input bit on a bounded input is not a denial of service.//!//! If a benchmark ever says otherwise, the table below stays the single source//! of truth and a lookup table can be derived from it at compile time without//! anything else in this file changing. That is the other reason to structure//! it this way.
const std = @import("std");const assert = std.debug.assert;
const Writer = std.Io.Writer;
/// One row of Appendix B: the code, aligned to the least significant bit of/// `bits`, and how many bits of it are meaningful.pub const Code = struct { bits: u32, len: u5,};
/// The end-of-string symbol. It is never emitted — RFC 7541 §5.2 requires a/// string literal containing it to be refused — but it is part of the code,/// and its top bits are what valid padding is made of.pub const eos = 256;
/// The longest code in the table. Worth knowing as a constant because it/// bounds the decoder's bit accumulator.pub const max_code_len = 30;
/// RFC 7541 Appendix B, transcribed. The comment on each row is the/// appendix's own label for the symbol, so that this table can be diffed/// against the RFC by eye — which is the only defence against a transcription/// error that there is.////// Every other table in this file is computed from this one, so this is the/// only thing a reviewer has to check.pub const codes: [257]Code = .{ .{ .bits = 0x1ff8, .len = 13 }, // ( 0) .{ .bits = 0x7fffd8, .len = 23 }, // ( 1) .{ .bits = 0xfffffe2, .len = 28 }, // ( 2) .{ .bits = 0xfffffe3, .len = 28 }, // ( 3) .{ .bits = 0xfffffe4, .len = 28 }, // ( 4) .{ .bits = 0xfffffe5, .len = 28 }, // ( 5) .{ .bits = 0xfffffe6, .len = 28 }, // ( 6) .{ .bits = 0xfffffe7, .len = 28 }, // ( 7) .{ .bits = 0xfffffe8, .len = 28 }, // ( 8) .{ .bits = 0xffffea, .len = 24 }, // ( 9) .{ .bits = 0x3ffffffc, .len = 30 }, // ( 10) .{ .bits = 0xfffffe9, .len = 28 }, // ( 11) .{ .bits = 0xfffffea, .len = 28 }, // ( 12) .{ .bits = 0x3ffffffd, .len = 30 }, // ( 13) .{ .bits = 0xfffffeb, .len = 28 }, // ( 14) .{ .bits = 0xfffffec, .len = 28 }, // ( 15) .{ .bits = 0xfffffed, .len = 28 }, // ( 16) .{ .bits = 0xfffffee, .len = 28 }, // ( 17) .{ .bits = 0xfffffef, .len = 28 }, // ( 18) .{ .bits = 0xffffff0, .len = 28 }, // ( 19) .{ .bits = 0xffffff1, .len = 28 }, // ( 20) .{ .bits = 0xffffff2, .len = 28 }, // ( 21) .{ .bits = 0x3ffffffe, .len = 30 }, // ( 22) .{ .bits = 0xffffff3, .len = 28 }, // ( 23) .{ .bits = 0xffffff4, .len = 28 }, // ( 24) .{ .bits = 0xffffff5, .len = 28 }, // ( 25) .{ .bits = 0xffffff6, .len = 28 }, // ( 26) .{ .bits = 0xffffff7, .len = 28 }, // ( 27) .{ .bits = 0xffffff8, .len = 28 }, // ( 28) .{ .bits = 0xffffff9, .len = 28 }, // ( 29) .{ .bits = 0xffffffa, .len = 28 }, // ( 30) .{ .bits = 0xffffffb, .len = 28 }, // ( 31) .{ .bits = 0x14, .len = 6 }, // ' ' ( 32) .{ .bits = 0x3f8, .len = 10 }, // '!' ( 33) .{ .bits = 0x3f9, .len = 10 }, // '"' ( 34) .{ .bits = 0xffa, .len = 12 }, // '#' ( 35) .{ .bits = 0x1ff9, .len = 13 }, // '$' ( 36) .{ .bits = 0x15, .len = 6 }, // '%' ( 37) .{ .bits = 0xf8, .len = 8 }, // '&' ( 38) .{ .bits = 0x7fa, .len = 11 }, // ''' ( 39) .{ .bits = 0x3fa, .len = 10 }, // '(' ( 40) .{ .bits = 0x3fb, .len = 10 }, // ')' ( 41) .{ .bits = 0xf9, .len = 8 }, // '*' ( 42) .{ .bits = 0x7fb, .len = 11 }, // '+' ( 43) .{ .bits = 0xfa, .len = 8 }, // ',' ( 44) .{ .bits = 0x16, .len = 6 }, // '-' ( 45) .{ .bits = 0x17, .len = 6 }, // '.' ( 46) .{ .bits = 0x18, .len = 6 }, // '/' ( 47) .{ .bits = 0x0, .len = 5 }, // '0' ( 48) .{ .bits = 0x1, .len = 5 }, // '1' ( 49) .{ .bits = 0x2, .len = 5 }, // '2' ( 50) .{ .bits = 0x19, .len = 6 }, // '3' ( 51) .{ .bits = 0x1a, .len = 6 }, // '4' ( 52) .{ .bits = 0x1b, .len = 6 }, // '5' ( 53) .{ .bits = 0x1c, .len = 6 }, // '6' ( 54) .{ .bits = 0x1d, .len = 6 }, // '7' ( 55) .{ .bits = 0x1e, .len = 6 }, // '8' ( 56) .{ .bits = 0x1f, .len = 6 }, // '9' ( 57) .{ .bits = 0x5c, .len = 7 }, // ':' ( 58) .{ .bits = 0xfb, .len = 8 }, // ';' ( 59) .{ .bits = 0x7ffc, .len = 15 }, // '<' ( 60) .{ .bits = 0x20, .len = 6 }, // '=' ( 61) .{ .bits = 0xffb, .len = 12 }, // '>' ( 62) .{ .bits = 0x3fc, .len = 10 }, // '?' ( 63) .{ .bits = 0x1ffa, .len = 13 }, // '@' ( 64) .{ .bits = 0x21, .len = 6 }, // 'A' ( 65) .{ .bits = 0x5d, .len = 7 }, // 'B' ( 66) .{ .bits = 0x5e, .len = 7 }, // 'C' ( 67) .{ .bits = 0x5f, .len = 7 }, // 'D' ( 68) .{ .bits = 0x60, .len = 7 }, // 'E' ( 69) .{ .bits = 0x61, .len = 7 }, // 'F' ( 70) .{ .bits = 0x62, .len = 7 }, // 'G' ( 71) .{ .bits = 0x63, .len = 7 }, // 'H' ( 72) .{ .bits = 0x64, .len = 7 }, // 'I' ( 73) .{ .bits = 0x65, .len = 7 }, // 'J' ( 74) .{ .bits = 0x66, .len = 7 }, // 'K' ( 75) .{ .bits = 0x67, .len = 7 }, // 'L' ( 76) .{ .bits = 0x68, .len = 7 }, // 'M' ( 77) .{ .bits = 0x69, .len = 7 }, // 'N' ( 78) .{ .bits = 0x6a, .len = 7 }, // 'O' ( 79) .{ .bits = 0x6b, .len = 7 }, // 'P' ( 80) .{ .bits = 0x6c, .len = 7 }, // 'Q' ( 81) .{ .bits = 0x6d, .len = 7 }, // 'R' ( 82) .{ .bits = 0x6e, .len = 7 }, // 'S' ( 83) .{ .bits = 0x6f, .len = 7 }, // 'T' ( 84) .{ .bits = 0x70, .len = 7 }, // 'U' ( 85) .{ .bits = 0x71, .len = 7 }, // 'V' ( 86) .{ .bits = 0x72, .len = 7 }, // 'W' ( 87) .{ .bits = 0xfc, .len = 8 }, // 'X' ( 88) .{ .bits = 0x73, .len = 7 }, // 'Y' ( 89) .{ .bits = 0xfd, .len = 8 }, // 'Z' ( 90) .{ .bits = 0x1ffb, .len = 13 }, // '[' ( 91) .{ .bits = 0x7fff0, .len = 19 }, // '\' ( 92) .{ .bits = 0x1ffc, .len = 13 }, // ']' ( 93) .{ .bits = 0x3ffc, .len = 14 }, // '^' ( 94) .{ .bits = 0x22, .len = 6 }, // '_' ( 95) .{ .bits = 0x7ffd, .len = 15 }, // '`' ( 96) .{ .bits = 0x3, .len = 5 }, // 'a' ( 97) .{ .bits = 0x23, .len = 6 }, // 'b' ( 98) .{ .bits = 0x4, .len = 5 }, // 'c' ( 99) .{ .bits = 0x24, .len = 6 }, // 'd' (100) .{ .bits = 0x5, .len = 5 }, // 'e' (101) .{ .bits = 0x25, .len = 6 }, // 'f' (102) .{ .bits = 0x26, .len = 6 }, // 'g' (103) .{ .bits = 0x27, .len = 6 }, // 'h' (104) .{ .bits = 0x6, .len = 5 }, // 'i' (105) .{ .bits = 0x74, .len = 7 }, // 'j' (106) .{ .bits = 0x75, .len = 7 }, // 'k' (107) .{ .bits = 0x28, .len = 6 }, // 'l' (108) .{ .bits = 0x29, .len = 6 }, // 'm' (109) .{ .bits = 0x2a, .len = 6 }, // 'n' (110) .{ .bits = 0x7, .len = 5 }, // 'o' (111) .{ .bits = 0x2b, .len = 6 }, // 'p' (112) .{ .bits = 0x76, .len = 7 }, // 'q' (113) .{ .bits = 0x2c, .len = 6 }, // 'r' (114) .{ .bits = 0x8, .len = 5 }, // 's' (115) .{ .bits = 0x9, .len = 5 }, // 't' (116) .{ .bits = 0x2d, .len = 6 }, // 'u' (117) .{ .bits = 0x77, .len = 7 }, // 'v' (118) .{ .bits = 0x78, .len = 7 }, // 'w' (119) .{ .bits = 0x79, .len = 7 }, // 'x' (120) .{ .bits = 0x7a, .len = 7 }, // 'y' (121) .{ .bits = 0x7b, .len = 7 }, // 'z' (122) .{ .bits = 0x7ffe, .len = 15 }, // '{' (123) .{ .bits = 0x7fc, .len = 11 }, // '|' (124) .{ .bits = 0x3ffd, .len = 14 }, // '}' (125) .{ .bits = 0x1ffd, .len = 13 }, // '~' (126) .{ .bits = 0xffffffc, .len = 28 }, // (127) .{ .bits = 0xfffe6, .len = 20 }, // (128) .{ .bits = 0x3fffd2, .len = 22 }, // (129) .{ .bits = 0xfffe7, .len = 20 }, // (130) .{ .bits = 0xfffe8, .len = 20 }, // (131) .{ .bits = 0x3fffd3, .len = 22 }, // (132) .{ .bits = 0x3fffd4, .len = 22 }, // (133) .{ .bits = 0x3fffd5, .len = 22 }, // (134) .{ .bits = 0x7fffd9, .len = 23 }, // (135) .{ .bits = 0x3fffd6, .len = 22 }, // (136) .{ .bits = 0x7fffda, .len = 23 }, // (137) .{ .bits = 0x7fffdb, .len = 23 }, // (138) .{ .bits = 0x7fffdc, .len = 23 }, // (139) .{ .bits = 0x7fffdd, .len = 23 }, // (140) .{ .bits = 0x7fffde, .len = 23 }, // (141) .{ .bits = 0xffffeb, .len = 24 }, // (142) .{ .bits = 0x7fffdf, .len = 23 }, // (143) .{ .bits = 0xffffec, .len = 24 }, // (144) .{ .bits = 0xffffed, .len = 24 }, // (145) .{ .bits = 0x3fffd7, .len = 22 }, // (146) .{ .bits = 0x7fffe0, .len = 23 }, // (147) .{ .bits = 0xffffee, .len = 24 }, // (148) .{ .bits = 0x7fffe1, .len = 23 }, // (149) .{ .bits = 0x7fffe2, .len = 23 }, // (150) .{ .bits = 0x7fffe3, .len = 23 }, // (151) .{ .bits = 0x7fffe4, .len = 23 }, // (152) .{ .bits = 0x1fffdc, .len = 21 }, // (153) .{ .bits = 0x3fffd8, .len = 22 }, // (154) .{ .bits = 0x7fffe5, .len = 23 }, // (155) .{ .bits = 0x3fffd9, .len = 22 }, // (156) .{ .bits = 0x7fffe6, .len = 23 }, // (157) .{ .bits = 0x7fffe7, .len = 23 }, // (158) .{ .bits = 0xffffef, .len = 24 }, // (159) .{ .bits = 0x3fffda, .len = 22 }, // (160) .{ .bits = 0x1fffdd, .len = 21 }, // (161) .{ .bits = 0xfffe9, .len = 20 }, // (162) .{ .bits = 0x3fffdb, .len = 22 }, // (163) .{ .bits = 0x3fffdc, .len = 22 }, // (164) .{ .bits = 0x7fffe8, .len = 23 }, // (165) .{ .bits = 0x7fffe9, .len = 23 }, // (166) .{ .bits = 0x1fffde, .len = 21 }, // (167) .{ .bits = 0x7fffea, .len = 23 }, // (168) .{ .bits = 0x3fffdd, .len = 22 }, // (169) .{ .bits = 0x3fffde, .len = 22 }, // (170) .{ .bits = 0xfffff0, .len = 24 }, // (171) .{ .bits = 0x1fffdf, .len = 21 }, // (172) .{ .bits = 0x3fffdf, .len = 22 }, // (173) .{ .bits = 0x7fffeb, .len = 23 }, // (174) .{ .bits = 0x7fffec, .len = 23 }, // (175) .{ .bits = 0x1fffe0, .len = 21 }, // (176) .{ .bits = 0x1fffe1, .len = 21 }, // (177) .{ .bits = 0x3fffe0, .len = 22 }, // (178) .{ .bits = 0x1fffe2, .len = 21 }, // (179) .{ .bits = 0x7fffed, .len = 23 }, // (180) .{ .bits = 0x3fffe1, .len = 22 }, // (181) .{ .bits = 0x7fffee, .len = 23 }, // (182) .{ .bits = 0x7fffef, .len = 23 }, // (183) .{ .bits = 0xfffea, .len = 20 }, // (184) .{ .bits = 0x3fffe2, .len = 22 }, // (185) .{ .bits = 0x3fffe3, .len = 22 }, // (186) .{ .bits = 0x3fffe4, .len = 22 }, // (187) .{ .bits = 0x7ffff0, .len = 23 }, // (188) .{ .bits = 0x3fffe5, .len = 22 }, // (189) .{ .bits = 0x3fffe6, .len = 22 }, // (190) .{ .bits = 0x7ffff1, .len = 23 }, // (191) .{ .bits = 0x3ffffe0, .len = 26 }, // (192) .{ .bits = 0x3ffffe1, .len = 26 }, // (193) .{ .bits = 0xfffeb, .len = 20 }, // (194) .{ .bits = 0x7fff1, .len = 19 }, // (195) .{ .bits = 0x3fffe7, .len = 22 }, // (196) .{ .bits = 0x7ffff2, .len = 23 }, // (197) .{ .bits = 0x3fffe8, .len = 22 }, // (198) .{ .bits = 0x1ffffec, .len = 25 }, // (199) .{ .bits = 0x3ffffe2, .len = 26 }, // (200) .{ .bits = 0x3ffffe3, .len = 26 }, // (201) .{ .bits = 0x3ffffe4, .len = 26 }, // (202) .{ .bits = 0x7ffffde, .len = 27 }, // (203) .{ .bits = 0x7ffffdf, .len = 27 }, // (204) .{ .bits = 0x3ffffe5, .len = 26 }, // (205) .{ .bits = 0xfffff1, .len = 24 }, // (206) .{ .bits = 0x1ffffed, .len = 25 }, // (207) .{ .bits = 0x7fff2, .len = 19 }, // (208) .{ .bits = 0x1fffe3, .len = 21 }, // (209) .{ .bits = 0x3ffffe6, .len = 26 }, // (210) .{ .bits = 0x7ffffe0, .len = 27 }, // (211) .{ .bits = 0x7ffffe1, .len = 27 }, // (212) .{ .bits = 0x3ffffe7, .len = 26 }, // (213) .{ .bits = 0x7ffffe2, .len = 27 }, // (214) .{ .bits = 0xfffff2, .len = 24 }, // (215) .{ .bits = 0x1fffe4, .len = 21 }, // (216) .{ .bits = 0x1fffe5, .len = 21 }, // (217) .{ .bits = 0x3ffffe8, .len = 26 }, // (218) .{ .bits = 0x3ffffe9, .len = 26 }, // (219) .{ .bits = 0xffffffd, .len = 28 }, // (220) .{ .bits = 0x7ffffe3, .len = 27 }, // (221) .{ .bits = 0x7ffffe4, .len = 27 }, // (222) .{ .bits = 0x7ffffe5, .len = 27 }, // (223) .{ .bits = 0xfffec, .len = 20 }, // (224) .{ .bits = 0xfffff3, .len = 24 }, // (225) .{ .bits = 0xfffed, .len = 20 }, // (226) .{ .bits = 0x1fffe6, .len = 21 }, // (227) .{ .bits = 0x3fffe9, .len = 22 }, // (228) .{ .bits = 0x1fffe7, .len = 21 }, // (229) .{ .bits = 0x1fffe8, .len = 21 }, // (230) .{ .bits = 0x7ffff3, .len = 23 }, // (231) .{ .bits = 0x3fffea, .len = 22 }, // (232) .{ .bits = 0x3fffeb, .len = 22 }, // (233) .{ .bits = 0x1ffffee, .len = 25 }, // (234) .{ .bits = 0x1ffffef, .len = 25 }, // (235) .{ .bits = 0xfffff4, .len = 24 }, // (236) .{ .bits = 0xfffff5, .len = 24 }, // (237) .{ .bits = 0x3ffffea, .len = 26 }, // (238) .{ .bits = 0x7ffff4, .len = 23 }, // (239) .{ .bits = 0x3ffffeb, .len = 26 }, // (240) .{ .bits = 0x7ffffe6, .len = 27 }, // (241) .{ .bits = 0x3ffffec, .len = 26 }, // (242) .{ .bits = 0x3ffffed, .len = 26 }, // (243) .{ .bits = 0x7ffffe7, .len = 27 }, // (244) .{ .bits = 0x7ffffe8, .len = 27 }, // (245) .{ .bits = 0x7ffffe9, .len = 27 }, // (246) .{ .bits = 0x7ffffea, .len = 27 }, // (247) .{ .bits = 0x7ffffeb, .len = 27 }, // (248) .{ .bits = 0xffffffe, .len = 28 }, // (249) .{ .bits = 0x7ffffec, .len = 27 }, // (250) .{ .bits = 0x7ffffed, .len = 27 }, // (251) .{ .bits = 0x7ffffee, .len = 27 }, // (252) .{ .bits = 0x7ffffef, .len = 27 }, // (253) .{ .bits = 0x7fffff0, .len = 27 }, // (254) .{ .bits = 0x3ffffee, .len = 26 }, // (255) .{ .bits = 0x3fffffff, .len = 30 }, // EOS (256)};
/// The table above, rearranged into what a decoder actually needs — and,/// while it is being rearranged, checked.////// A canonical Huffman code has two properties that together make decoding a/// matter of one comparison per bit:////// * **It is complete.** The Kraft sum — the total of `2^-len` over every/// symbol — is exactly one, which means every infinite bit string starts/// with exactly one code. No bit pattern is undecodable for want of a/// symbol, so the decoder never has to ask whether it has gone wrong; it/// only has to ask whether it has run out of input./// * **Each length's codes are one contiguous run**, and each run begins/// where the previous length's ended, shifted up by one bit. That is what/// makes `code < limit[len]` a sufficient test for "this is a code of/// length `len`", and it is what turns the symbol lookup into an index.////// Both are asserted below at compile time. They are true of Appendix B, and/// if a row is ever mistyped one of them stops being true — which is a build/// failure naming this file rather than a server that decodes one header in a/// million into somebody else's bytes.const Canonical = struct { /// How many symbols have a code of each length. count: [max_code_len + 1]u16, /// The numerically smallest code of each length. first_code: [max_code_len + 1]u32, /// One past the largest code of each length — `first_code + count`, /// precomputed because it is what the decoder compares against. limit: [max_code_len + 1]u32, /// Where each length's symbols begin in `symbols`. first_index: [max_code_len + 1]u16, /// Every symbol, ordered by (length, code). For a canonical code that is /// the same as ordered by code within each length, which is why the /// decoder can index straight into it. symbols: [257]u16,};
const canonical: Canonical = build();
fn build() Canonical { @setEvalBranchQuota(100_000);
var c: Canonical = .{ .count = @splat(0), .first_code = @splat(0), .limit = @splat(0), .first_index = @splat(0), .symbols = @splat(0), };
for (codes) |code| { assert(code.len >= 1 and code.len <= max_code_len); // A code whose value does not fit in the length it claims is a // mistyped row, and the cheapest one to catch. assert(code.bits < (@as(u64, 1) << code.len)); c.count[code.len] += 1; }
// Kraft's equality, computed in a fixed-point fraction with 2^-30 as its // unit so that it is exact: a complete code sums to exactly 1 << 30. var kraft: u64 = 0; for (1..max_code_len + 1) |len| { kraft += @as(u64, c.count[len]) << @intCast(max_code_len - len); } assert(kraft == @as(u64, 1) << max_code_len);
// Lay out the runs, and check as we go that each one starts where the // previous ended. var code: u32 = 0; var index: u16 = 0; for (1..max_code_len + 1) |len| { c.first_code[len] = code; c.first_index[len] = index; c.limit[len] = code + c.count[len]; code = (code + c.count[len]) << 1; index += c.count[len]; } assert(index == codes.len);
// And place the symbols, which is also where "contiguous" is checked: a // code that is not `first_code[len] + n` for the n-th symbol of that // length would land outside its run. var next: [max_code_len + 1]u16 = @splat(0); for (codes, 0..) |entry, symbol| { const offset = entry.bits - c.first_code[entry.len]; assert(offset < c.count[entry.len]); assert(next[entry.len] <= c.count[entry.len]); c.symbols[c.first_index[entry.len] + offset] = @intCast(symbol); next[entry.len] += 1; }
return c;}
/// The octets `s` occupies once Huffman-coded, padding included.////// `lowercase` maps A-Z to a-z on the way, because RFC 9113 §8.2.1 requires/// field names to be lower case on the wire and `protocol.Headers`/// deliberately keeps them as the handler wrote them. Doing it here rather/// than in a buffer somewhere is what makes the conversion free.pub fn encodedLen(s: []const u8, lowercase: bool) usize { var bits: usize = 0; for (s) |raw| bits += codes[fold(raw, lowercase)].len; return (bits + 7) / 8;}
test encodedLen { // RFC 7541 C.4.1: fifteen octets code to twelve. try testing.expectEqual(@as(usize, 12), encodedLen("www.example.com", false)); // Folding does not change the length of a name that is already lower case. try testing.expectEqual(encodedLen("content-type", false), encodedLen("Content-Type", true));}
/// Whether Huffman coding `s` would make it shorter. RFC 7541 §5.2 leaves the/// choice to the encoder, and a coded string longer than its input is one the/// decoder has to do more work to get back.pub fn worthwhile(s: []const u8, lowercase: bool) bool { return encodedLen(s, lowercase) < s.len;}
test worthwhile { try testing.expect(worthwhile("www.example.com", false)); // Octets outside printable ASCII have long codes and would grow. try testing.expect(!worthwhile("\x00\x01\x02", false));}
fn fold(c: u8, lowercase: bool) u8 { return if (lowercase and c >= 'A' and c <= 'Z') c + 32 else c;}
/// Writes `s` Huffman-coded, `encodedLen` octets of it, folding A-Z to a-z/// when `lowercase` is set. The final octet is padded with the most/// significant bits of the EOS code, which are all ones — §5.2 requires/// exactly that, and `decode` refuses anything else.pub fn encode(out: *Writer, s: []const u8, lowercase: bool) Writer.Error!void { var acc: u64 = 0; var bits: u6 = 0; for (s) |raw| { const code = codes[fold(raw, lowercase)]; acc = (acc << code.len) | code.bits; bits += code.len; while (bits >= 8) { bits -= 8; try out.writeByte(@truncate(acc >> bits)); } } if (bits != 0) { const pad: u6 = 8 - bits; try out.writeByte(@truncate((acc << pad) | ((@as(u64, 1) << pad) - 1))); }}
test encode { var buffer: [16]u8 = undefined; var w: Writer = .fixed(&buffer); // RFC 7541 C.4.2. try encode(&w, "no-cache", false); try testing.expectEqualSlices(u8, &.{ 0xa8, 0xeb, 0x10, 0x64, 0x9c, 0xbf }, w.buffered());}
pub const DecodeError = error{ /// RFC 7541 §5.2: "A padding strictly longer than 7 bits MUST be treated /// as a decoding error." /// /// Reachable because the all-ones padding is a prefix of EOS and no /// all-ones string shorter than thirty bits completes any code, so eight /// or more leftover bits can only be over-long padding. PaddingTooLong, /// RFC 7541 §5.2: "A padding not corresponding to the most significant /// bits of the code corresponding to the EOS symbol MUST be treated as a /// decoding error." Which is to say the leftover bits must all be ones. BadPadding, /// RFC 7541 §5.2: "A Huffman-encoded string literal containing the EOS /// symbol MUST be treated as a decoding error." /// /// It is forbidden because it is a second way to say where a string ends, /// and two ways is one too many: an intermediary that honoured it and one /// that did not would disagree about the length of a header. EosInInput, /// The decoded string is longer than the buffer it was given. StringTooLong,};
/// Decodes `src` into `dst`, returning the part of `dst` that was used.////// The padding and EOS rules of §5.2 are enforced rather than tolerated, and a/// result that would not fit `dst` is `StringTooLong` rather than truncated.pub fn decode(src: []const u8, dst: []u8) DecodeError![]u8 { // The live bits, right-aligned in `acc`, with `bits` of them meaningful. // Never more than 37 at once — 30 for the longest code plus the seven that // can be left over — so nothing is ever shifted off the top. var acc: u64 = 0; var bits: u6 = 0; var read: usize = 0; var written: usize = 0;
while (true) { while (bits <= max_code_len - 1 and read < src.len) : (read += 1) { acc = (acc << 8) | src[read]; bits += 8; } if (bits == 0) return dst[0..written];
// Walk the bits, longest-possible-code first, stopping the moment the // accumulated value falls inside a length's run. One comparison per // bit, and no search: a shorter code would already have matched. var len: u5 = 0; var code: u32 = 0; const symbol: ?u16 = found: while (len < max_code_len) { if (len == bits) break :found null; len += 1; // Parenthesised deliberately: in Zig `&`, `^` and `|` share one // precedence level and associate left, so without them this reads // as `(code | bit) & 1` and the accumulated code never exceeds a // single bit. code = (code << 1) | (@as(u32, @truncate(acc >> (bits - len))) & 1); if (code < canonical.limit[len]) { const offset = code - canonical.first_code[len]; break :found canonical.symbols[canonical.first_index[len] + offset]; } } else null;
const sym = symbol orelse { // Nothing left but padding: `bits` of it, which must be the top // `bits` bits of EOS, which are all ones. if (bits > 7) return error.PaddingTooLong; if (code != (@as(u32, 1) << @intCast(bits)) - 1) return error.BadPadding; return dst[0..written]; }; if (sym == eos) return error.EosInInput; if (written == dst.len) return error.StringTooLong; dst[written] = @intCast(sym); written += 1; bits -= len; acc &= (@as(u64, 1) << bits) - 1; }}
test decode { var dst: [16]u8 = undefined; // RFC 7541 C.4.2, back the other way. const plain = try decode(&.{ 0xa8, 0xeb, 0x10, 0x64, 0x9c, 0xbf }, &dst); try testing.expectEqualStrings("no-cache", plain);}
const testing = std.testing;
fn expectRoundTrip(s: []const u8) !void { var buffer: [1024]u8 = undefined; var w: Writer = .fixed(&buffer); try encode(&w, s, false); try testing.expectEqual(encodedLen(s, false), w.end);
var back: [1024]u8 = undefined; try testing.expectEqualStrings(s, try decode(buffer[0..w.end], &back));}
test "every octet survives a round trip, alone and in company" { for (0..256) |i| { const one = [_]u8{@intCast(i)}; try expectRoundTrip(&one); } var all: [256]u8 = undefined; for (&all, 0..) |*c, i| c.* = @intCast(i); try expectRoundTrip(&all); try expectRoundTrip(""); try expectRoundTrip("www.example.com"); try expectRoundTrip("no-cache"); try expectRoundTrip("custom-key");}
test "the strings RFC 7541 Appendix C.4 codes" { // C.4.1: "www.example.com" is fifteen octets and codes to twelve. var buffer: [64]u8 = undefined; var w: Writer = .fixed(&buffer); try encode(&w, "www.example.com", false); try testing.expectEqualSlices(u8, &.{ 0xf1, 0xe3, 0xc2, 0xe5, 0xf2, 0x3a, 0x6b, 0xa0, 0xab, 0x90, 0xf4, 0xff, }, buffer[0..w.end]);
// C.4.2: "no-cache". w = .fixed(&buffer); try encode(&w, "no-cache", false); try testing.expectEqualSlices(u8, &.{ 0xa8, 0xeb, 0x10, 0x64, 0x9c, 0xbf, }, buffer[0..w.end]);}
test "lower-casing on the way out" { var buffer: [64]u8 = undefined; var w: Writer = .fixed(&buffer); try encode(&w, "Content-Type", true);
var back: [64]u8 = undefined; try testing.expectEqualStrings("content-type", try decode(buffer[0..w.end], &back)); try testing.expectEqual(encodedLen("Content-Type", true), w.end);}
test "the three conditions RFC 7541 requires to be refused" { var back: [64]u8 = undefined;
// An explicit EOS: thirty one-bits, then padding. Refused even though it // is a perfectly good code, because §5.2 says so. try testing.expectError(error.EosInInput, decode(&.{ 0xff, 0xff, 0xff, 0xff }, &back));
// Padding of eight bits or more. `0x14` is ' ' in six bits; the two bits // left over are fine, but a whole extra all-ones octet is not. try testing.expectError(error.PaddingTooLong, decode(&.{ 0x53, 0xff }, &back));
// Padding that is not all ones. `0x50` is ' ' followed by two zero bits. try testing.expectError(error.BadPadding, decode(&.{0x50}, &back));}
test "a decode that will not fit is refused rather than truncated" { var tiny: [2]u8 = undefined; // "www.example.com" needs fifteen octets and is being given two. try testing.expectError(error.StringTooLong, decode(&.{ 0xf1, 0xe3, 0xc2, 0xe5, 0xf2, 0x3a, 0x6b, 0xa0, 0xab, 0x90, 0xf4, 0xff, }, &tiny));}
test "the derived tables agree with the transcribed one" { // Everything `build` asserts is checked at compile time; this checks the // result the other way round, by walking every symbol back out of the // tables the decoder actually reads. for (codes, 0..) |code, symbol| { const offset = code.bits - canonical.first_code[code.len]; const index = canonical.first_index[code.len] + offset; try testing.expectEqual(@as(u16, @intCast(symbol)), canonical.symbols[index]); try testing.expect(code.bits < canonical.limit[code.len]); }}