simoom_hpack/
table.rs

1//! The static table (RFC 7541 Appendix A) and the dynamic table (§2.3.2, §4).
2
3use std::collections::VecDeque;
4
5use crate::bytes_eq;
6
7/// The static table, 1-based in the protocol (index `i` is `STATIC_TABLE[i - 1]`).
8pub static STATIC_TABLE: [(&[u8], &[u8]); 61] = STATIC_ENTRIES;
9
10/// [`STATIC_TABLE`] as a constant, for the name lookup built at compile time.
11const STATIC_ENTRIES: [(&[u8], &[u8]); 61] = [
12    (b":authority", b""),
13    (b":method", b"GET"),
14    (b":method", b"POST"),
15    (b":path", b"/"),
16    (b":path", b"/index.html"),
17    (b":scheme", b"http"),
18    (b":scheme", b"https"),
19    (b":status", b"200"),
20    (b":status", b"204"),
21    (b":status", b"206"),
22    (b":status", b"304"),
23    (b":status", b"400"),
24    (b":status", b"404"),
25    (b":status", b"500"),
26    (b"accept-charset", b""),
27    (b"accept-encoding", b"gzip, deflate"),
28    (b"accept-language", b""),
29    (b"accept-ranges", b""),
30    (b"accept", b""),
31    (b"access-control-allow-origin", b""),
32    (b"age", b""),
33    (b"allow", b""),
34    (b"authorization", b""),
35    (b"cache-control", b""),
36    (b"content-disposition", b""),
37    (b"content-encoding", b""),
38    (b"content-language", b""),
39    (b"content-length", b""),
40    (b"content-location", b""),
41    (b"content-range", b""),
42    (b"content-type", b""),
43    (b"cookie", b""),
44    (b"date", b""),
45    (b"etag", b""),
46    (b"expect", b""),
47    (b"expires", b""),
48    (b"from", b""),
49    (b"host", b""),
50    (b"if-match", b""),
51    (b"if-modified-since", b""),
52    (b"if-none-match", b""),
53    (b"if-range", b""),
54    (b"if-unmodified-since", b""),
55    (b"last-modified", b""),
56    (b"link", b""),
57    (b"location", b""),
58    (b"max-forwards", b""),
59    (b"proxy-authenticate", b""),
60    (b"proxy-authorization", b""),
61    (b"range", b""),
62    (b"referer", b""),
63    (b"refresh", b""),
64    (b"retry-after", b""),
65    (b"server", b""),
66    (b"set-cookie", b""),
67    (b"strict-transport-security", b""),
68    (b"transfer-encoding", b""),
69    (b"user-agent", b""),
70    (b"vary", b""),
71    (b"via", b""),
72    (b"www-authenticate", b""),
73];
74
75/// The longest name in the static table (`access-control-allow-origin`).
76const MAX_NAME: usize = 27;
77
78/// The static names by length, built at compile time: `NAMES.0[NAMES.1[n]..NAMES.1[n + 1]]`
79/// holds (first index, entries) of each distinct name of length `n`. A lookup compares a few
80/// names of the right length; a `match` on the names cost about 2 KB of code per caller.
81static NAMES: ([(u8, u8); 61], [u8; MAX_NAME + 2]) = names_by_len();
82
83const fn same(a: &[u8], b: &[u8]) -> bool {
84    if a.len() != b.len() {
85        return false;
86    }
87    let mut i = 0;
88    while i < a.len() {
89        if a[i] != b[i] {
90            return false;
91        }
92        i += 1;
93    }
94    true
95}
96
97const fn names_by_len() -> ([(u8, u8); 61], [u8; MAX_NAME + 2]) {
98    let t = &STATIC_ENTRIES;
99    let mut names = [(0u8, 0u8); 61];
100    let mut starts = [0u8; MAX_NAME + 2];
101    let mut k = 0;
102    let mut len = 0;
103    while len <= MAX_NAME {
104        starts[len] = k as u8;
105        let mut i = 0;
106        while i < t.len() {
107            assert!(t[i].0.len() <= MAX_NAME);
108            if t[i].0.len() == len && (i == 0 || !same(t[i - 1].0, t[i].0)) {
109                let mut n = 1;
110                while i + n < t.len() && same(t[i + n].0, t[i].0) {
111                    n += 1;
112                }
113                names[k] = (i as u8 + 1, n as u8);
114                k += 1;
115            }
116            i += 1;
117        }
118        len += 1;
119    }
120    starts[MAX_NAME + 1] = k as u8;
121    (names, starts)
122}
123
124/// The 1-based static indices that carry `name`: (first, count).
125pub(crate) fn static_name(name: &[u8]) -> Option<(usize, usize)> {
126    let n = name.len();
127    if n > MAX_NAME {
128        return None;
129    }
130    let (names, starts) = &NAMES;
131    for &(first, count) in &names[starts[n] as usize..starts[n + 1] as usize] {
132        if bytes_eq(STATIC_TABLE[first as usize - 1].0, name) {
133            return Some((first as usize, count as usize));
134        }
135    }
136    None
137}
138
139/// A dynamic table entry: offset of the name in the byte buffer, name and value lengths.
140#[derive(Clone, Copy, Debug)]
141struct Entry {
142    off: u32,
143    name: u32,
144    value: u32,
145}
146
147/// Where the name of a new entry comes from.
148pub(crate) enum Name<'a> {
149    Bytes(&'a [u8]),
150    /// An existing dynamic entry (0 = newest); copied before it can be evicted.
151    Dyn(usize),
152}
153
154/// The dynamic table. All names and values live back to back in one byte buffer that only
155/// grows at the end; evicting moves no bytes, and the dead prefix is dropped once it is larger
156/// than the live part, so inserts do not allocate in steady state and the buffer stays below
157/// about twice the maximum size.
158#[derive(Debug, Clone)]
159pub(crate) struct DynTable {
160    buf: Vec<u8>,
161    entries: VecDeque<Entry>, // front = newest
162    size: usize,
163    max: usize,
164}
165
166impl DynTable {
167    pub(crate) fn new(max: usize) -> Self {
168        DynTable { buf: Vec::new(), entries: VecDeque::new(), size: 0, max }
169    }
170
171    pub(crate) fn size(&self) -> usize {
172        self.size
173    }
174
175    pub(crate) fn max(&self) -> usize {
176        self.max
177    }
178
179    pub(crate) fn len(&self) -> usize {
180        self.entries.len()
181    }
182
183    #[inline]
184    pub(crate) fn get(&self, i: usize) -> Option<(&[u8], &[u8])> {
185        let e = self.entries.get(i)?;
186        let (o, n, v) = (e.off as usize, e.name as usize, e.value as usize);
187        Some((&self.buf[o..o + n], &self.buf[o + n..o + n + v]))
188    }
189
190    pub(crate) fn clear(&mut self) {
191        self.entries.clear();
192        self.size = 0;
193        self.buf.clear();
194    }
195
196    pub(crate) fn set_max(&mut self, max: usize) {
197        self.max = max;
198        self.evict(0);
199        if self.entries.is_empty() {
200            self.buf.clear();
201        }
202    }
203
204    fn evict(&mut self, incoming: usize) {
205        while self.size + incoming > self.max {
206            match self.entries.pop_back() {
207                Some(e) => self.size -= e.name as usize + e.value as usize + 32,
208                None => break,
209            }
210        }
211    }
212
213    pub(crate) fn insert(&mut self, name: Name<'_>, value: &[u8]) {
214        let nlen = match name {
215            Name::Bytes(b) => b.len(),
216            Name::Dyn(i) => self.entries[i].name as usize,
217        };
218        let s = nlen + value.len() + 32;
219        if s > self.max {
220            // RFC 7541 §4.4: an entry larger than the table empties it
221            self.entries.clear();
222            self.size = 0;
223            self.buf.clear();
224            return;
225        }
226        // Append first (a dynamic name is copied while its entry still exists), then evict:
227        // eviction never moves bytes.
228        let off = self.buf.len();
229        match name {
230            Name::Bytes(b) => self.buf.extend_from_slice(b),
231            Name::Dyn(i) => {
232                let o = self.entries[i].off as usize;
233                self.buf.extend_from_within(o..o + nlen);
234            }
235        }
236        self.buf.extend_from_slice(value);
237        self.evict(s);
238        self.entries.push_front(Entry { off: off as u32, name: nlen as u32, value: value.len() as u32 });
239        self.size += s;
240        // drop the dead prefix once it outweighs the live bytes
241        let start = self.entries.back().map_or(0, |e| e.off as usize);
242        if start > 1024 && start * 2 > self.buf.len() {
243            self.buf.drain(..start);
244            for e in self.entries.iter_mut() {
245                e.off -= start as u32;
246            }
247        }
248    }
249
250    /// Finds `name` (and `value`): (index of a full match, index of the first name match),
251    /// 0-based from the newest entry. Lengths are compared before any bytes.
252    #[inline]
253    pub(crate) fn find(&self, name: &[u8], value: &[u8]) -> (Option<usize>, Option<usize>) {
254        let mut name_idx = None;
255        for (i, e) in self.entries.iter().enumerate() {
256            if e.name as usize != name.len() {
257                continue;
258            }
259            let o = e.off as usize;
260            if !bytes_eq(&self.buf[o..o + name.len()], name) {
261                continue;
262            }
263            if e.value as usize == value.len() && bytes_eq(&self.buf[o + name.len()..o + name.len() + value.len()], value) {
264                return (Some(i), Some(i));
265            }
266            name_idx.get_or_insert(i);
267        }
268        (None, name_idx)
269    }
270}
271
272#[cfg(test)]
273mod tests {
274    use super::*;
275
276    #[test]
277    fn static_lookup_matches_table() {
278        for (i, (n, _)) in STATIC_TABLE.iter().enumerate() {
279            let (first, count) = static_name(n).unwrap();
280            assert!(first <= i + 1 && i + 1 < first + count, "{}", String::from_utf8_lossy(n));
281            assert_eq!(STATIC_TABLE[first - 1].0, *n);
282        }
283        assert!(static_name(b"x-unknown").is_none());
284        assert!(static_name(b":protocol").is_none());
285    }
286
287    #[test]
288    fn eviction_and_compaction() {
289        let mut t = DynTable::new(200);
290        for i in 0..1000u32 {
291            let v = format!("value-{i}");
292            if i % 3 == 0 && t.len() > 0 {
293                t.insert(Name::Dyn(t.len() - 1), v.as_bytes()); // name of the oldest entry
294            } else {
295                t.insert(Name::Bytes(b"name"), v.as_bytes());
296            }
297            assert!(t.size() <= 200);
298            assert_eq!(t.get(0).unwrap(), (&b"name"[..], v.as_bytes()));
299            assert!(t.buf.len() <= 2 * 200 + 2048);
300        }
301        // a name referring to the only entry, which the insert evicts
302        let mut t = DynTable::new(60);
303        t.insert(Name::Bytes(b"abcdefgh"), b"1");
304        t.insert(Name::Dyn(0), b"2");
305        assert_eq!(t.len(), 1);
306        assert_eq!(t.get(0).unwrap(), (&b"abcdefgh"[..], &b"2"[..]));
307        t.insert(Name::Bytes(&[b'x'; 300]), b"");
308        assert_eq!(t.len(), 0);
309        assert_eq!(t.size(), 0);
310        t.insert(Name::Bytes(b"a"), b"b");
311        t.set_max(0);
312        assert_eq!(t.len(), 0);
313    }
314}
simoom_hpack/table.rs

simoom_hpack/
table.rs
