summaryrefslogtreecommitdiffstats
path: root/third_party/rust/h2/src/hpack/encoder.rs
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/rust/h2/src/hpack/encoder.rs')
-rw-r--r--third_party/rust/h2/src/hpack/encoder.rs721
1 files changed, 721 insertions, 0 deletions
diff --git a/third_party/rust/h2/src/hpack/encoder.rs b/third_party/rust/h2/src/hpack/encoder.rs
new file mode 100644
index 0000000000..76b373830e
--- /dev/null
+++ b/third_party/rust/h2/src/hpack/encoder.rs
@@ -0,0 +1,721 @@
+use super::table::{Index, Table};
+use super::{huffman, Header};
+
+use bytes::{BufMut, BytesMut};
+use http::header::{HeaderName, HeaderValue};
+
+#[derive(Debug)]
+pub struct Encoder {
+ table: Table,
+ size_update: Option<SizeUpdate>,
+}
+
+#[derive(Debug, Copy, Clone, Eq, PartialEq)]
+enum SizeUpdate {
+ One(usize),
+ Two(usize, usize), // min, max
+}
+
+impl Encoder {
+ pub fn new(max_size: usize, capacity: usize) -> Encoder {
+ Encoder {
+ table: Table::new(max_size, capacity),
+ size_update: None,
+ }
+ }
+
+ /// Queues a max size update.
+ ///
+ /// The next call to `encode` will include a dynamic size update frame.
+ pub fn update_max_size(&mut self, val: usize) {
+ match self.size_update {
+ Some(SizeUpdate::One(old)) => {
+ if val > old {
+ if old > self.table.max_size() {
+ self.size_update = Some(SizeUpdate::One(val));
+ } else {
+ self.size_update = Some(SizeUpdate::Two(old, val));
+ }
+ } else {
+ self.size_update = Some(SizeUpdate::One(val));
+ }
+ }
+ Some(SizeUpdate::Two(min, _)) => {
+ if val < min {
+ self.size_update = Some(SizeUpdate::One(val));
+ } else {
+ self.size_update = Some(SizeUpdate::Two(min, val));
+ }
+ }
+ None => {
+ if val != self.table.max_size() {
+ // Don't bother writing a frame if the value already matches
+ // the table's max size.
+ self.size_update = Some(SizeUpdate::One(val));
+ }
+ }
+ }
+ }
+
+ /// Encode a set of headers into the provide buffer
+ pub fn encode<I>(&mut self, headers: I, dst: &mut BytesMut)
+ where
+ I: IntoIterator<Item = Header<Option<HeaderName>>>,
+ {
+ let span = tracing::trace_span!("hpack::encode");
+ let _e = span.enter();
+
+ self.encode_size_updates(dst);
+
+ let mut last_index = None;
+
+ for header in headers {
+ match header.reify() {
+ // The header has an associated name. In which case, try to
+ // index it in the table.
+ Ok(header) => {
+ let index = self.table.index(header);
+ self.encode_header(&index, dst);
+
+ last_index = Some(index);
+ }
+ // The header does not have an associated name. This means that
+ // the name is the same as the previously yielded header. In
+ // which case, we skip table lookup and just use the same index
+ // as the previous entry.
+ Err(value) => {
+ self.encode_header_without_name(
+ last_index.as_ref().unwrap_or_else(|| {
+ panic!("encoding header without name, but no previous index to use for name");
+ }),
+ &value,
+ dst,
+ );
+ }
+ }
+ }
+ }
+
+ fn encode_size_updates(&mut self, dst: &mut BytesMut) {
+ match self.size_update.take() {
+ Some(SizeUpdate::One(val)) => {
+ self.table.resize(val);
+ encode_size_update(val, dst);
+ }
+ Some(SizeUpdate::Two(min, max)) => {
+ self.table.resize(min);
+ self.table.resize(max);
+ encode_size_update(min, dst);
+ encode_size_update(max, dst);
+ }
+ None => {}
+ }
+ }
+
+ fn encode_header(&mut self, index: &Index, dst: &mut BytesMut) {
+ match *index {
+ Index::Indexed(idx, _) => {
+ encode_int(idx, 7, 0x80, dst);
+ }
+ Index::Name(idx, _) => {
+ let header = self.table.resolve(&index);
+
+ encode_not_indexed(idx, header.value_slice(), header.is_sensitive(), dst);
+ }
+ Index::Inserted(_) => {
+ let header = self.table.resolve(&index);
+
+ assert!(!header.is_sensitive());
+
+ dst.put_u8(0b0100_0000);
+
+ encode_str(header.name().as_slice(), dst);
+ encode_str(header.value_slice(), dst);
+ }
+ Index::InsertedValue(idx, _) => {
+ let header = self.table.resolve(&index);
+
+ assert!(!header.is_sensitive());
+
+ encode_int(idx, 6, 0b0100_0000, dst);
+ encode_str(header.value_slice(), dst);
+ }
+ Index::NotIndexed(_) => {
+ let header = self.table.resolve(&index);
+
+ encode_not_indexed2(
+ header.name().as_slice(),
+ header.value_slice(),
+ header.is_sensitive(),
+ dst,
+ );
+ }
+ }
+ }
+
+ fn encode_header_without_name(
+ &mut self,
+ last: &Index,
+ value: &HeaderValue,
+ dst: &mut BytesMut,
+ ) {
+ match *last {
+ Index::Indexed(..)
+ | Index::Name(..)
+ | Index::Inserted(..)
+ | Index::InsertedValue(..) => {
+ let idx = self.table.resolve_idx(last);
+
+ encode_not_indexed(idx, value.as_ref(), value.is_sensitive(), dst);
+ }
+ Index::NotIndexed(_) => {
+ let last = self.table.resolve(last);
+
+ encode_not_indexed2(
+ last.name().as_slice(),
+ value.as_ref(),
+ value.is_sensitive(),
+ dst,
+ );
+ }
+ }
+ }
+}
+
+impl Default for Encoder {
+ fn default() -> Encoder {
+ Encoder::new(4096, 0)
+ }
+}
+
+fn encode_size_update(val: usize, dst: &mut BytesMut) {
+ encode_int(val, 5, 0b0010_0000, dst)
+}
+
+fn encode_not_indexed(name: usize, value: &[u8], sensitive: bool, dst: &mut BytesMut) {
+ if sensitive {
+ encode_int(name, 4, 0b10000, dst);
+ } else {
+ encode_int(name, 4, 0, dst);
+ }
+
+ encode_str(value, dst);
+}
+
+fn encode_not_indexed2(name: &[u8], value: &[u8], sensitive: bool, dst: &mut BytesMut) {
+ if sensitive {
+ dst.put_u8(0b10000);
+ } else {
+ dst.put_u8(0);
+ }
+
+ encode_str(name, dst);
+ encode_str(value, dst);
+}
+
+fn encode_str(val: &[u8], dst: &mut BytesMut) {
+ if !val.is_empty() {
+ let idx = position(dst);
+
+ // Push a placeholder byte for the length header
+ dst.put_u8(0);
+
+ // Encode with huffman
+ huffman::encode(val, dst);
+
+ let huff_len = position(dst) - (idx + 1);
+
+ if encode_int_one_byte(huff_len, 7) {
+ // Write the string head
+ dst[idx] = 0x80 | huff_len as u8;
+ } else {
+ // Write the head to a placeholder
+ const PLACEHOLDER_LEN: usize = 8;
+ let mut buf = [0u8; PLACEHOLDER_LEN];
+
+ let head_len = {
+ let mut head_dst = &mut buf[..];
+ encode_int(huff_len, 7, 0x80, &mut head_dst);
+ PLACEHOLDER_LEN - head_dst.remaining_mut()
+ };
+
+ // This is just done to reserve space in the destination
+ dst.put_slice(&buf[1..head_len]);
+
+ // Shift the header forward
+ for i in 0..huff_len {
+ let src_i = idx + 1 + (huff_len - (i + 1));
+ let dst_i = idx + head_len + (huff_len - (i + 1));
+ dst[dst_i] = dst[src_i];
+ }
+
+ // Copy in the head
+ for i in 0..head_len {
+ dst[idx + i] = buf[i];
+ }
+ }
+ } else {
+ // Write an empty string
+ dst.put_u8(0);
+ }
+}
+
+/// Encode an integer into the given destination buffer
+fn encode_int<B: BufMut>(
+ mut value: usize, // The integer to encode
+ prefix_bits: usize, // The number of bits in the prefix
+ first_byte: u8, // The base upon which to start encoding the int
+ dst: &mut B,
+) {
+ if encode_int_one_byte(value, prefix_bits) {
+ dst.put_u8(first_byte | value as u8);
+ return;
+ }
+
+ let low = (1 << prefix_bits) - 1;
+
+ value -= low;
+
+ dst.put_u8(first_byte | low as u8);
+
+ while value >= 128 {
+ dst.put_u8(0b1000_0000 | value as u8);
+
+ value >>= 7;
+ }
+
+ dst.put_u8(value as u8);
+}
+
+/// Returns true if the in the int can be fully encoded in the first byte.
+fn encode_int_one_byte(value: usize, prefix_bits: usize) -> bool {
+ value < (1 << prefix_bits) - 1
+}
+
+fn position(buf: &BytesMut) -> usize {
+ buf.len()
+}
+
+#[cfg(test)]
+mod test {
+ use super::*;
+ use crate::hpack::Header;
+ use http::*;
+
+ #[test]
+ fn test_encode_method_get() {
+ let mut encoder = Encoder::default();
+ let res = encode(&mut encoder, vec![method("GET")]);
+ assert_eq!(*res, [0x80 | 2]);
+ assert_eq!(encoder.table.len(), 0);
+ }
+
+ #[test]
+ fn test_encode_method_post() {
+ let mut encoder = Encoder::default();
+ let res = encode(&mut encoder, vec![method("POST")]);
+ assert_eq!(*res, [0x80 | 3]);
+ assert_eq!(encoder.table.len(), 0);
+ }
+
+ #[test]
+ fn test_encode_method_patch() {
+ let mut encoder = Encoder::default();
+ let res = encode(&mut encoder, vec![method("PATCH")]);
+
+ assert_eq!(res[0], 0b01000000 | 2); // Incremental indexing w/ name pulled from table
+ assert_eq!(res[1], 0x80 | 5); // header value w/ huffman coding
+
+ assert_eq!("PATCH", huff_decode(&res[2..7]));
+ assert_eq!(encoder.table.len(), 1);
+
+ let res = encode(&mut encoder, vec![method("PATCH")]);
+
+ assert_eq!(1 << 7 | 62, res[0]);
+ assert_eq!(1, res.len());
+ }
+
+ #[test]
+ fn test_encode_indexed_name_literal_value() {
+ let mut encoder = Encoder::default();
+ let res = encode(&mut encoder, vec![header("content-language", "foo")]);
+
+ assert_eq!(res[0], 0b01000000 | 27); // Indexed name
+ assert_eq!(res[1], 0x80 | 2); // header value w/ huffman coding
+
+ assert_eq!("foo", huff_decode(&res[2..4]));
+
+ // Same name, new value should still use incremental
+ let res = encode(&mut encoder, vec![header("content-language", "bar")]);
+ assert_eq!(res[0], 0b01000000 | 27); // Indexed name
+ assert_eq!(res[1], 0x80 | 3); // header value w/ huffman coding
+ assert_eq!("bar", huff_decode(&res[2..5]));
+ }
+
+ #[test]
+ fn test_repeated_headers_are_indexed() {
+ let mut encoder = Encoder::default();
+ let res = encode(&mut encoder, vec![header("foo", "hello")]);
+
+ assert_eq!(&[0b01000000, 0x80 | 2], &res[0..2]);
+ assert_eq!("foo", huff_decode(&res[2..4]));
+ assert_eq!(0x80 | 4, res[4]);
+ assert_eq!("hello", huff_decode(&res[5..]));
+ assert_eq!(9, res.len());
+
+ assert_eq!(1, encoder.table.len());
+
+ let res = encode(&mut encoder, vec![header("foo", "hello")]);
+ assert_eq!([0x80 | 62], *res);
+
+ assert_eq!(encoder.table.len(), 1);
+ }
+
+ #[test]
+ fn test_evicting_headers() {
+ let mut encoder = Encoder::default();
+
+ // Fill the table
+ for i in 0..64 {
+ let key = format!("x-hello-world-{:02}", i);
+ let res = encode(&mut encoder, vec![header(&key, &key)]);
+
+ assert_eq!(&[0b01000000, 0x80 | 12], &res[0..2]);
+ assert_eq!(key, huff_decode(&res[2..14]));
+ assert_eq!(0x80 | 12, res[14]);
+ assert_eq!(key, huff_decode(&res[15..]));
+ assert_eq!(27, res.len());
+
+ // Make sure the header can be found...
+ let res = encode(&mut encoder, vec![header(&key, &key)]);
+
+ // Only check that it is found
+ assert_eq!(0x80, res[0] & 0x80);
+ }
+
+ assert_eq!(4096, encoder.table.size());
+ assert_eq!(64, encoder.table.len());
+
+ // Find existing headers
+ for i in 0..64 {
+ let key = format!("x-hello-world-{:02}", i);
+ let res = encode(&mut encoder, vec![header(&key, &key)]);
+ assert_eq!(0x80, res[0] & 0x80);
+ }
+
+ // Insert a new header
+ let key = "x-hello-world-64";
+ let res = encode(&mut encoder, vec![header(key, key)]);
+
+ assert_eq!(&[0b01000000, 0x80 | 12], &res[0..2]);
+ assert_eq!(key, huff_decode(&res[2..14]));
+ assert_eq!(0x80 | 12, res[14]);
+ assert_eq!(key, huff_decode(&res[15..]));
+ assert_eq!(27, res.len());
+
+ assert_eq!(64, encoder.table.len());
+
+ // Now try encoding entries that should exist in the table
+ for i in 1..65 {
+ let key = format!("x-hello-world-{:02}", i);
+ let res = encode(&mut encoder, vec![header(&key, &key)]);
+ assert_eq!(0x80 | (61 + (65 - i)), res[0]);
+ }
+ }
+
+ #[test]
+ fn test_large_headers_are_not_indexed() {
+ let mut encoder = Encoder::new(128, 0);
+ let key = "hello-world-hello-world-HELLO-zzz";
+
+ let res = encode(&mut encoder, vec![header(key, key)]);
+
+ assert_eq!(&[0, 0x80 | 25], &res[..2]);
+
+ assert_eq!(0, encoder.table.len());
+ assert_eq!(0, encoder.table.size());
+ }
+
+ #[test]
+ fn test_sensitive_headers_are_never_indexed() {
+ use http::header::HeaderValue;
+
+ let name = "my-password".parse().unwrap();
+ let mut value = HeaderValue::from_bytes(b"12345").unwrap();
+ value.set_sensitive(true);
+
+ let header = Header::Field {
+ name: Some(name),
+ value,
+ };
+
+ // Now, try to encode the sensitive header
+
+ let mut encoder = Encoder::default();
+ let res = encode(&mut encoder, vec![header]);
+
+ assert_eq!(&[0b10000, 0x80 | 8], &res[..2]);
+ assert_eq!("my-password", huff_decode(&res[2..10]));
+ assert_eq!(0x80 | 4, res[10]);
+ assert_eq!("12345", huff_decode(&res[11..]));
+
+ // Now, try to encode a sensitive header w/ a name in the static table
+ let name = "authorization".parse().unwrap();
+ let mut value = HeaderValue::from_bytes(b"12345").unwrap();
+ value.set_sensitive(true);
+
+ let header = Header::Field {
+ name: Some(name),
+ value,
+ };
+
+ let mut encoder = Encoder::default();
+ let res = encode(&mut encoder, vec![header]);
+
+ assert_eq!(&[0b11111, 8], &res[..2]);
+ assert_eq!(0x80 | 4, res[2]);
+ assert_eq!("12345", huff_decode(&res[3..]));
+
+ // Using the name component of a previously indexed header (without
+ // sensitive flag set)
+
+ let _ = encode(
+ &mut encoder,
+ vec![self::header("my-password", "not-so-secret")],
+ );
+
+ let name = "my-password".parse().unwrap();
+ let mut value = HeaderValue::from_bytes(b"12345").unwrap();
+ value.set_sensitive(true);
+
+ let header = Header::Field {
+ name: Some(name),
+ value,
+ };
+ let res = encode(&mut encoder, vec![header]);
+
+ assert_eq!(&[0b11111, 47], &res[..2]);
+ assert_eq!(0x80 | 4, res[2]);
+ assert_eq!("12345", huff_decode(&res[3..]));
+ }
+
+ #[test]
+ fn test_content_length_value_not_indexed() {
+ let mut encoder = Encoder::default();
+ let res = encode(&mut encoder, vec![header("content-length", "1234")]);
+
+ assert_eq!(&[15, 13, 0x80 | 3], &res[0..3]);
+ assert_eq!("1234", huff_decode(&res[3..]));
+ assert_eq!(6, res.len());
+ }
+
+ #[test]
+ fn test_encoding_headers_with_same_name() {
+ let mut encoder = Encoder::default();
+ let name = "hello";
+
+ // Encode first one
+ let _ = encode(&mut encoder, vec![header(name, "one")]);
+
+ // Encode second one
+ let res = encode(&mut encoder, vec![header(name, "two")]);
+ assert_eq!(&[0x40 | 62, 0x80 | 3], &res[0..2]);
+ assert_eq!("two", huff_decode(&res[2..]));
+ assert_eq!(5, res.len());
+
+ // Encode the first one again
+ let res = encode(&mut encoder, vec![header(name, "one")]);
+ assert_eq!(&[0x80 | 63], &res[..]);
+
+ // Now the second one
+ let res = encode(&mut encoder, vec![header(name, "two")]);
+ assert_eq!(&[0x80 | 62], &res[..]);
+ }
+
+ #[test]
+ fn test_evicting_headers_when_multiple_of_same_name_are_in_table() {
+ // The encoder only has space for 2 headers
+ let mut encoder = Encoder::new(76, 0);
+
+ let _ = encode(&mut encoder, vec![header("foo", "bar")]);
+ assert_eq!(1, encoder.table.len());
+
+ let _ = encode(&mut encoder, vec![header("bar", "foo")]);
+ assert_eq!(2, encoder.table.len());
+
+ // This will evict the first header, while still referencing the header
+ // name
+ let res = encode(&mut encoder, vec![header("foo", "baz")]);
+ assert_eq!(&[0x40 | 63, 0, 0x80 | 3], &res[..3]);
+ assert_eq!(2, encoder.table.len());
+
+ // Try adding the same header again
+ let res = encode(&mut encoder, vec![header("foo", "baz")]);
+ assert_eq!(&[0x80 | 62], &res[..]);
+ assert_eq!(2, encoder.table.len());
+ }
+
+ #[test]
+ fn test_max_size_zero() {
+ // Static table only
+ let mut encoder = Encoder::new(0, 0);
+ let res = encode(&mut encoder, vec![method("GET")]);
+ assert_eq!(*res, [0x80 | 2]);
+ assert_eq!(encoder.table.len(), 0);
+
+ let res = encode(&mut encoder, vec![header("foo", "bar")]);
+ assert_eq!(&[0, 0x80 | 2], &res[..2]);
+ assert_eq!("foo", huff_decode(&res[2..4]));
+ assert_eq!(0x80 | 3, res[4]);
+ assert_eq!("bar", huff_decode(&res[5..8]));
+ assert_eq!(0, encoder.table.len());
+
+ // Encode a custom value
+ let res = encode(&mut encoder, vec![header("transfer-encoding", "chunked")]);
+ assert_eq!(&[15, 42, 0x80 | 6], &res[..3]);
+ assert_eq!("chunked", huff_decode(&res[3..]));
+ }
+
+ #[test]
+ fn test_update_max_size_combos() {
+ let mut encoder = Encoder::default();
+ assert!(encoder.size_update.is_none());
+ assert_eq!(4096, encoder.table.max_size());
+
+ encoder.update_max_size(4096); // Default size
+ assert!(encoder.size_update.is_none());
+
+ encoder.update_max_size(0);
+ assert_eq!(Some(SizeUpdate::One(0)), encoder.size_update);
+
+ encoder.update_max_size(100);
+ assert_eq!(Some(SizeUpdate::Two(0, 100)), encoder.size_update);
+
+ let mut encoder = Encoder::default();
+ encoder.update_max_size(8000);
+ assert_eq!(Some(SizeUpdate::One(8000)), encoder.size_update);
+
+ encoder.update_max_size(100);
+ assert_eq!(Some(SizeUpdate::One(100)), encoder.size_update);
+
+ encoder.update_max_size(8000);
+ assert_eq!(Some(SizeUpdate::Two(100, 8000)), encoder.size_update);
+
+ encoder.update_max_size(4000);
+ assert_eq!(Some(SizeUpdate::Two(100, 4000)), encoder.size_update);
+
+ encoder.update_max_size(50);
+ assert_eq!(Some(SizeUpdate::One(50)), encoder.size_update);
+ }
+
+ #[test]
+ fn test_resizing_table() {
+ let mut encoder = Encoder::default();
+
+ // Add a header
+ let _ = encode(&mut encoder, vec![header("foo", "bar")]);
+
+ encoder.update_max_size(1);
+ assert_eq!(1, encoder.table.len());
+
+ let res = encode(&mut encoder, vec![method("GET")]);
+ assert_eq!(&[32 | 1, 0x80 | 2], &res[..]);
+ assert_eq!(0, encoder.table.len());
+
+ let res = encode(&mut encoder, vec![header("foo", "bar")]);
+ assert_eq!(0, res[0]);
+
+ encoder.update_max_size(100);
+ let res = encode(&mut encoder, vec![header("foo", "bar")]);
+ assert_eq!(&[32 | 31, 69, 64], &res[..3]);
+
+ encoder.update_max_size(0);
+ let res = encode(&mut encoder, vec![header("foo", "bar")]);
+ assert_eq!(&[32, 0], &res[..2]);
+ }
+
+ #[test]
+ fn test_decreasing_table_size_without_eviction() {
+ let mut encoder = Encoder::default();
+
+ // Add a header
+ let _ = encode(&mut encoder, vec![header("foo", "bar")]);
+
+ encoder.update_max_size(100);
+ assert_eq!(1, encoder.table.len());
+
+ let res = encode(&mut encoder, vec![header("foo", "bar")]);
+ assert_eq!(&[32 | 31, 69, 0x80 | 62], &res[..]);
+ }
+
+ #[test]
+ fn test_nameless_header() {
+ let mut encoder = Encoder::default();
+
+ let res = encode(
+ &mut encoder,
+ vec![
+ Header::Field {
+ name: Some("hello".parse().unwrap()),
+ value: HeaderValue::from_bytes(b"world").unwrap(),
+ },
+ Header::Field {
+ name: None,
+ value: HeaderValue::from_bytes(b"zomg").unwrap(),
+ },
+ ],
+ );
+
+ assert_eq!(&[0x40, 0x80 | 4], &res[0..2]);
+ assert_eq!("hello", huff_decode(&res[2..6]));
+ assert_eq!(0x80 | 4, res[6]);
+ assert_eq!("world", huff_decode(&res[7..11]));
+
+ // Next is not indexed
+ assert_eq!(&[15, 47, 0x80 | 3], &res[11..14]);
+ assert_eq!("zomg", huff_decode(&res[14..]));
+ }
+
+ #[test]
+ fn test_large_size_update() {
+ let mut encoder = Encoder::default();
+
+ encoder.update_max_size(1912930560);
+ assert_eq!(Some(SizeUpdate::One(1912930560)), encoder.size_update);
+
+ let mut dst = BytesMut::with_capacity(6);
+ encoder.encode_size_updates(&mut dst);
+ assert_eq!([63, 225, 129, 148, 144, 7], &dst[..]);
+ }
+
+ #[test]
+ #[ignore]
+ fn test_evicted_overflow() {
+ // Not sure what the best way to do this is.
+ }
+
+ fn encode(e: &mut Encoder, hdrs: Vec<Header<Option<HeaderName>>>) -> BytesMut {
+ let mut dst = BytesMut::with_capacity(1024);
+ e.encode(&mut hdrs.into_iter(), &mut dst);
+ dst
+ }
+
+ fn method(s: &str) -> Header<Option<HeaderName>> {
+ Header::Method(Method::from_bytes(s.as_bytes()).unwrap())
+ }
+
+ fn header(name: &str, val: &str) -> Header<Option<HeaderName>> {
+ let name = HeaderName::from_bytes(name.as_bytes()).unwrap();
+ let value = HeaderValue::from_bytes(val.as_bytes()).unwrap();
+
+ Header::Field {
+ name: Some(name),
+ value,
+ }
+ }
+
+ fn huff_decode(src: &[u8]) -> BytesMut {
+ let mut buf = BytesMut::new();
+ huffman::decode(src, &mut buf).unwrap()
+ }
+}