h2/hpack/huffman/decode.rs
1//! Huffman decoding for HPACK (RFC 7541 §5.2).
2//!
3//! The decoder has a fast path which decodes 12 bits a time. The decoder
4//! looks the next 12 bits up in `FAST_TABLE`, which maps directly to either
5//! one or two symbols to decode. Since ASCII letters and digits have 5-7 bit
6//! codes, one lookup usually decodes two symbols at once.
7//!
8//! Two situations fall off this fast path:
9//!
10//! - Codes longer than 12 bits: control characters and bytes >= 0x80
11//! - The end of the input, when fewer than 12 bits remain.
12//!
13//! These are decoded by walking the generated `DECODE_TABLE` one input byte at a time.
14
15use crate::hpack::huffman::table::{DECODE_TABLE, ENCODE_CODES, ENCODE_CODE_LENGTHS};
16use crate::hpack::DecoderError;
17
18use bytes::BytesMut;
19
20// DECODE_TABLE (in the generated `table.rs`) is a series of 256-entry
21// tables, walked one input byte at a time. A leaf entry (BRANCH bit clear)
22// holds a decoded symbol and the number of bits its code used. A branch
23// entry (BRANCH bit set) holds the index of the table for the next byte.
24// No valid code leads back to table 0, so a branch to 0 means the input is
25// not a valid code.
26const BRANCH: u16 = 0x8000;
27const TABLE_INDEX_MASK: u16 = 0x7f00;
28const TABLE_WIDTH: usize = 256;
29
30// Maps each possible 12-bit chunk of input to the symbol(s) it starts
31// with. Entry layout (u32):
32//
33// bits 0..8 first decoded byte
34// bits 8..16 second decoded byte (if any)
35// bits 16..24 number of symbols decoded: 1, 2, or 0, where 0 means the
36// code is longer than 12 bits and the slow path must run
37// bits 24..32 how many of the 12 bits the decoded symbols used
38const FAST_BITS: usize = 12;
39const FAST_DECODE_TABLE: [u32; 1 << FAST_BITS] = build_fast_table();
40
41const fn build_fast_table() -> [u32; 1 << FAST_BITS] {
42 let mut table = [0; 1 << FAST_BITS];
43
44 // First fill in every index that starts with one whole code
45 let mut a = 0;
46 while a < 256 {
47 let len1 = ENCODE_CODE_LENGTHS[a] as usize;
48 let code1 = ENCODE_CODES[a] as u64;
49 if len1 <= FAST_BITS {
50 let rem = FAST_BITS - len1;
51 let base = (code1 as usize) << rem;
52 let single = (1 << 16) | ((len1 as u32) << 24) | a as u32;
53 let mut i = 0;
54 while i < (1 << rem) {
55 table[base + i] = single;
56 i += 1;
57 }
58 }
59 a += 1;
60 }
61
62 // Overwrite the indices where a second whole code fit right after the first
63 let mut a = 0;
64 while a < 256 {
65 let len1 = ENCODE_CODE_LENGTHS[a] as usize;
66 let code1 = ENCODE_CODES[a] as u64;
67 // A second code needs at least 5 more bits (the shortest code)
68 if len1 + 5 <= FAST_BITS {
69 let rem = FAST_BITS - len1;
70 let mut b = 0;
71 while b < 256 {
72 let len2 = ENCODE_CODE_LENGTHS[b] as usize;
73 let code2 = ENCODE_CODES[b] as u64;
74 if len2 <= rem {
75 let rem2 = rem - len2;
76 let base = ((code1 as usize) << rem) | ((code2 as usize) << rem2);
77 let pair =
78 (2 << 16) | (((len1 + len2) as u32) << 24) | ((b as u32) << 8) | a as u32;
79 let mut i = 0;
80 while i < (1 << rem2) {
81 table[base + i] = pair;
82 i += 1;
83 }
84 }
85 b += 1;
86 }
87 }
88 a += 1;
89 }
90
91 table
92}
93
94// Decodes one code of any length by walking DECODE_TABLE one input byte at
95// a time, and writes the symbol to `dst[*o]`. Used for codes longer than
96// FAST_BITS bits and for the tail of the input.
97//
98// Inlining avoids a 35% performance regression on ASCII benchmarks.
99#[inline(always)]
100fn decode_code_slow(
101 acc: &mut u64,
102 bits: &mut usize,
103 dst: &mut [u8],
104 o: &mut usize,
105) -> Result<(), DecoderError> {
106 let mut table = 0;
107 loop {
108 let e = DECODE_TABLE[table * TABLE_WIDTH + (*acc >> 56) as usize];
109 if e & BRANCH == 0 {
110 let used = (e >> 8) as usize;
111 if used > *bits {
112 return Err(DecoderError::InvalidHuffmanCode);
113 }
114 dst[*o] = e as u8;
115 *o += 1;
116 *acc <<= used;
117 *bits -= used;
118 return Ok(());
119 }
120 if *bits < 8 {
121 return Err(DecoderError::InvalidHuffmanCode);
122 }
123 table = ((e & TABLE_INDEX_MASK) >> 8) as usize;
124 if table == 0 {
125 return Err(DecoderError::InvalidHuffmanCode);
126 }
127 *acc <<= 8;
128 *bits -= 8;
129 }
130}
131
132// Decodes a Huffman encoded string into the provided buffer.
133pub fn decode(src: &[u8], buf: &mut BytesMut) -> Result<BytesMut, DecoderError> {
134 let len = src.len();
135 let base_len = buf.len();
136
137 // Reserve the worst case output size. Every code is at least 5 bits,
138 // so `len` input bytes can't decode to more than `len * 8 / 5` output
139 // bytes. One more byte covers the fast path always writing two bytes
140 // even when it decoded only one symbol.
141 buf.resize(base_len + len * 8 / 5 + 1, 0);
142 let dst = &mut buf[base_len..];
143 let mut o = 0;
144
145 let mut acc: u64 = 0;
146 let mut bits: usize = 0;
147 let mut pos: usize = 0;
148
149 'outer: loop {
150 // Fill the bit buffer. While 8 or more input bytes remain, load
151 // the next 8 in one go and count as many whole bytes as fit under
152 // the bits already in the buffer (bringing it to 56-63 bits). The
153 // bytes that didn't fit still land in the low end of `acc`; the
154 // next refill just ORs the same values over them, so no harm done.
155 if pos + 8 <= len {
156 let word = u64::from_be_bytes(src[pos..pos + 8].try_into().unwrap());
157 acc |= word >> bits;
158 pos += (63 - bits) >> 3; // bytes now accounted for in `bits`
159 bits |= 56; // equals bits + 8 * (bytes added)
160 } else {
161 while bits <= 56 && pos < len {
162 acc |= (src[pos] as u64) << (56 - bits);
163 pos += 1;
164 bits += 8;
165 }
166 }
167
168 while bits >= FAST_BITS {
169 let entry = FAST_DECODE_TABLE[(acc >> (64 - FAST_BITS)) as usize];
170 let count = (entry >> 16) & 0xff;
171 if count == 0 {
172 // The next code is longer than 12 bits. Refill first if it
173 // might not be in the buffer yet (the longest code is 30
174 // bits), then decode it by walking DECODE_TABLE.
175 if bits < 30 && pos < len {
176 continue 'outer;
177 }
178 decode_code_slow(&mut acc, &mut bits, dst, &mut o)?;
179 continue;
180 }
181 let consumed = (entry >> 24) as usize;
182 dst[o] = entry as u8;
183 dst[o + 1] = (entry >> 8) as u8;
184 o += count as usize;
185 acc <<= consumed;
186 bits -= consumed;
187 }
188
189 if pos >= len {
190 break;
191 }
192 }
193
194 // Tail: the input is exhausted and fewer than 12 bits remain.
195 while bits > 0 {
196 // The encoder pads the last byte with up to 7 one-bits, which are
197 // valid only between symbols. Anything else must decode.
198 if bits < 8 && (acc >> (64 - bits)) == (1 << bits) - 1 {
199 break;
200 }
201 decode_code_slow(&mut acc, &mut bits, dst, &mut o)?;
202 }
203
204 buf.truncate(base_len + o);
205 Ok(buf.split())
206}
207
208#[cfg(test)]
209mod test {
210 use super::*;
211
212 use bytes::BufMut;
213 use rand::rngs::StdRng;
214 use rand::{Rng, SeedableRng};
215
216 fn decode(src: &[u8]) -> Result<BytesMut, DecoderError> {
217 let mut buf = BytesMut::new();
218 super::decode(src, &mut buf)
219 }
220
221 // The simplest decoder we can write, used to double-check the real
222 // one: turn the input into a literal string of '0'/'1' characters and
223 // repeatedly strip off the first code that matches. No code is a
224 // prefix of another, so at most one can match. EOS (index 256) is left
225 // out on purpose: encoded EOS is an error per RFC 7541 §5.2.
226 fn reference_decode(src: &[u8]) -> Result<BytesMut, DecoderError> {
227 // Each symbol's code as a string of '0' and '1', e.g. "11111000".
228 let codes: Vec<String> = ENCODE_CODES
229 .iter()
230 .zip(ENCODE_CODE_LENGTHS.iter())
231 .map(|(&code, &len)| format!("{code:0len$b}", len = len as usize))
232 .collect();
233 let bits: String = src.iter().map(|byte| format!("{byte:08b}")).collect();
234
235 let mut decoded = BytesMut::new();
236 let mut remaining_bits: &str = &bits;
237 while let Some(sym) = (0..256).find(|&sym| remaining_bits.starts_with(&codes[sym])) {
238 decoded.put_u8(sym as u8);
239 remaining_bits = &remaining_bits[codes[sym].len()..];
240 }
241 // We expect anything that cannot be matched to be padding. Padding is
242 // fewer than 8 bits, and all ones.
243 if remaining_bits.len() >= 8 || remaining_bits.chars().any(|bit| bit == '0') {
244 return Err(DecoderError::InvalidHuffmanCode);
245 }
246 Ok(decoded)
247 }
248
249 #[test]
250 fn decode_single_byte() {
251 assert_eq!("o", decode(&[0b00111111]).unwrap());
252 assert_eq!("0", decode(&[7]).unwrap());
253 assert_eq!("A", decode(&[(0x21 << 2) + 3]).unwrap());
254 }
255
256 #[test]
257 fn single_char_multi_byte() {
258 assert_eq!("#", decode(&[255, 160 + 15]).unwrap());
259 assert_eq!("$", decode(&[255, 200 + 7]).unwrap());
260 assert_eq!("\x0a", decode(&[255, 255, 255, 240 + 3]).unwrap());
261 }
262
263 #[test]
264 fn multi_char() {
265 assert_eq!("!0", decode(&[254, 1]).unwrap());
266 assert_eq!(" !", decode(&[0b01010011, 0b11111000]).unwrap());
267 }
268
269 // Random (mostly invalid) byte strings must produce identical results to reference impl
270 #[test]
271 fn matches_reference_on_arbitrary_bytes() {
272 let mut rng = StdRng::seed_from_u64(0xdeadbeefcafe);
273
274 for _ in 0..10_000 {
275 let len = rng.gen_range(0..40);
276 let src: Vec<u8> = (0..len).map(|_| rng.gen()).collect();
277 assert_eq!(reference_decode(&src), decode(&src), "src={:?}", src);
278 }
279
280 // Bias toward high bytes to exercise long codes and EOS prefixes.
281 for _ in 0..10_000 {
282 let len = rng.gen_range(0..40);
283 let src: Vec<u8> = (0..len).map(|_| rng.gen::<u8>() | 0xe0).collect();
284 assert_eq!(reference_decode(&src), decode(&src), "src={:?}", src);
285 }
286 }
287
288 #[test]
289 fn rejects_eos_and_invalid_padding() {
290 assert_eq!(decode(&[0xff]), Err(DecoderError::InvalidHuffmanCode));
291 assert_eq!(
292 decode(&[0xff, 0xff, 0xff, 0xff]),
293 Err(DecoderError::InvalidHuffmanCode)
294 );
295 assert_eq!(decode(&[0]), Err(DecoderError::InvalidHuffmanCode));
296 }
297}
298
299/*
300// uncomment to run benchmarks
301#[cfg(test)]
302mod bench {
303 extern crate test;
304
305 use self::test::{black_box, Bencher};
306 use super::*;
307
308 use crate::hpack::huffman::encode;
309
310 fn decode_input(b: &mut Bencher, input: &[u8]) {
311 let mut encoded = BytesMut::new();
312 encode(input, &mut encoded);
313
314 let mut scratch = BytesMut::with_capacity(input.len() * 2);
315 b.bytes = encoded.len() as u64;
316 b.iter(|| {
317 let decoded = decode(black_box(encoded.as_ref()), &mut scratch).unwrap();
318 black_box(decoded);
319 });
320 }
321
322 #[bench]
323 fn decode_short_ascii(b: &mut Bencher) {
324 decode_input(b, b"www.example.com");
325 }
326
327 #[bench]
328 fn decode_header_value(b: &mut Bencher) {
329 decode_input(
330 b,
331 b"text/html,application/xhtml+xml,application/xml;q=0.9;q=0.8",
332 );
333 }
334
335 #[bench]
336 fn decode_long_ascii(b: &mut Bencher) {
337 decode_input(
338 b,
339 b"Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:16.0) Gecko/20100101 Firefox/16.0",
340 );
341 }
342
343 #[bench]
344 fn decode_all_octets(b: &mut Bencher) {
345 let input: Vec<_> = (0..=u8::MAX).collect();
346 decode_input(b, &input);
347 }
348}
349*/