sozu_lib/protocol/mux/hpack/
mod.rs

1//! HPACK, the header compression of HTTP/2 (RFC 7541), with no I/O.
2//!
3//! The decoder reads a complete header block from a `&[u8]` and hands each
4//! field to a callback; the encoder appends to a `Vec<u8>` the caller owns.
5//! Neither reads a socket, a clock or anything but its arguments and its own
6//! tables, so both are driven byte-in, byte-out like the rest of the H2 core.
7//!
8//! # Allocations
9//!
10//! The hot path allocates nothing once a connection is warm:
11//!
12//! - Huffman decoding reads a state machine computed at compile time
13//!   ([`huffman`]) and writes into the decoder's scratch buffer;
14//! - a string sent without Huffman coding is borrowed from the block;
15//! - a field found in a table is borrowed from the table;
16//! - the dynamic table keeps all its entries in one byte buffer plus one ring
17//!   of offsets, both grown to a high-water mark bounded by the table size.
18//!
19//! The only allocations are the growth of those three buffers — the scratch
20//! buffer, the table bytes and the offset ring — up to their high-water mark.
21//!
22//! # Guards on untrusted input
23//!
24//! Every malformed block is a [`DecoderError`], never a panic:
25//!
26//! - an integer longer than five octets ([`DecoderError::IntegerOverflow`],
27//!   §5.1), or a block ending inside an integer or a string
28//!   ([`DecoderError::Truncated`]);
29//! - index 0 or an index past both tables ([`DecoderError::InvalidIndex`],
30//!   §2.3.3);
31//! - a size update above the advertised `SETTINGS_HEADER_TABLE_SIZE`
32//!   ([`DecoderError::TableSizeTooLarge`], §6.3), after a field
33//!   ([`DecoderError::SizeUpdateNotAtStart`], §4.2), more than two of them
34//!   ([`DecoderError::TooManySizeUpdates`]) or ending the block
35//!   ([`DecoderError::SizeUpdateAtEnd`]);
36//! - EOS inside a Huffman string, padding that is not all ones, or longer than
37//!   seven bits ([`HuffmanError`], §5.2).
38//!
39//! The decoded header-list size (RFC 9113 §6.5.2) is the caller's to enforce:
40//! `decode_headers_with_budget` (`lib/src/protocol/mux/pkawa.rs`) counts every
41//! field the callback receives. The decoder still decodes the whole block past
42//! that budget, because the dynamic table must stay in step with the peer's
43//! encoder.
44//!
45//! # Provenance
46//!
47//! Written from RFC 7541. `table::STATIC_TABLE` is Appendix A and
48//! `huffman::CODES` is Appendix B, both transcribed from the RFC text; the
49//! code table was also checked, octet by octet, against HAProxy's `ht` table
50//! (`src/hpack-huff.c`). No code comes from `loona-hpack` or `hpack-rs`, which
51//! this module replaces; the encoder only reproduces the representation policy
52//! `loona-hpack` applied, so that the bytes sozu sends do not change.
53
54mod decoder;
55mod encoder;
56pub mod huffman;
57mod table;
58
59#[cfg(test)]
60mod tests;
61
62pub use decoder::Decoder;
63pub use encoder::{Encoder, Representation};
64pub use huffman::HuffmanError;
65
66/// Why a header block could not be decoded. Every variant is a connection
67/// error of type COMPRESSION_ERROR (RFC 9113 §4.3).
68#[derive(Debug, Clone, Copy, PartialEq, Eq, thiserror::Error)]
69pub enum DecoderError {
70    /// The block ends inside an integer or a string.
71    #[error("header block truncated")]
72    Truncated,
73    /// An integer takes more than five octets (RFC 7541 §5.1).
74    #[error("integer encoded on more than five octets")]
75    IntegerOverflow,
76    /// Index 0, or an index past the static and dynamic tables (§2.3.3).
77    #[error("index outside the static and dynamic tables")]
78    InvalidIndex,
79    /// A Huffman string is invalid (§5.2).
80    #[error("invalid Huffman string: {0}")]
81    Huffman(HuffmanError),
82    /// A size update exceeds the advertised `SETTINGS_HEADER_TABLE_SIZE`
83    /// (§6.3).
84    #[error("dynamic table size update above SETTINGS_HEADER_TABLE_SIZE")]
85    TableSizeTooLarge,
86    /// A size update follows a field in the same block (§4.2).
87    #[error("dynamic table size update after a header field")]
88    SizeUpdateNotAtStart,
89    /// More than two size updates open the block (§4.2).
90    #[error("more than two dynamic table size updates")]
91    TooManySizeUpdates,
92    /// The block ends with a size update.
93    #[error("dynamic table size update at the end of a header block")]
94    SizeUpdateAtEnd,
95}
96
97/// Octets an integer may take: its prefix octet and four continuation octets,
98/// enough for 2^28 plus the prefix maximum, far above any length, index or
99/// table size a block can carry.
100const MAX_INTEGER_OCTETS: usize = 5;
101
102/// Decodes the integer (§5.1) whose `prefix_bits`-bit prefix starts `input`,
103/// and returns it with the number of octets it takes.
104fn decode_integer(input: &[u8], prefix_bits: u8) -> Result<(usize, usize), DecoderError> {
105    debug_assert!(
106        (1..=8).contains(&prefix_bits),
107        "an HPACK prefix is 1 to 8 bits"
108    );
109    let Some(&first) = input.first() else {
110        return Err(DecoderError::Truncated);
111    };
112    let mask = ((1u16 << prefix_bits) - 1) as u8;
113    let mut value = usize::from(first & mask);
114    if value < usize::from(mask) {
115        return Ok((value, 1));
116    }
117    for (position, &octet) in input.iter().enumerate().skip(1) {
118        if position >= MAX_INTEGER_OCTETS {
119            return Err(DecoderError::IntegerOverflow);
120        }
121        // At most four continuation octets of 7 bits: the sum stays below
122        // 2^28 + 255 and cannot overflow a 32-bit `usize`.
123        value += usize::from(octet & 0x7f) << (7 * (position - 1));
124        if octet & 0x80 == 0 {
125            debug_assert!(position < MAX_INTEGER_OCTETS, "the octet bound holds");
126            return Ok((value, position + 1));
127        }
128    }
129    Err(DecoderError::Truncated)
130}
131
132/// Appends `value` as an integer with a `prefix_bits`-bit prefix (§5.1), the
133/// high bits of the first octet set to `flags`.
134pub fn encode_integer(value: usize, prefix_bits: u8, flags: u8, out: &mut Vec<u8>) {
135    debug_assert!(
136        (1..=8).contains(&prefix_bits),
137        "an HPACK prefix is 1 to 8 bits"
138    );
139    let mask = ((1u16 << prefix_bits) - 1) as u8;
140    debug_assert!(flags & mask == 0, "flags do not overlap the prefix");
141    if value < usize::from(mask) {
142        out.push(flags | value as u8);
143        return;
144    }
145    out.push(flags | mask);
146    let mut rest = value - usize::from(mask);
147    while rest >= 0x80 {
148        out.push((rest & 0x7f) as u8 | 0x80);
149        rest >>= 7;
150    }
151    out.push(rest as u8);
152}
sozu_lib/protocol/mux/hpack/mod.rs

sozu_lib/protocol/mux/hpack/
mod.rs
