simoom_hpack/
lib.rs

1//! HPACK (RFC 7541) for simoom.
2//!
3//! - [`Decoder`]: decodes header blocks into a callback, with a cap on the dynamic table size
4//!   (the value we advertise in `SETTINGS_HEADER_TABLE_SIZE`) and on the decoded header list
5//!   size. Literal strings that are not Huffman coded are passed straight from the input;
6//!   Huffman strings are decoded into two reusable scratch buffers, and the dynamic table keeps
7//!   all entries in one byte buffer, so steady-state decoding does not allocate.
8//! - [`Encoder`]: indexes repeated fields, never indexes sensitive ones (`authorization`,
9//!   `proxy-authorization`, `cookie`, `set-cookie`), and does not index fields whose values are
10//!   usually unique (`content-length`, `etag`, validators, `:path` with a query).
11//! - [`huffman`]: table-driven Huffman decoding, four bits per step, and encoding.
12//!
13//! ```
14//! use simoom_hpack::{Decoder, Encoder};
15//! let mut enc = Encoder::new(4096);
16//! let mut dec = Decoder::new(4096, 16 * 1024);
17//! let mut block = Vec::new();
18//! enc.encode(&[(b":method", b"GET"), (b"x-id", b"42")], &mut block);
19//! let mut got = Vec::new();
20//! dec.decode(&block, &mut |n: &[u8], v: &[u8]| got.push((n.to_vec(), v.to_vec()))).unwrap();
21//! assert_eq!(got[1], (b"x-id".to_vec(), b"42".to_vec()));
22//! ```
23#![forbid(unsafe_code)]
24
25mod decoder;
26mod encoder;
27pub mod huffman;
28mod table;
29
30pub use decoder::Decoder;
31pub use encoder::{is_sensitive, Encoder};
32pub use table::STATIC_TABLE;
33
34use std::fmt;
35
36/// The protocol's initial dynamic table size (RFC 7541 §4.2, RFC 9113 §6.5.2).
37pub const DEFAULT_TABLE_SIZE: usize = 4096;
38
39/// Size of a header field for table and list accounting: name + value + 32 (RFC 7541 §4.1).
40#[inline]
41pub fn field_size(name: &[u8], value: &[u8]) -> usize {
42    name.len() + value.len() + 32
43}
44
45/// HPACK decoding errors. Every error except [`Error::HeaderListTooLarge`] leaves the decoder
46/// out of step with the peer's encoder and maps to the HTTP/2 connection error
47/// `COMPRESSION_ERROR`.
48#[derive(Debug, Clone, Copy, PartialEq, Eq)]
49pub enum Error {
50    /// The block ends in the middle of a representation.
51    Truncated,
52    /// A prefix integer is too large.
53    IntegerOverflow,
54    /// An index outside the static and dynamic tables (or index 0).
55    InvalidIndex,
56    /// Invalid Huffman data: EOS in the string, bad or overlong padding.
57    Huffman,
58    /// A dynamic table size update above the allowed maximum or after the first field.
59    InvalidTableSizeUpdate,
60    /// The decoded list is larger than the cap. The block was still decoded completely, so the
61    /// decoder stays in step with the encoder and the connection can continue; fields after the
62    /// limit were not passed to the callback.
63    HeaderListTooLarge,
64}
65
66impl fmt::Display for Error {
67    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
68        f.write_str(match self {
69            Error::Truncated => "truncated header block",
70            Error::IntegerOverflow => "integer overflow",
71            Error::InvalidIndex => "invalid table index",
72            Error::Huffman => "invalid huffman string",
73            Error::InvalidTableSizeUpdate => "invalid dynamic table size update",
74            Error::HeaderListTooLarge => "header list too large",
75        })
76    }
77}
78
79impl std::error::Error for Error {}
80
81/// Byte-slice equality for short strings, done with word loads instead of a `memcmp` call
82/// (header names and values are mostly under 32 bytes).
83#[inline]
84pub fn bytes_eq(a: &[u8], b: &[u8]) -> bool {
85    let n = a.len();
86    if n != b.len() {
87        return false;
88    }
89    if n >= 8 {
90        #[inline(always)]
91        fn w(s: &[u8], i: usize) -> u64 {
92            u64::from_ne_bytes(s[i..i + 8].try_into().unwrap_or([0; 8]))
93        }
94        let mut i = 0;
95        while i + 8 <= n {
96            if w(a, i) != w(b, i) {
97                return false;
98            }
99            i += 8;
100        }
101        i == n || w(a, n - 8) == w(b, n - 8)
102    } else if n >= 4 {
103        #[inline(always)]
104        fn w(s: &[u8], i: usize) -> u32 {
105            u32::from_ne_bytes(s[i..i + 4].try_into().unwrap_or([0; 4]))
106        }
107        w(a, 0) == w(b, 0) && w(a, n - 4) == w(b, n - 4)
108    } else {
109        a.iter().zip(b).all(|(x, y)| x == y)
110    }
111}
112
113/// Encodes `value` with an N-bit prefix (RFC 7541 §5.1); `first` holds the high bits of the
114/// first byte.
115pub fn encode_integer(value: usize, prefix_bits: u8, first: u8, out: &mut Vec<u8>) {
116    let max = (1usize << prefix_bits) - 1;
117    if value < max {
118        out.push(first | value as u8);
119        return;
120    }
121    out.push(first | max as u8);
122    let mut v = value - max;
123    while v >= 128 {
124        out.push((v as u8 & 0x7f) | 0x80);
125        v >>= 7;
126    }
127    out.push(v as u8);
128}
129
130/// Decodes an N-bit prefix integer at `buf[*pos]`. At most four continuation bytes are
131/// accepted (values up to about 2^28), far above anything a header block can carry.
132pub fn decode_integer(buf: &[u8], pos: &mut usize, prefix_bits: u8) -> Result<usize, Error> {
133    let max = (1usize << prefix_bits) - 1;
134    let first = *buf.get(*pos).ok_or(Error::Truncated)? as usize & max;
135    *pos += 1;
136    if first < max {
137        return Ok(first);
138    }
139    let mut value = max;
140    let mut shift = 0u32;
141    loop {
142        let b = *buf.get(*pos).ok_or(Error::Truncated)? as usize;
143        *pos += 1;
144        if shift > 21 {
145            return Err(Error::IntegerOverflow);
146        }
147        value += (b & 0x7f) << shift;
148        shift += 7;
149        if b & 0x80 == 0 {
150            return Ok(value);
151        }
152    }
153}
154
155/// Encodes a string literal, Huffman coded when that is shorter and `huffman` is set.
156pub fn encode_string(s: &[u8], huffman: bool, out: &mut Vec<u8>) {
157    if huffman {
158        let hlen = huffman::encoded_len(s);
159        if hlen < s.len() {
160            encode_integer(hlen, 7, 0x80, out);
161            huffman::encode(s, out);
162            return;
163        }
164    }
165    encode_integer(s.len(), 7, 0, out);
166    out.extend_from_slice(s);
167}
168
169/// Reads a string literal: a slice of `block` when it is raw, or the Huffman-decoded bytes in
170/// `scratch`.
171pub(crate) fn read_string<'a>(block: &'a [u8], pos: &mut usize, scratch: &'a mut Vec<u8>) -> Result<&'a [u8], Error> {
172    let huff = *block.get(*pos).ok_or(Error::Truncated)? & 0x80 != 0;
173    let len = decode_integer(block, pos, 7)?;
174    if len > block.len() - *pos {
175        return Err(Error::Truncated);
176    }
177    let raw = &block[*pos..*pos + len];
178    *pos += len;
179    if huff {
180        scratch.clear();
181        huffman::decode(raw, scratch)?;
182        Ok(scratch)
183    } else {
184        Ok(raw)
185    }
186}
187
188#[cfg(test)]
189mod tests {
190    use super::*;
191
192    #[test]
193    fn integers_c1() {
194        let mut out = Vec::new();
195        encode_integer(10, 5, 0, &mut out);
196        assert_eq!(out, [0b01010]);
197        out.clear();
198        encode_integer(1337, 5, 0, &mut out);
199        assert_eq!(out, [31, 154, 10]);
200        let mut pos = 0;
201        assert_eq!(decode_integer(&out, &mut pos, 5), Ok(1337));
202        assert_eq!(pos, 3);
203        out.clear();
204        encode_integer(42, 8, 0, &mut out);
205        assert_eq!(out, [42]);
206        for v in [0usize, 30, 31, 127, 128, 255, 16_383, 1 << 20, (1 << 28) - 1] {
207            for p in 1..=8u8 {
208                let mut o = Vec::new();
209                encode_integer(v, p, 0, &mut o);
210                let mut pos = 0;
211                assert_eq!(decode_integer(&o, &mut pos, p), Ok(v), "{v} prefix {p}");
212                assert_eq!(pos, o.len());
213            }
214        }
215        let mut pos = 0;
216        assert_eq!(decode_integer(&[0x1f, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f], &mut pos, 5), Err(Error::IntegerOverflow));
217        let mut pos = 0;
218        assert_eq!(decode_integer(&[0x1f, 0xff], &mut pos, 5), Err(Error::Truncated));
219        let mut pos = 0;
220        assert_eq!(decode_integer(&[], &mut pos, 5), Err(Error::Truncated));
221    }
222
223    #[test]
224    fn short_equality() {
225        let s = b"abcdefghijklmnopqrstuvwxyz0123456789";
226        for i in 0..s.len() {
227            for j in i..s.len() {
228                let a = &s[i..j];
229                assert!(bytes_eq(a, &a.to_vec()));
230                let mut b = a.to_vec();
231                for k in 0..b.len() {
232                    b[k] ^= 1;
233                    assert!(!bytes_eq(a, &b));
234                    b[k] ^= 1;
235                }
236                if j < s.len() {
237                    assert!(!bytes_eq(a, &s[i..j + 1]), "different lengths");
238                }
239            }
240        }
241    }
242
243    #[test]
244    fn strings() {
245        let mut out = Vec::new();
246        encode_string(b"www.example.com", true, &mut out);
247        assert_eq!(out[0], 0x8c);
248        let mut scratch = Vec::new();
249        let mut pos = 0;
250        assert_eq!(read_string(&out, &mut pos, &mut scratch).unwrap(), b"www.example.com");
251        out.clear();
252        encode_string(b"\xff\xfe", true, &mut out); // Huffman would be longer
253        assert_eq!(out, [2, 0xff, 0xfe]);
254        let mut pos = 0;
255        assert_eq!(read_string(&[5, b'a'], &mut pos, &mut scratch), Err(Error::Truncated));
256    }
257}
simoom_hpack/lib.rs

simoom_hpack/
lib.rs
