simoom_qpack/
encoder.rs

1//! QPACK encoder (RFC 9204 sections 2.1, 4.3, 4.4 and 4.5).
2
3use std::collections::VecDeque;
4
5use crate::prim::{get_int, put_int, put_str, static_find, Short};
6use crate::Error;
7
8#[derive(Debug)]
9struct Entry {
10    name: Vec<u8>,
11    value: Vec<u8>,
12}
13
14impl Entry {
15    fn size(&self) -> u64 {
16        self.name.len() as u64 + self.value.len() as u64 + 32
17    }
18}
19
20/// An outstanding field section with dynamic references, waiting for its Section Ack.
21#[derive(Debug)]
22struct Section {
23    stream: u64,
24    ric: u64,
25    min_ref: u64,
26}
27
28/// How one field line is represented.
29enum Rep {
30    Static(u64),
31    StaticName(u64),
32    Dyn(u64),
33    DynName(u64),
34    Literal,
35}
36
37/// A QPACK encoder for one HTTP/3 connection.
38#[derive(Debug)]
39pub struct Encoder {
40    max_cap: u64,
41    cap: u64,
42    peer_max_entries: u64,
43    peer_blocked: u64,
44    entries: VecDeque<Entry>,
45    size: u64,
46    inserted: u64,
47    /// Known Received Count: inserts the decoder has acknowledged.
48    known: u64,
49    sections: Vec<Section>,
50    enc_out: Vec<u8>,
51    dec_buf: Vec<u8>,
52}
53
54impl Default for Encoder {
55    fn default() -> Self {
56        Self::new()
57    }
58}
59
60/// Names whose values are never put in the dynamic table and are sent as never-indexed literals.
61fn sensitive(name: &[u8]) -> bool {
62    name == b"authorization" || name == b"proxy-authorization"
63}
64
65impl Encoder {
66    /// A static-table-only encoder: it never writes to the encoder stream and every section has
67    /// a Required Insert Count of 0.
68    pub fn new() -> Self {
69        Self::with_dynamic_table(0)
70    }
71
72    /// An encoder that uses a dynamic table of up to `max_capacity` bytes, limited further by the
73    /// peer's SETTINGS_QPACK_MAX_TABLE_CAPACITY (see [`Encoder::set_peer_settings`]).
74    pub fn with_dynamic_table(max_capacity: u64) -> Self {
75        Encoder {
76            max_cap: max_capacity,
77            cap: 0,
78            peer_max_entries: 0,
79            peer_blocked: 0,
80            entries: VecDeque::new(),
81            size: 0,
82            inserted: 0,
83            known: 0,
84            sections: Vec::new(),
85            enc_out: Vec::new(),
86            dec_buf: Vec::new(),
87        }
88    }
89
90    /// Applies the peer's SETTINGS_QPACK_MAX_TABLE_CAPACITY and SETTINGS_QPACK_BLOCKED_STREAMS.
91    /// Takes effect only before the first insertion.
92    pub fn set_peer_settings(&mut self, max_table_capacity: u64, blocked_streams: u64) {
93        if self.inserted > 0 {
94            return;
95        }
96        self.peer_max_entries = max_table_capacity / 32;
97        self.peer_blocked = blocked_streams;
98        let cap = self.max_cap.min(max_table_capacity);
99        if cap != self.cap {
100            self.cap = cap;
101            put_int(&mut self.enc_out, 0x20, 5, cap);
102        }
103    }
104
105    /// Number of entries inserted so far.
106    pub fn insert_count(&self) -> u64 {
107        self.inserted
108    }
109
110    /// Number of inserts the decoder has acknowledged.
111    pub fn known_received_count(&self) -> u64 {
112        self.known
113    }
114
115    fn dropped(&self) -> u64 {
116        self.inserted - self.entries.len() as u64
117    }
118
119    fn blocking_streams(&self) -> u64 {
120        let mut n = 0;
121        for (i, s) in self.sections.iter().enumerate() {
122            if s.ric > self.known && !self.sections[..i].iter().any(|x| x.stream == s.stream && x.ric > self.known) {
123                n += 1;
124            }
125        }
126        n
127    }
128
129    /// Whether the entry `abs` may be referenced from a section on `stream`; `blocking` records
130    /// that this section may block the stream.
131    fn can_ref(&self, abs: u64, stream: u64, blocking: &mut bool) -> bool {
132        if abs < self.known || *blocking {
133            return true;
134        }
135        let stream_blocked = self.sections.iter().any(|s| s.stream == stream && s.ric > self.known);
136        if stream_blocked || self.blocking_streams() < self.peer_blocked {
137            *blocking = true;
138            return true;
139        }
140        false
141    }
142
143    /// Evicts acknowledged, unreferenced entries until `size` more bytes fit. Changes nothing and
144    /// returns false when that is not possible.
145    fn make_room(&mut self, size: u64, cur_min_ref: u64) -> bool {
146        if size > self.cap {
147            return false;
148        }
149        let min_ref = self.sections.iter().map(|s| s.min_ref).min().unwrap_or(u64::MAX).min(cur_min_ref);
150        let mut free = self.cap - self.size;
151        let mut n = 0;
152        let d = self.dropped();
153        for (i, e) in self.entries.iter().enumerate() {
154            if free >= size {
155                break;
156            }
157            let abs = d + i as u64;
158            if abs >= self.known || abs >= min_ref {
159                return false;
160            }
161            free += e.size();
162            n += 1;
163        }
164        if free < size {
165            return false;
166        }
167        for _ in 0..n {
168            let e = self.entries.pop_front().expect("counted above");
169            self.size -= e.size();
170        }
171        true
172    }
173
174    fn find(&self, name: &[u8], value: &[u8]) -> (Option<u64>, Option<u64>) {
175        let d = self.dropped();
176        let mut name_idx = None;
177        for (i, e) in self.entries.iter().enumerate().rev() {
178            if e.name == name {
179                if e.value == value {
180                    return (Some(d + i as u64), Some(d + i as u64));
181                }
182                name_idx.get_or_insert(d + i as u64);
183            }
184        }
185        (None, name_idx)
186    }
187
188    /// Inserts an entry, writing the instruction to the encoder stream. Returns its index.
189    fn insert(&mut self, name: &[u8], value: &[u8], cur_min_ref: u64) -> Option<u64> {
190        let size = name.len() as u64 + value.len() as u64 + 32;
191        // name references are resolved before eviction by the decoder (RFC 9204 3.2.2)
192        let sname = static_find(name, b"").1;
193        let dname = if sname.is_none() { self.find(name, value).1 } else { None };
194        if !self.make_room(size, cur_min_ref) {
195            return None;
196        }
197        if let Some(i) = sname {
198            put_int(&mut self.enc_out, 0xc0, 6, i as u64);
199        } else if let Some(abs) = dname {
200            put_int(&mut self.enc_out, 0x80, 6, self.inserted - 1 - abs);
201        } else {
202            put_str(&mut self.enc_out, 0x40, 5, name);
203        }
204        put_str(&mut self.enc_out, 0, 7, value);
205        self.entries.push_back(Entry { name: name.to_vec(), value: value.to_vec() });
206        self.size += size;
207        self.inserted += 1;
208        Some(self.inserted - 1)
209    }
210
211    /// Encodes a field section for `stream_id` into `out`. Field names must already be lowercase.
212    pub fn encode(&mut self, stream_id: u64, fields: &[(&[u8], &[u8])], out: &mut Vec<u8>) {
213        let mut reps = Vec::with_capacity(fields.len());
214        let mut blocking = false;
215        let mut min_ref = u64::MAX;
216        let mut max_ref: Option<u64> = None;
217        for &(name, value) in fields {
218            let (sfull, sname) = static_find(name, value);
219            let rep = if let Some(i) = sfull {
220                Rep::Static(i as u64)
221            } else if self.cap == 0 || sensitive(name) {
222                sname.map_or(Rep::Literal, |i| Rep::StaticName(i as u64))
223            } else {
224                let (dfull, dname) = self.find(name, value);
225                let mut abs = dfull;
226                if abs.is_none() && (name.len() + value.len() + 32) as u64 <= self.cap * 3 / 4 {
227                    abs = self.insert(name, value, min_ref);
228                }
229                match abs {
230                    Some(a) if self.can_ref(a, stream_id, &mut blocking) => Rep::Dyn(a),
231                    _ => match (sname, dname) {
232                        (Some(i), _) => Rep::StaticName(i as u64),
233                        (None, Some(a)) if self.dropped() <= a && self.can_ref(a, stream_id, &mut blocking) => {
234                            Rep::DynName(a)
235                        }
236                        _ => Rep::Literal,
237                    },
238                }
239            };
240            if let Rep::Dyn(a) | Rep::DynName(a) = rep {
241                min_ref = min_ref.min(a);
242                max_ref = Some(max_ref.map_or(a, |m| m.max(a)));
243            }
244            reps.push(rep);
245        }
246        let ric = max_ref.map_or(0, |m| m + 1);
247        let base = self.inserted;
248        if ric == 0 {
249            out.extend_from_slice(&[0, 0]);
250        } else {
251            put_int(out, 0, 8, ric % (2 * self.peer_max_entries) + 1);
252            put_int(out, 0, 7, base - ric);
253            self.sections.push(Section { stream: stream_id, ric, min_ref });
254        }
255        for (rep, &(name, value)) in reps.iter().zip(fields) {
256            let never = if sensitive(name) { 0x20 } else { 0 };
257            match *rep {
258                Rep::Static(i) => put_int(out, 0xc0, 6, i),
259                Rep::Dyn(a) => put_int(out, 0x80, 6, base - 1 - a),
260                Rep::StaticName(i) => {
261                    put_int(out, 0x50 | never, 4, i);
262                    put_str(out, 0, 7, value);
263                }
264                Rep::DynName(a) => {
265                    put_int(out, 0x40 | never, 4, base - 1 - a);
266                    put_str(out, 0, 7, value);
267                }
268                Rep::Literal => {
269                    put_str(out, 0x20 | (never >> 1), 3, name);
270                    put_str(out, 0, 7, value);
271                }
272            }
273        }
274    }
275
276    /// Processes bytes from the peer's decoder stream (RFC 9204 4.4).
277    pub fn on_decoder_stream(&mut self, data: &[u8]) -> Result<(), Error> {
278        let mut buf = std::mem::take(&mut self.dec_buf);
279        buf.extend_from_slice(data);
280        let mut pos = 0;
281        loop {
282            let start = pos;
283            match self.instruction(&buf, &mut pos) {
284                Ok(()) => {}
285                Err(Short::Incomplete) => {
286                    pos = start;
287                    break;
288                }
289                Err(Short::Invalid) => return Err(Error::DecoderStream),
290            }
291        }
292        buf.drain(..pos);
293        if buf.len() > 16 {
294            return Err(Error::DecoderStream);
295        }
296        self.dec_buf = buf;
297        Ok(())
298    }
299
300    fn instruction(&mut self, buf: &[u8], pos: &mut usize) -> Result<(), Short> {
301        let b = *buf.get(*pos).ok_or(Short::Incomplete)?;
302        if b & 0x80 != 0 {
303            // Section Acknowledgment
304            let stream = get_int(buf, pos, 7)?;
305            let i = self.sections.iter().position(|s| s.stream == stream).ok_or(Short::Invalid)?;
306            let s = self.sections.remove(i);
307            self.known = self.known.max(s.ric);
308        } else if b & 0x40 != 0 {
309            // Stream Cancellation
310            let stream = get_int(buf, pos, 6)?;
311            self.sections.retain(|s| s.stream != stream);
312        } else {
313            // Insert Count Increment
314            let inc = get_int(buf, pos, 6)?;
315            if inc == 0 || inc > self.inserted - self.known {
316                return Err(Short::Invalid);
317            }
318            self.known += inc;
319        }
320        Ok(())
321    }
322
323    /// Appends pending encoder-stream instructions to `out`.
324    pub fn take_encoder_stream(&mut self, out: &mut Vec<u8>) {
325        out.append(&mut self.enc_out);
326    }
327}
simoom_qpack/encoder.rs

simoom_qpack/
encoder.rs
