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(max_size:4096, capacity:0)
188 }
189}
190
191fn encode_size_update(val: usize, dst: &mut BytesMut) {
192 encode_int(value:val, prefix_bits:5, first_byte:0b0010_0000, dst)
193}
194
195fn encode_not_indexed(name: usize, value: &[u8], sensitive: bool, dst: &mut BytesMut) {
196 if sensitive {
197 encode_int(value:name, prefix_bits:4, first_byte:0b10000, dst);
198 } else {
199 encode_int(value:name, prefix_bits:4, first_byte:0, dst);
200 }
201
202 encode_str(val: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(val:name, dst);
213 encode_str(val: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: usize = (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 crate::hpack::Header;
303 use http::*;
304
305 #[test]
306 fn test_encode_method_get() {
307 let mut encoder = Encoder::default();
308 let res = encode(&mut encoder, vec![method("GET")]);
309 assert_eq!(*res, [0x80 | 2]);
310 assert_eq!(encoder.table.len(), 0);
311 }
312
313 #[test]
314 fn test_encode_method_post() {
315 let mut encoder = Encoder::default();
316 let res = encode(&mut encoder, vec![method("POST")]);
317 assert_eq!(*res, [0x80 | 3]);
318 assert_eq!(encoder.table.len(), 0);
319 }
320
321 #[test]
322 fn test_encode_method_patch() {
323 let mut encoder = Encoder::default();
324 let res = encode(&mut encoder, vec![method("PATCH")]);
325
326 assert_eq!(res[0], 0b01000000 | 2); // Incremental indexing w/ name pulled from table
327 assert_eq!(res[1], 0x80 | 5); // header value w/ huffman coding
328
329 assert_eq!("PATCH", huff_decode(&res[2..7]));
330 assert_eq!(encoder.table.len(), 1);
331
332 let res = encode(&mut encoder, vec![method("PATCH")]);
333
334 assert_eq!(1 << 7 | 62, res[0]);
335 assert_eq!(1, res.len());
336 }
337
338 #[test]
339 fn test_encode_indexed_name_literal_value() {
340 let mut encoder = Encoder::default();
341 let res = encode(&mut encoder, vec![header("content-language", "foo")]);
342
343 assert_eq!(res[0], 0b01000000 | 27); // Indexed name
344 assert_eq!(res[1], 0x80 | 2); // header value w/ huffman coding
345
346 assert_eq!("foo", huff_decode(&res[2..4]));
347
348 // Same name, new value should still use incremental
349 let res = encode(&mut encoder, vec![header("content-language", "bar")]);
350 assert_eq!(res[0], 0b01000000 | 27); // Indexed name
351 assert_eq!(res[1], 0x80 | 3); // header value w/ huffman coding
352 assert_eq!("bar", huff_decode(&res[2..5]));
353 }
354
355 #[test]
356 fn test_repeated_headers_are_indexed() {
357 let mut encoder = Encoder::default();
358 let res = encode(&mut encoder, vec![header("foo", "hello")]);
359
360 assert_eq!(&[0b01000000, 0x80 | 2], &res[0..2]);
361 assert_eq!("foo", huff_decode(&res[2..4]));
362 assert_eq!(0x80 | 4, res[4]);
363 assert_eq!("hello", huff_decode(&res[5..]));
364 assert_eq!(9, res.len());
365
366 assert_eq!(1, encoder.table.len());
367
368 let res = encode(&mut encoder, vec![header("foo", "hello")]);
369 assert_eq!([0x80 | 62], *res);
370
371 assert_eq!(encoder.table.len(), 1);
372 }
373
374 #[test]
375 fn test_evicting_headers() {
376 let mut encoder = Encoder::default();
377
378 // Fill the table
379 for i in 0..64 {
380 let key = format!("x-hello-world-{:02}", i);
381 let res = encode(&mut encoder, vec![header(&key, &key)]);
382
383 assert_eq!(&[0b01000000, 0x80 | 12], &res[0..2]);
384 assert_eq!(key, huff_decode(&res[2..14]));
385 assert_eq!(0x80 | 12, res[14]);
386 assert_eq!(key, huff_decode(&res[15..]));
387 assert_eq!(27, res.len());
388
389 // Make sure the header can be found...
390 let res = encode(&mut encoder, vec![header(&key, &key)]);
391
392 // Only check that it is found
393 assert_eq!(0x80, res[0] & 0x80);
394 }
395
396 assert_eq!(4096, encoder.table.size());
397 assert_eq!(64, encoder.table.len());
398
399 // Find existing headers
400 for i in 0..64 {
401 let key = format!("x-hello-world-{:02}", i);
402 let res = encode(&mut encoder, vec![header(&key, &key)]);
403 assert_eq!(0x80, res[0] & 0x80);
404 }
405
406 // Insert a new header
407 let key = "x-hello-world-64";
408 let res = encode(&mut encoder, vec![header(key, key)]);
409
410 assert_eq!(&[0b01000000, 0x80 | 12], &res[0..2]);
411 assert_eq!(key, huff_decode(&res[2..14]));
412 assert_eq!(0x80 | 12, res[14]);
413 assert_eq!(key, huff_decode(&res[15..]));
414 assert_eq!(27, res.len());
415
416 assert_eq!(64, encoder.table.len());
417
418 // Now try encoding entries that should exist in the table
419 for i in 1..65 {
420 let key = format!("x-hello-world-{:02}", i);
421 let res = encode(&mut encoder, vec![header(&key, &key)]);
422 assert_eq!(0x80 | (61 + (65 - i)), res[0]);
423 }
424 }
425
426 #[test]
427 fn test_large_headers_are_not_indexed() {
428 let mut encoder = Encoder::new(128, 0);
429 let key = "hello-world-hello-world-HELLO-zzz";
430
431 let res = encode(&mut encoder, vec![header(key, key)]);
432
433 assert_eq!(&[0, 0x80 | 25], &res[..2]);
434
435 assert_eq!(0, encoder.table.len());
436 assert_eq!(0, encoder.table.size());
437 }
438
439 #[test]
440 fn test_sensitive_headers_are_never_indexed() {
441 use http::header::HeaderValue;
442
443 let name = "my-password".parse().unwrap();
444 let mut value = HeaderValue::from_bytes(b"12345").unwrap();
445 value.set_sensitive(true);
446
447 let header = Header::Field {
448 name: Some(name),
449 value,
450 };
451
452 // Now, try to encode the sensitive header
453
454 let mut encoder = Encoder::default();
455 let res = encode(&mut encoder, vec![header]);
456
457 assert_eq!(&[0b10000, 0x80 | 8], &res[..2]);
458 assert_eq!("my-password", huff_decode(&res[2..10]));
459 assert_eq!(0x80 | 4, res[10]);
460 assert_eq!("12345", huff_decode(&res[11..]));
461
462 // Now, try to encode a sensitive header w/ a name in the static table
463 let name = "authorization".parse().unwrap();
464 let mut value = HeaderValue::from_bytes(b"12345").unwrap();
465 value.set_sensitive(true);
466
467 let header = Header::Field {
468 name: Some(name),
469 value,
470 };
471
472 let mut encoder = Encoder::default();
473 let res = encode(&mut encoder, vec![header]);
474
475 assert_eq!(&[0b11111, 8], &res[..2]);
476 assert_eq!(0x80 | 4, res[2]);
477 assert_eq!("12345", huff_decode(&res[3..]));
478
479 // Using the name component of a previously indexed header (without
480 // sensitive flag set)
481
482 let _ = encode(
483 &mut encoder,
484 vec![self::header("my-password", "not-so-secret")],
485 );
486
487 let name = "my-password".parse().unwrap();
488 let mut value = HeaderValue::from_bytes(b"12345").unwrap();
489 value.set_sensitive(true);
490
491 let header = Header::Field {
492 name: Some(name),
493 value,
494 };
495 let res = encode(&mut encoder, vec![header]);
496
497 assert_eq!(&[0b11111, 47], &res[..2]);
498 assert_eq!(0x80 | 4, res[2]);
499 assert_eq!("12345", huff_decode(&res[3..]));
500 }
501
502 #[test]
503 fn test_content_length_value_not_indexed() {
504 let mut encoder = Encoder::default();
505 let res = encode(&mut encoder, vec![header("content-length", "1234")]);
506
507 assert_eq!(&[15, 13, 0x80 | 3], &res[0..3]);
508 assert_eq!("1234", huff_decode(&res[3..]));
509 assert_eq!(6, res.len());
510 }
511
512 #[test]
513 fn test_encoding_headers_with_same_name() {
514 let mut encoder = Encoder::default();
515 let name = "hello";
516
517 // Encode first one
518 let _ = encode(&mut encoder, vec![header(name, "one")]);
519
520 // Encode second one
521 let res = encode(&mut encoder, vec![header(name, "two")]);
522 assert_eq!(&[0x40 | 62, 0x80 | 3], &res[0..2]);
523 assert_eq!("two", huff_decode(&res[2..]));
524 assert_eq!(5, res.len());
525
526 // Encode the first one again
527 let res = encode(&mut encoder, vec![header(name, "one")]);
528 assert_eq!(&[0x80 | 63], &res[..]);
529
530 // Now the second one
531 let res = encode(&mut encoder, vec![header(name, "two")]);
532 assert_eq!(&[0x80 | 62], &res[..]);
533 }
534
535 #[test]
536 fn test_evicting_headers_when_multiple_of_same_name_are_in_table() {
537 // The encoder only has space for 2 headers
538 let mut encoder = Encoder::new(76, 0);
539
540 let _ = encode(&mut encoder, vec![header("foo", "bar")]);
541 assert_eq!(1, encoder.table.len());
542
543 let _ = encode(&mut encoder, vec![header("bar", "foo")]);
544 assert_eq!(2, encoder.table.len());
545
546 // This will evict the first header, while still referencing the header
547 // name
548 let res = encode(&mut encoder, vec![header("foo", "baz")]);
549 assert_eq!(&[0x40 | 63, 0, 0x80 | 3], &res[..3]);
550 assert_eq!(2, encoder.table.len());
551
552 // Try adding the same header again
553 let res = encode(&mut encoder, vec![header("foo", "baz")]);
554 assert_eq!(&[0x80 | 62], &res[..]);
555 assert_eq!(2, encoder.table.len());
556 }
557
558 #[test]
559 fn test_max_size_zero() {
560 // Static table only
561 let mut encoder = Encoder::new(0, 0);
562 let res = encode(&mut encoder, vec![method("GET")]);
563 assert_eq!(*res, [0x80 | 2]);
564 assert_eq!(encoder.table.len(), 0);
565
566 let res = encode(&mut encoder, vec![header("foo", "bar")]);
567 assert_eq!(&[0, 0x80 | 2], &res[..2]);
568 assert_eq!("foo", huff_decode(&res[2..4]));
569 assert_eq!(0x80 | 3, res[4]);
570 assert_eq!("bar", huff_decode(&res[5..8]));
571 assert_eq!(0, encoder.table.len());
572
573 // Encode a custom value
574 let res = encode(&mut encoder, vec![header("transfer-encoding", "chunked")]);
575 assert_eq!(&[15, 42, 0x80 | 6], &res[..3]);
576 assert_eq!("chunked", huff_decode(&res[3..]));
577 }
578
579 #[test]
580 fn test_update_max_size_combos() {
581 let mut encoder = Encoder::default();
582 assert!(encoder.size_update.is_none());
583 assert_eq!(4096, encoder.table.max_size());
584
585 encoder.update_max_size(4096); // Default size
586 assert!(encoder.size_update.is_none());
587
588 encoder.update_max_size(0);
589 assert_eq!(Some(SizeUpdate::One(0)), encoder.size_update);
590
591 encoder.update_max_size(100);
592 assert_eq!(Some(SizeUpdate::Two(0, 100)), encoder.size_update);
593
594 let mut encoder = Encoder::default();
595 encoder.update_max_size(8000);
596 assert_eq!(Some(SizeUpdate::One(8000)), encoder.size_update);
597
598 encoder.update_max_size(100);
599 assert_eq!(Some(SizeUpdate::One(100)), encoder.size_update);
600
601 encoder.update_max_size(8000);
602 assert_eq!(Some(SizeUpdate::Two(100, 8000)), encoder.size_update);
603
604 encoder.update_max_size(4000);
605 assert_eq!(Some(SizeUpdate::Two(100, 4000)), encoder.size_update);
606
607 encoder.update_max_size(50);
608 assert_eq!(Some(SizeUpdate::One(50)), encoder.size_update);
609 }
610
611 #[test]
612 fn test_resizing_table() {
613 let mut encoder = Encoder::default();
614
615 // Add a header
616 let _ = encode(&mut encoder, vec![header("foo", "bar")]);
617
618 encoder.update_max_size(1);
619 assert_eq!(1, encoder.table.len());
620
621 let res = encode(&mut encoder, vec![method("GET")]);
622 assert_eq!(&[32 | 1, 0x80 | 2], &res[..]);
623 assert_eq!(0, encoder.table.len());
624
625 let res = encode(&mut encoder, vec![header("foo", "bar")]);
626 assert_eq!(0, res[0]);
627
628 encoder.update_max_size(100);
629 let res = encode(&mut encoder, vec![header("foo", "bar")]);
630 assert_eq!(&[32 | 31, 69, 64], &res[..3]);
631
632 encoder.update_max_size(0);
633 let res = encode(&mut encoder, vec![header("foo", "bar")]);
634 assert_eq!(&[32, 0], &res[..2]);
635 }
636
637 #[test]
638 fn test_decreasing_table_size_without_eviction() {
639 let mut encoder = Encoder::default();
640
641 // Add a header
642 let _ = encode(&mut encoder, vec![header("foo", "bar")]);
643
644 encoder.update_max_size(100);
645 assert_eq!(1, encoder.table.len());
646
647 let res = encode(&mut encoder, vec![header("foo", "bar")]);
648 assert_eq!(&[32 | 31, 69, 0x80 | 62], &res[..]);
649 }
650
651 #[test]
652 fn test_nameless_header() {
653 let mut encoder = Encoder::default();
654
655 let res = encode(
656 &mut encoder,
657 vec![
658 Header::Field {
659 name: Some("hello".parse().unwrap()),
660 value: HeaderValue::from_bytes(b"world").unwrap(),
661 },
662 Header::Field {
663 name: None,
664 value: HeaderValue::from_bytes(b"zomg").unwrap(),
665 },
666 ],
667 );
668
669 assert_eq!(&[0x40, 0x80 | 4], &res[0..2]);
670 assert_eq!("hello", huff_decode(&res[2..6]));
671 assert_eq!(0x80 | 4, res[6]);
672 assert_eq!("world", huff_decode(&res[7..11]));
673
674 // Next is not indexed
675 assert_eq!(&[15, 47, 0x80 | 3], &res[11..14]);
676 assert_eq!("zomg", huff_decode(&res[14..]));
677 }
678
679 #[test]
680 fn test_large_size_update() {
681 let mut encoder = Encoder::default();
682
683 encoder.update_max_size(1912930560);
684 assert_eq!(Some(SizeUpdate::One(1912930560)), encoder.size_update);
685
686 let mut dst = BytesMut::with_capacity(6);
687 encoder.encode_size_updates(&mut dst);
688 assert_eq!([63, 225, 129, 148, 144, 7], &dst[..]);
689 }
690
691 #[test]
692 #[ignore]
693 fn test_evicted_overflow() {
694 // Not sure what the best way to do this is.
695 }
696
697 fn encode(e: &mut Encoder, hdrs: Vec<Header<Option<HeaderName>>>) -> BytesMut {
698 let mut dst = BytesMut::with_capacity(1024);
699 e.encode(&mut hdrs.into_iter(), &mut dst);
700 dst
701 }
702
703 fn method(s: &str) -> Header<Option<HeaderName>> {
704 Header::Method(Method::from_bytes(s.as_bytes()).unwrap())
705 }
706
707 fn header(name: &str, val: &str) -> Header<Option<HeaderName>> {
708 let name = HeaderName::from_bytes(name.as_bytes()).unwrap();
709 let value = HeaderValue::from_bytes(val.as_bytes()).unwrap();
710
711 Header::Field {
712 name: Some(name),
713 value,
714 }
715 }
716
717 fn huff_decode(src: &[u8]) -> BytesMut {
718 let mut buf = BytesMut::new();
719 huffman::decode(src, &mut buf).unwrap()
720 }
721}
722