qpack: convert to lowercase during encoding
Instead of immediately converting header names to lower-case when
creating a `Header`, defer the conversion to the huffman encoding phase
as in many cases we don't actually need to convert. This also makes it
possible to avoid modifying the headers.
The main annoyance of this is that the static table lookups now need to
be case insensitive, otherwise we could potentially miss some of the
headers if the applications passes them as upper-case.
Case-insensitive matching is done by turning the static table into an
actual table, and doing the lookup by iterating over it. In practice
this should be equivalent in terms of performance as I belive pattern
matching also compares cases one by one. This also makes it possible to
share the static table between endoder and decoder, without having to
duplicate it.
In the future we might want to further optimize this, e.g. by using a
pre-built trie, or something like that.
diff --git a/src/h3/mod.rs b/src/h3/mod.rs
index 0697bd8..7e108d2 100644
--- a/src/h3/mod.rs
+++ b/src/h3/mod.rs
@@ -433,8 +433,8 @@
///
/// Both `name` and `value` will be cloned, and `name` will also be
/// converted into lower-case.
- pub fn new(name: &str, value: &str) -> Header {
- Header(name.to_lowercase(), String::from(value))
+ pub fn new(name: &str, value: &str) -> Self {
+ Self(String::from(name), String::from(value))
}
/// Returns the header's name.
diff --git a/src/h3/qpack/decoder.rs b/src/h3/qpack/decoder.rs
index 18533ac..c89e380 100644
--- a/src/h3/qpack/decoder.rs
+++ b/src/h3/qpack/decoder.rs
@@ -206,120 +206,11 @@
}
fn lookup_static(idx: u64) -> Result<(&'static str, &'static str)> {
- let hdr = match idx {
- 0 => (":authority", ""),
- 1 => (":path", "/"),
- 2 => ("age", "0"),
- 3 => ("content-disposition", ""),
- 4 => ("content-length", "0"),
- 5 => ("cookie", ""),
- 6 => ("date", ""),
- 7 => ("etag", ""),
- 8 => ("if-modified-since", ""),
- 9 => ("if-none-match", ""),
- 10 => ("last-modified", ""),
- 11 => ("link", ""),
- 12 => ("location", ""),
- 13 => ("referer", ""),
- 14 => ("set-cookie", ""),
- 15 => (":method", "CONNECT"),
- 16 => (":method", "DELETE"),
- 17 => (":method", "GET"),
- 18 => (":method", "HEAD"),
- 19 => (":method", "OPTIONS"),
- 20 => (":method", "POST"),
- 21 => (":method", "PUT"),
- 22 => (":scheme", "http"),
- 23 => (":scheme", "https"),
- 24 => (":status", "103"),
- 25 => (":status", "200"),
- 26 => (":status", "304"),
- 27 => (":status", "404"),
- 28 => (":status", "503"),
- 29 => ("accept", "*/*"),
- 30 => ("accept", "application/dns-message"),
- 31 => ("accept-encoding", "gzip, deflate, br"),
- 32 => ("accept-ranges", "bytes"),
- 33 => ("access-control-allow-headers", "cache-control"),
- 34 => ("access-control-allow-headers", "content-type"),
- 35 => ("access-control-allow-origin", "*"),
- 36 => ("cache-control", "max-age=0"),
- 37 => ("cache-control", "max-age=2592000"),
- 38 => ("cache-control", "max-age=604800"),
- 39 => ("cache-control", "no-cache"),
- 40 => ("cache-control", "no-store"),
- 41 => ("cache-control", "public, max-age=31536000"),
- 42 => ("content-encoding", "br"),
- 43 => ("content-encoding", "gzip"),
- 44 => ("content-type", "application/dns-message"),
- 45 => ("content-type", "application/javascript"),
- 46 => ("content-type", "application/json"),
- 47 => ("content-type", "application/x-www-form-urlencoded"),
- 48 => ("content-type", "image/gif"),
- 49 => ("content-type", "image/jpeg"),
- 50 => ("content-type", "image/png"),
- 51 => ("content-type", "text/css"),
- 52 => ("content-type", "text/html; charset=utf-8"),
- 53 => ("content-type", "text/plain"),
- 54 => ("content-type", "text/plain;charset=utf-8"),
- 55 => ("range", "bytes=0-"),
- 56 => ("strict-transport-security", "max-age=31536000"),
- 57 => (
- "strict-transport-security",
- "max-age=31536000; includesubdomains",
- ),
- 58 => (
- "strict-transport-security",
- "max-age=31536000; includesubdomains; preload",
- ),
- 59 => ("vary", "accept-encoding"),
- 60 => ("vary", "origin"),
- 61 => ("x-content-type-options", "nosniff"),
- 62 => ("x-xss-protection", "1; mode=block"),
- 63 => (":status", "100"),
- 64 => (":status", "204"),
- 65 => (":status", "206"),
- 66 => (":status", "302"),
- 67 => (":status", "400"),
- 68 => (":status", "403"),
- 69 => (":status", "421"),
- 70 => (":status", "425"),
- 71 => (":status", "500"),
- 72 => ("accept-language", ""),
- 73 => ("access-control-allow-credentials", "FALSE"),
- 74 => ("access-control-allow-credentials", "TRUE"),
- 75 => ("access-control-allow-headers", "*"),
- 76 => ("access-control-allow-methods", "get"),
- 77 => ("access-control-allow-methods", "get, post, options"),
- 78 => ("access-control-allow-methods", "options"),
- 79 => ("access-control-expose-headers", "content-length"),
- 80 => ("access-control-request-headers", "content-type"),
- 81 => ("access-control-request-method", "get"),
- 82 => ("access-control-request-method", "post"),
- 83 => ("alt-svc", "clear"),
- 84 => ("authorization", ""),
- 85 => (
- "content-security-policy",
- "script-src 'none'; object-src 'none'; base-uri 'none'",
- ),
- 86 => ("early-data", "1"),
- 87 => ("expect-ct", ""),
- 88 => ("forwarded", ""),
- 89 => ("if-range", ""),
- 90 => ("origin", ""),
- 91 => ("purpose", "prefetch"),
- 92 => ("server", ""),
- 93 => ("timing-allow-origin", "*"),
- 94 => ("upgrade-insecure-requests", "1"),
- 95 => ("user-agent", ""),
- 96 => ("x-forwarded-for", ""),
- 97 => ("x-frame-options", "deny"),
- 98 => ("x-frame-options", "sameorigin"),
+ if idx >= super::static_table::STATIC_TABLE.len() as u64 {
+ return Err(Error::InvalidStaticTableIndex);
+ }
- _ => return Err(Error::InvalidStaticTableIndex),
- };
-
- Ok(hdr)
+ Ok(super::static_table::STATIC_TABLE[idx as usize])
}
fn decode_int(b: &mut octets::Octets, prefix: usize) -> Result<u64> {
diff --git a/src/h3/qpack/encoder.rs b/src/h3/qpack/encoder.rs
index 94af982..990c774 100644
--- a/src/h3/qpack/encoder.rs
+++ b/src/h3/qpack/encoder.rs
@@ -80,12 +80,14 @@
None => {
// Encode as fully literal.
- let name_len =
- super::huffman::encode_output_length(h.0.as_bytes())?;
+ let name_len = super::huffman::encode_output_length(
+ h.0.as_bytes(),
+ true,
+ )?;
encode_int(name_len as u64, LITERAL | 0x08, 3, &mut b)?;
- super::huffman::encode(h.0.as_bytes(), &mut b)?;
+ super::huffman::encode(h.0.as_bytes(), &mut b, true)?;
encode_str(&h.1, 7, &mut b)?;
},
@@ -97,153 +99,27 @@
}
fn lookup_static(h: &Header) -> Option<(u64, bool)> {
- let name = h.0.as_ref();
- let value = h.1.as_ref();
+ let mut name_match = None;
- let idx = match (name, value) {
- (":authority", _) => (0, false),
- (":path", "/") => (1, true),
- ("age", "0") => (2, true),
- ("content-disposition", _) => (3, false),
- ("content-length", "0") => (4, true),
- ("cookie", _) => (5, false),
- ("date", _) => (6, false),
- ("etag", _) => (7, false),
- ("if-modified-since", _) => (8, false),
- ("if-none-match", _) => (9, false),
- ("last-modified", _) => (10, false),
- ("link", _) => (11, false),
- ("location", _) => (12, false),
- ("referer", _) => (13, false),
- ("set-cookie", _) => (14, false),
- (":method", "CONNECT") => (15, true),
- (":method", "DELETE") => (16, true),
- (":method", "GET") => (17, true),
- (":method", "HEAD") => (18, true),
- (":method", "OPTIONS") => (19, true),
- (":method", "POST") => (20, true),
- (":method", "PUT") => (21, true),
- (":scheme", "http") => (22, true),
- (":scheme", "https") => (23, true),
- (":status", "103") => (24, true),
- (":status", "200") => (25, true),
- (":status", "304") => (26, true),
- (":status", "404") => (27, true),
- (":status", "503") => (28, true),
- ("accept", "*/*") => (29, true),
- ("accept", "application/dns-message") => (30, true),
- ("accept-encoding", "gzip, deflate, br") => (31, true),
- ("accept-ranges", "bytes") => (32, true),
- ("access-control-allow-headers", "cache-control") => (33, true),
- ("access-control-allow-headers", "content-type") => (34, true),
- ("access-control-allow-origin", "*") => (35, true),
- ("cache-control", "max-age=0") => (36, true),
- ("cache-control", "max-age=2592000") => (37, true),
- ("cache-control", "max-age=604800") => (38, true),
- ("cache-control", "no-cache") => (39, true),
- ("cache-control", "no-store") => (40, true),
- ("cache-control", "public, max-age=31536000") => (41, true),
- ("content-encoding", "br") => (42, true),
- ("content-encoding", "gzip") => (43, true),
- ("content-type", "application/dns-message") => (44, true),
- ("content-type", "application/javascript") => (45, true),
- ("content-type", "application/json") => (46, true),
- ("content-type", "application/x-www-form-urlencoded") => (47, true),
- ("content-type", "image/gif") => (48, true),
- ("content-type", "image/jpeg") => (49, true),
- ("content-type", "image/png") => (50, true),
- ("content-type", "text/css") => (51, true),
- ("content-type", "text/html; charset=utf-8") => (52, true),
- ("content-type", "text/plain") => (53, true),
- ("content-type", "text/plain;charset=utf-8") => (54, true),
- ("range", "bytes=0-") => (55, true),
- ("strict-transport-security", "max-age=31536000") => (56, true),
- ("strict-transport-security", "max-age=31536000; includesubdomains") =>
- (57, true),
- (
- "strict-transport-security",
- "max-age=31536000; includesubdomains; preload",
- ) => (58, true),
- ("vary", "accept-encoding") => (59, true),
- ("vary", "origin") => (60, true),
- ("x-content-type-options", "nosniff") => (61, true),
- ("x-xss-protection", "1; mode=block") => (62, true),
- (":status", "100") => (63, true),
- (":status", "204") => (64, true),
- (":status", "206") => (65, true),
- (":status", "302") => (66, true),
- (":status", "400") => (67, true),
- (":status", "403") => (68, true),
- (":status", "421") => (69, true),
- (":status", "425") => (70, true),
- (":status", "500") => (71, true),
- ("accept-language", _) => (72, false),
- ("access-control-allow-credentials", "FALSE") => (73, true),
- ("access-control-allow-credentials", "TRUE") => (74, true),
- ("access-control-allow-headers", "*") => (75, true),
- ("access-control-allow-methods", "get") => (76, true),
- ("access-control-allow-methods", "get, post, options") => (77, true),
- ("access-control-allow-methods", "options") => (78, true),
- ("access-control-expose-headers", "content-length") => (79, true),
- ("access-control-request-headers", "content-type") => (80, true),
- ("access-control-request-method", "get") => (81, true),
- ("access-control-request-method", "post") => (82, true),
- ("alt-svc", "clear") => (83, true),
- ("authorization", _) => (84, false),
- (
- "content-security-policy",
- "script-src 'none'; object-src 'none'; base-uri 'none'",
- ) => (85, true),
- ("early-data", "1") => (86, true),
- ("expect-ct", _) => (87, false),
- ("forwarded", _) => (88, false),
- ("if-range", _) => (89, false),
- ("origin", _) => (90, false),
- ("purpose", "prefetch") => (91, true),
- ("server", _) => (92, false),
- ("timing-allow-origin", "*") => (93, true),
- ("upgrade-insecure-requests", "1") => (94, true),
- ("user-agent", _) => (95, false),
- ("x-forwarded-for", _) => (96, false),
- ("x-frame-options", "deny") => (97, true),
- ("x-frame-options", "sameorigin") => (98, true),
+ for (i, e) in super::static_table::STATIC_TABLE.iter().enumerate() {
+ // Match header name first.
+ if h.name().len() == e.0.len() && h.name().eq_ignore_ascii_case(e.0) {
+ // No header value to match, return early.
+ if e.1.is_empty() {
+ return Some((i as u64, false));
+ }
- (":path", _) => (1, false),
- ("age", _) => (2, false),
- ("content-length", _) => (4, false),
- (":method", _) => (15, false),
- (":scheme", _) => (22, false),
- (":status", _) => (24, false),
- ("accept", _) => (29, false),
- ("accept-encoding", _) => (31, false),
- ("accept-ranges", _) => (32, false),
- ("access-control-allow-headers", _) => (33, false),
- ("access-control-allow-origin", _) => (35, false),
- ("cache-control", _) => (36, false),
- ("content-encoding", _) => (42, false),
- ("content-type", _) => (44, false),
- ("range", _) => (55, false),
- ("strict-transport-security", _) => (56, false),
- ("vary", _) => (59, false),
- ("x-content-type-options", _) => (61, false),
- ("x-xss-protection", _) => (62, false),
- ("access-control-allow-credentials", _) => (73, false),
- ("access-control-allow-methods", _) => (76, false),
- ("access-control-expose-headers", _) => (79, false),
- ("access-control-request-headers", _) => (80, false),
- ("access-control-request-method", _) => (81, false),
- ("alt-svc", _) => (83, false),
- ("content-security-policy", _) => (85, false),
- ("early-data", _) => (86, false),
- ("purpose", _) => (91, false),
- ("timing-allow-origin", _) => (93, false),
- ("upgrade-insecure-requests", _) => (94, false),
- ("x-frame-options", _) => (97, false),
+ // Match header value.
+ if h.value().len() == e.1.len() && h.value() == e.1 {
+ return Some((i as u64, true));
+ }
- _ => return None,
- };
+ // Remember name-only match for later, but keep searching.
+ name_match = Some((i as u64, false));
+ }
+ }
- Some(idx)
+ name_match
}
fn encode_int(
@@ -276,11 +152,11 @@
}
fn encode_str(v: &str, prefix: usize, b: &mut octets::OctetsMut) -> Result<()> {
- let len = super::huffman::encode_output_length(v.as_bytes())?;
+ let len = super::huffman::encode_output_length(v.as_bytes(), false)?;
encode_int(len as u64, 0x80, prefix, b)?;
- super::huffman::encode(v.as_bytes(), b)?;
+ super::huffman::encode(v.as_bytes(), b, false)?;
Ok(())
}
diff --git a/src/h3/qpack/huffman/mod.rs b/src/h3/qpack/huffman/mod.rs
index e1810c7..3a6ff06 100644
--- a/src/h3/qpack/huffman/mod.rs
+++ b/src/h3/qpack/huffman/mod.rs
@@ -57,11 +57,13 @@
Ok(out)
}
-pub fn encode(src: &[u8], out: &mut octets::OctetsMut) -> Result<()> {
+pub fn encode(src: &[u8], out: &mut octets::OctetsMut, low: bool) -> Result<()> {
let mut bits: u64 = 0;
let mut bits_left = 40;
for &b in src {
+ let b = if low { b.to_ascii_lowercase() } else { b };
+
let (nbits, code) = ENCODE_TABLE[b as usize];
bits |= code << (bits_left - nbits);
@@ -85,10 +87,12 @@
Ok(())
}
-pub fn encode_output_length(src: &[u8]) -> Result<usize> {
+pub fn encode_output_length(src: &[u8], low: bool) -> Result<usize> {
let mut bits: usize = 0;
for &b in src {
+ let b = if low { b.to_ascii_lowercase() } else { b };
+
let (nbits, _) = ENCODE_TABLE[b as usize];
bits += nbits;
}
diff --git a/src/h3/qpack/mod.rs b/src/h3/qpack/mod.rs
index e284d6c..2715172 100644
--- a/src/h3/qpack/mod.rs
+++ b/src/h3/qpack/mod.rs
@@ -99,11 +99,41 @@
];
let mut enc = Encoder::new();
- assert!(enc.encode(&headers, &mut encoded).is_ok());
+ assert_eq!(enc.encode(&headers, &mut encoded), Ok(240));
let mut dec = Decoder::new();
assert_eq!(dec.decode(&mut encoded, std::u64::MAX), Ok(headers));
}
+
+ #[test]
+ fn lower_case() {
+ let mut encoded = [0u8; 35];
+
+ let headers_expected = vec![
+ crate::h3::Header::new(":status", "200"),
+ crate::h3::Header::new(":path", "/HeLlO"),
+ crate::h3::Header::new("woot", "woot"),
+ crate::h3::Header::new("hello", "WorlD"),
+ crate::h3::Header::new("foo", "BaR"),
+ ];
+
+ // Header.
+ let headers_in = vec![
+ crate::h3::Header::new(":StAtUs", "200"),
+ crate::h3::Header::new(":PaTh", "/HeLlO"),
+ crate::h3::Header::new("WooT", "woot"),
+ crate::h3::Header::new("hello", "WorlD"),
+ crate::h3::Header::new("fOo", "BaR"),
+ ];
+
+ let mut enc = Encoder::new();
+ assert_eq!(enc.encode(&headers_in, &mut encoded), Ok(35));
+
+ let mut dec = Decoder::new();
+ let headers_out = dec.decode(&mut encoded, std::u64::MAX).unwrap();
+
+ assert_eq!(headers_expected, headers_out);
+ }
}
pub use decoder::Decoder;
@@ -112,3 +142,4 @@
mod decoder;
mod encoder;
mod huffman;
+mod static_table;
diff --git a/src/h3/qpack/static_table.rs b/src/h3/qpack/static_table.rs
new file mode 100644
index 0000000..4010d12
--- /dev/null
+++ b/src/h3/qpack/static_table.rs
@@ -0,0 +1,136 @@
+// Copyright (C) 2020, Cloudflare, Inc.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+// * Redistributions of source code must retain the above copyright notice,
+// this list of conditions and the following disclaimer.
+//
+// * Redistributions in binary form must reproduce the above copyright
+// notice, this list of conditions and the following disclaimer in the
+// documentation and/or other materials provided with the distribution.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
+// IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+// THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
+// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+pub const STATIC_TABLE: [(&str, &str); 99] = [
+ (":authority", ""),
+ (":path", "/"),
+ ("age", "0"),
+ ("content-disposition", ""),
+ ("content-length", "0"),
+ ("cookie", ""),
+ ("date", ""),
+ ("etag", ""),
+ ("if-modified-since", ""),
+ ("if-none-match", ""),
+ ("last-modified", ""),
+ ("link", ""),
+ ("location", ""),
+ ("referer", ""),
+ ("set-cookie", ""),
+ (":method", "CONNECT"),
+ (":method", "DELETE"),
+ (":method", "GET"),
+ (":method", "HEAD"),
+ (":method", "OPTIONS"),
+ (":method", "POST"),
+ (":method", "PUT"),
+ (":scheme", "http"),
+ (":scheme", "https"),
+ (":status", "103"),
+ (":status", "200"),
+ (":status", "304"),
+ (":status", "404"),
+ (":status", "503"),
+ ("accept", "*/*"),
+ ("accept", "application/dns-message"),
+ ("accept-encoding", "gzip, deflate, br"),
+ ("accept-ranges", "bytes"),
+ ("access-control-allow-headers", "cache-control"),
+ ("access-control-allow-headers", "content-type"),
+ ("access-control-allow-origin", "*"),
+ ("cache-control", "max-age=0"),
+ ("cache-control", "max-age=2592000"),
+ ("cache-control", "max-age=604800"),
+ ("cache-control", "no-cache"),
+ ("cache-control", "no-store"),
+ ("cache-control", "public, max-age=31536000"),
+ ("content-encoding", "br"),
+ ("content-encoding", "gzip"),
+ ("content-type", "application/dns-message"),
+ ("content-type", "application/javascript"),
+ ("content-type", "application/json"),
+ ("content-type", "application/x-www-form-urlencoded"),
+ ("content-type", "image/gif"),
+ ("content-type", "image/jpeg"),
+ ("content-type", "image/png"),
+ ("content-type", "text/css"),
+ ("content-type", "text/html; charset=utf-8"),
+ ("content-type", "text/plain"),
+ ("content-type", "text/plain;charset=utf-8"),
+ ("range", "bytes=0-"),
+ ("strict-transport-security", "max-age=31536000"),
+ (
+ "strict-transport-security",
+ "max-age=31536000; includesubdomains",
+ ),
+ (
+ "strict-transport-security",
+ "max-age=31536000; includesubdomains; preload",
+ ),
+ ("vary", "accept-encoding"),
+ ("vary", "origin"),
+ ("x-content-type-options", "nosniff"),
+ ("x-xss-protection", "1; mode=block"),
+ (":status", "100"),
+ (":status", "204"),
+ (":status", "206"),
+ (":status", "302"),
+ (":status", "400"),
+ (":status", "403"),
+ (":status", "421"),
+ (":status", "425"),
+ (":status", "500"),
+ ("accept-language", ""),
+ ("access-control-allow-credentials", "FALSE"),
+ ("access-control-allow-credentials", "TRUE"),
+ ("access-control-allow-headers", "*"),
+ ("access-control-allow-methods", "get"),
+ ("access-control-allow-methods", "get, post, options"),
+ ("access-control-allow-methods", "options"),
+ ("access-control-expose-headers", "content-length"),
+ ("access-control-request-headers", "content-type"),
+ ("access-control-request-method", "get"),
+ ("access-control-request-method", "post"),
+ ("alt-svc", "clear"),
+ ("authorization", ""),
+ (
+ "content-security-policy",
+ "script-src 'none'; object-src 'none'; base-uri 'none'",
+ ),
+ ("early-data", "1"),
+ ("expect-ct", ""),
+ ("forwarded", ""),
+ ("if-range", ""),
+ ("origin", ""),
+ ("purpose", "prefetch"),
+ ("server", ""),
+ ("timing-allow-origin", "*"),
+ ("upgrade-insecure-requests", "1"),
+ ("user-agent", ""),
+ ("x-forwarded-for", ""),
+ ("x-frame-options", "deny"),
+ ("x-frame-options", "sameorigin"),
+];
