Skip to main content

turnloop_http/
hpack.rs

1//! RFC 7541 HPACK, implemented here. Bounded dynamic table and decoded output.
2use crate::{Error, Result, http1::Header};
3#[path = "huffman_table.rs"]
4mod huffman_table;
5use huffman_table::CODES;
6const STATIC: [(&str, &str); 61] = [
7    (":authority", ""),
8    (":method", "GET"),
9    (":method", "POST"),
10    (":path", "/"),
11    (":path", "/index.html"),
12    (":scheme", "http"),
13    (":scheme", "https"),
14    (":status", "200"),
15    (":status", "204"),
16    (":status", "206"),
17    (":status", "304"),
18    (":status", "400"),
19    (":status", "404"),
20    (":status", "500"),
21    ("accept-charset", ""),
22    ("accept-encoding", "gzip, deflate"),
23    ("accept-language", ""),
24    ("accept-ranges", ""),
25    ("accept", ""),
26    ("access-control-allow-origin", ""),
27    ("age", ""),
28    ("allow", ""),
29    ("authorization", ""),
30    ("cache-control", ""),
31    ("content-disposition", ""),
32    ("content-encoding", ""),
33    ("content-language", ""),
34    ("content-length", ""),
35    ("content-location", ""),
36    ("content-range", ""),
37    ("content-type", ""),
38    ("cookie", ""),
39    ("date", ""),
40    ("etag", ""),
41    ("expect", ""),
42    ("expires", ""),
43    ("from", ""),
44    ("host", ""),
45    ("if-match", ""),
46    ("if-modified-since", ""),
47    ("if-none-match", ""),
48    ("if-range", ""),
49    ("if-unmodified-since", ""),
50    ("last-modified", ""),
51    ("link", ""),
52    ("location", ""),
53    ("max-forwards", ""),
54    ("proxy-authenticate", ""),
55    ("proxy-authorization", ""),
56    ("range", ""),
57    ("referer", ""),
58    ("refresh", ""),
59    ("retry-after", ""),
60    ("server", ""),
61    ("set-cookie", ""),
62    ("strict-transport-security", ""),
63    ("transfer-encoding", ""),
64    ("user-agent", ""),
65    ("vary", ""),
66    ("via", ""),
67    ("www-authenticate", ""),
68];
69fn bad() -> Error {
70    Error::new("COMPRESSION_ERROR", "invalid HPACK block")
71}
72pub fn encode_integer(mut value: usize, bits: u8, prefix: u8, out: &mut Vec<u8>) {
73    let mask = (1usize << bits) - 1;
74    if value < mask {
75        out.push(prefix | value as u8);
76        return;
77    }
78    out.push(prefix | mask as u8);
79    value -= mask;
80    while value >= 128 {
81        out.push((value as u8 & 127) | 128);
82        value >>= 7;
83    }
84    out.push(value as u8);
85}
86fn integer(input: &[u8], pos: &mut usize, bits: u8) -> Result<usize> {
87    let mask = (1usize << bits) - 1;
88    let mut n = (*input.get(*pos).ok_or_else(bad)? as usize) & mask;
89    *pos += 1;
90    if n < mask {
91        return Ok(n);
92    }
93    let mut shift = 0;
94    loop {
95        let b = *input.get(*pos).ok_or_else(bad)?;
96        *pos += 1;
97        if shift >= usize::BITS || (b as usize & 127) > (usize::MAX >> shift) {
98            return Err(bad());
99        }
100        n = n.checked_add((b as usize & 127) << shift).ok_or_else(bad)?;
101        if b & 128 == 0 {
102            return Ok(n);
103        }
104        shift += 7;
105    }
106}
107pub fn huffman_encode(input: &[u8], out: &mut Vec<u8>) {
108    let mut acc = 0u64;
109    let mut bits = 0u8;
110    for b in input {
111        let (code, len) = CODES[*b as usize];
112        acc = (acc << len) | code as u64;
113        bits += len;
114        while bits >= 8 {
115            bits -= 8;
116            out.push((acc >> bits) as u8);
117        }
118        acc &= (1u64 << bits) - 1;
119    }
120    if bits > 0 {
121        out.push(((acc << (8 - bits)) | ((1 << (8 - bits)) - 1)) as u8);
122    }
123}
124#[derive(Clone, Copy)]
125struct Node {
126    child: [usize; 2],
127    symbol: Option<u16>,
128}
129fn trie() -> &'static [Node] {
130    static TREE: std::sync::OnceLock<Vec<Node>> = std::sync::OnceLock::new();
131    TREE.get_or_init(|| {
132        let mut nodes = vec![Node {
133            child: [0; 2],
134            symbol: None,
135        }];
136        for (symbol, (code, len)) in CODES.iter().enumerate() {
137            let mut node = 0;
138            for shift in (0..*len).rev() {
139                let bit = ((code >> shift) & 1) as usize;
140                if nodes[node].child[bit] == 0 {
141                    nodes[node].child[bit] = nodes.len();
142                    nodes.push(Node {
143                        child: [0; 2],
144                        symbol: None,
145                    });
146                }
147                node = nodes[node].child[bit];
148            }
149            nodes[node].symbol = Some(symbol as u16);
150        }
151        nodes
152    })
153}
154pub fn huffman_decode(input: &[u8], out: &mut Vec<u8>, limit: usize) -> Result<()> {
155    let nodes = trie();
156    let mut node = 0;
157    let mut pending = 0;
158    let mut ones = true;
159    for b in input {
160        for bit in (0..8).rev() {
161            let value = ((b >> bit) & 1) as usize;
162            node = nodes[node].child[value];
163            if node == 0 {
164                return Err(bad());
165            }
166            pending += 1;
167            ones &= value == 1;
168            if let Some(symbol) = nodes[node].symbol {
169                if symbol == 256 || out.len() >= limit {
170                    return Err(bad());
171                }
172                out.push(symbol as u8);
173                node = 0;
174                pending = 0;
175                ones = true;
176            }
177        }
178    }
179    if pending > 7 || !ones {
180        return Err(bad());
181    }
182    Ok(())
183}
184fn string(input: &[u8], pos: &mut usize, limit: usize) -> Result<Vec<u8>> {
185    let huffman = *input.get(*pos).ok_or_else(bad)? & 128 != 0;
186    let n = integer(input, pos, 7)?;
187    let end = pos.checked_add(n).ok_or_else(bad)?;
188    let raw = input.get(*pos..end).ok_or_else(bad)?;
189    *pos = end;
190    let mut out = Vec::new();
191    if huffman {
192        huffman_decode(raw, &mut out, limit)?;
193    } else {
194        if n > limit {
195            return Err(bad());
196        }
197        out.extend_from_slice(raw);
198    }
199    Ok(out)
200}
201fn emit_string(value: &[u8], out: &mut Vec<u8>) {
202    let bits: usize = value.iter().map(|b| CODES[*b as usize].1 as usize).sum();
203    let n = bits.div_ceil(8);
204    if n < value.len() {
205        encode_integer(n, 7, 128, out);
206        huffman_encode(value, out);
207    } else {
208        encode_integer(value.len(), 7, 0, out);
209        out.extend_from_slice(value);
210    }
211}
212#[derive(Debug)]
213struct Table {
214    slots: Vec<Header>,
215    used: usize,
216    bytes: usize,
217    max: usize,
218}
219impl Table {
220    fn new(max: usize) -> Self {
221        Self {
222            slots: Vec::new(),
223            used: 0,
224            bytes: 0,
225            max,
226        }
227    }
228    fn resize(&mut self, max: usize) {
229        self.max = max;
230        while self.bytes > max {
231            self.evict();
232        }
233    }
234    fn evict(&mut self) {
235        self.used -= 1;
236        let h = &self.slots[self.used];
237        self.bytes -= h.name.len() + h.value.len() + 32;
238    }
239    fn add(&mut self, name: &str, value: &[u8]) {
240        let size = name.len() + value.len() + 32;
241        if size > self.max {
242            self.used = 0;
243            self.bytes = 0;
244            return;
245        }
246        while self.bytes + size > self.max {
247            self.evict();
248        }
249        if self.used == self.slots.len() {
250            self.slots.push(Header::new("", []));
251        }
252        let h = &mut self.slots[self.used];
253        h.name.clear();
254        h.name.push_str(name);
255        h.value.clear();
256        h.value.extend_from_slice(value);
257        self.used += 1;
258        self.slots[..self.used].rotate_right(1);
259        self.bytes += size;
260    }
261    fn get(&self, index: usize) -> Result<(&str, &[u8])> {
262        if index == 0 {
263            return Err(bad());
264        }
265        if index <= 61 {
266            let (n, v) = STATIC[index - 1];
267            Ok((n, v.as_bytes()))
268        } else {
269            self.slots
270                .get(index - 62)
271                .filter(|_| index - 62 < self.used)
272                .map(|h| (h.name.as_str(), h.value.as_slice()))
273                .ok_or_else(bad)
274        }
275    }
276    fn find(&self, name: &str, value: Option<&[u8]>) -> Option<usize> {
277        (1..=61 + self.used).find(|i| {
278            let (n, v) = self.get(*i).unwrap();
279            n == name && value.is_none_or(|x| x == v)
280        })
281    }
282}
283pub struct Decoder {
284    table: Table,
285    allowed: usize,
286    pub max_list_size: usize,
287    failed: bool,
288}
289impl Decoder {
290    pub fn new(table_size: usize, max_list_size: usize) -> Self {
291        Self {
292            table: Table::new(table_size),
293            allowed: table_size,
294            max_list_size,
295            failed: false,
296        }
297    }
298    /// The largest dynamic table size the peer's encoder may signal: the
299    /// HEADER_TABLE_SIZE this endpoint has advertised.
300    pub fn set_allowed(&mut self, size: usize) {
301        self.allowed = size;
302    }
303    pub fn decode(&mut self, input: &[u8], out: &mut Vec<Header>) -> Result<()> {
304        if self.failed {
305            return Err(bad());
306        }
307        let result = self.decode_inner(input, out);
308        if result.is_err() {
309            self.failed = true;
310        }
311        result
312    }
313    fn decode_inner(&mut self, input: &[u8], out: &mut Vec<Header>) -> Result<()> {
314        out.clear();
315        let mut pos = 0;
316        let mut size = 0;
317        let mut fields = false;
318        while pos < input.len() {
319            let b = input[pos];
320            if b & 0xe0 == 0x20 {
321                if fields {
322                    return Err(bad());
323                }
324                let n = integer(input, &mut pos, 5)?;
325                if n > self.allowed {
326                    return Err(bad());
327                }
328                self.table.resize(n);
329                continue;
330            }
331            fields = true;
332            let header = if b & 128 != 0 {
333                let index = integer(input, &mut pos, 7)?;
334                let (n, v) = self.table.get(index)?;
335                Header {
336                    name: n.to_string(),
337                    value: v.to_vec(),
338                }
339            } else {
340                let indexed = b & 64 != 0;
341                let index = integer(input, &mut pos, if indexed { 6 } else { 4 })?;
342                let name = if index == 0 {
343                    String::from_utf8(string(
344                        input,
345                        &mut pos,
346                        self.max_list_size.saturating_sub(size),
347                    )?)
348                    .map_err(|_| bad())?
349                } else {
350                    self.table.get(index)?.0.to_string()
351                };
352                let value = string(
353                    input,
354                    &mut pos,
355                    self.max_list_size.saturating_sub(size + name.len()),
356                )?;
357                if indexed {
358                    self.table.add(&name, &value);
359                }
360                Header { name, value }
361            };
362            size = size
363                .checked_add(header.name.len() + header.value.len() + 32)
364                .ok_or_else(bad)?;
365            if size > self.max_list_size {
366                return Err(Error::new("ENHANCE_YOUR_CALM", "header list limit"));
367            }
368            out.push(header);
369        }
370        Ok(())
371    }
372}
373pub struct Encoder {
374    table: Table,
375    pending: Option<(usize, usize)>,
376}
377impl Encoder {
378    pub fn new(table_size: usize) -> Self {
379        Self {
380            table: Table::new(table_size),
381            pending: None,
382        }
383    }
384    pub fn set_table_size(&mut self, size: usize) {
385        self.table.resize(size);
386        self.pending = Some((self.pending.map_or(size, |(min, _)| min.min(size)), size));
387    }
388    pub fn encode(&mut self, headers: &[Header], out: &mut Vec<u8>) {
389        if let Some((min, last)) = self.pending.take() {
390            encode_integer(min, 5, 0x20, out);
391            if last != min {
392                encode_integer(last, 5, 0x20, out);
393            }
394        }
395        for h in headers {
396            let sensitive = matches!(
397                h.name.as_str(),
398                "authorization" | "proxy-authorization" | "cookie" | "set-cookie"
399            );
400            if !sensitive && let Some(index) = self.table.find(&h.name, Some(&h.value)) {
401                encode_integer(index, 7, 128, out);
402                continue;
403            }
404            let index = self.table.find(&h.name, None).unwrap_or(0);
405            encode_integer(
406                index,
407                if sensitive { 4 } else { 6 },
408                if sensitive { 16 } else { 64 },
409                out,
410            );
411            if index == 0 {
412                emit_string(h.name.as_bytes(), out);
413            }
414            emit_string(&h.value, out);
415            if !sensitive {
416                self.table.add(&h.name, &h.value);
417            }
418        }
419    }
420}