nexora_proto/http2/
hpack.rs

1//! RFC 7541 header compression with independent encoding and decoding contexts.
2
3use std::collections::VecDeque;
4
5use super::huffman::{huffman_decode, huffman_encode, huffman_encoded_len};
6use crate::{BytesMut, ProtoError, Result};
7
8const INITIAL_TABLE_SIZE: usize = 4096;
9const DEFAULT_HEADER_LIST_SIZE: usize = 16 * 1024;
10
11// RFC 7541 Appendix A. Index zero is reserved and is not stored here.
12const STATIC_TABLE: [(&str, &str); 61] = [
13    (":authority", ""),
14    (":method", "GET"),
15    (":method", "POST"),
16    (":path", "/"),
17    (":path", "/index.html"),
18    (":scheme", "http"),
19    (":scheme", "https"),
20    (":status", "200"),
21    (":status", "204"),
22    (":status", "206"),
23    (":status", "304"),
24    (":status", "400"),
25    (":status", "404"),
26    (":status", "500"),
27    ("accept-charset", ""),
28    ("accept-encoding", "gzip, deflate"),
29    ("accept-language", ""),
30    ("accept-ranges", ""),
31    ("accept", ""),
32    ("access-control-allow-origin", ""),
33    ("age", ""),
34    ("allow", ""),
35    ("authorization", ""),
36    ("cache-control", ""),
37    ("content-disposition", ""),
38    ("content-encoding", ""),
39    ("content-language", ""),
40    ("content-length", ""),
41    ("content-location", ""),
42    ("content-range", ""),
43    ("content-type", ""),
44    ("cookie", ""),
45    ("date", ""),
46    ("etag", ""),
47    ("expect", ""),
48    ("expires", ""),
49    ("from", ""),
50    ("host", ""),
51    ("if-match", ""),
52    ("if-modified-since", ""),
53    ("if-none-match", ""),
54    ("if-range", ""),
55    ("if-unmodified-since", ""),
56    ("last-modified", ""),
57    ("link", ""),
58    ("location", ""),
59    ("max-forwards", ""),
60    ("proxy-authenticate", ""),
61    ("proxy-authorization", ""),
62    ("range", ""),
63    ("referer", ""),
64    ("refresh", ""),
65    ("retry-after", ""),
66    ("server", ""),
67    ("set-cookie", ""),
68    ("strict-transport-security", ""),
69    ("transfer-encoding", ""),
70    ("user-agent", ""),
71    ("vary", ""),
72    ("via", ""),
73    ("www-authenticate", ""),
74];
75
76#[derive(Debug)]
77struct DynamicTable {
78    entries: VecDeque<(String, String)>,
79    size: usize,
80    maximum: usize,
81}
82
83impl DynamicTable {
84    fn new(maximum: usize) -> Self {
85        Self {
86            entries: VecDeque::new(),
87            size: 0,
88            maximum,
89        }
90    }
91
92    fn resize(&mut self, maximum: usize) {
93        self.maximum = maximum;
94        self.evict_to(maximum);
95    }
96
97    fn evict_to(&mut self, target: usize) {
98        while self.size > target {
99            if let Some((name, value)) = self.entries.pop_back() {
100                self.size -= name.len() + value.len() + 32;
101            } else {
102                self.size = 0;
103                break;
104            }
105        }
106    }
107
108    fn insert(&mut self, name: String, value: String) {
109        let Some(size) = entry_size(&name, &value) else {
110            self.entries.clear();
111            self.size = 0;
112            return;
113        };
114        if size > self.maximum {
115            self.entries.clear();
116            self.size = 0;
117            return;
118        }
119        self.evict_to(self.maximum - size);
120        self.entries.push_front((name, value));
121        self.size += size;
122    }
123
124    fn get(&self, index: usize) -> Result<(&str, &str)> {
125        let index = index
126            .checked_sub(1)
127            .ok_or_else(|| hpack_error("zero index"))?;
128        if let Some(&(name, value)) = STATIC_TABLE.get(index) {
129            return Ok((name, value));
130        }
131        self.entries
132            .get(index - STATIC_TABLE.len())
133            .map(|(name, value)| (name.as_str(), value.as_str()))
134            .ok_or_else(|| hpack_error("header index outside table"))
135    }
136
137    fn find(&self, name: &str, value: Option<&str>) -> Option<usize> {
138        STATIC_TABLE
139            .iter()
140            .position(|&(n, v)| n == name && value.is_none_or(|value| value == v))
141            .map(|index| index + 1)
142            .or_else(|| {
143                self.entries
144                    .iter()
145                    .position(|(n, v)| n == name && value.is_none_or(|value| value == v))
146                    .map(|index| index + STATIC_TABLE.len() + 1)
147            })
148    }
149}
150
151/// A connection-direction HPACK encoder with a FIFO dynamic table.
152#[derive(Debug)]
153pub struct HpackEncoder {
154    table: DynamicTable,
155    pending_minimum: Option<usize>,
156}
157
158impl Default for HpackEncoder {
159    fn default() -> Self {
160        Self::new(INITIAL_TABLE_SIZE)
161    }
162}
163
164impl HpackEncoder {
165    /// Creates an encoder using the peer's permitted dynamic table size.
166    ///
167    /// # Errors
168    /// This function does not return errors.
169    ///
170    /// # Panics
171    /// This function does not panic.
172    pub fn new(max_table_size: usize) -> Self {
173        Self {
174            table: DynamicTable::new(max_table_size),
175            pending_minimum: (max_table_size != INITIAL_TABLE_SIZE).then_some(max_table_size),
176        }
177    }
178
179    /// Applies the peer's table limit and schedules the next block's size update.
180    /// The smallest intermediate limit is retained so evictions stay synchronized.
181    ///
182    /// # Errors
183    /// This function does not return errors.
184    ///
185    /// # Panics
186    /// This function does not panic.
187    pub fn set_max_table_size(&mut self, size: usize) {
188        if size != self.table.maximum {
189            self.pending_minimum = Some(self.pending_minimum.map_or(size, |min| min.min(size)));
190            self.table.resize(size);
191        }
192    }
193
194    /// Appends a complete header block, preserving field order and duplicates.
195    /// Authorization and cookie fields always use never-indexed literals.
196    /// Huffman encoding is selected only when it shortens a string.
197    ///
198    /// # Errors
199    /// This function does not return errors.
200    ///
201    /// # Panics
202    /// This function does not panic.
203    pub fn encode(&mut self, headers: &[(String, String)], out: &mut BytesMut) {
204        if let Some(minimum) = self.pending_minimum.take() {
205            encode_integer(minimum, 5, 0x20, out);
206            if minimum != self.table.maximum {
207                encode_integer(self.table.maximum, 5, 0x20, out);
208            }
209        }
210        for (name, value) in headers {
211            let sensitive = [
212                "authorization",
213                "proxy-authorization",
214                "cookie",
215                "set-cookie",
216            ]
217            .iter()
218            .any(|field| name.eq_ignore_ascii_case(field));
219            if !sensitive && let Some(index) = self.table.find(name, Some(value)) {
220                encode_integer(index, 7, 0x80, out);
221                continue;
222            }
223            let indexed = !sensitive
224                && entry_size(name, value).is_some_and(|size| size <= self.table.maximum);
225            let (prefix, flags) = if sensitive {
226                (4, 0x10)
227            } else if indexed {
228                (6, 0x40)
229            } else {
230                (4, 0)
231            };
232            let name_index = self.table.find(name, None).unwrap_or(0);
233            encode_integer(name_index, prefix, flags, out);
234            if name_index == 0 {
235                encode_string(name, out);
236            }
237            encode_string(value, out);
238            if indexed {
239                self.table.insert(name.clone(), value.clone());
240            }
241        }
242    }
243}
244
245/// A connection-direction HPACK decoder with bounded table and header-list sizes.
246#[derive(Debug)]
247pub struct HpackDecoder {
248    table: DynamicTable,
249    max_table_size: usize,
250    max_header_list_size: usize,
251    required_reduction: Option<usize>,
252    failed: bool,
253}
254
255impl Default for HpackDecoder {
256    fn default() -> Self {
257        Self::new(INITIAL_TABLE_SIZE, DEFAULT_HEADER_LIST_SIZE)
258    }
259}
260
261impl HpackDecoder {
262    /// Creates a decoder with explicit dynamic table and decoded list limits.
263    /// Each decoded field contributes its name and value octets plus 32 bytes.
264    ///
265    /// # Errors
266    /// This function does not return errors.
267    ///
268    /// # Panics
269    /// This function does not panic.
270    pub fn new(max_table_size: usize, max_header_list_size: usize) -> Self {
271        Self {
272            table: DynamicTable::new(max_table_size),
273            max_table_size,
274            max_header_list_size,
275            required_reduction: None,
276            failed: false,
277        }
278    }
279
280    /// Changes the permitted table limit after the peer acknowledges SETTINGS.
281    /// A reduction requires a matching update at the next header block's start.
282    ///
283    /// # Errors
284    /// This function does not return errors.
285    ///
286    /// # Panics
287    /// This function does not panic.
288    pub fn set_max_table_size(&mut self, size: usize) {
289        self.max_table_size = size;
290        if size < self.table.maximum {
291            self.required_reduction =
292                Some(self.required_reduction.map_or(size, |min| min.min(size)));
293            self.table.resize(size);
294        }
295    }
296
297    /// Decodes one complete header block, preserving order and duplicate fields.
298    /// A list-size rejection still processes valid table changes through the end
299    /// of the block, allowing later streams to reuse the compression context.
300    /// Names and values must be UTF-8 because this API exposes Rust strings.
301    /// A compression error permanently rejects later blocks because the peer's
302    /// table state can no longer be recovered from the malformed block.
303    ///
304    /// # Errors
305    /// Returns [`ProtoError::Hpack`] for malformed representations, invalid table
306    /// references, integer overflow, invalid UTF-8, missing required updates,
307    /// or a compression context that previously failed.
308    /// Returns [`ProtoError::HeaderListTooLarge`] if the decoded list exceeds its limit.
309    ///
310    /// # Panics
311    /// This function does not panic.
312    pub fn decode(&mut self, block: &[u8]) -> Result<Vec<(String, String)>> {
313        if self.failed {
314            return Err(hpack_error("compression context previously failed"));
315        }
316        let result = self.decode_block(block);
317        if matches!(result, Err(ProtoError::Hpack(_))) {
318            self.failed = true;
319        }
320        result
321    }
322
323    fn decode_block(&mut self, block: &[u8]) -> Result<Vec<(String, String)>> {
324        let mut cursor = 0;
325        let mut headers = Vec::new();
326        let mut list_size = 0usize;
327        let mut too_large = false;
328        let mut saw_field = false;
329        let mut first_update = None;
330        let mut update_count = 0;
331        while let Some(&first) = block.get(cursor) {
332            if first & 0xe0 == 0x20 {
333                if saw_field {
334                    return Err(hpack_error("table size update after header field"));
335                }
336                let size = decode_integer(block, &mut cursor, 5)?;
337                update_count += 1;
338                if update_count > 2 || first_update.is_some_and(|minimum| size < minimum) {
339                    return Err(hpack_error("invalid table size update sequence"));
340                }
341                if size > self.max_table_size {
342                    return Err(hpack_error("table size update exceeds permitted maximum"));
343                }
344                if self
345                    .required_reduction
346                    .is_some_and(|minimum| size > minimum)
347                {
348                    return Err(hpack_error("table size update omits required reduction"));
349                }
350                self.required_reduction = None;
351                first_update = Some(size);
352                self.table.resize(size);
353                continue;
354            }
355            if self.required_reduction.is_some() {
356                return Err(hpack_error("missing required table size update"));
357            }
358            saw_field = true;
359            let incremental = first & 0xc0 == 0x40;
360            let field = if first & 0x80 != 0 {
361                let index = decode_integer(block, &mut cursor, 7)?;
362                let (name, value) = self.table.get(index)?;
363                add_list_size(
364                    name,
365                    value,
366                    &mut list_size,
367                    &mut too_large,
368                    self.max_header_list_size,
369                );
370                if too_large {
371                    continue;
372                }
373                (name.to_owned(), value.to_owned())
374            } else {
375                let prefix = if incremental { 6 } else { 4 };
376                let index = decode_integer(block, &mut cursor, prefix)?;
377                let name = if index == 0 {
378                    decode_string(block, &mut cursor)?
379                } else {
380                    self.table.get(index)?.0.to_owned()
381                };
382                let value = decode_string(block, &mut cursor)?;
383                add_list_size(
384                    &name,
385                    &value,
386                    &mut list_size,
387                    &mut too_large,
388                    self.max_header_list_size,
389                );
390                (name, value)
391            };
392            if incremental {
393                self.table.insert(field.0.clone(), field.1.clone());
394            }
395            if !too_large {
396                headers.push(field);
397            }
398        }
399        if self.required_reduction.is_some() {
400            return Err(hpack_error("missing required table size update"));
401        }
402        if too_large {
403            return Err(ProtoError::HeaderListTooLarge {
404                size: list_size,
405                max: self.max_header_list_size,
406            });
407        }
408        Ok(headers)
409    }
410}
411
412fn hpack_error(reason: &str) -> ProtoError {
413    ProtoError::Hpack(reason.to_owned())
414}
415
416fn entry_size(name: &str, value: &str) -> Option<usize> {
417    name.len().checked_add(value.len())?.checked_add(32)
418}
419
420fn add_list_size(name: &str, value: &str, total: &mut usize, too_large: &mut bool, maximum: usize) {
421    match entry_size(name, value).and_then(|size| total.checked_add(size)) {
422        Some(size) => {
423            *total = size;
424            *too_large |= size > maximum;
425        }
426        None => {
427            *total = usize::MAX;
428            *too_large = true;
429        }
430    }
431}
432
433fn encode_integer(mut value: usize, prefix: u32, flags: u8, out: &mut BytesMut) {
434    let mask = (1u8 << prefix) - 1;
435    if value < usize::from(mask) {
436        out.put_u8(flags | value as u8);
437        return;
438    }
439    out.put_u8(flags | mask);
440    value -= usize::from(mask);
441    while value >= 128 {
442        out.put_u8((value as u8 & 0x7f) | 0x80);
443        value >>= 7;
444    }
445    out.put_u8(value as u8);
446}
447
448fn decode_integer(input: &[u8], cursor: &mut usize, prefix: u32) -> Result<usize> {
449    let first = *input
450        .get(*cursor)
451        .ok_or_else(|| hpack_error("truncated integer"))?;
452    *cursor += 1;
453    let mask = (1u8 << prefix) - 1;
454    let mut value = usize::from(first & mask);
455    if value < usize::from(mask) {
456        return Ok(value);
457    }
458    let mut shift = 0;
459    loop {
460        let byte = *input
461            .get(*cursor)
462            .ok_or_else(|| hpack_error("truncated integer"))?;
463        *cursor += 1;
464        let part = usize::from(byte & 0x7f);
465        if shift >= usize::BITS || part > (usize::MAX >> shift) {
466            return Err(hpack_error("integer overflow"));
467        }
468        value = value
469            .checked_add(part << shift)
470            .ok_or_else(|| hpack_error("integer overflow"))?;
471        if byte & 0x80 == 0 {
472            return Ok(value);
473        }
474        shift += 7;
475    }
476}
477
478fn encode_string(value: &str, out: &mut BytesMut) {
479    let encoded_len = huffman_encoded_len(value.as_bytes());
480    if encoded_len < value.len() {
481        encode_integer(encoded_len, 7, 0x80, out);
482        huffman_encode(value.as_bytes(), out);
483    } else {
484        encode_integer(value.len(), 7, 0, out);
485        out.extend_from_slice(value.as_bytes());
486    }
487}
488
489fn decode_string(input: &[u8], cursor: &mut usize) -> Result<String> {
490    let first = *input
491        .get(*cursor)
492        .ok_or_else(|| hpack_error("missing string length"))?;
493    let length = decode_integer(input, cursor, 7)?;
494    let end = cursor
495        .checked_add(length)
496        .ok_or_else(|| hpack_error("string length overflow"))?;
497    let bytes = input
498        .get(*cursor..end)
499        .ok_or_else(|| hpack_error("truncated string"))?;
500    *cursor = end;
501    let bytes = if first & 0x80 != 0 {
502        huffman_decode(bytes)?
503    } else {
504        bytes.to_vec()
505    };
506    String::from_utf8(bytes).map_err(|_| hpack_error("string is not UTF-8"))
507}
nexora_proto/http2/hpack.rs

nexora_proto/http2/
hpack.rs
