h2/hpack/
encoder.rs

Help
1use super::table::{Index, Table};
2use super::{huffman, Header};
3
4use bytes::{BufMut, BytesMut};
5use http::header::{HeaderName, HeaderValue};
6
7#[derive(Debug)]
8pub struct Encoder {
9    table: Table,
10    size_update: Option<SizeUpdate>,
11}
12
13#[derive(Debug, Copy, Clone, Eq, PartialEq)]
14enum SizeUpdate {
15    One(usize),
16    Two(usize, usize), // min, max
17}
18
19impl Encoder {
20    pub fn new(max_size: usize, capacity: usize) -> Encoder {
21        Encoder {
22            table: Table::new(max_size, capacity),
23            size_update: None,
24        }
25    }
26
27    /// Queues a max size update.
28    ///
29    /// The next call to `encode` will include a dynamic size update frame.
30    pub fn update_max_size(&mut self, val: usize) {
31        match self.size_update {
32            Some(SizeUpdate::One(old)) => {
33                if val > old {
34                    if old > self.table.max_size() {
35                        self.size_update = Some(SizeUpdate::One(val));
36                    } else {
37                        self.size_update = Some(SizeUpdate::Two(old, val));
38                    }
39                } else {
40                    self.size_update = Some(SizeUpdate::One(val));
41                }
42            }
43            Some(SizeUpdate::Two(min, _)) => {
44                if val < min {
45                    self.size_update = Some(SizeUpdate::One(val));
46                } else {
47                    self.size_update = Some(SizeUpdate::Two(min, val));
48                }
49            }
50            None => {
51                if val != self.table.max_size() {
52                    // Don't bother writing a frame if the value already matches
53                    // the table's max size.
54                    self.size_update = Some(SizeUpdate::One(val));
55                }
56            }
57        }
58    }
59
60    /// Encode a set of headers into the provide buffer
61    pub fn encode<I>(&mut self, headers: I, dst: &mut BytesMut)
62    where
63        I: IntoIterator<Item = Header<Option<HeaderName>>>,
64    {
65        let span = tracing::trace_span!("hpack::encode");
66        let _e = span.enter();
67
68        self.encode_size_updates(dst);
69
70        let mut last_index = None;
71
72        for header in headers {
73            match header.reify() {
74                // The header has an associated name. In which case, try to
75                // index it in the table.
76                Ok(header) => {
77                    let index = self.table.index(header);
78                    self.encode_header(&index, dst);
79
80                    last_index = Some(index);
81                }
82                // The header does not have an associated name. This means that
83                // the name is the same as the previously yielded header. In
84                // which case, we skip table lookup and just use the same index
85                // as the previous entry.
86                Err(value) => {
87                    self.encode_header_without_name(
88                        last_index.as_ref().unwrap_or_else(|| {
89                            panic!("encoding header without name, but no previous index to use for name");
90                        }),
91                        &value,
92                        dst,
93                    );
94                }
95            }
96        }
97    }
98
99    fn encode_size_updates(&mut self, dst: &mut BytesMut) {
100        match self.size_update.take() {
101            Some(SizeUpdate::One(val)) => {
102                self.table.resize(val);
103                encode_size_update(val, dst);
104            }
105            Some(SizeUpdate::Two(min, max)) => {
106                self.table.resize(min);
107                self.table.resize(max);
108                encode_size_update(min, dst);
109                encode_size_update(max, dst);
110            }
111            None => {}
112        }
113    }
114
115    fn encode_header(&mut self, index: &Index, dst: &mut BytesMut) {
116        match *index {
117            Index::Indexed(idx, _) => {
118                encode_int(idx, 7, 0x80, dst);
119            }
120            Index::Name(idx, _) => {
121                let header = self.table.resolve(index);
122
123                encode_not_indexed(idx, header.value_slice(), header.is_sensitive(), dst);
124            }
125            Index::Inserted(_) => {
126                let header = self.table.resolve(index);
127
128                assert!(!header.is_sensitive());
129
130                dst.put_u8(0b0100_0000);
131
132                encode_str(header.name().as_slice(), dst);
133                encode_str(header.value_slice(), dst);
134            }
135            Index::InsertedValue(idx, _) => {
136                let header = self.table.resolve(index);
137
138                assert!(!header.is_sensitive());
139
140                encode_int(idx, 6, 0b0100_0000, dst);
141                encode_str(header.value_slice(), dst);
142            }
143            Index::NotIndexed(_) => {
144                let header = self.table.resolve(index);
145
146                encode_not_indexed2(
147                    header.name().as_slice(),
148                    header.value_slice(),
149                    header.is_sensitive(),
150                    dst,
151                );
152            }
153        }
154    }
155
156    fn encode_header_without_name(
157        &mut self,
158        last: &Index,
159        value: &HeaderValue,
160        dst: &mut BytesMut,
161    ) {
162        match *last {
163            Index::Indexed(..)
164            | Index::Name(..)
165            | Index::Inserted(..)
166            | Index::InsertedValue(..) => {
167                let idx = self.table.resolve_idx(last);
168
169                encode_not_indexed(idx, value.as_ref(), value.is_sensitive(), dst);
170            }
171            Index::NotIndexed(_) => {
172                let last = self.table.resolve(last);
173
174                encode_not_indexed2(
175                    last.name().as_slice(),
176                    value.as_ref(),
177                    value.is_sensitive(),
178                    dst,
179                );
180            }
181        }
182    }
183}
184
185impl Default for Encoder {
186    fn default() -> Encoder {
187        Encoder::new(4096, 0)
188    }
189}
190
191fn encode_size_update(val: usize, dst: &mut BytesMut) {
192    encode_int(val, 5, 0b0010_0000, dst)
193}
194
195fn encode_not_indexed(name: usize, value: &[u8], sensitive: bool, dst: &mut BytesMut) {
196    if sensitive {
197        encode_int(name, 4, 0b10000, dst);
198    } else {
199        encode_int(name, 4, 0, dst);
200    }
201
202    encode_str(value, dst);
203}
204
205fn encode_not_indexed2(name: &[u8], value: &[u8], sensitive: bool, dst: &mut BytesMut) {
206    if sensitive {
207        dst.put_u8(0b10000);
208    } else {
209        dst.put_u8(0);
210    }
211
212    encode_str(name, dst);
213    encode_str(value, dst);
214}
215
216fn encode_str(val: &[u8], dst: &mut BytesMut) {
217    if !val.is_empty() {
218        let idx = position(dst);
219
220        // Push a placeholder byte for the length header
221        dst.put_u8(0);
222
223        // Encode with huffman
224        huffman::encode(val, dst);
225
226        let huff_len = position(dst) - (idx + 1);
227
228        if encode_int_one_byte(huff_len, 7) {
229            // Write the string head
230            dst[idx] = 0x80 | huff_len as u8;
231        } else {
232            // Write the head to a placeholder
233            const PLACEHOLDER_LEN: usize = 8;
234            let mut buf = [0u8; PLACEHOLDER_LEN];
235
236            let head_len = {
237                let mut head_dst = &mut buf[..];
238                encode_int(huff_len, 7, 0x80, &mut head_dst);
239                PLACEHOLDER_LEN - head_dst.remaining_mut()
240            };
241
242            // This is just done to reserve space in the destination
243            dst.put_slice(&buf[1..head_len]);
244
245            // Shift the header forward
246            for i in 0..huff_len {
247                let src_i = idx + 1 + (huff_len - (i + 1));
248                let dst_i = idx + head_len + (huff_len - (i + 1));
249                dst[dst_i] = dst[src_i];
250            }
251
252            // Copy in the head
253            for i in 0..head_len {
254                dst[idx + i] = buf[i];
255            }
256        }
257    } else {
258        // Write an empty string
259        dst.put_u8(0);
260    }
261}
262
263/// Encode an integer into the given destination buffer
264fn encode_int<B: BufMut>(
265    mut value: usize,   // The integer to encode
266    prefix_bits: usize, // The number of bits in the prefix
267    first_byte: u8,     // The base upon which to start encoding the int
268    dst: &mut B,
269) {
270    if encode_int_one_byte(value, prefix_bits) {
271        dst.put_u8(first_byte | value as u8);
272        return;
273    }
274
275    let low = (1 << prefix_bits) - 1;
276
277    value -= low;
278
279    dst.put_u8(first_byte | low as u8);
280
281    while value >= 128 {
282        dst.put_u8(0b1000_0000 | value as u8);
283
284        value >>= 7;
285    }
286
287    dst.put_u8(value as u8);
288}
289
290/// Returns true if the in the int can be fully encoded in the first byte.
291fn encode_int_one_byte(value: usize, prefix_bits: usize) -> bool {
292    value < (1 << prefix_bits) - 1
293}
294
295fn position(buf: &BytesMut) -> usize {
296    buf.len()
297}
298
299#[cfg(test)]
300mod test {
301    use super::*;
302    use http::*;
303
304    #[test]
305    fn test_encode_method_get() {
306        let mut encoder = Encoder::default();
307        let res = encode(&mut encoder, vec![method("GET")]);
308        assert_eq!(*res, [0x80 | 2]);
309        assert_eq!(encoder.table.len(), 0);
310    }
311
312    #[test]
313    fn test_encode_method_post() {
314        let mut encoder = Encoder::default();
315        let res = encode(&mut encoder, vec![method("POST")]);
316        assert_eq!(*res, [0x80 | 3]);
317        assert_eq!(encoder.table.len(), 0);
318    }
319
320    #[test]
321    fn test_encode_method_patch() {
322        let mut encoder = Encoder::default();
323        let res = encode(&mut encoder, vec![method("PATCH")]);
324
325        assert_eq!(res[0], 0b01000000 | 2); // Incremental indexing w/ name pulled from table
326        assert_eq!(res[1], 0x80 | 5); // header value w/ huffman coding
327
328        assert_eq!("PATCH", huff_decode(&res[2..7]));
329        assert_eq!(encoder.table.len(), 1);
330
331        let res = encode(&mut encoder, vec![method("PATCH")]);
332
333        assert_eq!(1 << 7 | 62, res[0]);
334        assert_eq!(1, res.len());
335    }
336
337    #[test]
338    fn test_encode_indexed_name_literal_value() {
339        let mut encoder = Encoder::default();
340        let res = encode(&mut encoder, vec![header("content-language", "foo")]);
341
342        assert_eq!(res[0], 0b01000000 | 27); // Indexed name
343        assert_eq!(res[1], 0x80 | 2); // header value w/ huffman coding
344
345        assert_eq!("foo", huff_decode(&res[2..4]));
346
347        // Same name, new value should still use incremental
348        let res = encode(&mut encoder, vec![header("content-language", "bar")]);
349        assert_eq!(res[0], 0b01000000 | 27); // Indexed name
350        assert_eq!(res[1], 0x80 | 3); // header value w/ huffman coding
351        assert_eq!("bar", huff_decode(&res[2..5]));
352    }
353
354    #[test]
355    fn test_repeated_headers_are_indexed() {
356        let mut encoder = Encoder::default();
357        let res = encode(&mut encoder, vec![header("foo", "hello")]);
358
359        assert_eq!(&[0b01000000, 0x80 | 2], &res[0..2]);
360        assert_eq!("foo", huff_decode(&res[2..4]));
361        assert_eq!(0x80 | 4, res[4]);
362        assert_eq!("hello", huff_decode(&res[5..]));
363        assert_eq!(9, res.len());
364
365        assert_eq!(1, encoder.table.len());
366
367        let res = encode(&mut encoder, vec![header("foo", "hello")]);
368        assert_eq!([0x80 | 62], *res);
369
370        assert_eq!(encoder.table.len(), 1);
371    }
372
373    #[test]
374    fn test_evicting_headers() {
375        let mut encoder = Encoder::default();
376
377        // Fill the table
378        for i in 0..64 {
379            let key = format!("x-hello-world-{:02}", i);
380            let res = encode(&mut encoder, vec![header(&key, &key)]);
381
382            assert_eq!(&[0b01000000, 0x80 | 12], &res[0..2]);
383            assert_eq!(key, huff_decode(&res[2..14]));
384            assert_eq!(0x80 | 12, res[14]);
385            assert_eq!(key, huff_decode(&res[15..]));
386            assert_eq!(27, res.len());
387
388            // Make sure the header can be found...
389            let res = encode(&mut encoder, vec![header(&key, &key)]);
390
391            // Only check that it is found
392            assert_eq!(0x80, res[0] & 0x80);
393        }
394
395        assert_eq!(4096, encoder.table.size());
396        assert_eq!(64, encoder.table.len());
397
398        // Find existing headers
399        for i in 0..64 {
400            let key = format!("x-hello-world-{:02}", i);
401            let res = encode(&mut encoder, vec![header(&key, &key)]);
402            assert_eq!(0x80, res[0] & 0x80);
403        }
404
405        // Insert a new header
406        let key = "x-hello-world-64";
407        let res = encode(&mut encoder, vec![header(key, key)]);
408
409        assert_eq!(&[0b01000000, 0x80 | 12], &res[0..2]);
410        assert_eq!(key, huff_decode(&res[2..14]));
411        assert_eq!(0x80 | 12, res[14]);
412        assert_eq!(key, huff_decode(&res[15..]));
413        assert_eq!(27, res.len());
414
415        assert_eq!(64, encoder.table.len());
416
417        // Now try encoding entries that should exist in the table
418        for i in 1..65 {
419            let key = format!("x-hello-world-{:02}", i);
420            let res = encode(&mut encoder, vec![header(&key, &key)]);
421            assert_eq!(0x80 | (61 + (65 - i)), res[0]);
422        }
423    }
424
425    #[test]
426    fn test_large_headers_are_not_indexed() {
427        let mut encoder = Encoder::new(128, 0);
428        let key = "hello-world-hello-world-HELLO-zzz";
429
430        let res = encode(&mut encoder, vec![header(key, key)]);
431
432        assert_eq!(&[0, 0x80 | 25], &res[..2]);
433
434        assert_eq!(0, encoder.table.len());
435        assert_eq!(0, encoder.table.size());
436    }
437
438    #[test]
439    fn test_sensitive_headers_are_never_indexed() {
440        use http::header::HeaderValue;
441
442        let name = "my-password".parse().unwrap();
443        let mut value = HeaderValue::from_bytes(b"12345").unwrap();
444        value.set_sensitive(true);
445
446        let header = Header::Field {
447            name: Some(name),
448            value,
449        };
450
451        // Now, try to encode the sensitive header
452
453        let mut encoder = Encoder::default();
454        let res = encode(&mut encoder, vec![header]);
455
456        assert_eq!(&[0b10000, 0x80 | 8], &res[..2]);
457        assert_eq!("my-password", huff_decode(&res[2..10]));
458        assert_eq!(0x80 | 4, res[10]);
459        assert_eq!("12345", huff_decode(&res[11..]));
460
461        // Now, try to encode a sensitive header w/ a name in the static table
462        let name = "authorization".parse().unwrap();
463        let mut value = HeaderValue::from_bytes(b"12345").unwrap();
464        value.set_sensitive(true);
465
466        let header = Header::Field {
467            name: Some(name),
468            value,
469        };
470
471        let mut encoder = Encoder::default();
472        let res = encode(&mut encoder, vec![header]);
473
474        assert_eq!(&[0b11111, 8], &res[..2]);
475        assert_eq!(0x80 | 4, res[2]);
476        assert_eq!("12345", huff_decode(&res[3..]));
477
478        // Using the name component of a previously indexed header (without
479        // sensitive flag set)
480
481        let _ = encode(
482            &mut encoder,
483            vec![self::header("my-password", "not-so-secret")],
484        );
485
486        let name = "my-password".parse().unwrap();
487        let mut value = HeaderValue::from_bytes(b"12345").unwrap();
488        value.set_sensitive(true);
489
490        let header = Header::Field {
491            name: Some(name),
492            value,
493        };
494        let res = encode(&mut encoder, vec![header]);
495
496        assert_eq!(&[0b11111, 47], &res[..2]);
497        assert_eq!(0x80 | 4, res[2]);
498        assert_eq!("12345", huff_decode(&res[3..]));
499    }
500
501    #[test]
502    fn test_content_length_value_not_indexed() {
503        let mut encoder = Encoder::default();
504        let res = encode(&mut encoder, vec![header("content-length", "1234")]);
505
506        assert_eq!(&[15, 13, 0x80 | 3], &res[0..3]);
507        assert_eq!("1234", huff_decode(&res[3..]));
508        assert_eq!(6, res.len());
509    }
510
511    #[test]
512    fn test_encoding_headers_with_same_name() {
513        let mut encoder = Encoder::default();
514        let name = "hello";
515
516        // Encode first one
517        let _ = encode(&mut encoder, vec![header(name, "one")]);
518
519        // Encode second one
520        let res = encode(&mut encoder, vec![header(name, "two")]);
521        assert_eq!(&[0x40 | 62, 0x80 | 3], &res[0..2]);
522        assert_eq!("two", huff_decode(&res[2..]));
523        assert_eq!(5, res.len());
524
525        // Encode the first one again
526        let res = encode(&mut encoder, vec![header(name, "one")]);
527        assert_eq!(&[0x80 | 63], &res[..]);
528
529        // Now the second one
530        let res = encode(&mut encoder, vec![header(name, "two")]);
531        assert_eq!(&[0x80 | 62], &res[..]);
532    }
533
534    #[test]
535    fn test_evicting_headers_when_multiple_of_same_name_are_in_table() {
536        // The encoder only has space for 2 headers
537        let mut encoder = Encoder::new(76, 0);
538
539        let _ = encode(&mut encoder, vec![header("foo", "bar")]);
540        assert_eq!(1, encoder.table.len());
541
542        let _ = encode(&mut encoder, vec![header("bar", "foo")]);
543        assert_eq!(2, encoder.table.len());
544
545        // This will evict the first header, while still referencing the header
546        // name
547        let res = encode(&mut encoder, vec![header("foo", "baz")]);
548        assert_eq!(&[0x40 | 63, 0, 0x80 | 3], &res[..3]);
549        assert_eq!(2, encoder.table.len());
550
551        // Try adding the same header again
552        let res = encode(&mut encoder, vec![header("foo", "baz")]);
553        assert_eq!(&[0x80 | 62], &res[..]);
554        assert_eq!(2, encoder.table.len());
555    }
556
557    #[test]
558    fn test_max_size_zero() {
559        // Static table only
560        let mut encoder = Encoder::new(0, 0);
561        let res = encode(&mut encoder, vec![method("GET")]);
562        assert_eq!(*res, [0x80 | 2]);
563        assert_eq!(encoder.table.len(), 0);
564
565        let res = encode(&mut encoder, vec![header("foo", "bar")]);
566        assert_eq!(&[0, 0x80 | 2], &res[..2]);
567        assert_eq!("foo", huff_decode(&res[2..4]));
568        assert_eq!(0x80 | 3, res[4]);
569        assert_eq!("bar", huff_decode(&res[5..8]));
570        assert_eq!(0, encoder.table.len());
571
572        // Encode a custom value
573        let res = encode(&mut encoder, vec![header("transfer-encoding", "chunked")]);
574        assert_eq!(&[15, 42, 0x80 | 6], &res[..3]);
575        assert_eq!("chunked", huff_decode(&res[3..]));
576    }
577
578    #[test]
579    fn test_update_max_size_combos() {
580        let mut encoder = Encoder::default();
581        assert!(encoder.size_update.is_none());
582        assert_eq!(4096, encoder.table.max_size());
583
584        encoder.update_max_size(4096); // Default size
585        assert!(encoder.size_update.is_none());
586
587        encoder.update_max_size(0);
588        assert_eq!(Some(SizeUpdate::One(0)), encoder.size_update);
589
590        encoder.update_max_size(100);
591        assert_eq!(Some(SizeUpdate::Two(0, 100)), encoder.size_update);
592
593        let mut encoder = Encoder::default();
594        encoder.update_max_size(8000);
595        assert_eq!(Some(SizeUpdate::One(8000)), encoder.size_update);
596
597        encoder.update_max_size(100);
598        assert_eq!(Some(SizeUpdate::One(100)), encoder.size_update);
599
600        encoder.update_max_size(8000);
601        assert_eq!(Some(SizeUpdate::Two(100, 8000)), encoder.size_update);
602
603        encoder.update_max_size(4000);
604        assert_eq!(Some(SizeUpdate::Two(100, 4000)), encoder.size_update);
605
606        encoder.update_max_size(50);
607        assert_eq!(Some(SizeUpdate::One(50)), encoder.size_update);
608    }
609
610    #[test]
611    fn test_resizing_table() {
612        let mut encoder = Encoder::default();
613
614        // Add a header
615        let _ = encode(&mut encoder, vec![header("foo", "bar")]);
616
617        encoder.update_max_size(1);
618        assert_eq!(1, encoder.table.len());
619
620        let res = encode(&mut encoder, vec![method("GET")]);
621        assert_eq!(&[32 | 1, 0x80 | 2], &res[..]);
622        assert_eq!(0, encoder.table.len());
623
624        let res = encode(&mut encoder, vec![header("foo", "bar")]);
625        assert_eq!(0, res[0]);
626
627        encoder.update_max_size(100);
628        let res = encode(&mut encoder, vec![header("foo", "bar")]);
629        assert_eq!(&[32 | 31, 69, 64], &res[..3]);
630
631        encoder.update_max_size(0);
632        let res = encode(&mut encoder, vec![header("foo", "bar")]);
633        assert_eq!(&[32, 0], &res[..2]);
634    }
635
636    #[test]
637    fn test_decreasing_table_size_without_eviction() {
638        let mut encoder = Encoder::default();
639
640        // Add a header
641        let _ = encode(&mut encoder, vec![header("foo", "bar")]);
642
643        encoder.update_max_size(100);
644        assert_eq!(1, encoder.table.len());
645
646        let res = encode(&mut encoder, vec![header("foo", "bar")]);
647        assert_eq!(&[32 | 31, 69, 0x80 | 62], &res[..]);
648    }
649
650    #[test]
651    fn test_nameless_header() {
652        let mut encoder = Encoder::default();
653
654        let res = encode(
655            &mut encoder,
656            vec![
657                Header::Field {
658                    name: Some("hello".parse().unwrap()),
659                    value: HeaderValue::from_bytes(b"world").unwrap(),
660                },
661                Header::Field {
662                    name: None,
663                    value: HeaderValue::from_bytes(b"zomg").unwrap(),
664                },
665            ],
666        );
667
668        assert_eq!(&[0x40, 0x80 | 4], &res[0..2]);
669        assert_eq!("hello", huff_decode(&res[2..6]));
670        assert_eq!(0x80 | 4, res[6]);
671        assert_eq!("world", huff_decode(&res[7..11]));
672
673        // Next is not indexed
674        assert_eq!(&[15, 47, 0x80 | 3], &res[11..14]);
675        assert_eq!("zomg", huff_decode(&res[14..]));
676    }
677
678    #[test]
679    fn test_large_size_update() {
680        let mut encoder = Encoder::default();
681
682        encoder.update_max_size(1912930560);
683        assert_eq!(Some(SizeUpdate::One(1912930560)), encoder.size_update);
684
685        let mut dst = BytesMut::with_capacity(6);
686        encoder.encode_size_updates(&mut dst);
687        assert_eq!([63, 225, 129, 148, 144, 7], &dst[..]);
688    }
689
690    #[test]
691    #[ignore]
692    fn test_evicted_overflow() {
693        // Not sure what the best way to do this is.
694    }
695
696    fn encode(e: &mut Encoder, hdrs: Vec<Header<Option<HeaderName>>>) -> BytesMut {
697        let mut dst = BytesMut::with_capacity(1024);
698        e.encode(&mut hdrs.into_iter(), &mut dst);
699        dst
700    }
701
702    fn method(s: &str) -> Header<Option<HeaderName>> {
703        Header::Method(Method::from_bytes(s.as_bytes()).unwrap())
704    }
705
706    fn header(name: &str, val: &str) -> Header<Option<HeaderName>> {
707        let name = HeaderName::from_bytes(name.as_bytes()).unwrap();
708        let value = HeaderValue::from_bytes(val.as_bytes()).unwrap();
709
710        Header::Field {
711            name: Some(name),
712            value,
713        }
714    }
715
716    fn huff_decode(src: &[u8]) -> BytesMut {
717        let mut buf = BytesMut::new();
718        huffman::decode(src, &mut buf).unwrap()
719    }
720}
h2/hpack/encoder.rs

h2/hpack/
encoder.rs
