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
120fn 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]
150fn 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 super::huffman::encode_output_length::<LOWER_CASE>(v) {
156        Ok(len) => {
157            encode_int(len as u64, first | (1 << prefix), prefix, b)?;
158            super::huffman::encode::<LOWER_CASE>(v, b)?;
159        },
160
161        Err(super::Error::InflatedHuffmanEncoding) => {
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        Err(e) => return Err(e),
171    }
172
173    Ok(())
174}
175
176#[cfg(test)]
177mod tests {
178    use super::*;
179
180    #[test]
181    fn encode_int1() {
182        let expected = [0b01010];
183        let mut encoded = [0; 1];
184        let mut b = octets::OctetsMut::with_slice(&mut encoded);
185
186        assert!(encode_int(10, 0, 5, &mut b).is_ok());
187
188        assert_eq!(expected, encoded);
189    }
190
191    #[test]
192    fn encode_int2() {
193        let expected = [0b11111, 0b10011010, 0b00001010];
194        let mut encoded = [0; 3];
195        let mut b = octets::OctetsMut::with_slice(&mut encoded);
196
197        assert!(encode_int(1337, 0, 5, &mut b).is_ok());
198
199        assert_eq!(expected, encoded);
200    }
201
202    #[test]
203    fn encode_int3() {
204        let expected = [0b101010];
205        let mut encoded = [0; 1];
206        let mut b = octets::OctetsMut::with_slice(&mut encoded);
207
208        assert!(encode_int(42, 0, 8, &mut b).is_ok());
209
210        assert_eq!(expected, encoded);
211    }
212
213    #[test]
214    fn encode_static_header() {
215        let mut encoded = [0; 3];
216        Encoder::default()
217            .encode(&[(b":method", b"GET")], &mut encoded)
218            .unwrap();
219        assert_eq!(encoded, [0, 0, INDEXED | 0x40 | 17]);
220    }
221
222    #[test]
223    fn encode_static_header_name_only() {
224        let mut encoded = [0; 11];
225        let mut expected = [0; 11];
226        let mut buf = octets::OctetsMut::with_slice(&mut expected[..]);
227        buf.put_u16(0).unwrap();
228        buf.put_u8(LITERAL_WITH_NAME_REF | 0x10 | 15).unwrap();
229        buf.put_u8(0).unwrap();
230        encode_str::<false>(b"FORGET", 0, 7, &mut buf).unwrap();
231
232        Encoder::default()
233            .encode(&[(b":method", b"FORGET")], &mut encoded)
234            .unwrap();
235        assert_eq!(encoded, expected);
236    }
237}
quiche/h3/qpack/encoder.rs

quiche/h3/qpack/
encoder.rs
