h2/hpack/huffman/
mod.rs

1mod table;
2
3use self::table::{DECODE_TABLE, ENCODE_TABLE};
4use crate::hpack::DecoderError;
5
6use bytes::{BufMut, BytesMut};
7
8const BRANCH: u16 = 0x8000;
9const TABLE_INDEX_MASK: u16 = 0x7f00;
10const TABLE_WIDTH: usize = 256;
11
12pub fn decode(src: &[u8], buf: &mut BytesMut) -> Result<BytesMut, DecoderError> {
13    // Max compression ratio is >= 0.5
14    buf.reserve(src.len() << 1);
15
16    let mut table = 0;
17    let mut acc = 0u32;
18    let mut bits = 0;
19
20    for &byte in src {
21        acc = (acc << 8) | byte as u32;
22        bits += 8;
23
24        while bits >= 8 {
25            let index = (acc >> (bits - 8)) as u8 as usize;
26            let entry = DECODE_TABLE[table * TABLE_WIDTH + index];
27
28            if entry & BRANCH == 0 {
29                buf.put_u8(entry as u8);
30                table = 0;
31                bits -= (entry >> 8) as usize;
32            } else {
33                table = ((entry & TABLE_INDEX_MASK) >> 8) as usize;
34                if table == 0 {
35                    return Err(DecoderError::InvalidHuffmanCode);
36                }
37                bits -= 8;
38            }
39        }
40    }
41
42    // Fewer than eight bits remain. A prefix of the EOS code (all ones) is
43    // valid padding only when the previous symbol has completed.
44    while bits > 0 {
45        debug_assert!(bits < 8);
46        let padding = (1u32 << bits) - 1;
47        if table == 0 && acc & padding == padding {
48            break;
49        }
50
51        let index = (acc << (8 - bits)) as u8 as usize;
52        let entry = DECODE_TABLE[table * TABLE_WIDTH + index];
53        if entry & BRANCH != 0 {
54            return Err(DecoderError::InvalidHuffmanCode);
55        }
56
57        let used = (entry >> 8) as usize;
58        if used > bits {
59            return Err(DecoderError::InvalidHuffmanCode);
60        }
61
62        buf.put_u8(entry as u8);
63        table = 0;
64        bits -= used;
65    }
66
67    if table == 0 {
68        Ok(buf.split())
69    } else {
70        Err(DecoderError::InvalidHuffmanCode)
71    }
72}
73
74pub fn encode(src: &[u8], dst: &mut BytesMut) {
75    let mut bits: u64 = 0;
76    let mut bits_left = 40;
77
78    for &b in src {
79        let (nbits, code) = ENCODE_TABLE[b as usize];
80
81        bits |= code << (bits_left - nbits);
82        bits_left -= nbits;
83
84        while bits_left <= 32 {
85            dst.put_u8((bits >> 32) as u8);
86
87            bits <<= 8;
88            bits_left += 8;
89        }
90    }
91
92    if bits_left != 40 {
93        // This writes the EOS token
94        bits |= (1 << bits_left) - 1;
95        dst.put_u8((bits >> 32) as u8);
96    }
97}
98
99#[cfg(test)]
100mod test {
101    use super::*;
102
103    fn decode(src: &[u8]) -> Result<BytesMut, DecoderError> {
104        let mut buf = BytesMut::new();
105        super::decode(src, &mut buf)
106    }
107
108    #[test]
109    fn decode_single_byte() {
110        assert_eq!("o", decode(&[0b00111111]).unwrap());
111        assert_eq!("0", decode(&[7]).unwrap());
112        assert_eq!("A", decode(&[(0x21 << 2) + 3]).unwrap());
113    }
114
115    #[test]
116    fn single_char_multi_byte() {
117        assert_eq!("#", decode(&[255, 160 + 15]).unwrap());
118        assert_eq!("$", decode(&[255, 200 + 7]).unwrap());
119        assert_eq!("\x0a", decode(&[255, 255, 255, 240 + 3]).unwrap());
120    }
121
122    #[test]
123    fn multi_char() {
124        assert_eq!("!0", decode(&[254, 1]).unwrap());
125        assert_eq!(" !", decode(&[0b01010011, 0b11111000]).unwrap());
126    }
127
128    #[test]
129    fn encode_single_byte() {
130        let mut dst = BytesMut::with_capacity(1);
131
132        encode(b"o", &mut dst);
133        assert_eq!(&dst[..], &[0b00111111]);
134
135        dst.clear();
136        encode(b"0", &mut dst);
137        assert_eq!(&dst[..], &[7]);
138
139        dst.clear();
140        encode(b"A", &mut dst);
141        assert_eq!(&dst[..], &[(0x21 << 2) + 3]);
142    }
143
144    #[test]
145    fn encode_decode_str() {
146        const DATA: &[&str] = &[
147            "hello world",
148            ":method",
149            ":scheme",
150            ":authority",
151            "yahoo.co.jp",
152            "GET",
153            "http",
154            ":path",
155            "/images/top/sp2/cmn/logo-ns-130528.png",
156            "example.com",
157            "hpack-test",
158            "xxxxxxx1",
159            "Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:16.0) Gecko/20100101 Firefox/16.0",
160            "accept",
161            "Accept",
162            "text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8",
163            "cookie",
164            "B=76j09a189a6h4&b=3&s=0b",
165            "TE",
166            "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Morbi non bibendum libero. \
167             Etiam ultrices lorem ut.",
168        ];
169
170        for s in DATA {
171            let mut dst = BytesMut::with_capacity(s.len());
172
173            encode(s.as_bytes(), &mut dst);
174
175            let decoded = decode(&dst).unwrap();
176
177            assert_eq!(&decoded[..], s.as_bytes());
178        }
179    }
180
181    #[test]
182    fn encode_decode_u8() {
183        const DATA: &[&[u8]] = &[b"\0", b"\0\0\0", b"\0\x01\x02\x03\x04\x05", b"\xFF\xF8"];
184
185        for s in DATA {
186            let mut dst = BytesMut::with_capacity(s.len());
187
188            encode(s, &mut dst);
189
190            let decoded = decode(&dst).unwrap();
191
192            assert_eq!(&decoded[..], &s[..]);
193        }
194    }
195
196    #[test]
197    fn encode_decode_all_octets() {
198        let src: Vec<_> = (0..=u8::MAX).collect();
199        let mut encoded = BytesMut::new();
200        encode(&src, &mut encoded);
201        assert_eq!(decode(&encoded).unwrap(), src);
202    }
203
204    #[test]
205    fn rejects_eos_and_invalid_padding() {
206        assert_eq!(decode(&[0xff]), Err(DecoderError::InvalidHuffmanCode));
207        assert_eq!(
208            decode(&[0xff, 0xff, 0xff, 0xff]),
209            Err(DecoderError::InvalidHuffmanCode)
210        );
211        assert_eq!(decode(&[0]), Err(DecoderError::InvalidHuffmanCode));
212    }
213}
214
215/*
216// uncomment to run benchmarks
217#[cfg(test)]
218mod bench {
219    extern crate test;
220
221    use self::test::{black_box, Bencher};
222    use super::*;
223
224    fn decode_input(b: &mut Bencher, input: &[u8]) {
225        let mut encoded = BytesMut::new();
226        encode(input, &mut encoded);
227
228        let mut scratch = BytesMut::with_capacity(input.len() * 2);
229        b.bytes = encoded.len() as u64;
230        b.iter(|| {
231            let decoded = decode(black_box(encoded.as_ref()), &mut scratch).unwrap();
232            black_box(decoded);
233        });
234    }
235
236    #[bench]
237    fn decode_short_ascii(b: &mut Bencher) {
238        decode_input(b, b"www.example.com");
239    }
240
241    #[bench]
242    fn decode_header_value(b: &mut Bencher) {
243        decode_input(
244            b,
245            b"text/html,application/xhtml+xml,application/xml;q=0.9;q=0.8",
246        );
247    }
248
249    #[bench]
250    fn decode_long_ascii(b: &mut Bencher) {
251        decode_input(
252            b,
253            b"Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:16.0) Gecko/20100101 Firefox/16.0",
254        );
255    }
256
257    #[bench]
258    fn decode_all_octets(b: &mut Bencher) {
259        let input: Vec<_> = (0..=u8::MAX).collect();
260        decode_input(b, &input);
261    }
262}
263*/
h2/hpack/huffman/mod.rs

h2/hpack/huffman/
mod.rs
