ntex_h2/hpack/
encoder.rs

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

ntex_h2/hpack/
encoder.rs
