h2/hpack/huffman/
mod.rs

Help
1mod table;
2
3use self::table::{DECODE_TABLE, ENCODE_TABLE};
4use crate::hpack::DecoderError;
5
6use bytes::{BufMut, BytesMut};
7
8// Constructed in the generated `table.rs` file
9struct Decoder {
10    state: usize,
11    maybe_eos: bool,
12}
13
14// These flags must match the ones in genhuff.rs
15
16const MAYBE_EOS: u8 = 1;
17const DECODED: u8 = 2;
18const ERROR: u8 = 4;
19
20pub fn decode(src: &[u8], buf: &mut BytesMut) -> Result<BytesMut, DecoderError> {
21    let mut decoder = Decoder::new();
22
23    // Max compression ratio is >= 0.5
24    buf.reserve(src.len() << 1);
25
26    for b in src {
27        if let Some(b) = decoder.decode4(b >> 4)? {
28            buf.put_u8(b);
29        }
30
31        if let Some(b) = decoder.decode4(b & 0xf)? {
32            buf.put_u8(b);
33        }
34    }
35
36    if !decoder.is_final() {
37        return Err(DecoderError::InvalidHuffmanCode);
38    }
39
40    Ok(buf.split())
41}
42
43pub fn encode(src: &[u8], dst: &mut BytesMut) {
44    let mut bits: u64 = 0;
45    let mut bits_left = 40;
46
47    for &b in src {
48        let (nbits, code) = ENCODE_TABLE[b as usize];
49
50        bits |= code << (bits_left - nbits);
51        bits_left -= nbits;
52
53        while bits_left <= 32 {
54            dst.put_u8((bits >> 32) as u8);
55
56            bits <<= 8;
57            bits_left += 8;
58        }
59    }
60
61    if bits_left != 40 {
62        // This writes the EOS token
63        bits |= (1 << bits_left) - 1;
64        dst.put_u8((bits >> 32) as u8);
65    }
66}
67
68impl Decoder {
69    fn new() -> Decoder {
70        Decoder {
71            state: 0,
72            maybe_eos: false,
73        }
74    }
75
76    // Decodes 4 bits
77    fn decode4(&mut self, input: u8) -> Result<Option<u8>, DecoderError> {
78        // (next-state, byte, flags)
79        let (next, byte, flags) = DECODE_TABLE[self.state][input as usize];
80
81        if flags & ERROR == ERROR {
82            // Data followed the EOS marker
83            return Err(DecoderError::InvalidHuffmanCode);
84        }
85
86        let mut ret = None;
87
88        if flags & DECODED == DECODED {
89            ret = Some(byte);
90        }
91
92        self.state = next;
93        self.maybe_eos = flags & MAYBE_EOS == MAYBE_EOS;
94
95        Ok(ret)
96    }
97
98    fn is_final(&self) -> bool {
99        self.state == 0 || self.maybe_eos
100    }
101}
102
103#[cfg(test)]
104mod test {
105    use super::*;
106
107    fn decode(src: &[u8]) -> Result<BytesMut, DecoderError> {
108        let mut buf = BytesMut::new();
109        super::decode(src, &mut buf)
110    }
111
112    #[test]
113    fn decode_single_byte() {
114        assert_eq!("o", decode(&[0b00111111]).unwrap());
115        assert_eq!("0", decode(&[7]).unwrap());
116        assert_eq!("A", decode(&[(0x21 << 2) + 3]).unwrap());
117    }
118
119    #[test]
120    fn single_char_multi_byte() {
121        assert_eq!("#", decode(&[255, 160 + 15]).unwrap());
122        assert_eq!("$", decode(&[255, 200 + 7]).unwrap());
123        assert_eq!("\x0a", decode(&[255, 255, 255, 240 + 3]).unwrap());
124    }
125
126    #[test]
127    fn multi_char() {
128        assert_eq!("!0", decode(&[254, 1]).unwrap());
129        assert_eq!(" !", decode(&[0b01010011, 0b11111000]).unwrap());
130    }
131
132    #[test]
133    fn encode_single_byte() {
134        let mut dst = BytesMut::with_capacity(1);
135
136        encode(b"o", &mut dst);
137        assert_eq!(&dst[..], &[0b00111111]);
138
139        dst.clear();
140        encode(b"0", &mut dst);
141        assert_eq!(&dst[..], &[7]);
142
143        dst.clear();
144        encode(b"A", &mut dst);
145        assert_eq!(&dst[..], &[(0x21 << 2) + 3]);
146    }
147
148    #[test]
149    fn encode_decode_str() {
150        const DATA: &[&str] = &[
151            "hello world",
152            ":method",
153            ":scheme",
154            ":authority",
155            "yahoo.co.jp",
156            "GET",
157            "http",
158            ":path",
159            "/images/top/sp2/cmn/logo-ns-130528.png",
160            "example.com",
161            "hpack-test",
162            "xxxxxxx1",
163            "Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:16.0) Gecko/20100101 Firefox/16.0",
164            "accept",
165            "Accept",
166            "text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8",
167            "cookie",
168            "B=76j09a189a6h4&b=3&s=0b",
169            "TE",
170            "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Morbi non bibendum libero. \
171             Etiam ultrices lorem ut.",
172        ];
173
174        for s in DATA {
175            let mut dst = BytesMut::with_capacity(s.len());
176
177            encode(s.as_bytes(), &mut dst);
178
179            let decoded = decode(&dst).unwrap();
180
181            assert_eq!(&decoded[..], s.as_bytes());
182        }
183    }
184
185    #[test]
186    fn encode_decode_u8() {
187        const DATA: &[&[u8]] = &[b"\0", b"\0\0\0", b"\0\x01\x02\x03\x04\x05", b"\xFF\xF8"];
188
189        for s in DATA {
190            let mut dst = BytesMut::with_capacity(s.len());
191
192            encode(s, &mut dst);
193
194            let decoded = decode(&dst).unwrap();
195
196            assert_eq!(&decoded[..], &s[..]);
197        }
198    }
199}
h2/hpack/huffman/mod.rs

h2/hpack/huffman/
mod.rs
