1 mod table;
2 
3 use self::table::{DECODE_TABLE, ENCODE_TABLE};
4 use crate::hpack::DecoderError;
5 
6 use bytes::{BufMut, BytesMut};
7 
8 // Constructed in the generated `table.rs` file
9 struct Decoder {
10     state: usize,
11     maybe_eos: bool,
12 }
13 
14 // These flags must match the ones in genhuff.rs
15 
16 const MAYBE_EOS: u8 = 1;
17 const DECODED: u8 = 2;
18 const ERROR: u8 = 4;
19 
decode(src: &[u8], buf: &mut BytesMut) -> Result<BytesMut, DecoderError>20 pub 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 
encode(src: &[u8], dst: &mut BytesMut)43 pub 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 
68 impl Decoder {
new() -> Decoder69     fn new() -> Decoder {
70         Decoder {
71             state: 0,
72             maybe_eos: false,
73         }
74     }
75 
76     // Decodes 4 bits
decode4(&mut self, input: u8) -> Result<Option<u8>, DecoderError>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 
is_final(&self) -> bool98     fn is_final(&self) -> bool {
99         self.state == 0 || self.maybe_eos
100     }
101 }
102 
103 #[cfg(test)]
104 mod test {
105     use super::*;
106 
decode(src: &[u8]) -> Result<BytesMut, DecoderError>107     fn decode(src: &[u8]) -> Result<BytesMut, DecoderError> {
108         let mut buf = BytesMut::new();
109         super::decode(src, &mut buf)
110     }
111 
112     #[test]
decode_single_byte()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]
single_char_multi_byte()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]
multi_char()127     fn multi_char() {
128         assert_eq!("!0", decode(&[254, 1]).unwrap());
129         assert_eq!(" !", decode(&[0b01010011, 0b11111000]).unwrap());
130     }
131 
132     #[test]
encode_single_byte()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]
encode_decode_str()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]
encode_decode_u8()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 }
200