quiche/h3/qpack/huffman/
mod.rs

Help
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::Error;
28use super::Result;
29
30use self::table::DECODE_TABLE;
31use self::table::ENCODE_TABLE;
32
33pub fn decode(b: &mut octets::Octets) -> Result<Vec<u8>> {
34    // Max compression ratio is >= 0.5
35    let mut out = Vec::with_capacity(b.len() << 1);
36
37    let mut decoder = Decoder::new();
38
39    while b.cap() > 0 {
40        let byte = b.get_u8()?;
41
42        if let Some(b) = decoder.decode4(byte >> 4)? {
43            out.push(b);
44        }
45
46        if let Some(b) = decoder.decode4(byte & 0xf)? {
47            out.push(b);
48        }
49    }
50
51    if !decoder.is_final() {
52        return Err(Error::InvalidHuffmanEncoding);
53    }
54
55    Ok(out)
56}
57
58pub fn encode<const LOWER_CASE: bool>(
59    src: &[u8], out: &mut octets::OctetsMut,
60) -> Result<()> {
61    let mut bits: u64 = 0;
62    let mut pending = 0;
63
64    for &b in src {
65        let b = if LOWER_CASE {
66            b.to_ascii_lowercase()
67        } else {
68            b
69        };
70        let (nbits, code) = ENCODE_TABLE[b as usize];
71
72        pending += nbits;
73
74        if pending < 64 {
75            // Have room for the new token
76            bits |= code << (64 - pending);
77            continue;
78        }
79
80        pending -= 64;
81        // Take only the bits that fit
82        bits |= code >> pending;
83        out.put_u64(bits)?;
84
85        bits = if pending == 0 {
86            0
87        } else {
88            code << (64 - pending)
89        };
90    }
91
92    if pending == 0 {
93        return Ok(());
94    }
95
96    bits |= u64::MAX >> pending;
97    // TODO: replace with `next_multiple_of(8)` when stable
98    pending = (pending + 7) & !7; // Round up to a byte
99    bits >>= 64 - pending;
100
101    if pending >= 32 {
102        pending -= 32;
103        out.put_u32((bits >> pending) as u32)?;
104    }
105
106    while pending > 0 {
107        pending -= 8;
108        out.put_u8((bits >> pending) as u8)?;
109    }
110
111    Ok(())
112}
113
114pub fn encode_output_length<const LOWER_CASE: bool>(src: &[u8]) -> Result<usize> {
115    let mut bits: usize = 0;
116
117    for &b in src {
118        let b = if LOWER_CASE {
119            b.to_ascii_lowercase()
120        } else {
121            b
122        };
123
124        let (nbits, _) = ENCODE_TABLE[b as usize];
125        bits += nbits;
126    }
127
128    let mut len = bits / 8;
129
130    if bits & 7 != 0 {
131        len += 1;
132    }
133
134    if len > src.len() {
135        return Err(Error::InflatedHuffmanEncoding);
136    }
137
138    Ok(len)
139}
140
141struct Decoder {
142    state: usize,
143    maybe_eos: bool,
144}
145
146impl Decoder {
147    fn new() -> Decoder {
148        Decoder {
149            state: 0,
150            maybe_eos: false,
151        }
152    }
153
154    // Decodes 4 bits
155    fn decode4(&mut self, input: u8) -> Result<Option<u8>> {
156        const MAYBE_EOS: u8 = 1;
157        const DECODED: u8 = 2;
158        const ERROR: u8 = 4;
159
160        // (next-state, byte, flags)
161        let (next, byte, flags) = DECODE_TABLE[self.state][input as usize];
162
163        if flags & ERROR == ERROR {
164            // Data followed the EOS marker
165            return Err(Error::InvalidHuffmanEncoding);
166        }
167
168        let ret = if flags & DECODED == DECODED {
169            Some(byte)
170        } else {
171            None
172        };
173
174        self.state = next;
175        self.maybe_eos = flags & MAYBE_EOS == MAYBE_EOS;
176
177        Ok(ret)
178    }
179
180    fn is_final(&self) -> bool {
181        self.state == 0 || self.maybe_eos
182    }
183}
184
185mod table;
quiche/h3/qpack/huffman/mod.rs

quiche/h3/qpack/huffman/
mod.rs
