quiche/h3/qpack/
encoder.rs

1// Copyright (C) 2019, Cloudflare, Inc.
2// All rights reserved.
3//
4// Redistribution and use in source and binary forms, with or without
5// modification, are permitted provided that the following conditions are
6// met:
7//
8//     * Redistributions of source code must retain the above copyright notice,
9//       this list of conditions and the following disclaimer.
10//
11//     * Redistributions in binary form must reproduce the above copyright
12//       notice, this list of conditions and the following disclaimer in the
13//       documentation and/or other materials provided with the distribution.
14//
15// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
16// IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
17// THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
18// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
19// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
20// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
21// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
22// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
23// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
24// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26
27use super::Result;
28
29use crate::h3::NameValue;
30
31use super::INDEXED;
32use super::LITERAL;
33use super::LITERAL_WITH_NAME_REF;
34
35/// A QPACK encoder.
36#[derive(Default)]
37pub struct Encoder {}
38
39impl Encoder {
40    /// Creates a new QPACK encoder.
41    pub fn new() -> Encoder {
42        Encoder::default()
43    }
44
45    /// Encodes a list of headers into a QPACK header block.
46    pub fn encode<T: NameValue>(
47        &mut self, headers: &[T], out: &mut [u8],
48    ) -> Result<usize> {
49        let mut b = octets::OctetsMut::with_slice(out);
50
51        // Required Insert Count.
52        encode_int(0, 0, 8, &mut b)?;
53
54        // Base.
55        encode_int(0, 0, 7, &mut b)?;
56
57        for h in headers {
58            match lookup_static(h) {
59                Some((idx, true)) => {
60                    const STATIC: u8 = 0x40;
61
62                    // Encode as statically indexed.
63                    encode_int(idx, INDEXED | STATIC, 6, &mut b)?;
64                },
65
66                Some((idx, false)) => {
67                    const STATIC: u8 = 0x10;
68
69                    // Encode value as literal with static name reference.
70                    encode_int(idx, LITERAL_WITH_NAME_REF | STATIC, 4, &mut b)?;
71                    encode_str::<false>(h.value(), 0, 7, &mut b)?;
72                },
73
74                None => {
75                    // Encode as fully literal.
76
77                    encode_str::<true>(h.name(), LITERAL, 3, &mut b)?;
78                    encode_str::<false>(h.value(), 0, 7, &mut b)?;
79                },
80            };
81        }
82
83        Ok(b.off())
84    }
85}
86
87fn lookup_static<T: NameValue>(h: &T) -> Option<(u64, bool)> {
88    // Fetch the right encoding table for this header length.
89    let table_for_len =
90        super::static_table::STATIC_ENCODE_TABLE.get(h.name().len())?;
91
92    // Similar to [`eq_ignore_ascii_case`], but only lowercases the second
93    // operand, as the entries in the table are already lower cased.
94    let cmp_lowercase = |a: &[u8], b: &[u8]| {
95        std::iter::zip(a, b).all(|(a, b)| a.eq(&b.to_ascii_lowercase()))
96    };
97
98    for (name, values) in table_for_len.iter() {
99        // Match header name first.
100        if cmp_lowercase(name, h.name()) {
101            // Second iterate over possible values for the header.
102            for (value, enc) in values.iter() {
103                // Match header value.
104                if value.is_empty() {
105                    return Some((*enc, false));
106                }
107
108                if h.value() == *value {
109                    return Some((*enc, true));
110                }
111            }
112            // Only matched the header, not the value.
113            return Some((values.first()?.1, false));
114        }
115    }
116
117    None
118}
119
120pub fn encode_int(
121    mut v: u64, first: u8, prefix: usize, b: &mut octets::OctetsMut,
122) -> Result<()> {
123    let mask = 2u64.pow(prefix as u32) - 1;
124
125    // Encode I on N bits.
126    if v < mask {
127        b.put_u8(first | v as u8)?;
128        return Ok(());
129    }
130
131    // Encode (2^N - 1) on N bits.
132    b.put_u8(first | mask as u8)?;
133
134    v -= mask;
135
136    while v >= 128 {
137        // Encode (I % 128 + 128) on 8 bits.
138        b.put_u8((v % 128 + 128) as u8)?;
139
140        v >>= 7;
141    }
142
143    // Encode I on 8 bits.
144    b.put_u8(v as u8)?;
145
146    Ok(())
147}
148
149#[inline]
150pub fn encode_str<const LOWER_CASE: bool>(
151    v: &[u8], first: u8, prefix: usize, b: &mut octets::OctetsMut,
152) -> Result<()> {
153    // Huffman-encoding generally saves space but in some cases it doesn't, for
154    // those just encode the literal string.
155    match octets::huffman_encoding_len::<LOWER_CASE>(v) {
156        Ok(len) => {
157            encode_int(len as u64, first | (1 << prefix), prefix, b)?;
158            b.put_huffman_encoded::<LOWER_CASE>(v)?;
159        },
160
161        Err(_) => {
162            encode_int(v.len() as u64, first, prefix, b)?;
163            if LOWER_CASE {
164                b.put_bytes(&v.to_ascii_lowercase())?;
165            } else {
166                b.put_bytes(v)?;
167            }
168        },
169    }
170
171    Ok(())
172}
173
174#[cfg(test)]
175mod tests {
176    use super::*;
177
178    #[test]
179    fn encode_int1() {
180        let expected = [0b01010];
181        let mut encoded = [0; 1];
182        let mut b = octets::OctetsMut::with_slice(&mut encoded);
183
184        assert!(encode_int(10, 0, 5, &mut b).is_ok());
185
186        assert_eq!(expected, encoded);
187    }
188
189    #[test]
190    fn encode_int2() {
191        let expected = [0b11111, 0b10011010, 0b00001010];
192        let mut encoded = [0; 3];
193        let mut b = octets::OctetsMut::with_slice(&mut encoded);
194
195        assert!(encode_int(1337, 0, 5, &mut b).is_ok());
196
197        assert_eq!(expected, encoded);
198    }
199
200    #[test]
201    fn encode_int3() {
202        let expected = [0b101010];
203        let mut encoded = [0; 1];
204        let mut b = octets::OctetsMut::with_slice(&mut encoded);
205
206        assert!(encode_int(42, 0, 8, &mut b).is_ok());
207
208        assert_eq!(expected, encoded);
209    }
210
211    #[test]
212    fn encode_static_header() {
213        let mut encoded = [0; 3];
214        Encoder::default()
215            .encode(&[(b":method", b"GET")], &mut encoded)
216            .unwrap();
217        assert_eq!(encoded, [0, 0, INDEXED | 0x40 | 17]);
218    }
219
220    #[test]
221    fn encode_static_header_name_only() {
222        let mut encoded = [0; 11];
223        let mut expected = [0; 11];
224        let mut buf = octets::OctetsMut::with_slice(&mut expected[..]);
225        buf.put_u16(0).unwrap();
226        buf.put_u8(LITERAL_WITH_NAME_REF | 0x10 | 15).unwrap();
227        buf.put_u8(0).unwrap();
228        encode_str::<false>(b"FORGET", 0, 7, &mut buf).unwrap();
229
230        Encoder::default()
231            .encode(&[(b":method", b"FORGET")], &mut encoded)
232            .unwrap();
233        assert_eq!(encoded, expected);
234    }
235}
quiche/h3/qpack/encoder.rs

quiche/h3/qpack/
encoder.rs
