diff options
Diffstat (limited to 'third_party/rust/h2/src/hpack')
-rw-r--r-- | third_party/rust/h2/src/hpack/decoder.rs | 937 | ||||
-rw-r--r-- | third_party/rust/h2/src/hpack/encoder.rs | 721 | ||||
-rw-r--r-- | third_party/rust/h2/src/hpack/header.rs | 308 | ||||
-rw-r--r-- | third_party/rust/h2/src/hpack/huffman/mod.rs | 199 | ||||
-rw-r--r-- | third_party/rust/h2/src/hpack/huffman/table.rs | 5130 | ||||
-rw-r--r-- | third_party/rust/h2/src/hpack/mod.rs | 12 | ||||
-rw-r--r-- | third_party/rust/h2/src/hpack/table.rs | 766 | ||||
-rw-r--r-- | third_party/rust/h2/src/hpack/test/fixture.rs | 615 | ||||
-rw-r--r-- | third_party/rust/h2/src/hpack/test/fuzz.rs | 365 | ||||
-rw-r--r-- | third_party/rust/h2/src/hpack/test/mod.rs | 2 |
10 files changed, 9055 insertions, 0 deletions
diff --git a/third_party/rust/h2/src/hpack/decoder.rs b/third_party/rust/h2/src/hpack/decoder.rs new file mode 100644 index 0000000000..960cbb143c --- /dev/null +++ b/third_party/rust/h2/src/hpack/decoder.rs @@ -0,0 +1,937 @@ +use super::{header::BytesStr, huffman, Header}; +use crate::frame; + +use bytes::{Buf, Bytes, BytesMut}; +use http::header; +use http::method::{self, Method}; +use http::status::{self, StatusCode}; + +use std::cmp; +use std::collections::VecDeque; +use std::io::Cursor; +use std::str::Utf8Error; + +/// Decodes headers using HPACK +#[derive(Debug)] +pub struct Decoder { + // Protocol indicated that the max table size will update + max_size_update: Option<usize>, + last_max_update: usize, + table: Table, + buffer: BytesMut, +} + +/// Represents all errors that can be encountered while performing the decoding +/// of an HPACK header set. +#[derive(Debug, Copy, Clone, PartialEq, Eq)] +pub enum DecoderError { + InvalidRepresentation, + InvalidIntegerPrefix, + InvalidTableIndex, + InvalidHuffmanCode, + InvalidUtf8, + InvalidStatusCode, + InvalidPseudoheader, + InvalidMaxDynamicSize, + IntegerOverflow, + NeedMore(NeedMore), +} + +#[derive(Debug, Copy, Clone, PartialEq, Eq)] +pub enum NeedMore { + UnexpectedEndOfStream, + IntegerUnderflow, + StringUnderflow, +} + +enum Representation { + /// Indexed header field representation + /// + /// An indexed header field representation identifies an entry in either the + /// static table or the dynamic table (see Section 2.3). + /// + /// # Header encoding + /// + /// ```text + /// 0 1 2 3 4 5 6 7 + /// +---+---+---+---+---+---+---+---+ + /// | 1 | Index (7+) | + /// +---+---------------------------+ + /// ``` + Indexed, + + /// Literal Header Field with Incremental Indexing + /// + /// A literal header field with incremental indexing representation results + /// in appending a header field to the decoded header list and inserting it + /// as a new entry into the dynamic table. + /// + /// # Header encoding + /// + /// ```text + /// 0 1 2 3 4 5 6 7 + /// +---+---+---+---+---+---+---+---+ + /// | 0 | 1 | Index (6+) | + /// +---+---+-----------------------+ + /// | H | Value Length (7+) | + /// +---+---------------------------+ + /// | Value String (Length octets) | + /// +-------------------------------+ + /// ``` + LiteralWithIndexing, + + /// Literal Header Field without Indexing + /// + /// A literal header field without indexing representation results in + /// appending a header field to the decoded header list without altering the + /// dynamic table. + /// + /// # Header encoding + /// + /// ```text + /// 0 1 2 3 4 5 6 7 + /// +---+---+---+---+---+---+---+---+ + /// | 0 | 0 | 0 | 0 | Index (4+) | + /// +---+---+-----------------------+ + /// | H | Value Length (7+) | + /// +---+---------------------------+ + /// | Value String (Length octets) | + /// +-------------------------------+ + /// ``` + LiteralWithoutIndexing, + + /// Literal Header Field Never Indexed + /// + /// A literal header field never-indexed representation results in appending + /// a header field to the decoded header list without altering the dynamic + /// table. Intermediaries MUST use the same representation for encoding this + /// header field. + /// + /// ```text + /// 0 1 2 3 4 5 6 7 + /// +---+---+---+---+---+---+---+---+ + /// | 0 | 0 | 0 | 1 | Index (4+) | + /// +---+---+-----------------------+ + /// | H | Value Length (7+) | + /// +---+---------------------------+ + /// | Value String (Length octets) | + /// +-------------------------------+ + /// ``` + LiteralNeverIndexed, + + /// Dynamic Table Size Update + /// + /// A dynamic table size update signals a change to the size of the dynamic + /// table. + /// + /// # Header encoding + /// + /// ```text + /// 0 1 2 3 4 5 6 7 + /// +---+---+---+---+---+---+---+---+ + /// | 0 | 0 | 1 | Max size (5+) | + /// +---+---------------------------+ + /// ``` + SizeUpdate, +} + +#[derive(Debug)] +struct Table { + entries: VecDeque<Header>, + size: usize, + max_size: usize, +} + +struct StringMarker { + offset: usize, + len: usize, + string: Option<Bytes>, +} + +// ===== impl Decoder ===== + +impl Decoder { + /// Creates a new `Decoder` with all settings set to default values. + pub fn new(size: usize) -> Decoder { + Decoder { + max_size_update: None, + last_max_update: size, + table: Table::new(size), + buffer: BytesMut::with_capacity(4096), + } + } + + /// Queues a potential size update + #[allow(dead_code)] + pub fn queue_size_update(&mut self, size: usize) { + let size = match self.max_size_update { + Some(v) => cmp::max(v, size), + None => size, + }; + + self.max_size_update = Some(size); + } + + /// Decodes the headers found in the given buffer. + pub fn decode<F>( + &mut self, + src: &mut Cursor<&mut BytesMut>, + mut f: F, + ) -> Result<(), DecoderError> + where + F: FnMut(Header), + { + use self::Representation::*; + + let mut can_resize = true; + + if let Some(size) = self.max_size_update.take() { + self.last_max_update = size; + } + + let span = tracing::trace_span!("hpack::decode"); + let _e = span.enter(); + + tracing::trace!("decode"); + + while let Some(ty) = peek_u8(src) { + // At this point we are always at the beginning of the next block + // within the HPACK data. The type of the block can always be + // determined from the first byte. + match Representation::load(ty)? { + Indexed => { + tracing::trace!(rem = src.remaining(), kind = %"Indexed"); + can_resize = false; + let entry = self.decode_indexed(src)?; + consume(src); + f(entry); + } + LiteralWithIndexing => { + tracing::trace!(rem = src.remaining(), kind = %"LiteralWithIndexing"); + can_resize = false; + let entry = self.decode_literal(src, true)?; + + // Insert the header into the table + self.table.insert(entry.clone()); + consume(src); + + f(entry); + } + LiteralWithoutIndexing => { + tracing::trace!(rem = src.remaining(), kind = %"LiteralWithoutIndexing"); + can_resize = false; + let entry = self.decode_literal(src, false)?; + consume(src); + f(entry); + } + LiteralNeverIndexed => { + tracing::trace!(rem = src.remaining(), kind = %"LiteralNeverIndexed"); + can_resize = false; + let entry = self.decode_literal(src, false)?; + consume(src); + + // TODO: Track that this should never be indexed + + f(entry); + } + SizeUpdate => { + tracing::trace!(rem = src.remaining(), kind = %"SizeUpdate"); + if !can_resize { + return Err(DecoderError::InvalidMaxDynamicSize); + } + + // Handle the dynamic table size update + self.process_size_update(src)?; + consume(src); + } + } + } + + Ok(()) + } + + fn process_size_update(&mut self, buf: &mut Cursor<&mut BytesMut>) -> Result<(), DecoderError> { + let new_size = decode_int(buf, 5)?; + + if new_size > self.last_max_update { + return Err(DecoderError::InvalidMaxDynamicSize); + } + + tracing::debug!( + from = self.table.size(), + to = new_size, + "Decoder changed max table size" + ); + + self.table.set_max_size(new_size); + + Ok(()) + } + + fn decode_indexed(&self, buf: &mut Cursor<&mut BytesMut>) -> Result<Header, DecoderError> { + let index = decode_int(buf, 7)?; + self.table.get(index) + } + + fn decode_literal( + &mut self, + buf: &mut Cursor<&mut BytesMut>, + index: bool, + ) -> Result<Header, DecoderError> { + let prefix = if index { 6 } else { 4 }; + + // Extract the table index for the name, or 0 if not indexed + let table_idx = decode_int(buf, prefix)?; + + // First, read the header name + if table_idx == 0 { + let old_pos = buf.position(); + let name_marker = self.try_decode_string(buf)?; + let value_marker = self.try_decode_string(buf)?; + buf.set_position(old_pos); + // Read the name as a literal + let name = name_marker.consume(buf); + let value = value_marker.consume(buf); + Header::new(name, value) + } else { + let e = self.table.get(table_idx)?; + let value = self.decode_string(buf)?; + + e.name().into_entry(value) + } + } + + fn try_decode_string( + &mut self, + buf: &mut Cursor<&mut BytesMut>, + ) -> Result<StringMarker, DecoderError> { + let old_pos = buf.position(); + const HUFF_FLAG: u8 = 0b1000_0000; + + // The first bit in the first byte contains the huffman encoded flag. + let huff = match peek_u8(buf) { + Some(hdr) => (hdr & HUFF_FLAG) == HUFF_FLAG, + None => return Err(DecoderError::NeedMore(NeedMore::UnexpectedEndOfStream)), + }; + + // Decode the string length using 7 bit prefix + let len = decode_int(buf, 7)?; + + if len > buf.remaining() { + tracing::trace!(len, remaining = buf.remaining(), "decode_string underflow",); + return Err(DecoderError::NeedMore(NeedMore::StringUnderflow)); + } + + let offset = (buf.position() - old_pos) as usize; + if huff { + let ret = { + let raw = &buf.chunk()[..len]; + huffman::decode(raw, &mut self.buffer).map(|buf| StringMarker { + offset, + len, + string: Some(BytesMut::freeze(buf)), + }) + }; + + buf.advance(len); + ret + } else { + buf.advance(len); + Ok(StringMarker { + offset, + len, + string: None, + }) + } + } + + fn decode_string(&mut self, buf: &mut Cursor<&mut BytesMut>) -> Result<Bytes, DecoderError> { + let old_pos = buf.position(); + let marker = self.try_decode_string(buf)?; + buf.set_position(old_pos); + Ok(marker.consume(buf)) + } +} + +impl Default for Decoder { + fn default() -> Decoder { + Decoder::new(4096) + } +} + +// ===== impl Representation ===== + +impl Representation { + pub fn load(byte: u8) -> Result<Representation, DecoderError> { + const INDEXED: u8 = 0b1000_0000; + const LITERAL_WITH_INDEXING: u8 = 0b0100_0000; + const LITERAL_WITHOUT_INDEXING: u8 = 0b1111_0000; + const LITERAL_NEVER_INDEXED: u8 = 0b0001_0000; + const SIZE_UPDATE_MASK: u8 = 0b1110_0000; + const SIZE_UPDATE: u8 = 0b0010_0000; + + // TODO: What did I even write here? + + if byte & INDEXED == INDEXED { + Ok(Representation::Indexed) + } else if byte & LITERAL_WITH_INDEXING == LITERAL_WITH_INDEXING { + Ok(Representation::LiteralWithIndexing) + } else if byte & LITERAL_WITHOUT_INDEXING == 0 { + Ok(Representation::LiteralWithoutIndexing) + } else if byte & LITERAL_WITHOUT_INDEXING == LITERAL_NEVER_INDEXED { + Ok(Representation::LiteralNeverIndexed) + } else if byte & SIZE_UPDATE_MASK == SIZE_UPDATE { + Ok(Representation::SizeUpdate) + } else { + Err(DecoderError::InvalidRepresentation) + } + } +} + +fn decode_int<B: Buf>(buf: &mut B, prefix_size: u8) -> Result<usize, DecoderError> { + // The octet limit is chosen such that the maximum allowed *value* can + // never overflow an unsigned 32-bit integer. The maximum value of any + // integer that can be encoded with 5 octets is ~2^28 + const MAX_BYTES: usize = 5; + const VARINT_MASK: u8 = 0b0111_1111; + const VARINT_FLAG: u8 = 0b1000_0000; + + if prefix_size < 1 || prefix_size > 8 { + return Err(DecoderError::InvalidIntegerPrefix); + } + + if !buf.has_remaining() { + return Err(DecoderError::NeedMore(NeedMore::IntegerUnderflow)); + } + + let mask = if prefix_size == 8 { + 0xFF + } else { + (1u8 << prefix_size).wrapping_sub(1) + }; + + let mut ret = (buf.get_u8() & mask) as usize; + + if ret < mask as usize { + // Value fits in the prefix bits + return Ok(ret); + } + + // The int did not fit in the prefix bits, so continue reading. + // + // The total number of bytes used to represent the int. The first byte was + // the prefix, so start at 1. + let mut bytes = 1; + + // The rest of the int is stored as a varint -- 7 bits for the value and 1 + // bit to indicate if it is the last byte. + let mut shift = 0; + + while buf.has_remaining() { + let b = buf.get_u8(); + + bytes += 1; + ret += ((b & VARINT_MASK) as usize) << shift; + shift += 7; + + if b & VARINT_FLAG == 0 { + return Ok(ret); + } + + if bytes == MAX_BYTES { + // The spec requires that this situation is an error + return Err(DecoderError::IntegerOverflow); + } + } + + Err(DecoderError::NeedMore(NeedMore::IntegerUnderflow)) +} + +fn peek_u8<B: Buf>(buf: &B) -> Option<u8> { + if buf.has_remaining() { + Some(buf.chunk()[0]) + } else { + None + } +} + +fn take(buf: &mut Cursor<&mut BytesMut>, n: usize) -> Bytes { + let pos = buf.position() as usize; + let mut head = buf.get_mut().split_to(pos + n); + buf.set_position(0); + head.advance(pos); + head.freeze() +} + +impl StringMarker { + fn consume(self, buf: &mut Cursor<&mut BytesMut>) -> Bytes { + buf.advance(self.offset); + match self.string { + Some(string) => { + buf.advance(self.len); + string + } + None => take(buf, self.len), + } + } +} + +fn consume(buf: &mut Cursor<&mut BytesMut>) { + // remove bytes from the internal BytesMut when they have been successfully + // decoded. This is a more permanent cursor position, which will be + // used to resume if decoding was only partial. + take(buf, 0); +} + +// ===== impl Table ===== + +impl Table { + fn new(max_size: usize) -> Table { + Table { + entries: VecDeque::new(), + size: 0, + max_size, + } + } + + fn size(&self) -> usize { + self.size + } + + /// Returns the entry located at the given index. + /// + /// The table is 1-indexed and constructed in such a way that the first + /// entries belong to the static table, followed by entries in the dynamic + /// table. They are merged into a single index address space, though. + /// + /// This is according to the [HPACK spec, section 2.3.3.] + /// (http://http2.github.io/http2-spec/compression.html#index.address.space) + pub fn get(&self, index: usize) -> Result<Header, DecoderError> { + if index == 0 { + return Err(DecoderError::InvalidTableIndex); + } + + if index <= 61 { + return Ok(get_static(index)); + } + + // Convert the index for lookup in the entries structure. + match self.entries.get(index - 62) { + Some(e) => Ok(e.clone()), + None => Err(DecoderError::InvalidTableIndex), + } + } + + fn insert(&mut self, entry: Header) { + let len = entry.len(); + + self.reserve(len); + + if self.size + len <= self.max_size { + self.size += len; + + // Track the entry + self.entries.push_front(entry); + } + } + + fn set_max_size(&mut self, size: usize) { + self.max_size = size; + // Make the table size fit within the new constraints. + self.consolidate(); + } + + fn reserve(&mut self, size: usize) { + while self.size + size > self.max_size { + match self.entries.pop_back() { + Some(last) => { + self.size -= last.len(); + } + None => return, + } + } + } + + fn consolidate(&mut self) { + while self.size > self.max_size { + { + let last = match self.entries.back() { + Some(x) => x, + None => { + // Can never happen as the size of the table must reach + // 0 by the time we've exhausted all elements. + panic!("Size of table != 0, but no headers left!"); + } + }; + + self.size -= last.len(); + } + + self.entries.pop_back(); + } + } +} + +// ===== impl DecoderError ===== + +impl From<Utf8Error> for DecoderError { + fn from(_: Utf8Error) -> DecoderError { + // TODO: Better error? + DecoderError::InvalidUtf8 + } +} + +impl From<header::InvalidHeaderValue> for DecoderError { + fn from(_: header::InvalidHeaderValue) -> DecoderError { + // TODO: Better error? + DecoderError::InvalidUtf8 + } +} + +impl From<header::InvalidHeaderName> for DecoderError { + fn from(_: header::InvalidHeaderName) -> DecoderError { + // TODO: Better error + DecoderError::InvalidUtf8 + } +} + +impl From<method::InvalidMethod> for DecoderError { + fn from(_: method::InvalidMethod) -> DecoderError { + // TODO: Better error + DecoderError::InvalidUtf8 + } +} + +impl From<status::InvalidStatusCode> for DecoderError { + fn from(_: status::InvalidStatusCode) -> DecoderError { + // TODO: Better error + DecoderError::InvalidUtf8 + } +} + +impl From<DecoderError> for frame::Error { + fn from(src: DecoderError) -> Self { + frame::Error::Hpack(src) + } +} + +/// Get an entry from the static table +pub fn get_static(idx: usize) -> Header { + use http::header::HeaderValue; + + match idx { + 1 => Header::Authority(BytesStr::from_static("")), + 2 => Header::Method(Method::GET), + 3 => Header::Method(Method::POST), + 4 => Header::Path(BytesStr::from_static("/")), + 5 => Header::Path(BytesStr::from_static("/index.html")), + 6 => Header::Scheme(BytesStr::from_static("http")), + 7 => Header::Scheme(BytesStr::from_static("https")), + 8 => Header::Status(StatusCode::OK), + 9 => Header::Status(StatusCode::NO_CONTENT), + 10 => Header::Status(StatusCode::PARTIAL_CONTENT), + 11 => Header::Status(StatusCode::NOT_MODIFIED), + 12 => Header::Status(StatusCode::BAD_REQUEST), + 13 => Header::Status(StatusCode::NOT_FOUND), + 14 => Header::Status(StatusCode::INTERNAL_SERVER_ERROR), + 15 => Header::Field { + name: header::ACCEPT_CHARSET, + value: HeaderValue::from_static(""), + }, + 16 => Header::Field { + name: header::ACCEPT_ENCODING, + value: HeaderValue::from_static("gzip, deflate"), + }, + 17 => Header::Field { + name: header::ACCEPT_LANGUAGE, + value: HeaderValue::from_static(""), + }, + 18 => Header::Field { + name: header::ACCEPT_RANGES, + value: HeaderValue::from_static(""), + }, + 19 => Header::Field { + name: header::ACCEPT, + value: HeaderValue::from_static(""), + }, + 20 => Header::Field { + name: header::ACCESS_CONTROL_ALLOW_ORIGIN, + value: HeaderValue::from_static(""), + }, + 21 => Header::Field { + name: header::AGE, + value: HeaderValue::from_static(""), + }, + 22 => Header::Field { + name: header::ALLOW, + value: HeaderValue::from_static(""), + }, + 23 => Header::Field { + name: header::AUTHORIZATION, + value: HeaderValue::from_static(""), + }, + 24 => Header::Field { + name: header::CACHE_CONTROL, + value: HeaderValue::from_static(""), + }, + 25 => Header::Field { + name: header::CONTENT_DISPOSITION, + value: HeaderValue::from_static(""), + }, + 26 => Header::Field { + name: header::CONTENT_ENCODING, + value: HeaderValue::from_static(""), + }, + 27 => Header::Field { + name: header::CONTENT_LANGUAGE, + value: HeaderValue::from_static(""), + }, + 28 => Header::Field { + name: header::CONTENT_LENGTH, + value: HeaderValue::from_static(""), + }, + 29 => Header::Field { + name: header::CONTENT_LOCATION, + value: HeaderValue::from_static(""), + }, + 30 => Header::Field { + name: header::CONTENT_RANGE, + value: HeaderValue::from_static(""), + }, + 31 => Header::Field { + name: header::CONTENT_TYPE, + value: HeaderValue::from_static(""), + }, + 32 => Header::Field { + name: header::COOKIE, + value: HeaderValue::from_static(""), + }, + 33 => Header::Field { + name: header::DATE, + value: HeaderValue::from_static(""), + }, + 34 => Header::Field { + name: header::ETAG, + value: HeaderValue::from_static(""), + }, + 35 => Header::Field { + name: header::EXPECT, + value: HeaderValue::from_static(""), + }, + 36 => Header::Field { + name: header::EXPIRES, + value: HeaderValue::from_static(""), + }, + 37 => Header::Field { + name: header::FROM, + value: HeaderValue::from_static(""), + }, + 38 => Header::Field { + name: header::HOST, + value: HeaderValue::from_static(""), + }, + 39 => Header::Field { + name: header::IF_MATCH, + value: HeaderValue::from_static(""), + }, + 40 => Header::Field { + name: header::IF_MODIFIED_SINCE, + value: HeaderValue::from_static(""), + }, + 41 => Header::Field { + name: header::IF_NONE_MATCH, + value: HeaderValue::from_static(""), + }, + 42 => Header::Field { + name: header::IF_RANGE, + value: HeaderValue::from_static(""), + }, + 43 => Header::Field { + name: header::IF_UNMODIFIED_SINCE, + value: HeaderValue::from_static(""), + }, + 44 => Header::Field { + name: header::LAST_MODIFIED, + value: HeaderValue::from_static(""), + }, + 45 => Header::Field { + name: header::LINK, + value: HeaderValue::from_static(""), + }, + 46 => Header::Field { + name: header::LOCATION, + value: HeaderValue::from_static(""), + }, + 47 => Header::Field { + name: header::MAX_FORWARDS, + value: HeaderValue::from_static(""), + }, + 48 => Header::Field { + name: header::PROXY_AUTHENTICATE, + value: HeaderValue::from_static(""), + }, + 49 => Header::Field { + name: header::PROXY_AUTHORIZATION, + value: HeaderValue::from_static(""), + }, + 50 => Header::Field { + name: header::RANGE, + value: HeaderValue::from_static(""), + }, + 51 => Header::Field { + name: header::REFERER, + value: HeaderValue::from_static(""), + }, + 52 => Header::Field { + name: header::REFRESH, + value: HeaderValue::from_static(""), + }, + 53 => Header::Field { + name: header::RETRY_AFTER, + value: HeaderValue::from_static(""), + }, + 54 => Header::Field { + name: header::SERVER, + value: HeaderValue::from_static(""), + }, + 55 => Header::Field { + name: header::SET_COOKIE, + value: HeaderValue::from_static(""), + }, + 56 => Header::Field { + name: header::STRICT_TRANSPORT_SECURITY, + value: HeaderValue::from_static(""), + }, + 57 => Header::Field { + name: header::TRANSFER_ENCODING, + value: HeaderValue::from_static(""), + }, + 58 => Header::Field { + name: header::USER_AGENT, + value: HeaderValue::from_static(""), + }, + 59 => Header::Field { + name: header::VARY, + value: HeaderValue::from_static(""), + }, + 60 => Header::Field { + name: header::VIA, + value: HeaderValue::from_static(""), + }, + 61 => Header::Field { + name: header::WWW_AUTHENTICATE, + value: HeaderValue::from_static(""), + }, + _ => unreachable!(), + } +} + +#[cfg(test)] +mod test { + use super::*; + use crate::hpack::Header; + + #[test] + fn test_peek_u8() { + let b = 0xff; + let mut buf = Cursor::new(vec![b]); + assert_eq!(peek_u8(&buf), Some(b)); + assert_eq!(buf.get_u8(), b); + assert_eq!(peek_u8(&buf), None); + } + + #[test] + fn test_decode_string_empty() { + let mut de = Decoder::new(0); + let mut buf = BytesMut::new(); + let err = de.decode_string(&mut Cursor::new(&mut buf)).unwrap_err(); + assert_eq!(err, DecoderError::NeedMore(NeedMore::UnexpectedEndOfStream)); + } + + #[test] + fn test_decode_empty() { + let mut de = Decoder::new(0); + let mut buf = BytesMut::new(); + let _: () = de.decode(&mut Cursor::new(&mut buf), |_| {}).unwrap(); + } + + #[test] + fn test_decode_indexed_larger_than_table() { + let mut de = Decoder::new(0); + + let mut buf = BytesMut::new(); + buf.extend([0b01000000, 0x80 | 2]); + buf.extend(huff_encode(b"foo")); + buf.extend([0x80 | 3]); + buf.extend(huff_encode(b"bar")); + + let mut res = vec![]; + de.decode(&mut Cursor::new(&mut buf), |h| { + res.push(h); + }) + .unwrap(); + + assert_eq!(res.len(), 1); + assert_eq!(de.table.size(), 0); + + match res[0] { + Header::Field { + ref name, + ref value, + } => { + assert_eq!(name, "foo"); + assert_eq!(value, "bar"); + } + _ => panic!(), + } + } + + fn huff_encode(src: &[u8]) -> BytesMut { + let mut buf = BytesMut::new(); + huffman::encode(src, &mut buf); + buf + } + + #[test] + fn test_decode_continuation_header_with_non_huff_encoded_name() { + let mut de = Decoder::new(0); + let value = huff_encode(b"bar"); + let mut buf = BytesMut::new(); + // header name is non_huff encoded + buf.extend([0b01000000, 3]); + buf.extend(b"foo"); + // header value is partial + buf.extend([0x80 | 3]); + buf.extend(&value[0..1]); + + let mut res = vec![]; + let e = de + .decode(&mut Cursor::new(&mut buf), |h| { + res.push(h); + }) + .unwrap_err(); + // decode error because the header value is partial + assert_eq!(e, DecoderError::NeedMore(NeedMore::StringUnderflow)); + + // extend buf with the remaining header value + buf.extend(&value[1..]); + de.decode(&mut Cursor::new(&mut buf), |h| { + res.push(h); + }) + .unwrap(); + + assert_eq!(res.len(), 1); + assert_eq!(de.table.size(), 0); + + match res[0] { + Header::Field { + ref name, + ref value, + } => { + assert_eq!(name, "foo"); + assert_eq!(value, "bar"); + } + _ => panic!(), + } + } +} 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..d121a2aaf5 --- /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() + } +} diff --git a/third_party/rust/h2/src/hpack/header.rs b/third_party/rust/h2/src/hpack/header.rs new file mode 100644 index 0000000000..0b5d1fdedd --- /dev/null +++ b/third_party/rust/h2/src/hpack/header.rs @@ -0,0 +1,308 @@ +use super::{DecoderError, NeedMore}; +use crate::ext::Protocol; + +use bytes::Bytes; +use http::header::{HeaderName, HeaderValue}; +use http::{Method, StatusCode}; +use std::fmt; + +/// HTTP/2 Header +#[derive(Debug, Clone, Eq, PartialEq)] +pub enum Header<T = HeaderName> { + Field { name: T, value: HeaderValue }, + // TODO: Change these types to `http::uri` types. + Authority(BytesStr), + Method(Method), + Scheme(BytesStr), + Path(BytesStr), + Protocol(Protocol), + Status(StatusCode), +} + +/// The header field name +#[derive(Debug, Clone, Eq, PartialEq, Hash)] +pub enum Name<'a> { + Field(&'a HeaderName), + Authority, + Method, + Scheme, + Path, + Protocol, + Status, +} + +#[doc(hidden)] +#[derive(Clone, Eq, PartialEq, Default)] +pub struct BytesStr(Bytes); + +pub fn len(name: &HeaderName, value: &HeaderValue) -> usize { + let n: &str = name.as_ref(); + 32 + n.len() + value.len() +} + +impl Header<Option<HeaderName>> { + pub fn reify(self) -> Result<Header, HeaderValue> { + use self::Header::*; + + Ok(match self { + Field { + name: Some(n), + value, + } => Field { name: n, value }, + Field { name: None, value } => return Err(value), + Authority(v) => Authority(v), + Method(v) => Method(v), + Scheme(v) => Scheme(v), + Path(v) => Path(v), + Protocol(v) => Protocol(v), + Status(v) => Status(v), + }) + } +} + +impl Header { + pub fn new(name: Bytes, value: Bytes) -> Result<Header, DecoderError> { + if name.is_empty() { + return Err(DecoderError::NeedMore(NeedMore::UnexpectedEndOfStream)); + } + if name[0] == b':' { + match &name[1..] { + b"authority" => { + let value = BytesStr::try_from(value)?; + Ok(Header::Authority(value)) + } + b"method" => { + let method = Method::from_bytes(&value)?; + Ok(Header::Method(method)) + } + b"scheme" => { + let value = BytesStr::try_from(value)?; + Ok(Header::Scheme(value)) + } + b"path" => { + let value = BytesStr::try_from(value)?; + Ok(Header::Path(value)) + } + b"protocol" => { + let value = Protocol::try_from(value)?; + Ok(Header::Protocol(value)) + } + b"status" => { + let status = StatusCode::from_bytes(&value)?; + Ok(Header::Status(status)) + } + _ => Err(DecoderError::InvalidPseudoheader), + } + } else { + // HTTP/2 requires lower case header names + let name = HeaderName::from_lowercase(&name)?; + let value = HeaderValue::from_bytes(&value)?; + + Ok(Header::Field { name, value }) + } + } + + pub fn len(&self) -> usize { + match *self { + Header::Field { + ref name, + ref value, + } => len(name, value), + Header::Authority(ref v) => 32 + 10 + v.len(), + Header::Method(ref v) => 32 + 7 + v.as_ref().len(), + Header::Scheme(ref v) => 32 + 7 + v.len(), + Header::Path(ref v) => 32 + 5 + v.len(), + Header::Protocol(ref v) => 32 + 9 + v.as_str().len(), + Header::Status(_) => 32 + 7 + 3, + } + } + + /// Returns the header name + pub fn name(&self) -> Name { + match *self { + Header::Field { ref name, .. } => Name::Field(name), + Header::Authority(..) => Name::Authority, + Header::Method(..) => Name::Method, + Header::Scheme(..) => Name::Scheme, + Header::Path(..) => Name::Path, + Header::Protocol(..) => Name::Protocol, + Header::Status(..) => Name::Status, + } + } + + pub fn value_slice(&self) -> &[u8] { + match *self { + Header::Field { ref value, .. } => value.as_ref(), + Header::Authority(ref v) => v.as_ref(), + Header::Method(ref v) => v.as_ref().as_ref(), + Header::Scheme(ref v) => v.as_ref(), + Header::Path(ref v) => v.as_ref(), + Header::Protocol(ref v) => v.as_ref(), + Header::Status(ref v) => v.as_str().as_ref(), + } + } + + pub fn value_eq(&self, other: &Header) -> bool { + match *self { + Header::Field { ref value, .. } => { + let a = value; + match *other { + Header::Field { ref value, .. } => a == value, + _ => false, + } + } + Header::Authority(ref a) => match *other { + Header::Authority(ref b) => a == b, + _ => false, + }, + Header::Method(ref a) => match *other { + Header::Method(ref b) => a == b, + _ => false, + }, + Header::Scheme(ref a) => match *other { + Header::Scheme(ref b) => a == b, + _ => false, + }, + Header::Path(ref a) => match *other { + Header::Path(ref b) => a == b, + _ => false, + }, + Header::Protocol(ref a) => match *other { + Header::Protocol(ref b) => a == b, + _ => false, + }, + Header::Status(ref a) => match *other { + Header::Status(ref b) => a == b, + _ => false, + }, + } + } + + pub fn is_sensitive(&self) -> bool { + match *self { + Header::Field { ref value, .. } => value.is_sensitive(), + // TODO: Technically these other header values can be sensitive too. + _ => false, + } + } + + pub fn skip_value_index(&self) -> bool { + use http::header; + + match *self { + Header::Field { ref name, .. } => matches!( + *name, + header::AGE + | header::AUTHORIZATION + | header::CONTENT_LENGTH + | header::ETAG + | header::IF_MODIFIED_SINCE + | header::IF_NONE_MATCH + | header::LOCATION + | header::COOKIE + | header::SET_COOKIE + ), + Header::Path(..) => true, + _ => false, + } + } +} + +// Mostly for tests +impl From<Header> for Header<Option<HeaderName>> { + fn from(src: Header) -> Self { + match src { + Header::Field { name, value } => Header::Field { + name: Some(name), + value, + }, + Header::Authority(v) => Header::Authority(v), + Header::Method(v) => Header::Method(v), + Header::Scheme(v) => Header::Scheme(v), + Header::Path(v) => Header::Path(v), + Header::Protocol(v) => Header::Protocol(v), + Header::Status(v) => Header::Status(v), + } + } +} + +impl<'a> Name<'a> { + pub fn into_entry(self, value: Bytes) -> Result<Header, DecoderError> { + match self { + Name::Field(name) => Ok(Header::Field { + name: name.clone(), + value: HeaderValue::from_bytes(&value)?, + }), + Name::Authority => Ok(Header::Authority(BytesStr::try_from(value)?)), + Name::Method => Ok(Header::Method(Method::from_bytes(&value)?)), + Name::Scheme => Ok(Header::Scheme(BytesStr::try_from(value)?)), + Name::Path => Ok(Header::Path(BytesStr::try_from(value)?)), + Name::Protocol => Ok(Header::Protocol(Protocol::try_from(value)?)), + Name::Status => { + match StatusCode::from_bytes(&value) { + Ok(status) => Ok(Header::Status(status)), + // TODO: better error handling + Err(_) => Err(DecoderError::InvalidStatusCode), + } + } + } + } + + pub fn as_slice(&self) -> &[u8] { + match *self { + Name::Field(ref name) => name.as_ref(), + Name::Authority => b":authority", + Name::Method => b":method", + Name::Scheme => b":scheme", + Name::Path => b":path", + Name::Protocol => b":protocol", + Name::Status => b":status", + } + } +} + +// ===== impl BytesStr ===== + +impl BytesStr { + pub(crate) const fn from_static(value: &'static str) -> Self { + BytesStr(Bytes::from_static(value.as_bytes())) + } + + pub(crate) fn from(value: &str) -> Self { + BytesStr(Bytes::copy_from_slice(value.as_bytes())) + } + + #[doc(hidden)] + pub fn try_from(bytes: Bytes) -> Result<Self, std::str::Utf8Error> { + std::str::from_utf8(bytes.as_ref())?; + Ok(BytesStr(bytes)) + } + + pub(crate) fn as_str(&self) -> &str { + // Safety: check valid utf-8 in constructor + unsafe { std::str::from_utf8_unchecked(self.0.as_ref()) } + } + + pub(crate) fn into_inner(self) -> Bytes { + self.0 + } +} + +impl std::ops::Deref for BytesStr { + type Target = str; + fn deref(&self) -> &str { + self.as_str() + } +} + +impl AsRef<[u8]> for BytesStr { + fn as_ref(&self) -> &[u8] { + self.0.as_ref() + } +} + +impl fmt::Debug for BytesStr { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + self.0.fmt(f) + } +} diff --git a/third_party/rust/h2/src/hpack/huffman/mod.rs b/third_party/rust/h2/src/hpack/huffman/mod.rs new file mode 100644 index 0000000000..86c97eb585 --- /dev/null +++ b/third_party/rust/h2/src/hpack/huffman/mod.rs @@ -0,0 +1,199 @@ +mod table; + +use self::table::{DECODE_TABLE, ENCODE_TABLE}; +use crate::hpack::DecoderError; + +use bytes::{BufMut, BytesMut}; + +// Constructed in the generated `table.rs` file +struct Decoder { + state: usize, + maybe_eos: bool, +} + +// These flags must match the ones in genhuff.rs + +const MAYBE_EOS: u8 = 1; +const DECODED: u8 = 2; +const ERROR: u8 = 4; + +pub fn decode(src: &[u8], buf: &mut BytesMut) -> Result<BytesMut, DecoderError> { + let mut decoder = Decoder::new(); + + // Max compression ratio is >= 0.5 + buf.reserve(src.len() << 1); + + for b in src { + if let Some(b) = decoder.decode4(b >> 4)? { + buf.put_u8(b); + } + + if let Some(b) = decoder.decode4(b & 0xf)? { + buf.put_u8(b); + } + } + + if !decoder.is_final() { + return Err(DecoderError::InvalidHuffmanCode); + } + + Ok(buf.split()) +} + +pub fn encode(src: &[u8], dst: &mut BytesMut) { + let mut bits: u64 = 0; + let mut bits_left = 40; + + for &b in src { + let (nbits, code) = ENCODE_TABLE[b as usize]; + + bits |= code << (bits_left - nbits); + bits_left -= nbits; + + while bits_left <= 32 { + dst.put_u8((bits >> 32) as u8); + + bits <<= 8; + bits_left += 8; + } + } + + if bits_left != 40 { + // This writes the EOS token + bits |= (1 << bits_left) - 1; + dst.put_u8((bits >> 32) as u8); + } +} + +impl Decoder { + fn new() -> Decoder { + Decoder { + state: 0, + maybe_eos: false, + } + } + + // Decodes 4 bits + fn decode4(&mut self, input: u8) -> Result<Option<u8>, DecoderError> { + // (next-state, byte, flags) + let (next, byte, flags) = DECODE_TABLE[self.state][input as usize]; + + if flags & ERROR == ERROR { + // Data followed the EOS marker + return Err(DecoderError::InvalidHuffmanCode); + } + + let mut ret = None; + + if flags & DECODED == DECODED { + ret = Some(byte); + } + + self.state = next; + self.maybe_eos = flags & MAYBE_EOS == MAYBE_EOS; + + Ok(ret) + } + + fn is_final(&self) -> bool { + self.state == 0 || self.maybe_eos + } +} + +#[cfg(test)] +mod test { + use super::*; + + fn decode(src: &[u8]) -> Result<BytesMut, DecoderError> { + let mut buf = BytesMut::new(); + super::decode(src, &mut buf) + } + + #[test] + fn decode_single_byte() { + assert_eq!("o", decode(&[0b00111111]).unwrap()); + assert_eq!("0", decode(&[7]).unwrap()); + assert_eq!("A", decode(&[(0x21 << 2) + 3]).unwrap()); + } + + #[test] + fn single_char_multi_byte() { + assert_eq!("#", decode(&[255, 160 + 15]).unwrap()); + assert_eq!("$", decode(&[255, 200 + 7]).unwrap()); + assert_eq!("\x0a", decode(&[255, 255, 255, 240 + 3]).unwrap()); + } + + #[test] + fn multi_char() { + assert_eq!("!0", decode(&[254, 1]).unwrap()); + assert_eq!(" !", decode(&[0b01010011, 0b11111000]).unwrap()); + } + + #[test] + fn encode_single_byte() { + let mut dst = BytesMut::with_capacity(1); + + encode(b"o", &mut dst); + assert_eq!(&dst[..], &[0b00111111]); + + dst.clear(); + encode(b"0", &mut dst); + assert_eq!(&dst[..], &[7]); + + dst.clear(); + encode(b"A", &mut dst); + assert_eq!(&dst[..], &[(0x21 << 2) + 3]); + } + + #[test] + fn encode_decode_str() { + const DATA: &[&str] = &[ + "hello world", + ":method", + ":scheme", + ":authority", + "yahoo.co.jp", + "GET", + "http", + ":path", + "/images/top/sp2/cmn/logo-ns-130528.png", + "example.com", + "hpack-test", + "xxxxxxx1", + "Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:16.0) Gecko/20100101 Firefox/16.0", + "accept", + "Accept", + "text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8", + "cookie", + "B=76j09a189a6h4&b=3&s=0b", + "TE", + "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Morbi non bibendum libero. \ + Etiam ultrices lorem ut.", + ]; + + for s in DATA { + let mut dst = BytesMut::with_capacity(s.len()); + + encode(s.as_bytes(), &mut dst); + + let decoded = decode(&dst).unwrap(); + + assert_eq!(&decoded[..], s.as_bytes()); + } + } + + #[test] + fn encode_decode_u8() { + const DATA: &[&[u8]] = &[b"\0", b"\0\0\0", b"\0\x01\x02\x03\x04\x05", b"\xFF\xF8"]; + + for s in DATA { + let mut dst = BytesMut::with_capacity(s.len()); + + encode(s, &mut dst); + + let decoded = decode(&dst).unwrap(); + + assert_eq!(&decoded[..], &s[..]); + } + } +} diff --git a/third_party/rust/h2/src/hpack/huffman/table.rs b/third_party/rust/h2/src/hpack/huffman/table.rs new file mode 100644 index 0000000000..560cfaf7be --- /dev/null +++ b/third_party/rust/h2/src/hpack/huffman/table.rs @@ -0,0 +1,5130 @@ +// !!! DO NOT EDIT !!! Generated by util/genhuff/src/main.rs + +// (num-bits, bits) +pub const ENCODE_TABLE: [(usize, u64); 257] = [ + (13, 0x1ff8), + (23, 0x007f_ffd8), + (28, 0x0fff_ffe2), + (28, 0x0fff_ffe3), + (28, 0x0fff_ffe4), + (28, 0x0fff_ffe5), + (28, 0x0fff_ffe6), + (28, 0x0fff_ffe7), + (28, 0x0fff_ffe8), + (24, 0x00ff_ffea), + (30, 0x3fff_fffc), + (28, 0x0fff_ffe9), + (28, 0x0fff_ffea), + (30, 0x3fff_fffd), + (28, 0x0fff_ffeb), + (28, 0x0fff_ffec), + (28, 0x0fff_ffed), + (28, 0x0fff_ffee), + (28, 0x0fff_ffef), + (28, 0x0fff_fff0), + (28, 0x0fff_fff1), + (28, 0x0fff_fff2), + (30, 0x3fff_fffe), + (28, 0x0fff_fff3), + (28, 0x0fff_fff4), + (28, 0x0fff_fff5), + (28, 0x0fff_fff6), + (28, 0x0fff_fff7), + (28, 0x0fff_fff8), + (28, 0x0fff_fff9), + (28, 0x0fff_fffa), + (28, 0x0fff_fffb), + (6, 0x14), + (10, 0x3f8), + (10, 0x3f9), + (12, 0xffa), + (13, 0x1ff9), + (6, 0x15), + (8, 0xf8), + (11, 0x7fa), + (10, 0x3fa), + (10, 0x3fb), + (8, 0xf9), + (11, 0x7fb), + (8, 0xfa), + (6, 0x16), + (6, 0x17), + (6, 0x18), + (5, 0x0), + (5, 0x1), + (5, 0x2), + (6, 0x19), + (6, 0x1a), + (6, 0x1b), + (6, 0x1c), + (6, 0x1d), + (6, 0x1e), + (6, 0x1f), + (7, 0x5c), + (8, 0xfb), + (15, 0x7ffc), + (6, 0x20), + (12, 0xffb), + (10, 0x3fc), + (13, 0x1ffa), + (6, 0x21), + (7, 0x5d), + (7, 0x5e), + (7, 0x5f), + (7, 0x60), + (7, 0x61), + (7, 0x62), + (7, 0x63), + (7, 0x64), + (7, 0x65), + (7, 0x66), + (7, 0x67), + (7, 0x68), + (7, 0x69), + (7, 0x6a), + (7, 0x6b), + (7, 0x6c), + (7, 0x6d), + (7, 0x6e), + (7, 0x6f), + (7, 0x70), + (7, 0x71), + (7, 0x72), + (8, 0xfc), + (7, 0x73), + (8, 0xfd), + (13, 0x1ffb), + (19, 0x7fff0), + (13, 0x1ffc), + (14, 0x3ffc), + (6, 0x22), + (15, 0x7ffd), + (5, 0x3), + (6, 0x23), + (5, 0x4), + (6, 0x24), + (5, 0x5), + (6, 0x25), + (6, 0x26), + (6, 0x27), + (5, 0x6), + (7, 0x74), + (7, 0x75), + (6, 0x28), + (6, 0x29), + (6, 0x2a), + (5, 0x7), + (6, 0x2b), + (7, 0x76), + (6, 0x2c), + (5, 0x8), + (5, 0x9), + (6, 0x2d), + (7, 0x77), + (7, 0x78), + (7, 0x79), + (7, 0x7a), + (7, 0x7b), + (15, 0x7ffe), + (11, 0x7fc), + (14, 0x3ffd), + (13, 0x1ffd), + (28, 0x0fff_fffc), + (20, 0xfffe6), + (22, 0x003f_ffd2), + (20, 0xfffe7), + (20, 0xfffe8), + (22, 0x003f_ffd3), + (22, 0x003f_ffd4), + (22, 0x003f_ffd5), + (23, 0x007f_ffd9), + (22, 0x003f_ffd6), + (23, 0x007f_ffda), + (23, 0x007f_ffdb), + (23, 0x007f_ffdc), + (23, 0x007f_ffdd), + (23, 0x007f_ffde), + (24, 0x00ff_ffeb), + (23, 0x007f_ffdf), + (24, 0x00ff_ffec), + (24, 0x00ff_ffed), + (22, 0x003f_ffd7), + (23, 0x007f_ffe0), + (24, 0x00ff_ffee), + (23, 0x007f_ffe1), + (23, 0x007f_ffe2), + (23, 0x007f_ffe3), + (23, 0x007f_ffe4), + (21, 0x001f_ffdc), + (22, 0x003f_ffd8), + (23, 0x007f_ffe5), + (22, 0x003f_ffd9), + (23, 0x007f_ffe6), + (23, 0x007f_ffe7), + (24, 0x00ff_ffef), + (22, 0x003f_ffda), + (21, 0x001f_ffdd), + (20, 0xfffe9), + (22, 0x003f_ffdb), + (22, 0x003f_ffdc), + (23, 0x007f_ffe8), + (23, 0x007f_ffe9), + (21, 0x001f_ffde), + (23, 0x007f_ffea), + (22, 0x003f_ffdd), + (22, 0x003f_ffde), + (24, 0x00ff_fff0), + (21, 0x001f_ffdf), + (22, 0x003f_ffdf), + (23, 0x007f_ffeb), + (23, 0x007f_ffec), + (21, 0x001f_ffe0), + (21, 0x001f_ffe1), + (22, 0x003f_ffe0), + (21, 0x001f_ffe2), + (23, 0x007f_ffed), + (22, 0x003f_ffe1), + (23, 0x007f_ffee), + (23, 0x007f_ffef), + (20, 0xfffea), + (22, 0x003f_ffe2), + (22, 0x003f_ffe3), + (22, 0x003f_ffe4), + (23, 0x007f_fff0), + (22, 0x003f_ffe5), + (22, 0x003f_ffe6), + (23, 0x007f_fff1), + (26, 0x03ff_ffe0), + (26, 0x03ff_ffe1), + (20, 0xfffeb), + (19, 0x7fff1), + (22, 0x003f_ffe7), + (23, 0x007f_fff2), + (22, 0x003f_ffe8), + (25, 0x01ff_ffec), + (26, 0x03ff_ffe2), + (26, 0x03ff_ffe3), + (26, 0x03ff_ffe4), + (27, 0x07ff_ffde), + (27, 0x07ff_ffdf), + (26, 0x03ff_ffe5), + (24, 0x00ff_fff1), + (25, 0x01ff_ffed), + (19, 0x7fff2), + (21, 0x001f_ffe3), + (26, 0x03ff_ffe6), + (27, 0x07ff_ffe0), + (27, 0x07ff_ffe1), + (26, 0x03ff_ffe7), + (27, 0x07ff_ffe2), + (24, 0x00ff_fff2), + (21, 0x001f_ffe4), + (21, 0x001f_ffe5), + (26, 0x03ff_ffe8), + (26, 0x03ff_ffe9), + (28, 0x0fff_fffd), + (27, 0x07ff_ffe3), + (27, 0x07ff_ffe4), + (27, 0x07ff_ffe5), + (20, 0xfffec), + (24, 0x00ff_fff3), + (20, 0xfffed), + (21, 0x001f_ffe6), + (22, 0x003f_ffe9), + (21, 0x001f_ffe7), + (21, 0x001f_ffe8), + (23, 0x007f_fff3), + (22, 0x003f_ffea), + (22, 0x003f_ffeb), + (25, 0x01ff_ffee), + (25, 0x01ff_ffef), + (24, 0x00ff_fff4), + (24, 0x00ff_fff5), + (26, 0x03ff_ffea), + (23, 0x007f_fff4), + (26, 0x03ff_ffeb), + (27, 0x07ff_ffe6), + (26, 0x03ff_ffec), + (26, 0x03ff_ffed), + (27, 0x07ff_ffe7), + (27, 0x07ff_ffe8), + (27, 0x07ff_ffe9), + (27, 0x07ff_ffea), + (27, 0x07ff_ffeb), + (28, 0x0fff_fffe), + (27, 0x07ff_ffec), + (27, 0x07ff_ffed), + (27, 0x07ff_ffee), + (27, 0x07ff_ffef), + (27, 0x07ff_fff0), + (26, 0x03ff_ffee), + (30, 0x3fff_ffff), +]; + +// (next-state, byte, flags) +pub const DECODE_TABLE: [[(usize, u8, u8); 16]; 256] = [ + // 0 + [ + (4, 0, 0x00), + (5, 0, 0x00), + (7, 0, 0x00), + (8, 0, 0x00), + (11, 0, 0x00), + (12, 0, 0x00), + (16, 0, 0x00), + (19, 0, 0x00), + (25, 0, 0x00), + (28, 0, 0x00), + (32, 0, 0x00), + (35, 0, 0x00), + (42, 0, 0x00), + (49, 0, 0x00), + (57, 0, 0x00), + (64, 0, 0x01), + ], + // 1 + [ + (0, 48, 0x02), + (0, 49, 0x02), + (0, 50, 0x02), + (0, 97, 0x02), + (0, 99, 0x02), + (0, 101, 0x02), + (0, 105, 0x02), + (0, 111, 0x02), + (0, 115, 0x02), + (0, 116, 0x02), + (13, 0, 0x00), + (14, 0, 0x00), + (17, 0, 0x00), + (18, 0, 0x00), + (20, 0, 0x00), + (21, 0, 0x00), + ], + // 2 + [ + (1, 48, 0x02), + (22, 48, 0x03), + (1, 49, 0x02), + (22, 49, 0x03), + (1, 50, 0x02), + (22, 50, 0x03), + (1, 97, 0x02), + (22, 97, 0x03), + (1, 99, 0x02), + (22, 99, 0x03), + (1, 101, 0x02), + (22, 101, 0x03), + (1, 105, 0x02), + (22, 105, 0x03), + (1, 111, 0x02), + (22, 111, 0x03), + ], + // 3 + [ + (2, 48, 0x02), + (9, 48, 0x02), + (23, 48, 0x02), + (40, 48, 0x03), + (2, 49, 0x02), + (9, 49, 0x02), + (23, 49, 0x02), + (40, 49, 0x03), + (2, 50, 0x02), + (9, 50, 0x02), + (23, 50, 0x02), + (40, 50, 0x03), + (2, 97, 0x02), + (9, 97, 0x02), + (23, 97, 0x02), + (40, 97, 0x03), + ], + // 4 + [ + (3, 48, 0x02), + (6, 48, 0x02), + (10, 48, 0x02), + (15, 48, 0x02), + (24, 48, 0x02), + (31, 48, 0x02), + (41, 48, 0x02), + (56, 48, 0x03), + (3, 49, 0x02), + (6, 49, 0x02), + (10, 49, 0x02), + (15, 49, 0x02), + (24, 49, 0x02), + (31, 49, 0x02), + (41, 49, 0x02), + (56, 49, 0x03), + ], + // 5 + [ + (3, 50, 0x02), + (6, 50, 0x02), + (10, 50, 0x02), + (15, 50, 0x02), + (24, 50, 0x02), + (31, 50, 0x02), + (41, 50, 0x02), + (56, 50, 0x03), + (3, 97, 0x02), + (6, 97, 0x02), + (10, 97, 0x02), + (15, 97, 0x02), + (24, 97, 0x02), + (31, 97, 0x02), + (41, 97, 0x02), + (56, 97, 0x03), + ], + // 6 + [ + (2, 99, 0x02), + (9, 99, 0x02), + (23, 99, 0x02), + (40, 99, 0x03), + (2, 101, 0x02), + (9, 101, 0x02), + (23, 101, 0x02), + (40, 101, 0x03), + (2, 105, 0x02), + (9, 105, 0x02), + (23, 105, 0x02), + (40, 105, 0x03), + (2, 111, 0x02), + (9, 111, 0x02), + (23, 111, 0x02), + (40, 111, 0x03), + ], + // 7 + [ + (3, 99, 0x02), + (6, 99, 0x02), + (10, 99, 0x02), + (15, 99, 0x02), + (24, 99, 0x02), + (31, 99, 0x02), + (41, 99, 0x02), + (56, 99, 0x03), + (3, 101, 0x02), + (6, 101, 0x02), + (10, 101, 0x02), + (15, 101, 0x02), + (24, 101, 0x02), + (31, 101, 0x02), + (41, 101, 0x02), + (56, 101, 0x03), + ], + // 8 + [ + (3, 105, 0x02), + (6, 105, 0x02), + (10, 105, 0x02), + (15, 105, 0x02), + (24, 105, 0x02), + (31, 105, 0x02), + (41, 105, 0x02), + (56, 105, 0x03), + (3, 111, 0x02), + (6, 111, 0x02), + (10, 111, 0x02), + (15, 111, 0x02), + (24, 111, 0x02), + (31, 111, 0x02), + (41, 111, 0x02), + (56, 111, 0x03), + ], + // 9 + [ + (1, 115, 0x02), + (22, 115, 0x03), + (1, 116, 0x02), + (22, 116, 0x03), + (0, 32, 0x02), + (0, 37, 0x02), + (0, 45, 0x02), + (0, 46, 0x02), + (0, 47, 0x02), + (0, 51, 0x02), + (0, 52, 0x02), + (0, 53, 0x02), + (0, 54, 0x02), + (0, 55, 0x02), + (0, 56, 0x02), + (0, 57, 0x02), + ], + // 10 + [ + (2, 115, 0x02), + (9, 115, 0x02), + (23, 115, 0x02), + (40, 115, 0x03), + (2, 116, 0x02), + (9, 116, 0x02), + (23, 116, 0x02), + (40, 116, 0x03), + (1, 32, 0x02), + (22, 32, 0x03), + (1, 37, 0x02), + (22, 37, 0x03), + (1, 45, 0x02), + (22, 45, 0x03), + (1, 46, 0x02), + (22, 46, 0x03), + ], + // 11 + [ + (3, 115, 0x02), + (6, 115, 0x02), + (10, 115, 0x02), + (15, 115, 0x02), + (24, 115, 0x02), + (31, 115, 0x02), + (41, 115, 0x02), + (56, 115, 0x03), + (3, 116, 0x02), + (6, 116, 0x02), + (10, 116, 0x02), + (15, 116, 0x02), + (24, 116, 0x02), + (31, 116, 0x02), + (41, 116, 0x02), + (56, 116, 0x03), + ], + // 12 + [ + (2, 32, 0x02), + (9, 32, 0x02), + (23, 32, 0x02), + (40, 32, 0x03), + (2, 37, 0x02), + (9, 37, 0x02), + (23, 37, 0x02), + (40, 37, 0x03), + (2, 45, 0x02), + (9, 45, 0x02), + (23, 45, 0x02), + (40, 45, 0x03), + (2, 46, 0x02), + (9, 46, 0x02), + (23, 46, 0x02), + (40, 46, 0x03), + ], + // 13 + [ + (3, 32, 0x02), + (6, 32, 0x02), + (10, 32, 0x02), + (15, 32, 0x02), + (24, 32, 0x02), + (31, 32, 0x02), + (41, 32, 0x02), + (56, 32, 0x03), + (3, 37, 0x02), + (6, 37, 0x02), + (10, 37, 0x02), + (15, 37, 0x02), + (24, 37, 0x02), + (31, 37, 0x02), + (41, 37, 0x02), + (56, 37, 0x03), + ], + // 14 + [ + (3, 45, 0x02), + (6, 45, 0x02), + (10, 45, 0x02), + (15, 45, 0x02), + (24, 45, 0x02), + (31, 45, 0x02), + (41, 45, 0x02), + (56, 45, 0x03), + (3, 46, 0x02), + (6, 46, 0x02), + (10, 46, 0x02), + (15, 46, 0x02), + (24, 46, 0x02), + (31, 46, 0x02), + (41, 46, 0x02), + (56, 46, 0x03), + ], + // 15 + [ + (1, 47, 0x02), + (22, 47, 0x03), + (1, 51, 0x02), + (22, 51, 0x03), + (1, 52, 0x02), + (22, 52, 0x03), + (1, 53, 0x02), + (22, 53, 0x03), + (1, 54, 0x02), + (22, 54, 0x03), + (1, 55, 0x02), + (22, 55, 0x03), + (1, 56, 0x02), + (22, 56, 0x03), + (1, 57, 0x02), + (22, 57, 0x03), + ], + // 16 + [ + (2, 47, 0x02), + (9, 47, 0x02), + (23, 47, 0x02), + (40, 47, 0x03), + (2, 51, 0x02), + (9, 51, 0x02), + (23, 51, 0x02), + (40, 51, 0x03), + (2, 52, 0x02), + (9, 52, 0x02), + (23, 52, 0x02), + (40, 52, 0x03), + (2, 53, 0x02), + (9, 53, 0x02), + (23, 53, 0x02), + (40, 53, 0x03), + ], + // 17 + [ + (3, 47, 0x02), + (6, 47, 0x02), + (10, 47, 0x02), + (15, 47, 0x02), + (24, 47, 0x02), + (31, 47, 0x02), + (41, 47, 0x02), + (56, 47, 0x03), + (3, 51, 0x02), + (6, 51, 0x02), + (10, 51, 0x02), + (15, 51, 0x02), + (24, 51, 0x02), + (31, 51, 0x02), + (41, 51, 0x02), + (56, 51, 0x03), + ], + // 18 + [ + (3, 52, 0x02), + (6, 52, 0x02), + (10, 52, 0x02), + (15, 52, 0x02), + (24, 52, 0x02), + (31, 52, 0x02), + (41, 52, 0x02), + (56, 52, 0x03), + (3, 53, 0x02), + (6, 53, 0x02), + (10, 53, 0x02), + (15, 53, 0x02), + (24, 53, 0x02), + (31, 53, 0x02), + (41, 53, 0x02), + (56, 53, 0x03), + ], + // 19 + [ + (2, 54, 0x02), + (9, 54, 0x02), + (23, 54, 0x02), + (40, 54, 0x03), + (2, 55, 0x02), + (9, 55, 0x02), + (23, 55, 0x02), + (40, 55, 0x03), + (2, 56, 0x02), + (9, 56, 0x02), + (23, 56, 0x02), + (40, 56, 0x03), + (2, 57, 0x02), + (9, 57, 0x02), + (23, 57, 0x02), + (40, 57, 0x03), + ], + // 20 + [ + (3, 54, 0x02), + (6, 54, 0x02), + (10, 54, 0x02), + (15, 54, 0x02), + (24, 54, 0x02), + (31, 54, 0x02), + (41, 54, 0x02), + (56, 54, 0x03), + (3, 55, 0x02), + (6, 55, 0x02), + (10, 55, 0x02), + (15, 55, 0x02), + (24, 55, 0x02), + (31, 55, 0x02), + (41, 55, 0x02), + (56, 55, 0x03), + ], + // 21 + [ + (3, 56, 0x02), + (6, 56, 0x02), + (10, 56, 0x02), + (15, 56, 0x02), + (24, 56, 0x02), + (31, 56, 0x02), + (41, 56, 0x02), + (56, 56, 0x03), + (3, 57, 0x02), + (6, 57, 0x02), + (10, 57, 0x02), + (15, 57, 0x02), + (24, 57, 0x02), + (31, 57, 0x02), + (41, 57, 0x02), + (56, 57, 0x03), + ], + // 22 + [ + (26, 0, 0x00), + (27, 0, 0x00), + (29, 0, 0x00), + (30, 0, 0x00), + (33, 0, 0x00), + (34, 0, 0x00), + (36, 0, 0x00), + (37, 0, 0x00), + (43, 0, 0x00), + (46, 0, 0x00), + (50, 0, 0x00), + (53, 0, 0x00), + (58, 0, 0x00), + (61, 0, 0x00), + (65, 0, 0x00), + (68, 0, 0x01), + ], + // 23 + [ + (0, 61, 0x02), + (0, 65, 0x02), + (0, 95, 0x02), + (0, 98, 0x02), + (0, 100, 0x02), + (0, 102, 0x02), + (0, 103, 0x02), + (0, 104, 0x02), + (0, 108, 0x02), + (0, 109, 0x02), + (0, 110, 0x02), + (0, 112, 0x02), + (0, 114, 0x02), + (0, 117, 0x02), + (38, 0, 0x00), + (39, 0, 0x00), + ], + // 24 + [ + (1, 61, 0x02), + (22, 61, 0x03), + (1, 65, 0x02), + (22, 65, 0x03), + (1, 95, 0x02), + (22, 95, 0x03), + (1, 98, 0x02), + (22, 98, 0x03), + (1, 100, 0x02), + (22, 100, 0x03), + (1, 102, 0x02), + (22, 102, 0x03), + (1, 103, 0x02), + (22, 103, 0x03), + (1, 104, 0x02), + (22, 104, 0x03), + ], + // 25 + [ + (2, 61, 0x02), + (9, 61, 0x02), + (23, 61, 0x02), + (40, 61, 0x03), + (2, 65, 0x02), + (9, 65, 0x02), + (23, 65, 0x02), + (40, 65, 0x03), + (2, 95, 0x02), + (9, 95, 0x02), + (23, 95, 0x02), + (40, 95, 0x03), + (2, 98, 0x02), + (9, 98, 0x02), + (23, 98, 0x02), + (40, 98, 0x03), + ], + // 26 + [ + (3, 61, 0x02), + (6, 61, 0x02), + (10, 61, 0x02), + (15, 61, 0x02), + (24, 61, 0x02), + (31, 61, 0x02), + (41, 61, 0x02), + (56, 61, 0x03), + (3, 65, 0x02), + (6, 65, 0x02), + (10, 65, 0x02), + (15, 65, 0x02), + (24, 65, 0x02), + (31, 65, 0x02), + (41, 65, 0x02), + (56, 65, 0x03), + ], + // 27 + [ + (3, 95, 0x02), + (6, 95, 0x02), + (10, 95, 0x02), + (15, 95, 0x02), + (24, 95, 0x02), + (31, 95, 0x02), + (41, 95, 0x02), + (56, 95, 0x03), + (3, 98, 0x02), + (6, 98, 0x02), + (10, 98, 0x02), + (15, 98, 0x02), + (24, 98, 0x02), + (31, 98, 0x02), + (41, 98, 0x02), + (56, 98, 0x03), + ], + // 28 + [ + (2, 100, 0x02), + (9, 100, 0x02), + (23, 100, 0x02), + (40, 100, 0x03), + (2, 102, 0x02), + (9, 102, 0x02), + (23, 102, 0x02), + (40, 102, 0x03), + (2, 103, 0x02), + (9, 103, 0x02), + (23, 103, 0x02), + (40, 103, 0x03), + (2, 104, 0x02), + (9, 104, 0x02), + (23, 104, 0x02), + (40, 104, 0x03), + ], + // 29 + [ + (3, 100, 0x02), + (6, 100, 0x02), + (10, 100, 0x02), + (15, 100, 0x02), + (24, 100, 0x02), + (31, 100, 0x02), + (41, 100, 0x02), + (56, 100, 0x03), + (3, 102, 0x02), + (6, 102, 0x02), + (10, 102, 0x02), + (15, 102, 0x02), + (24, 102, 0x02), + (31, 102, 0x02), + (41, 102, 0x02), + (56, 102, 0x03), + ], + // 30 + [ + (3, 103, 0x02), + (6, 103, 0x02), + (10, 103, 0x02), + (15, 103, 0x02), + (24, 103, 0x02), + (31, 103, 0x02), + (41, 103, 0x02), + (56, 103, 0x03), + (3, 104, 0x02), + (6, 104, 0x02), + (10, 104, 0x02), + (15, 104, 0x02), + (24, 104, 0x02), + (31, 104, 0x02), + (41, 104, 0x02), + (56, 104, 0x03), + ], + // 31 + [ + (1, 108, 0x02), + (22, 108, 0x03), + (1, 109, 0x02), + (22, 109, 0x03), + (1, 110, 0x02), + (22, 110, 0x03), + (1, 112, 0x02), + (22, 112, 0x03), + (1, 114, 0x02), + (22, 114, 0x03), + (1, 117, 0x02), + (22, 117, 0x03), + (0, 58, 0x02), + (0, 66, 0x02), + (0, 67, 0x02), + (0, 68, 0x02), + ], + // 32 + [ + (2, 108, 0x02), + (9, 108, 0x02), + (23, 108, 0x02), + (40, 108, 0x03), + (2, 109, 0x02), + (9, 109, 0x02), + (23, 109, 0x02), + (40, 109, 0x03), + (2, 110, 0x02), + (9, 110, 0x02), + (23, 110, 0x02), + (40, 110, 0x03), + (2, 112, 0x02), + (9, 112, 0x02), + (23, 112, 0x02), + (40, 112, 0x03), + ], + // 33 + [ + (3, 108, 0x02), + (6, 108, 0x02), + (10, 108, 0x02), + (15, 108, 0x02), + (24, 108, 0x02), + (31, 108, 0x02), + (41, 108, 0x02), + (56, 108, 0x03), + (3, 109, 0x02), + (6, 109, 0x02), + (10, 109, 0x02), + (15, 109, 0x02), + (24, 109, 0x02), + (31, 109, 0x02), + (41, 109, 0x02), + (56, 109, 0x03), + ], + // 34 + [ + (3, 110, 0x02), + (6, 110, 0x02), + (10, 110, 0x02), + (15, 110, 0x02), + (24, 110, 0x02), + (31, 110, 0x02), + (41, 110, 0x02), + (56, 110, 0x03), + (3, 112, 0x02), + (6, 112, 0x02), + (10, 112, 0x02), + (15, 112, 0x02), + (24, 112, 0x02), + (31, 112, 0x02), + (41, 112, 0x02), + (56, 112, 0x03), + ], + // 35 + [ + (2, 114, 0x02), + (9, 114, 0x02), + (23, 114, 0x02), + (40, 114, 0x03), + (2, 117, 0x02), + (9, 117, 0x02), + (23, 117, 0x02), + (40, 117, 0x03), + (1, 58, 0x02), + (22, 58, 0x03), + (1, 66, 0x02), + (22, 66, 0x03), + (1, 67, 0x02), + (22, 67, 0x03), + (1, 68, 0x02), + (22, 68, 0x03), + ], + // 36 + [ + (3, 114, 0x02), + (6, 114, 0x02), + (10, 114, 0x02), + (15, 114, 0x02), + (24, 114, 0x02), + (31, 114, 0x02), + (41, 114, 0x02), + (56, 114, 0x03), + (3, 117, 0x02), + (6, 117, 0x02), + (10, 117, 0x02), + (15, 117, 0x02), + (24, 117, 0x02), + (31, 117, 0x02), + (41, 117, 0x02), + (56, 117, 0x03), + ], + // 37 + [ + (2, 58, 0x02), + (9, 58, 0x02), + (23, 58, 0x02), + (40, 58, 0x03), + (2, 66, 0x02), + (9, 66, 0x02), + (23, 66, 0x02), + (40, 66, 0x03), + (2, 67, 0x02), + (9, 67, 0x02), + (23, 67, 0x02), + (40, 67, 0x03), + (2, 68, 0x02), + (9, 68, 0x02), + (23, 68, 0x02), + (40, 68, 0x03), + ], + // 38 + [ + (3, 58, 0x02), + (6, 58, 0x02), + (10, 58, 0x02), + (15, 58, 0x02), + (24, 58, 0x02), + (31, 58, 0x02), + (41, 58, 0x02), + (56, 58, 0x03), + (3, 66, 0x02), + (6, 66, 0x02), + (10, 66, 0x02), + (15, 66, 0x02), + (24, 66, 0x02), + (31, 66, 0x02), + (41, 66, 0x02), + (56, 66, 0x03), + ], + // 39 + [ + (3, 67, 0x02), + (6, 67, 0x02), + (10, 67, 0x02), + (15, 67, 0x02), + (24, 67, 0x02), + (31, 67, 0x02), + (41, 67, 0x02), + (56, 67, 0x03), + (3, 68, 0x02), + (6, 68, 0x02), + (10, 68, 0x02), + (15, 68, 0x02), + (24, 68, 0x02), + (31, 68, 0x02), + (41, 68, 0x02), + (56, 68, 0x03), + ], + // 40 + [ + (44, 0, 0x00), + (45, 0, 0x00), + (47, 0, 0x00), + (48, 0, 0x00), + (51, 0, 0x00), + (52, 0, 0x00), + (54, 0, 0x00), + (55, 0, 0x00), + (59, 0, 0x00), + (60, 0, 0x00), + (62, 0, 0x00), + (63, 0, 0x00), + (66, 0, 0x00), + (67, 0, 0x00), + (69, 0, 0x00), + (72, 0, 0x01), + ], + // 41 + [ + (0, 69, 0x02), + (0, 70, 0x02), + (0, 71, 0x02), + (0, 72, 0x02), + (0, 73, 0x02), + (0, 74, 0x02), + (0, 75, 0x02), + (0, 76, 0x02), + (0, 77, 0x02), + (0, 78, 0x02), + (0, 79, 0x02), + (0, 80, 0x02), + (0, 81, 0x02), + (0, 82, 0x02), + (0, 83, 0x02), + (0, 84, 0x02), + ], + // 42 + [ + (1, 69, 0x02), + (22, 69, 0x03), + (1, 70, 0x02), + (22, 70, 0x03), + (1, 71, 0x02), + (22, 71, 0x03), + (1, 72, 0x02), + (22, 72, 0x03), + (1, 73, 0x02), + (22, 73, 0x03), + (1, 74, 0x02), + (22, 74, 0x03), + (1, 75, 0x02), + (22, 75, 0x03), + (1, 76, 0x02), + (22, 76, 0x03), + ], + // 43 + [ + (2, 69, 0x02), + (9, 69, 0x02), + (23, 69, 0x02), + (40, 69, 0x03), + (2, 70, 0x02), + (9, 70, 0x02), + (23, 70, 0x02), + (40, 70, 0x03), + (2, 71, 0x02), + (9, 71, 0x02), + (23, 71, 0x02), + (40, 71, 0x03), + (2, 72, 0x02), + (9, 72, 0x02), + (23, 72, 0x02), + (40, 72, 0x03), + ], + // 44 + [ + (3, 69, 0x02), + (6, 69, 0x02), + (10, 69, 0x02), + (15, 69, 0x02), + (24, 69, 0x02), + (31, 69, 0x02), + (41, 69, 0x02), + (56, 69, 0x03), + (3, 70, 0x02), + (6, 70, 0x02), + (10, 70, 0x02), + (15, 70, 0x02), + (24, 70, 0x02), + (31, 70, 0x02), + (41, 70, 0x02), + (56, 70, 0x03), + ], + // 45 + [ + (3, 71, 0x02), + (6, 71, 0x02), + (10, 71, 0x02), + (15, 71, 0x02), + (24, 71, 0x02), + (31, 71, 0x02), + (41, 71, 0x02), + (56, 71, 0x03), + (3, 72, 0x02), + (6, 72, 0x02), + (10, 72, 0x02), + (15, 72, 0x02), + (24, 72, 0x02), + (31, 72, 0x02), + (41, 72, 0x02), + (56, 72, 0x03), + ], + // 46 + [ + (2, 73, 0x02), + (9, 73, 0x02), + (23, 73, 0x02), + (40, 73, 0x03), + (2, 74, 0x02), + (9, 74, 0x02), + (23, 74, 0x02), + (40, 74, 0x03), + (2, 75, 0x02), + (9, 75, 0x02), + (23, 75, 0x02), + (40, 75, 0x03), + (2, 76, 0x02), + (9, 76, 0x02), + (23, 76, 0x02), + (40, 76, 0x03), + ], + // 47 + [ + (3, 73, 0x02), + (6, 73, 0x02), + (10, 73, 0x02), + (15, 73, 0x02), + (24, 73, 0x02), + (31, 73, 0x02), + (41, 73, 0x02), + (56, 73, 0x03), + (3, 74, 0x02), + (6, 74, 0x02), + (10, 74, 0x02), + (15, 74, 0x02), + (24, 74, 0x02), + (31, 74, 0x02), + (41, 74, 0x02), + (56, 74, 0x03), + ], + // 48 + [ + (3, 75, 0x02), + (6, 75, 0x02), + (10, 75, 0x02), + (15, 75, 0x02), + (24, 75, 0x02), + (31, 75, 0x02), + (41, 75, 0x02), + (56, 75, 0x03), + (3, 76, 0x02), + (6, 76, 0x02), + (10, 76, 0x02), + (15, 76, 0x02), + (24, 76, 0x02), + (31, 76, 0x02), + (41, 76, 0x02), + (56, 76, 0x03), + ], + // 49 + [ + (1, 77, 0x02), + (22, 77, 0x03), + (1, 78, 0x02), + (22, 78, 0x03), + (1, 79, 0x02), + (22, 79, 0x03), + (1, 80, 0x02), + (22, 80, 0x03), + (1, 81, 0x02), + (22, 81, 0x03), + (1, 82, 0x02), + (22, 82, 0x03), + (1, 83, 0x02), + (22, 83, 0x03), + (1, 84, 0x02), + (22, 84, 0x03), + ], + // 50 + [ + (2, 77, 0x02), + (9, 77, 0x02), + (23, 77, 0x02), + (40, 77, 0x03), + (2, 78, 0x02), + (9, 78, 0x02), + (23, 78, 0x02), + (40, 78, 0x03), + (2, 79, 0x02), + (9, 79, 0x02), + (23, 79, 0x02), + (40, 79, 0x03), + (2, 80, 0x02), + (9, 80, 0x02), + (23, 80, 0x02), + (40, 80, 0x03), + ], + // 51 + [ + (3, 77, 0x02), + (6, 77, 0x02), + (10, 77, 0x02), + (15, 77, 0x02), + (24, 77, 0x02), + (31, 77, 0x02), + (41, 77, 0x02), + (56, 77, 0x03), + (3, 78, 0x02), + (6, 78, 0x02), + (10, 78, 0x02), + (15, 78, 0x02), + (24, 78, 0x02), + (31, 78, 0x02), + (41, 78, 0x02), + (56, 78, 0x03), + ], + // 52 + [ + (3, 79, 0x02), + (6, 79, 0x02), + (10, 79, 0x02), + (15, 79, 0x02), + (24, 79, 0x02), + (31, 79, 0x02), + (41, 79, 0x02), + (56, 79, 0x03), + (3, 80, 0x02), + (6, 80, 0x02), + (10, 80, 0x02), + (15, 80, 0x02), + (24, 80, 0x02), + (31, 80, 0x02), + (41, 80, 0x02), + (56, 80, 0x03), + ], + // 53 + [ + (2, 81, 0x02), + (9, 81, 0x02), + (23, 81, 0x02), + (40, 81, 0x03), + (2, 82, 0x02), + (9, 82, 0x02), + (23, 82, 0x02), + (40, 82, 0x03), + (2, 83, 0x02), + (9, 83, 0x02), + (23, 83, 0x02), + (40, 83, 0x03), + (2, 84, 0x02), + (9, 84, 0x02), + (23, 84, 0x02), + (40, 84, 0x03), + ], + // 54 + [ + (3, 81, 0x02), + (6, 81, 0x02), + (10, 81, 0x02), + (15, 81, 0x02), + (24, 81, 0x02), + (31, 81, 0x02), + (41, 81, 0x02), + (56, 81, 0x03), + (3, 82, 0x02), + (6, 82, 0x02), + (10, 82, 0x02), + (15, 82, 0x02), + (24, 82, 0x02), + (31, 82, 0x02), + (41, 82, 0x02), + (56, 82, 0x03), + ], + // 55 + [ + (3, 83, 0x02), + (6, 83, 0x02), + (10, 83, 0x02), + (15, 83, 0x02), + (24, 83, 0x02), + (31, 83, 0x02), + (41, 83, 0x02), + (56, 83, 0x03), + (3, 84, 0x02), + (6, 84, 0x02), + (10, 84, 0x02), + (15, 84, 0x02), + (24, 84, 0x02), + (31, 84, 0x02), + (41, 84, 0x02), + (56, 84, 0x03), + ], + // 56 + [ + (0, 85, 0x02), + (0, 86, 0x02), + (0, 87, 0x02), + (0, 89, 0x02), + (0, 106, 0x02), + (0, 107, 0x02), + (0, 113, 0x02), + (0, 118, 0x02), + (0, 119, 0x02), + (0, 120, 0x02), + (0, 121, 0x02), + (0, 122, 0x02), + (70, 0, 0x00), + (71, 0, 0x00), + (73, 0, 0x00), + (74, 0, 0x01), + ], + // 57 + [ + (1, 85, 0x02), + (22, 85, 0x03), + (1, 86, 0x02), + (22, 86, 0x03), + (1, 87, 0x02), + (22, 87, 0x03), + (1, 89, 0x02), + (22, 89, 0x03), + (1, 106, 0x02), + (22, 106, 0x03), + (1, 107, 0x02), + (22, 107, 0x03), + (1, 113, 0x02), + (22, 113, 0x03), + (1, 118, 0x02), + (22, 118, 0x03), + ], + // 58 + [ + (2, 85, 0x02), + (9, 85, 0x02), + (23, 85, 0x02), + (40, 85, 0x03), + (2, 86, 0x02), + (9, 86, 0x02), + (23, 86, 0x02), + (40, 86, 0x03), + (2, 87, 0x02), + (9, 87, 0x02), + (23, 87, 0x02), + (40, 87, 0x03), + (2, 89, 0x02), + (9, 89, 0x02), + (23, 89, 0x02), + (40, 89, 0x03), + ], + // 59 + [ + (3, 85, 0x02), + (6, 85, 0x02), + (10, 85, 0x02), + (15, 85, 0x02), + (24, 85, 0x02), + (31, 85, 0x02), + (41, 85, 0x02), + (56, 85, 0x03), + (3, 86, 0x02), + (6, 86, 0x02), + (10, 86, 0x02), + (15, 86, 0x02), + (24, 86, 0x02), + (31, 86, 0x02), + (41, 86, 0x02), + (56, 86, 0x03), + ], + // 60 + [ + (3, 87, 0x02), + (6, 87, 0x02), + (10, 87, 0x02), + (15, 87, 0x02), + (24, 87, 0x02), + (31, 87, 0x02), + (41, 87, 0x02), + (56, 87, 0x03), + (3, 89, 0x02), + (6, 89, 0x02), + (10, 89, 0x02), + (15, 89, 0x02), + (24, 89, 0x02), + (31, 89, 0x02), + (41, 89, 0x02), + (56, 89, 0x03), + ], + // 61 + [ + (2, 106, 0x02), + (9, 106, 0x02), + (23, 106, 0x02), + (40, 106, 0x03), + (2, 107, 0x02), + (9, 107, 0x02), + (23, 107, 0x02), + (40, 107, 0x03), + (2, 113, 0x02), + (9, 113, 0x02), + (23, 113, 0x02), + (40, 113, 0x03), + (2, 118, 0x02), + (9, 118, 0x02), + (23, 118, 0x02), + (40, 118, 0x03), + ], + // 62 + [ + (3, 106, 0x02), + (6, 106, 0x02), + (10, 106, 0x02), + (15, 106, 0x02), + (24, 106, 0x02), + (31, 106, 0x02), + (41, 106, 0x02), + (56, 106, 0x03), + (3, 107, 0x02), + (6, 107, 0x02), + (10, 107, 0x02), + (15, 107, 0x02), + (24, 107, 0x02), + (31, 107, 0x02), + (41, 107, 0x02), + (56, 107, 0x03), + ], + // 63 + [ + (3, 113, 0x02), + (6, 113, 0x02), + (10, 113, 0x02), + (15, 113, 0x02), + (24, 113, 0x02), + (31, 113, 0x02), + (41, 113, 0x02), + (56, 113, 0x03), + (3, 118, 0x02), + (6, 118, 0x02), + (10, 118, 0x02), + (15, 118, 0x02), + (24, 118, 0x02), + (31, 118, 0x02), + (41, 118, 0x02), + (56, 118, 0x03), + ], + // 64 + [ + (1, 119, 0x02), + (22, 119, 0x03), + (1, 120, 0x02), + (22, 120, 0x03), + (1, 121, 0x02), + (22, 121, 0x03), + (1, 122, 0x02), + (22, 122, 0x03), + (0, 38, 0x02), + (0, 42, 0x02), + (0, 44, 0x02), + (0, 59, 0x02), + (0, 88, 0x02), + (0, 90, 0x02), + (75, 0, 0x00), + (78, 0, 0x00), + ], + // 65 + [ + (2, 119, 0x02), + (9, 119, 0x02), + (23, 119, 0x02), + (40, 119, 0x03), + (2, 120, 0x02), + (9, 120, 0x02), + (23, 120, 0x02), + (40, 120, 0x03), + (2, 121, 0x02), + (9, 121, 0x02), + (23, 121, 0x02), + (40, 121, 0x03), + (2, 122, 0x02), + (9, 122, 0x02), + (23, 122, 0x02), + (40, 122, 0x03), + ], + // 66 + [ + (3, 119, 0x02), + (6, 119, 0x02), + (10, 119, 0x02), + (15, 119, 0x02), + (24, 119, 0x02), + (31, 119, 0x02), + (41, 119, 0x02), + (56, 119, 0x03), + (3, 120, 0x02), + (6, 120, 0x02), + (10, 120, 0x02), + (15, 120, 0x02), + (24, 120, 0x02), + (31, 120, 0x02), + (41, 120, 0x02), + (56, 120, 0x03), + ], + // 67 + [ + (3, 121, 0x02), + (6, 121, 0x02), + (10, 121, 0x02), + (15, 121, 0x02), + (24, 121, 0x02), + (31, 121, 0x02), + (41, 121, 0x02), + (56, 121, 0x03), + (3, 122, 0x02), + (6, 122, 0x02), + (10, 122, 0x02), + (15, 122, 0x02), + (24, 122, 0x02), + (31, 122, 0x02), + (41, 122, 0x02), + (56, 122, 0x03), + ], + // 68 + [ + (1, 38, 0x02), + (22, 38, 0x03), + (1, 42, 0x02), + (22, 42, 0x03), + (1, 44, 0x02), + (22, 44, 0x03), + (1, 59, 0x02), + (22, 59, 0x03), + (1, 88, 0x02), + (22, 88, 0x03), + (1, 90, 0x02), + (22, 90, 0x03), + (76, 0, 0x00), + (77, 0, 0x00), + (79, 0, 0x00), + (81, 0, 0x00), + ], + // 69 + [ + (2, 38, 0x02), + (9, 38, 0x02), + (23, 38, 0x02), + (40, 38, 0x03), + (2, 42, 0x02), + (9, 42, 0x02), + (23, 42, 0x02), + (40, 42, 0x03), + (2, 44, 0x02), + (9, 44, 0x02), + (23, 44, 0x02), + (40, 44, 0x03), + (2, 59, 0x02), + (9, 59, 0x02), + (23, 59, 0x02), + (40, 59, 0x03), + ], + // 70 + [ + (3, 38, 0x02), + (6, 38, 0x02), + (10, 38, 0x02), + (15, 38, 0x02), + (24, 38, 0x02), + (31, 38, 0x02), + (41, 38, 0x02), + (56, 38, 0x03), + (3, 42, 0x02), + (6, 42, 0x02), + (10, 42, 0x02), + (15, 42, 0x02), + (24, 42, 0x02), + (31, 42, 0x02), + (41, 42, 0x02), + (56, 42, 0x03), + ], + // 71 + [ + (3, 44, 0x02), + (6, 44, 0x02), + (10, 44, 0x02), + (15, 44, 0x02), + (24, 44, 0x02), + (31, 44, 0x02), + (41, 44, 0x02), + (56, 44, 0x03), + (3, 59, 0x02), + (6, 59, 0x02), + (10, 59, 0x02), + (15, 59, 0x02), + (24, 59, 0x02), + (31, 59, 0x02), + (41, 59, 0x02), + (56, 59, 0x03), + ], + // 72 + [ + (2, 88, 0x02), + (9, 88, 0x02), + (23, 88, 0x02), + (40, 88, 0x03), + (2, 90, 0x02), + (9, 90, 0x02), + (23, 90, 0x02), + (40, 90, 0x03), + (0, 33, 0x02), + (0, 34, 0x02), + (0, 40, 0x02), + (0, 41, 0x02), + (0, 63, 0x02), + (80, 0, 0x00), + (82, 0, 0x00), + (84, 0, 0x00), + ], + // 73 + [ + (3, 88, 0x02), + (6, 88, 0x02), + (10, 88, 0x02), + (15, 88, 0x02), + (24, 88, 0x02), + (31, 88, 0x02), + (41, 88, 0x02), + (56, 88, 0x03), + (3, 90, 0x02), + (6, 90, 0x02), + (10, 90, 0x02), + (15, 90, 0x02), + (24, 90, 0x02), + (31, 90, 0x02), + (41, 90, 0x02), + (56, 90, 0x03), + ], + // 74 + [ + (1, 33, 0x02), + (22, 33, 0x03), + (1, 34, 0x02), + (22, 34, 0x03), + (1, 40, 0x02), + (22, 40, 0x03), + (1, 41, 0x02), + (22, 41, 0x03), + (1, 63, 0x02), + (22, 63, 0x03), + (0, 39, 0x02), + (0, 43, 0x02), + (0, 124, 0x02), + (83, 0, 0x00), + (85, 0, 0x00), + (88, 0, 0x00), + ], + // 75 + [ + (2, 33, 0x02), + (9, 33, 0x02), + (23, 33, 0x02), + (40, 33, 0x03), + (2, 34, 0x02), + (9, 34, 0x02), + (23, 34, 0x02), + (40, 34, 0x03), + (2, 40, 0x02), + (9, 40, 0x02), + (23, 40, 0x02), + (40, 40, 0x03), + (2, 41, 0x02), + (9, 41, 0x02), + (23, 41, 0x02), + (40, 41, 0x03), + ], + // 76 + [ + (3, 33, 0x02), + (6, 33, 0x02), + (10, 33, 0x02), + (15, 33, 0x02), + (24, 33, 0x02), + (31, 33, 0x02), + (41, 33, 0x02), + (56, 33, 0x03), + (3, 34, 0x02), + (6, 34, 0x02), + (10, 34, 0x02), + (15, 34, 0x02), + (24, 34, 0x02), + (31, 34, 0x02), + (41, 34, 0x02), + (56, 34, 0x03), + ], + // 77 + [ + (3, 40, 0x02), + (6, 40, 0x02), + (10, 40, 0x02), + (15, 40, 0x02), + (24, 40, 0x02), + (31, 40, 0x02), + (41, 40, 0x02), + (56, 40, 0x03), + (3, 41, 0x02), + (6, 41, 0x02), + (10, 41, 0x02), + (15, 41, 0x02), + (24, 41, 0x02), + (31, 41, 0x02), + (41, 41, 0x02), + (56, 41, 0x03), + ], + // 78 + [ + (2, 63, 0x02), + (9, 63, 0x02), + (23, 63, 0x02), + (40, 63, 0x03), + (1, 39, 0x02), + (22, 39, 0x03), + (1, 43, 0x02), + (22, 43, 0x03), + (1, 124, 0x02), + (22, 124, 0x03), + (0, 35, 0x02), + (0, 62, 0x02), + (86, 0, 0x00), + (87, 0, 0x00), + (89, 0, 0x00), + (90, 0, 0x00), + ], + // 79 + [ + (3, 63, 0x02), + (6, 63, 0x02), + (10, 63, 0x02), + (15, 63, 0x02), + (24, 63, 0x02), + (31, 63, 0x02), + (41, 63, 0x02), + (56, 63, 0x03), + (2, 39, 0x02), + (9, 39, 0x02), + (23, 39, 0x02), + (40, 39, 0x03), + (2, 43, 0x02), + (9, 43, 0x02), + (23, 43, 0x02), + (40, 43, 0x03), + ], + // 80 + [ + (3, 39, 0x02), + (6, 39, 0x02), + (10, 39, 0x02), + (15, 39, 0x02), + (24, 39, 0x02), + (31, 39, 0x02), + (41, 39, 0x02), + (56, 39, 0x03), + (3, 43, 0x02), + (6, 43, 0x02), + (10, 43, 0x02), + (15, 43, 0x02), + (24, 43, 0x02), + (31, 43, 0x02), + (41, 43, 0x02), + (56, 43, 0x03), + ], + // 81 + [ + (2, 124, 0x02), + (9, 124, 0x02), + (23, 124, 0x02), + (40, 124, 0x03), + (1, 35, 0x02), + (22, 35, 0x03), + (1, 62, 0x02), + (22, 62, 0x03), + (0, 0, 0x02), + (0, 36, 0x02), + (0, 64, 0x02), + (0, 91, 0x02), + (0, 93, 0x02), + (0, 126, 0x02), + (91, 0, 0x00), + (92, 0, 0x00), + ], + // 82 + [ + (3, 124, 0x02), + (6, 124, 0x02), + (10, 124, 0x02), + (15, 124, 0x02), + (24, 124, 0x02), + (31, 124, 0x02), + (41, 124, 0x02), + (56, 124, 0x03), + (2, 35, 0x02), + (9, 35, 0x02), + (23, 35, 0x02), + (40, 35, 0x03), + (2, 62, 0x02), + (9, 62, 0x02), + (23, 62, 0x02), + (40, 62, 0x03), + ], + // 83 + [ + (3, 35, 0x02), + (6, 35, 0x02), + (10, 35, 0x02), + (15, 35, 0x02), + (24, 35, 0x02), + (31, 35, 0x02), + (41, 35, 0x02), + (56, 35, 0x03), + (3, 62, 0x02), + (6, 62, 0x02), + (10, 62, 0x02), + (15, 62, 0x02), + (24, 62, 0x02), + (31, 62, 0x02), + (41, 62, 0x02), + (56, 62, 0x03), + ], + // 84 + [ + (1, 0, 0x02), + (22, 0, 0x03), + (1, 36, 0x02), + (22, 36, 0x03), + (1, 64, 0x02), + (22, 64, 0x03), + (1, 91, 0x02), + (22, 91, 0x03), + (1, 93, 0x02), + (22, 93, 0x03), + (1, 126, 0x02), + (22, 126, 0x03), + (0, 94, 0x02), + (0, 125, 0x02), + (93, 0, 0x00), + (94, 0, 0x00), + ], + // 85 + [ + (2, 0, 0x02), + (9, 0, 0x02), + (23, 0, 0x02), + (40, 0, 0x03), + (2, 36, 0x02), + (9, 36, 0x02), + (23, 36, 0x02), + (40, 36, 0x03), + (2, 64, 0x02), + (9, 64, 0x02), + (23, 64, 0x02), + (40, 64, 0x03), + (2, 91, 0x02), + (9, 91, 0x02), + (23, 91, 0x02), + (40, 91, 0x03), + ], + // 86 + [ + (3, 0, 0x02), + (6, 0, 0x02), + (10, 0, 0x02), + (15, 0, 0x02), + (24, 0, 0x02), + (31, 0, 0x02), + (41, 0, 0x02), + (56, 0, 0x03), + (3, 36, 0x02), + (6, 36, 0x02), + (10, 36, 0x02), + (15, 36, 0x02), + (24, 36, 0x02), + (31, 36, 0x02), + (41, 36, 0x02), + (56, 36, 0x03), + ], + // 87 + [ + (3, 64, 0x02), + (6, 64, 0x02), + (10, 64, 0x02), + (15, 64, 0x02), + (24, 64, 0x02), + (31, 64, 0x02), + (41, 64, 0x02), + (56, 64, 0x03), + (3, 91, 0x02), + (6, 91, 0x02), + (10, 91, 0x02), + (15, 91, 0x02), + (24, 91, 0x02), + (31, 91, 0x02), + (41, 91, 0x02), + (56, 91, 0x03), + ], + // 88 + [ + (2, 93, 0x02), + (9, 93, 0x02), + (23, 93, 0x02), + (40, 93, 0x03), + (2, 126, 0x02), + (9, 126, 0x02), + (23, 126, 0x02), + (40, 126, 0x03), + (1, 94, 0x02), + (22, 94, 0x03), + (1, 125, 0x02), + (22, 125, 0x03), + (0, 60, 0x02), + (0, 96, 0x02), + (0, 123, 0x02), + (95, 0, 0x00), + ], + // 89 + [ + (3, 93, 0x02), + (6, 93, 0x02), + (10, 93, 0x02), + (15, 93, 0x02), + (24, 93, 0x02), + (31, 93, 0x02), + (41, 93, 0x02), + (56, 93, 0x03), + (3, 126, 0x02), + (6, 126, 0x02), + (10, 126, 0x02), + (15, 126, 0x02), + (24, 126, 0x02), + (31, 126, 0x02), + (41, 126, 0x02), + (56, 126, 0x03), + ], + // 90 + [ + (2, 94, 0x02), + (9, 94, 0x02), + (23, 94, 0x02), + (40, 94, 0x03), + (2, 125, 0x02), + (9, 125, 0x02), + (23, 125, 0x02), + (40, 125, 0x03), + (1, 60, 0x02), + (22, 60, 0x03), + (1, 96, 0x02), + (22, 96, 0x03), + (1, 123, 0x02), + (22, 123, 0x03), + (96, 0, 0x00), + (110, 0, 0x00), + ], + // 91 + [ + (3, 94, 0x02), + (6, 94, 0x02), + (10, 94, 0x02), + (15, 94, 0x02), + (24, 94, 0x02), + (31, 94, 0x02), + (41, 94, 0x02), + (56, 94, 0x03), + (3, 125, 0x02), + (6, 125, 0x02), + (10, 125, 0x02), + (15, 125, 0x02), + (24, 125, 0x02), + (31, 125, 0x02), + (41, 125, 0x02), + (56, 125, 0x03), + ], + // 92 + [ + (2, 60, 0x02), + (9, 60, 0x02), + (23, 60, 0x02), + (40, 60, 0x03), + (2, 96, 0x02), + (9, 96, 0x02), + (23, 96, 0x02), + (40, 96, 0x03), + (2, 123, 0x02), + (9, 123, 0x02), + (23, 123, 0x02), + (40, 123, 0x03), + (97, 0, 0x00), + (101, 0, 0x00), + (111, 0, 0x00), + (133, 0, 0x00), + ], + // 93 + [ + (3, 60, 0x02), + (6, 60, 0x02), + (10, 60, 0x02), + (15, 60, 0x02), + (24, 60, 0x02), + (31, 60, 0x02), + (41, 60, 0x02), + (56, 60, 0x03), + (3, 96, 0x02), + (6, 96, 0x02), + (10, 96, 0x02), + (15, 96, 0x02), + (24, 96, 0x02), + (31, 96, 0x02), + (41, 96, 0x02), + (56, 96, 0x03), + ], + // 94 + [ + (3, 123, 0x02), + (6, 123, 0x02), + (10, 123, 0x02), + (15, 123, 0x02), + (24, 123, 0x02), + (31, 123, 0x02), + (41, 123, 0x02), + (56, 123, 0x03), + (98, 0, 0x00), + (99, 0, 0x00), + (102, 0, 0x00), + (105, 0, 0x00), + (112, 0, 0x00), + (119, 0, 0x00), + (134, 0, 0x00), + (153, 0, 0x00), + ], + // 95 + [ + (0, 92, 0x02), + (0, 195, 0x02), + (0, 208, 0x02), + (100, 0, 0x00), + (103, 0, 0x00), + (104, 0, 0x00), + (106, 0, 0x00), + (107, 0, 0x00), + (113, 0, 0x00), + (116, 0, 0x00), + (120, 0, 0x00), + (126, 0, 0x00), + (135, 0, 0x00), + (142, 0, 0x00), + (154, 0, 0x00), + (169, 0, 0x00), + ], + // 96 + [ + (1, 92, 0x02), + (22, 92, 0x03), + (1, 195, 0x02), + (22, 195, 0x03), + (1, 208, 0x02), + (22, 208, 0x03), + (0, 128, 0x02), + (0, 130, 0x02), + (0, 131, 0x02), + (0, 162, 0x02), + (0, 184, 0x02), + (0, 194, 0x02), + (0, 224, 0x02), + (0, 226, 0x02), + (108, 0, 0x00), + (109, 0, 0x00), + ], + // 97 + [ + (2, 92, 0x02), + (9, 92, 0x02), + (23, 92, 0x02), + (40, 92, 0x03), + (2, 195, 0x02), + (9, 195, 0x02), + (23, 195, 0x02), + (40, 195, 0x03), + (2, 208, 0x02), + (9, 208, 0x02), + (23, 208, 0x02), + (40, 208, 0x03), + (1, 128, 0x02), + (22, 128, 0x03), + (1, 130, 0x02), + (22, 130, 0x03), + ], + // 98 + [ + (3, 92, 0x02), + (6, 92, 0x02), + (10, 92, 0x02), + (15, 92, 0x02), + (24, 92, 0x02), + (31, 92, 0x02), + (41, 92, 0x02), + (56, 92, 0x03), + (3, 195, 0x02), + (6, 195, 0x02), + (10, 195, 0x02), + (15, 195, 0x02), + (24, 195, 0x02), + (31, 195, 0x02), + (41, 195, 0x02), + (56, 195, 0x03), + ], + // 99 + [ + (3, 208, 0x02), + (6, 208, 0x02), + (10, 208, 0x02), + (15, 208, 0x02), + (24, 208, 0x02), + (31, 208, 0x02), + (41, 208, 0x02), + (56, 208, 0x03), + (2, 128, 0x02), + (9, 128, 0x02), + (23, 128, 0x02), + (40, 128, 0x03), + (2, 130, 0x02), + (9, 130, 0x02), + (23, 130, 0x02), + (40, 130, 0x03), + ], + // 100 + [ + (3, 128, 0x02), + (6, 128, 0x02), + (10, 128, 0x02), + (15, 128, 0x02), + (24, 128, 0x02), + (31, 128, 0x02), + (41, 128, 0x02), + (56, 128, 0x03), + (3, 130, 0x02), + (6, 130, 0x02), + (10, 130, 0x02), + (15, 130, 0x02), + (24, 130, 0x02), + (31, 130, 0x02), + (41, 130, 0x02), + (56, 130, 0x03), + ], + // 101 + [ + (1, 131, 0x02), + (22, 131, 0x03), + (1, 162, 0x02), + (22, 162, 0x03), + (1, 184, 0x02), + (22, 184, 0x03), + (1, 194, 0x02), + (22, 194, 0x03), + (1, 224, 0x02), + (22, 224, 0x03), + (1, 226, 0x02), + (22, 226, 0x03), + (0, 153, 0x02), + (0, 161, 0x02), + (0, 167, 0x02), + (0, 172, 0x02), + ], + // 102 + [ + (2, 131, 0x02), + (9, 131, 0x02), + (23, 131, 0x02), + (40, 131, 0x03), + (2, 162, 0x02), + (9, 162, 0x02), + (23, 162, 0x02), + (40, 162, 0x03), + (2, 184, 0x02), + (9, 184, 0x02), + (23, 184, 0x02), + (40, 184, 0x03), + (2, 194, 0x02), + (9, 194, 0x02), + (23, 194, 0x02), + (40, 194, 0x03), + ], + // 103 + [ + (3, 131, 0x02), + (6, 131, 0x02), + (10, 131, 0x02), + (15, 131, 0x02), + (24, 131, 0x02), + (31, 131, 0x02), + (41, 131, 0x02), + (56, 131, 0x03), + (3, 162, 0x02), + (6, 162, 0x02), + (10, 162, 0x02), + (15, 162, 0x02), + (24, 162, 0x02), + (31, 162, 0x02), + (41, 162, 0x02), + (56, 162, 0x03), + ], + // 104 + [ + (3, 184, 0x02), + (6, 184, 0x02), + (10, 184, 0x02), + (15, 184, 0x02), + (24, 184, 0x02), + (31, 184, 0x02), + (41, 184, 0x02), + (56, 184, 0x03), + (3, 194, 0x02), + (6, 194, 0x02), + (10, 194, 0x02), + (15, 194, 0x02), + (24, 194, 0x02), + (31, 194, 0x02), + (41, 194, 0x02), + (56, 194, 0x03), + ], + // 105 + [ + (2, 224, 0x02), + (9, 224, 0x02), + (23, 224, 0x02), + (40, 224, 0x03), + (2, 226, 0x02), + (9, 226, 0x02), + (23, 226, 0x02), + (40, 226, 0x03), + (1, 153, 0x02), + (22, 153, 0x03), + (1, 161, 0x02), + (22, 161, 0x03), + (1, 167, 0x02), + (22, 167, 0x03), + (1, 172, 0x02), + (22, 172, 0x03), + ], + // 106 + [ + (3, 224, 0x02), + (6, 224, 0x02), + (10, 224, 0x02), + (15, 224, 0x02), + (24, 224, 0x02), + (31, 224, 0x02), + (41, 224, 0x02), + (56, 224, 0x03), + (3, 226, 0x02), + (6, 226, 0x02), + (10, 226, 0x02), + (15, 226, 0x02), + (24, 226, 0x02), + (31, 226, 0x02), + (41, 226, 0x02), + (56, 226, 0x03), + ], + // 107 + [ + (2, 153, 0x02), + (9, 153, 0x02), + (23, 153, 0x02), + (40, 153, 0x03), + (2, 161, 0x02), + (9, 161, 0x02), + (23, 161, 0x02), + (40, 161, 0x03), + (2, 167, 0x02), + (9, 167, 0x02), + (23, 167, 0x02), + (40, 167, 0x03), + (2, 172, 0x02), + (9, 172, 0x02), + (23, 172, 0x02), + (40, 172, 0x03), + ], + // 108 + [ + (3, 153, 0x02), + (6, 153, 0x02), + (10, 153, 0x02), + (15, 153, 0x02), + (24, 153, 0x02), + (31, 153, 0x02), + (41, 153, 0x02), + (56, 153, 0x03), + (3, 161, 0x02), + (6, 161, 0x02), + (10, 161, 0x02), + (15, 161, 0x02), + (24, 161, 0x02), + (31, 161, 0x02), + (41, 161, 0x02), + (56, 161, 0x03), + ], + // 109 + [ + (3, 167, 0x02), + (6, 167, 0x02), + (10, 167, 0x02), + (15, 167, 0x02), + (24, 167, 0x02), + (31, 167, 0x02), + (41, 167, 0x02), + (56, 167, 0x03), + (3, 172, 0x02), + (6, 172, 0x02), + (10, 172, 0x02), + (15, 172, 0x02), + (24, 172, 0x02), + (31, 172, 0x02), + (41, 172, 0x02), + (56, 172, 0x03), + ], + // 110 + [ + (114, 0, 0x00), + (115, 0, 0x00), + (117, 0, 0x00), + (118, 0, 0x00), + (121, 0, 0x00), + (123, 0, 0x00), + (127, 0, 0x00), + (130, 0, 0x00), + (136, 0, 0x00), + (139, 0, 0x00), + (143, 0, 0x00), + (146, 0, 0x00), + (155, 0, 0x00), + (162, 0, 0x00), + (170, 0, 0x00), + (180, 0, 0x00), + ], + // 111 + [ + (0, 176, 0x02), + (0, 177, 0x02), + (0, 179, 0x02), + (0, 209, 0x02), + (0, 216, 0x02), + (0, 217, 0x02), + (0, 227, 0x02), + (0, 229, 0x02), + (0, 230, 0x02), + (122, 0, 0x00), + (124, 0, 0x00), + (125, 0, 0x00), + (128, 0, 0x00), + (129, 0, 0x00), + (131, 0, 0x00), + (132, 0, 0x00), + ], + // 112 + [ + (1, 176, 0x02), + (22, 176, 0x03), + (1, 177, 0x02), + (22, 177, 0x03), + (1, 179, 0x02), + (22, 179, 0x03), + (1, 209, 0x02), + (22, 209, 0x03), + (1, 216, 0x02), + (22, 216, 0x03), + (1, 217, 0x02), + (22, 217, 0x03), + (1, 227, 0x02), + (22, 227, 0x03), + (1, 229, 0x02), + (22, 229, 0x03), + ], + // 113 + [ + (2, 176, 0x02), + (9, 176, 0x02), + (23, 176, 0x02), + (40, 176, 0x03), + (2, 177, 0x02), + (9, 177, 0x02), + (23, 177, 0x02), + (40, 177, 0x03), + (2, 179, 0x02), + (9, 179, 0x02), + (23, 179, 0x02), + (40, 179, 0x03), + (2, 209, 0x02), + (9, 209, 0x02), + (23, 209, 0x02), + (40, 209, 0x03), + ], + // 114 + [ + (3, 176, 0x02), + (6, 176, 0x02), + (10, 176, 0x02), + (15, 176, 0x02), + (24, 176, 0x02), + (31, 176, 0x02), + (41, 176, 0x02), + (56, 176, 0x03), + (3, 177, 0x02), + (6, 177, 0x02), + (10, 177, 0x02), + (15, 177, 0x02), + (24, 177, 0x02), + (31, 177, 0x02), + (41, 177, 0x02), + (56, 177, 0x03), + ], + // 115 + [ + (3, 179, 0x02), + (6, 179, 0x02), + (10, 179, 0x02), + (15, 179, 0x02), + (24, 179, 0x02), + (31, 179, 0x02), + (41, 179, 0x02), + (56, 179, 0x03), + (3, 209, 0x02), + (6, 209, 0x02), + (10, 209, 0x02), + (15, 209, 0x02), + (24, 209, 0x02), + (31, 209, 0x02), + (41, 209, 0x02), + (56, 209, 0x03), + ], + // 116 + [ + (2, 216, 0x02), + (9, 216, 0x02), + (23, 216, 0x02), + (40, 216, 0x03), + (2, 217, 0x02), + (9, 217, 0x02), + (23, 217, 0x02), + (40, 217, 0x03), + (2, 227, 0x02), + (9, 227, 0x02), + (23, 227, 0x02), + (40, 227, 0x03), + (2, 229, 0x02), + (9, 229, 0x02), + (23, 229, 0x02), + (40, 229, 0x03), + ], + // 117 + [ + (3, 216, 0x02), + (6, 216, 0x02), + (10, 216, 0x02), + (15, 216, 0x02), + (24, 216, 0x02), + (31, 216, 0x02), + (41, 216, 0x02), + (56, 216, 0x03), + (3, 217, 0x02), + (6, 217, 0x02), + (10, 217, 0x02), + (15, 217, 0x02), + (24, 217, 0x02), + (31, 217, 0x02), + (41, 217, 0x02), + (56, 217, 0x03), + ], + // 118 + [ + (3, 227, 0x02), + (6, 227, 0x02), + (10, 227, 0x02), + (15, 227, 0x02), + (24, 227, 0x02), + (31, 227, 0x02), + (41, 227, 0x02), + (56, 227, 0x03), + (3, 229, 0x02), + (6, 229, 0x02), + (10, 229, 0x02), + (15, 229, 0x02), + (24, 229, 0x02), + (31, 229, 0x02), + (41, 229, 0x02), + (56, 229, 0x03), + ], + // 119 + [ + (1, 230, 0x02), + (22, 230, 0x03), + (0, 129, 0x02), + (0, 132, 0x02), + (0, 133, 0x02), + (0, 134, 0x02), + (0, 136, 0x02), + (0, 146, 0x02), + (0, 154, 0x02), + (0, 156, 0x02), + (0, 160, 0x02), + (0, 163, 0x02), + (0, 164, 0x02), + (0, 169, 0x02), + (0, 170, 0x02), + (0, 173, 0x02), + ], + // 120 + [ + (2, 230, 0x02), + (9, 230, 0x02), + (23, 230, 0x02), + (40, 230, 0x03), + (1, 129, 0x02), + (22, 129, 0x03), + (1, 132, 0x02), + (22, 132, 0x03), + (1, 133, 0x02), + (22, 133, 0x03), + (1, 134, 0x02), + (22, 134, 0x03), + (1, 136, 0x02), + (22, 136, 0x03), + (1, 146, 0x02), + (22, 146, 0x03), + ], + // 121 + [ + (3, 230, 0x02), + (6, 230, 0x02), + (10, 230, 0x02), + (15, 230, 0x02), + (24, 230, 0x02), + (31, 230, 0x02), + (41, 230, 0x02), + (56, 230, 0x03), + (2, 129, 0x02), + (9, 129, 0x02), + (23, 129, 0x02), + (40, 129, 0x03), + (2, 132, 0x02), + (9, 132, 0x02), + (23, 132, 0x02), + (40, 132, 0x03), + ], + // 122 + [ + (3, 129, 0x02), + (6, 129, 0x02), + (10, 129, 0x02), + (15, 129, 0x02), + (24, 129, 0x02), + (31, 129, 0x02), + (41, 129, 0x02), + (56, 129, 0x03), + (3, 132, 0x02), + (6, 132, 0x02), + (10, 132, 0x02), + (15, 132, 0x02), + (24, 132, 0x02), + (31, 132, 0x02), + (41, 132, 0x02), + (56, 132, 0x03), + ], + // 123 + [ + (2, 133, 0x02), + (9, 133, 0x02), + (23, 133, 0x02), + (40, 133, 0x03), + (2, 134, 0x02), + (9, 134, 0x02), + (23, 134, 0x02), + (40, 134, 0x03), + (2, 136, 0x02), + (9, 136, 0x02), + (23, 136, 0x02), + (40, 136, 0x03), + (2, 146, 0x02), + (9, 146, 0x02), + (23, 146, 0x02), + (40, 146, 0x03), + ], + // 124 + [ + (3, 133, 0x02), + (6, 133, 0x02), + (10, 133, 0x02), + (15, 133, 0x02), + (24, 133, 0x02), + (31, 133, 0x02), + (41, 133, 0x02), + (56, 133, 0x03), + (3, 134, 0x02), + (6, 134, 0x02), + (10, 134, 0x02), + (15, 134, 0x02), + (24, 134, 0x02), + (31, 134, 0x02), + (41, 134, 0x02), + (56, 134, 0x03), + ], + // 125 + [ + (3, 136, 0x02), + (6, 136, 0x02), + (10, 136, 0x02), + (15, 136, 0x02), + (24, 136, 0x02), + (31, 136, 0x02), + (41, 136, 0x02), + (56, 136, 0x03), + (3, 146, 0x02), + (6, 146, 0x02), + (10, 146, 0x02), + (15, 146, 0x02), + (24, 146, 0x02), + (31, 146, 0x02), + (41, 146, 0x02), + (56, 146, 0x03), + ], + // 126 + [ + (1, 154, 0x02), + (22, 154, 0x03), + (1, 156, 0x02), + (22, 156, 0x03), + (1, 160, 0x02), + (22, 160, 0x03), + (1, 163, 0x02), + (22, 163, 0x03), + (1, 164, 0x02), + (22, 164, 0x03), + (1, 169, 0x02), + (22, 169, 0x03), + (1, 170, 0x02), + (22, 170, 0x03), + (1, 173, 0x02), + (22, 173, 0x03), + ], + // 127 + [ + (2, 154, 0x02), + (9, 154, 0x02), + (23, 154, 0x02), + (40, 154, 0x03), + (2, 156, 0x02), + (9, 156, 0x02), + (23, 156, 0x02), + (40, 156, 0x03), + (2, 160, 0x02), + (9, 160, 0x02), + (23, 160, 0x02), + (40, 160, 0x03), + (2, 163, 0x02), + (9, 163, 0x02), + (23, 163, 0x02), + (40, 163, 0x03), + ], + // 128 + [ + (3, 154, 0x02), + (6, 154, 0x02), + (10, 154, 0x02), + (15, 154, 0x02), + (24, 154, 0x02), + (31, 154, 0x02), + (41, 154, 0x02), + (56, 154, 0x03), + (3, 156, 0x02), + (6, 156, 0x02), + (10, 156, 0x02), + (15, 156, 0x02), + (24, 156, 0x02), + (31, 156, 0x02), + (41, 156, 0x02), + (56, 156, 0x03), + ], + // 129 + [ + (3, 160, 0x02), + (6, 160, 0x02), + (10, 160, 0x02), + (15, 160, 0x02), + (24, 160, 0x02), + (31, 160, 0x02), + (41, 160, 0x02), + (56, 160, 0x03), + (3, 163, 0x02), + (6, 163, 0x02), + (10, 163, 0x02), + (15, 163, 0x02), + (24, 163, 0x02), + (31, 163, 0x02), + (41, 163, 0x02), + (56, 163, 0x03), + ], + // 130 + [ + (2, 164, 0x02), + (9, 164, 0x02), + (23, 164, 0x02), + (40, 164, 0x03), + (2, 169, 0x02), + (9, 169, 0x02), + (23, 169, 0x02), + (40, 169, 0x03), + (2, 170, 0x02), + (9, 170, 0x02), + (23, 170, 0x02), + (40, 170, 0x03), + (2, 173, 0x02), + (9, 173, 0x02), + (23, 173, 0x02), + (40, 173, 0x03), + ], + // 131 + [ + (3, 164, 0x02), + (6, 164, 0x02), + (10, 164, 0x02), + (15, 164, 0x02), + (24, 164, 0x02), + (31, 164, 0x02), + (41, 164, 0x02), + (56, 164, 0x03), + (3, 169, 0x02), + (6, 169, 0x02), + (10, 169, 0x02), + (15, 169, 0x02), + (24, 169, 0x02), + (31, 169, 0x02), + (41, 169, 0x02), + (56, 169, 0x03), + ], + // 132 + [ + (3, 170, 0x02), + (6, 170, 0x02), + (10, 170, 0x02), + (15, 170, 0x02), + (24, 170, 0x02), + (31, 170, 0x02), + (41, 170, 0x02), + (56, 170, 0x03), + (3, 173, 0x02), + (6, 173, 0x02), + (10, 173, 0x02), + (15, 173, 0x02), + (24, 173, 0x02), + (31, 173, 0x02), + (41, 173, 0x02), + (56, 173, 0x03), + ], + // 133 + [ + (137, 0, 0x00), + (138, 0, 0x00), + (140, 0, 0x00), + (141, 0, 0x00), + (144, 0, 0x00), + (145, 0, 0x00), + (147, 0, 0x00), + (150, 0, 0x00), + (156, 0, 0x00), + (159, 0, 0x00), + (163, 0, 0x00), + (166, 0, 0x00), + (171, 0, 0x00), + (174, 0, 0x00), + (181, 0, 0x00), + (190, 0, 0x00), + ], + // 134 + [ + (0, 178, 0x02), + (0, 181, 0x02), + (0, 185, 0x02), + (0, 186, 0x02), + (0, 187, 0x02), + (0, 189, 0x02), + (0, 190, 0x02), + (0, 196, 0x02), + (0, 198, 0x02), + (0, 228, 0x02), + (0, 232, 0x02), + (0, 233, 0x02), + (148, 0, 0x00), + (149, 0, 0x00), + (151, 0, 0x00), + (152, 0, 0x00), + ], + // 135 + [ + (1, 178, 0x02), + (22, 178, 0x03), + (1, 181, 0x02), + (22, 181, 0x03), + (1, 185, 0x02), + (22, 185, 0x03), + (1, 186, 0x02), + (22, 186, 0x03), + (1, 187, 0x02), + (22, 187, 0x03), + (1, 189, 0x02), + (22, 189, 0x03), + (1, 190, 0x02), + (22, 190, 0x03), + (1, 196, 0x02), + (22, 196, 0x03), + ], + // 136 + [ + (2, 178, 0x02), + (9, 178, 0x02), + (23, 178, 0x02), + (40, 178, 0x03), + (2, 181, 0x02), + (9, 181, 0x02), + (23, 181, 0x02), + (40, 181, 0x03), + (2, 185, 0x02), + (9, 185, 0x02), + (23, 185, 0x02), + (40, 185, 0x03), + (2, 186, 0x02), + (9, 186, 0x02), + (23, 186, 0x02), + (40, 186, 0x03), + ], + // 137 + [ + (3, 178, 0x02), + (6, 178, 0x02), + (10, 178, 0x02), + (15, 178, 0x02), + (24, 178, 0x02), + (31, 178, 0x02), + (41, 178, 0x02), + (56, 178, 0x03), + (3, 181, 0x02), + (6, 181, 0x02), + (10, 181, 0x02), + (15, 181, 0x02), + (24, 181, 0x02), + (31, 181, 0x02), + (41, 181, 0x02), + (56, 181, 0x03), + ], + // 138 + [ + (3, 185, 0x02), + (6, 185, 0x02), + (10, 185, 0x02), + (15, 185, 0x02), + (24, 185, 0x02), + (31, 185, 0x02), + (41, 185, 0x02), + (56, 185, 0x03), + (3, 186, 0x02), + (6, 186, 0x02), + (10, 186, 0x02), + (15, 186, 0x02), + (24, 186, 0x02), + (31, 186, 0x02), + (41, 186, 0x02), + (56, 186, 0x03), + ], + // 139 + [ + (2, 187, 0x02), + (9, 187, 0x02), + (23, 187, 0x02), + (40, 187, 0x03), + (2, 189, 0x02), + (9, 189, 0x02), + (23, 189, 0x02), + (40, 189, 0x03), + (2, 190, 0x02), + (9, 190, 0x02), + (23, 190, 0x02), + (40, 190, 0x03), + (2, 196, 0x02), + (9, 196, 0x02), + (23, 196, 0x02), + (40, 196, 0x03), + ], + // 140 + [ + (3, 187, 0x02), + (6, 187, 0x02), + (10, 187, 0x02), + (15, 187, 0x02), + (24, 187, 0x02), + (31, 187, 0x02), + (41, 187, 0x02), + (56, 187, 0x03), + (3, 189, 0x02), + (6, 189, 0x02), + (10, 189, 0x02), + (15, 189, 0x02), + (24, 189, 0x02), + (31, 189, 0x02), + (41, 189, 0x02), + (56, 189, 0x03), + ], + // 141 + [ + (3, 190, 0x02), + (6, 190, 0x02), + (10, 190, 0x02), + (15, 190, 0x02), + (24, 190, 0x02), + (31, 190, 0x02), + (41, 190, 0x02), + (56, 190, 0x03), + (3, 196, 0x02), + (6, 196, 0x02), + (10, 196, 0x02), + (15, 196, 0x02), + (24, 196, 0x02), + (31, 196, 0x02), + (41, 196, 0x02), + (56, 196, 0x03), + ], + // 142 + [ + (1, 198, 0x02), + (22, 198, 0x03), + (1, 228, 0x02), + (22, 228, 0x03), + (1, 232, 0x02), + (22, 232, 0x03), + (1, 233, 0x02), + (22, 233, 0x03), + (0, 1, 0x02), + (0, 135, 0x02), + (0, 137, 0x02), + (0, 138, 0x02), + (0, 139, 0x02), + (0, 140, 0x02), + (0, 141, 0x02), + (0, 143, 0x02), + ], + // 143 + [ + (2, 198, 0x02), + (9, 198, 0x02), + (23, 198, 0x02), + (40, 198, 0x03), + (2, 228, 0x02), + (9, 228, 0x02), + (23, 228, 0x02), + (40, 228, 0x03), + (2, 232, 0x02), + (9, 232, 0x02), + (23, 232, 0x02), + (40, 232, 0x03), + (2, 233, 0x02), + (9, 233, 0x02), + (23, 233, 0x02), + (40, 233, 0x03), + ], + // 144 + [ + (3, 198, 0x02), + (6, 198, 0x02), + (10, 198, 0x02), + (15, 198, 0x02), + (24, 198, 0x02), + (31, 198, 0x02), + (41, 198, 0x02), + (56, 198, 0x03), + (3, 228, 0x02), + (6, 228, 0x02), + (10, 228, 0x02), + (15, 228, 0x02), + (24, 228, 0x02), + (31, 228, 0x02), + (41, 228, 0x02), + (56, 228, 0x03), + ], + // 145 + [ + (3, 232, 0x02), + (6, 232, 0x02), + (10, 232, 0x02), + (15, 232, 0x02), + (24, 232, 0x02), + (31, 232, 0x02), + (41, 232, 0x02), + (56, 232, 0x03), + (3, 233, 0x02), + (6, 233, 0x02), + (10, 233, 0x02), + (15, 233, 0x02), + (24, 233, 0x02), + (31, 233, 0x02), + (41, 233, 0x02), + (56, 233, 0x03), + ], + // 146 + [ + (1, 1, 0x02), + (22, 1, 0x03), + (1, 135, 0x02), + (22, 135, 0x03), + (1, 137, 0x02), + (22, 137, 0x03), + (1, 138, 0x02), + (22, 138, 0x03), + (1, 139, 0x02), + (22, 139, 0x03), + (1, 140, 0x02), + (22, 140, 0x03), + (1, 141, 0x02), + (22, 141, 0x03), + (1, 143, 0x02), + (22, 143, 0x03), + ], + // 147 + [ + (2, 1, 0x02), + (9, 1, 0x02), + (23, 1, 0x02), + (40, 1, 0x03), + (2, 135, 0x02), + (9, 135, 0x02), + (23, 135, 0x02), + (40, 135, 0x03), + (2, 137, 0x02), + (9, 137, 0x02), + (23, 137, 0x02), + (40, 137, 0x03), + (2, 138, 0x02), + (9, 138, 0x02), + (23, 138, 0x02), + (40, 138, 0x03), + ], + // 148 + [ + (3, 1, 0x02), + (6, 1, 0x02), + (10, 1, 0x02), + (15, 1, 0x02), + (24, 1, 0x02), + (31, 1, 0x02), + (41, 1, 0x02), + (56, 1, 0x03), + (3, 135, 0x02), + (6, 135, 0x02), + (10, 135, 0x02), + (15, 135, 0x02), + (24, 135, 0x02), + (31, 135, 0x02), + (41, 135, 0x02), + (56, 135, 0x03), + ], + // 149 + [ + (3, 137, 0x02), + (6, 137, 0x02), + (10, 137, 0x02), + (15, 137, 0x02), + (24, 137, 0x02), + (31, 137, 0x02), + (41, 137, 0x02), + (56, 137, 0x03), + (3, 138, 0x02), + (6, 138, 0x02), + (10, 138, 0x02), + (15, 138, 0x02), + (24, 138, 0x02), + (31, 138, 0x02), + (41, 138, 0x02), + (56, 138, 0x03), + ], + // 150 + [ + (2, 139, 0x02), + (9, 139, 0x02), + (23, 139, 0x02), + (40, 139, 0x03), + (2, 140, 0x02), + (9, 140, 0x02), + (23, 140, 0x02), + (40, 140, 0x03), + (2, 141, 0x02), + (9, 141, 0x02), + (23, 141, 0x02), + (40, 141, 0x03), + (2, 143, 0x02), + (9, 143, 0x02), + (23, 143, 0x02), + (40, 143, 0x03), + ], + // 151 + [ + (3, 139, 0x02), + (6, 139, 0x02), + (10, 139, 0x02), + (15, 139, 0x02), + (24, 139, 0x02), + (31, 139, 0x02), + (41, 139, 0x02), + (56, 139, 0x03), + (3, 140, 0x02), + (6, 140, 0x02), + (10, 140, 0x02), + (15, 140, 0x02), + (24, 140, 0x02), + (31, 140, 0x02), + (41, 140, 0x02), + (56, 140, 0x03), + ], + // 152 + [ + (3, 141, 0x02), + (6, 141, 0x02), + (10, 141, 0x02), + (15, 141, 0x02), + (24, 141, 0x02), + (31, 141, 0x02), + (41, 141, 0x02), + (56, 141, 0x03), + (3, 143, 0x02), + (6, 143, 0x02), + (10, 143, 0x02), + (15, 143, 0x02), + (24, 143, 0x02), + (31, 143, 0x02), + (41, 143, 0x02), + (56, 143, 0x03), + ], + // 153 + [ + (157, 0, 0x00), + (158, 0, 0x00), + (160, 0, 0x00), + (161, 0, 0x00), + (164, 0, 0x00), + (165, 0, 0x00), + (167, 0, 0x00), + (168, 0, 0x00), + (172, 0, 0x00), + (173, 0, 0x00), + (175, 0, 0x00), + (177, 0, 0x00), + (182, 0, 0x00), + (185, 0, 0x00), + (191, 0, 0x00), + (207, 0, 0x00), + ], + // 154 + [ + (0, 147, 0x02), + (0, 149, 0x02), + (0, 150, 0x02), + (0, 151, 0x02), + (0, 152, 0x02), + (0, 155, 0x02), + (0, 157, 0x02), + (0, 158, 0x02), + (0, 165, 0x02), + (0, 166, 0x02), + (0, 168, 0x02), + (0, 174, 0x02), + (0, 175, 0x02), + (0, 180, 0x02), + (0, 182, 0x02), + (0, 183, 0x02), + ], + // 155 + [ + (1, 147, 0x02), + (22, 147, 0x03), + (1, 149, 0x02), + (22, 149, 0x03), + (1, 150, 0x02), + (22, 150, 0x03), + (1, 151, 0x02), + (22, 151, 0x03), + (1, 152, 0x02), + (22, 152, 0x03), + (1, 155, 0x02), + (22, 155, 0x03), + (1, 157, 0x02), + (22, 157, 0x03), + (1, 158, 0x02), + (22, 158, 0x03), + ], + // 156 + [ + (2, 147, 0x02), + (9, 147, 0x02), + (23, 147, 0x02), + (40, 147, 0x03), + (2, 149, 0x02), + (9, 149, 0x02), + (23, 149, 0x02), + (40, 149, 0x03), + (2, 150, 0x02), + (9, 150, 0x02), + (23, 150, 0x02), + (40, 150, 0x03), + (2, 151, 0x02), + (9, 151, 0x02), + (23, 151, 0x02), + (40, 151, 0x03), + ], + // 157 + [ + (3, 147, 0x02), + (6, 147, 0x02), + (10, 147, 0x02), + (15, 147, 0x02), + (24, 147, 0x02), + (31, 147, 0x02), + (41, 147, 0x02), + (56, 147, 0x03), + (3, 149, 0x02), + (6, 149, 0x02), + (10, 149, 0x02), + (15, 149, 0x02), + (24, 149, 0x02), + (31, 149, 0x02), + (41, 149, 0x02), + (56, 149, 0x03), + ], + // 158 + [ + (3, 150, 0x02), + (6, 150, 0x02), + (10, 150, 0x02), + (15, 150, 0x02), + (24, 150, 0x02), + (31, 150, 0x02), + (41, 150, 0x02), + (56, 150, 0x03), + (3, 151, 0x02), + (6, 151, 0x02), + (10, 151, 0x02), + (15, 151, 0x02), + (24, 151, 0x02), + (31, 151, 0x02), + (41, 151, 0x02), + (56, 151, 0x03), + ], + // 159 + [ + (2, 152, 0x02), + (9, 152, 0x02), + (23, 152, 0x02), + (40, 152, 0x03), + (2, 155, 0x02), + (9, 155, 0x02), + (23, 155, 0x02), + (40, 155, 0x03), + (2, 157, 0x02), + (9, 157, 0x02), + (23, 157, 0x02), + (40, 157, 0x03), + (2, 158, 0x02), + (9, 158, 0x02), + (23, 158, 0x02), + (40, 158, 0x03), + ], + // 160 + [ + (3, 152, 0x02), + (6, 152, 0x02), + (10, 152, 0x02), + (15, 152, 0x02), + (24, 152, 0x02), + (31, 152, 0x02), + (41, 152, 0x02), + (56, 152, 0x03), + (3, 155, 0x02), + (6, 155, 0x02), + (10, 155, 0x02), + (15, 155, 0x02), + (24, 155, 0x02), + (31, 155, 0x02), + (41, 155, 0x02), + (56, 155, 0x03), + ], + // 161 + [ + (3, 157, 0x02), + (6, 157, 0x02), + (10, 157, 0x02), + (15, 157, 0x02), + (24, 157, 0x02), + (31, 157, 0x02), + (41, 157, 0x02), + (56, 157, 0x03), + (3, 158, 0x02), + (6, 158, 0x02), + (10, 158, 0x02), + (15, 158, 0x02), + (24, 158, 0x02), + (31, 158, 0x02), + (41, 158, 0x02), + (56, 158, 0x03), + ], + // 162 + [ + (1, 165, 0x02), + (22, 165, 0x03), + (1, 166, 0x02), + (22, 166, 0x03), + (1, 168, 0x02), + (22, 168, 0x03), + (1, 174, 0x02), + (22, 174, 0x03), + (1, 175, 0x02), + (22, 175, 0x03), + (1, 180, 0x02), + (22, 180, 0x03), + (1, 182, 0x02), + (22, 182, 0x03), + (1, 183, 0x02), + (22, 183, 0x03), + ], + // 163 + [ + (2, 165, 0x02), + (9, 165, 0x02), + (23, 165, 0x02), + (40, 165, 0x03), + (2, 166, 0x02), + (9, 166, 0x02), + (23, 166, 0x02), + (40, 166, 0x03), + (2, 168, 0x02), + (9, 168, 0x02), + (23, 168, 0x02), + (40, 168, 0x03), + (2, 174, 0x02), + (9, 174, 0x02), + (23, 174, 0x02), + (40, 174, 0x03), + ], + // 164 + [ + (3, 165, 0x02), + (6, 165, 0x02), + (10, 165, 0x02), + (15, 165, 0x02), + (24, 165, 0x02), + (31, 165, 0x02), + (41, 165, 0x02), + (56, 165, 0x03), + (3, 166, 0x02), + (6, 166, 0x02), + (10, 166, 0x02), + (15, 166, 0x02), + (24, 166, 0x02), + (31, 166, 0x02), + (41, 166, 0x02), + (56, 166, 0x03), + ], + // 165 + [ + (3, 168, 0x02), + (6, 168, 0x02), + (10, 168, 0x02), + (15, 168, 0x02), + (24, 168, 0x02), + (31, 168, 0x02), + (41, 168, 0x02), + (56, 168, 0x03), + (3, 174, 0x02), + (6, 174, 0x02), + (10, 174, 0x02), + (15, 174, 0x02), + (24, 174, 0x02), + (31, 174, 0x02), + (41, 174, 0x02), + (56, 174, 0x03), + ], + // 166 + [ + (2, 175, 0x02), + (9, 175, 0x02), + (23, 175, 0x02), + (40, 175, 0x03), + (2, 180, 0x02), + (9, 180, 0x02), + (23, 180, 0x02), + (40, 180, 0x03), + (2, 182, 0x02), + (9, 182, 0x02), + (23, 182, 0x02), + (40, 182, 0x03), + (2, 183, 0x02), + (9, 183, 0x02), + (23, 183, 0x02), + (40, 183, 0x03), + ], + // 167 + [ + (3, 175, 0x02), + (6, 175, 0x02), + (10, 175, 0x02), + (15, 175, 0x02), + (24, 175, 0x02), + (31, 175, 0x02), + (41, 175, 0x02), + (56, 175, 0x03), + (3, 180, 0x02), + (6, 180, 0x02), + (10, 180, 0x02), + (15, 180, 0x02), + (24, 180, 0x02), + (31, 180, 0x02), + (41, 180, 0x02), + (56, 180, 0x03), + ], + // 168 + [ + (3, 182, 0x02), + (6, 182, 0x02), + (10, 182, 0x02), + (15, 182, 0x02), + (24, 182, 0x02), + (31, 182, 0x02), + (41, 182, 0x02), + (56, 182, 0x03), + (3, 183, 0x02), + (6, 183, 0x02), + (10, 183, 0x02), + (15, 183, 0x02), + (24, 183, 0x02), + (31, 183, 0x02), + (41, 183, 0x02), + (56, 183, 0x03), + ], + // 169 + [ + (0, 188, 0x02), + (0, 191, 0x02), + (0, 197, 0x02), + (0, 231, 0x02), + (0, 239, 0x02), + (176, 0, 0x00), + (178, 0, 0x00), + (179, 0, 0x00), + (183, 0, 0x00), + (184, 0, 0x00), + (186, 0, 0x00), + (187, 0, 0x00), + (192, 0, 0x00), + (199, 0, 0x00), + (208, 0, 0x00), + (223, 0, 0x00), + ], + // 170 + [ + (1, 188, 0x02), + (22, 188, 0x03), + (1, 191, 0x02), + (22, 191, 0x03), + (1, 197, 0x02), + (22, 197, 0x03), + (1, 231, 0x02), + (22, 231, 0x03), + (1, 239, 0x02), + (22, 239, 0x03), + (0, 9, 0x02), + (0, 142, 0x02), + (0, 144, 0x02), + (0, 145, 0x02), + (0, 148, 0x02), + (0, 159, 0x02), + ], + // 171 + [ + (2, 188, 0x02), + (9, 188, 0x02), + (23, 188, 0x02), + (40, 188, 0x03), + (2, 191, 0x02), + (9, 191, 0x02), + (23, 191, 0x02), + (40, 191, 0x03), + (2, 197, 0x02), + (9, 197, 0x02), + (23, 197, 0x02), + (40, 197, 0x03), + (2, 231, 0x02), + (9, 231, 0x02), + (23, 231, 0x02), + (40, 231, 0x03), + ], + // 172 + [ + (3, 188, 0x02), + (6, 188, 0x02), + (10, 188, 0x02), + (15, 188, 0x02), + (24, 188, 0x02), + (31, 188, 0x02), + (41, 188, 0x02), + (56, 188, 0x03), + (3, 191, 0x02), + (6, 191, 0x02), + (10, 191, 0x02), + (15, 191, 0x02), + (24, 191, 0x02), + (31, 191, 0x02), + (41, 191, 0x02), + (56, 191, 0x03), + ], + // 173 + [ + (3, 197, 0x02), + (6, 197, 0x02), + (10, 197, 0x02), + (15, 197, 0x02), + (24, 197, 0x02), + (31, 197, 0x02), + (41, 197, 0x02), + (56, 197, 0x03), + (3, 231, 0x02), + (6, 231, 0x02), + (10, 231, 0x02), + (15, 231, 0x02), + (24, 231, 0x02), + (31, 231, 0x02), + (41, 231, 0x02), + (56, 231, 0x03), + ], + // 174 + [ + (2, 239, 0x02), + (9, 239, 0x02), + (23, 239, 0x02), + (40, 239, 0x03), + (1, 9, 0x02), + (22, 9, 0x03), + (1, 142, 0x02), + (22, 142, 0x03), + (1, 144, 0x02), + (22, 144, 0x03), + (1, 145, 0x02), + (22, 145, 0x03), + (1, 148, 0x02), + (22, 148, 0x03), + (1, 159, 0x02), + (22, 159, 0x03), + ], + // 175 + [ + (3, 239, 0x02), + (6, 239, 0x02), + (10, 239, 0x02), + (15, 239, 0x02), + (24, 239, 0x02), + (31, 239, 0x02), + (41, 239, 0x02), + (56, 239, 0x03), + (2, 9, 0x02), + (9, 9, 0x02), + (23, 9, 0x02), + (40, 9, 0x03), + (2, 142, 0x02), + (9, 142, 0x02), + (23, 142, 0x02), + (40, 142, 0x03), + ], + // 176 + [ + (3, 9, 0x02), + (6, 9, 0x02), + (10, 9, 0x02), + (15, 9, 0x02), + (24, 9, 0x02), + (31, 9, 0x02), + (41, 9, 0x02), + (56, 9, 0x03), + (3, 142, 0x02), + (6, 142, 0x02), + (10, 142, 0x02), + (15, 142, 0x02), + (24, 142, 0x02), + (31, 142, 0x02), + (41, 142, 0x02), + (56, 142, 0x03), + ], + // 177 + [ + (2, 144, 0x02), + (9, 144, 0x02), + (23, 144, 0x02), + (40, 144, 0x03), + (2, 145, 0x02), + (9, 145, 0x02), + (23, 145, 0x02), + (40, 145, 0x03), + (2, 148, 0x02), + (9, 148, 0x02), + (23, 148, 0x02), + (40, 148, 0x03), + (2, 159, 0x02), + (9, 159, 0x02), + (23, 159, 0x02), + (40, 159, 0x03), + ], + // 178 + [ + (3, 144, 0x02), + (6, 144, 0x02), + (10, 144, 0x02), + (15, 144, 0x02), + (24, 144, 0x02), + (31, 144, 0x02), + (41, 144, 0x02), + (56, 144, 0x03), + (3, 145, 0x02), + (6, 145, 0x02), + (10, 145, 0x02), + (15, 145, 0x02), + (24, 145, 0x02), + (31, 145, 0x02), + (41, 145, 0x02), + (56, 145, 0x03), + ], + // 179 + [ + (3, 148, 0x02), + (6, 148, 0x02), + (10, 148, 0x02), + (15, 148, 0x02), + (24, 148, 0x02), + (31, 148, 0x02), + (41, 148, 0x02), + (56, 148, 0x03), + (3, 159, 0x02), + (6, 159, 0x02), + (10, 159, 0x02), + (15, 159, 0x02), + (24, 159, 0x02), + (31, 159, 0x02), + (41, 159, 0x02), + (56, 159, 0x03), + ], + // 180 + [ + (0, 171, 0x02), + (0, 206, 0x02), + (0, 215, 0x02), + (0, 225, 0x02), + (0, 236, 0x02), + (0, 237, 0x02), + (188, 0, 0x00), + (189, 0, 0x00), + (193, 0, 0x00), + (196, 0, 0x00), + (200, 0, 0x00), + (203, 0, 0x00), + (209, 0, 0x00), + (216, 0, 0x00), + (224, 0, 0x00), + (238, 0, 0x00), + ], + // 181 + [ + (1, 171, 0x02), + (22, 171, 0x03), + (1, 206, 0x02), + (22, 206, 0x03), + (1, 215, 0x02), + (22, 215, 0x03), + (1, 225, 0x02), + (22, 225, 0x03), + (1, 236, 0x02), + (22, 236, 0x03), + (1, 237, 0x02), + (22, 237, 0x03), + (0, 199, 0x02), + (0, 207, 0x02), + (0, 234, 0x02), + (0, 235, 0x02), + ], + // 182 + [ + (2, 171, 0x02), + (9, 171, 0x02), + (23, 171, 0x02), + (40, 171, 0x03), + (2, 206, 0x02), + (9, 206, 0x02), + (23, 206, 0x02), + (40, 206, 0x03), + (2, 215, 0x02), + (9, 215, 0x02), + (23, 215, 0x02), + (40, 215, 0x03), + (2, 225, 0x02), + (9, 225, 0x02), + (23, 225, 0x02), + (40, 225, 0x03), + ], + // 183 + [ + (3, 171, 0x02), + (6, 171, 0x02), + (10, 171, 0x02), + (15, 171, 0x02), + (24, 171, 0x02), + (31, 171, 0x02), + (41, 171, 0x02), + (56, 171, 0x03), + (3, 206, 0x02), + (6, 206, 0x02), + (10, 206, 0x02), + (15, 206, 0x02), + (24, 206, 0x02), + (31, 206, 0x02), + (41, 206, 0x02), + (56, 206, 0x03), + ], + // 184 + [ + (3, 215, 0x02), + (6, 215, 0x02), + (10, 215, 0x02), + (15, 215, 0x02), + (24, 215, 0x02), + (31, 215, 0x02), + (41, 215, 0x02), + (56, 215, 0x03), + (3, 225, 0x02), + (6, 225, 0x02), + (10, 225, 0x02), + (15, 225, 0x02), + (24, 225, 0x02), + (31, 225, 0x02), + (41, 225, 0x02), + (56, 225, 0x03), + ], + // 185 + [ + (2, 236, 0x02), + (9, 236, 0x02), + (23, 236, 0x02), + (40, 236, 0x03), + (2, 237, 0x02), + (9, 237, 0x02), + (23, 237, 0x02), + (40, 237, 0x03), + (1, 199, 0x02), + (22, 199, 0x03), + (1, 207, 0x02), + (22, 207, 0x03), + (1, 234, 0x02), + (22, 234, 0x03), + (1, 235, 0x02), + (22, 235, 0x03), + ], + // 186 + [ + (3, 236, 0x02), + (6, 236, 0x02), + (10, 236, 0x02), + (15, 236, 0x02), + (24, 236, 0x02), + (31, 236, 0x02), + (41, 236, 0x02), + (56, 236, 0x03), + (3, 237, 0x02), + (6, 237, 0x02), + (10, 237, 0x02), + (15, 237, 0x02), + (24, 237, 0x02), + (31, 237, 0x02), + (41, 237, 0x02), + (56, 237, 0x03), + ], + // 187 + [ + (2, 199, 0x02), + (9, 199, 0x02), + (23, 199, 0x02), + (40, 199, 0x03), + (2, 207, 0x02), + (9, 207, 0x02), + (23, 207, 0x02), + (40, 207, 0x03), + (2, 234, 0x02), + (9, 234, 0x02), + (23, 234, 0x02), + (40, 234, 0x03), + (2, 235, 0x02), + (9, 235, 0x02), + (23, 235, 0x02), + (40, 235, 0x03), + ], + // 188 + [ + (3, 199, 0x02), + (6, 199, 0x02), + (10, 199, 0x02), + (15, 199, 0x02), + (24, 199, 0x02), + (31, 199, 0x02), + (41, 199, 0x02), + (56, 199, 0x03), + (3, 207, 0x02), + (6, 207, 0x02), + (10, 207, 0x02), + (15, 207, 0x02), + (24, 207, 0x02), + (31, 207, 0x02), + (41, 207, 0x02), + (56, 207, 0x03), + ], + // 189 + [ + (3, 234, 0x02), + (6, 234, 0x02), + (10, 234, 0x02), + (15, 234, 0x02), + (24, 234, 0x02), + (31, 234, 0x02), + (41, 234, 0x02), + (56, 234, 0x03), + (3, 235, 0x02), + (6, 235, 0x02), + (10, 235, 0x02), + (15, 235, 0x02), + (24, 235, 0x02), + (31, 235, 0x02), + (41, 235, 0x02), + (56, 235, 0x03), + ], + // 190 + [ + (194, 0, 0x00), + (195, 0, 0x00), + (197, 0, 0x00), + (198, 0, 0x00), + (201, 0, 0x00), + (202, 0, 0x00), + (204, 0, 0x00), + (205, 0, 0x00), + (210, 0, 0x00), + (213, 0, 0x00), + (217, 0, 0x00), + (220, 0, 0x00), + (225, 0, 0x00), + (231, 0, 0x00), + (239, 0, 0x00), + (246, 0, 0x00), + ], + // 191 + [ + (0, 192, 0x02), + (0, 193, 0x02), + (0, 200, 0x02), + (0, 201, 0x02), + (0, 202, 0x02), + (0, 205, 0x02), + (0, 210, 0x02), + (0, 213, 0x02), + (0, 218, 0x02), + (0, 219, 0x02), + (0, 238, 0x02), + (0, 240, 0x02), + (0, 242, 0x02), + (0, 243, 0x02), + (0, 255, 0x02), + (206, 0, 0x00), + ], + // 192 + [ + (1, 192, 0x02), + (22, 192, 0x03), + (1, 193, 0x02), + (22, 193, 0x03), + (1, 200, 0x02), + (22, 200, 0x03), + (1, 201, 0x02), + (22, 201, 0x03), + (1, 202, 0x02), + (22, 202, 0x03), + (1, 205, 0x02), + (22, 205, 0x03), + (1, 210, 0x02), + (22, 210, 0x03), + (1, 213, 0x02), + (22, 213, 0x03), + ], + // 193 + [ + (2, 192, 0x02), + (9, 192, 0x02), + (23, 192, 0x02), + (40, 192, 0x03), + (2, 193, 0x02), + (9, 193, 0x02), + (23, 193, 0x02), + (40, 193, 0x03), + (2, 200, 0x02), + (9, 200, 0x02), + (23, 200, 0x02), + (40, 200, 0x03), + (2, 201, 0x02), + (9, 201, 0x02), + (23, 201, 0x02), + (40, 201, 0x03), + ], + // 194 + [ + (3, 192, 0x02), + (6, 192, 0x02), + (10, 192, 0x02), + (15, 192, 0x02), + (24, 192, 0x02), + (31, 192, 0x02), + (41, 192, 0x02), + (56, 192, 0x03), + (3, 193, 0x02), + (6, 193, 0x02), + (10, 193, 0x02), + (15, 193, 0x02), + (24, 193, 0x02), + (31, 193, 0x02), + (41, 193, 0x02), + (56, 193, 0x03), + ], + // 195 + [ + (3, 200, 0x02), + (6, 200, 0x02), + (10, 200, 0x02), + (15, 200, 0x02), + (24, 200, 0x02), + (31, 200, 0x02), + (41, 200, 0x02), + (56, 200, 0x03), + (3, 201, 0x02), + (6, 201, 0x02), + (10, 201, 0x02), + (15, 201, 0x02), + (24, 201, 0x02), + (31, 201, 0x02), + (41, 201, 0x02), + (56, 201, 0x03), + ], + // 196 + [ + (2, 202, 0x02), + (9, 202, 0x02), + (23, 202, 0x02), + (40, 202, 0x03), + (2, 205, 0x02), + (9, 205, 0x02), + (23, 205, 0x02), + (40, 205, 0x03), + (2, 210, 0x02), + (9, 210, 0x02), + (23, 210, 0x02), + (40, 210, 0x03), + (2, 213, 0x02), + (9, 213, 0x02), + (23, 213, 0x02), + (40, 213, 0x03), + ], + // 197 + [ + (3, 202, 0x02), + (6, 202, 0x02), + (10, 202, 0x02), + (15, 202, 0x02), + (24, 202, 0x02), + (31, 202, 0x02), + (41, 202, 0x02), + (56, 202, 0x03), + (3, 205, 0x02), + (6, 205, 0x02), + (10, 205, 0x02), + (15, 205, 0x02), + (24, 205, 0x02), + (31, 205, 0x02), + (41, 205, 0x02), + (56, 205, 0x03), + ], + // 198 + [ + (3, 210, 0x02), + (6, 210, 0x02), + (10, 210, 0x02), + (15, 210, 0x02), + (24, 210, 0x02), + (31, 210, 0x02), + (41, 210, 0x02), + (56, 210, 0x03), + (3, 213, 0x02), + (6, 213, 0x02), + (10, 213, 0x02), + (15, 213, 0x02), + (24, 213, 0x02), + (31, 213, 0x02), + (41, 213, 0x02), + (56, 213, 0x03), + ], + // 199 + [ + (1, 218, 0x02), + (22, 218, 0x03), + (1, 219, 0x02), + (22, 219, 0x03), + (1, 238, 0x02), + (22, 238, 0x03), + (1, 240, 0x02), + (22, 240, 0x03), + (1, 242, 0x02), + (22, 242, 0x03), + (1, 243, 0x02), + (22, 243, 0x03), + (1, 255, 0x02), + (22, 255, 0x03), + (0, 203, 0x02), + (0, 204, 0x02), + ], + // 200 + [ + (2, 218, 0x02), + (9, 218, 0x02), + (23, 218, 0x02), + (40, 218, 0x03), + (2, 219, 0x02), + (9, 219, 0x02), + (23, 219, 0x02), + (40, 219, 0x03), + (2, 238, 0x02), + (9, 238, 0x02), + (23, 238, 0x02), + (40, 238, 0x03), + (2, 240, 0x02), + (9, 240, 0x02), + (23, 240, 0x02), + (40, 240, 0x03), + ], + // 201 + [ + (3, 218, 0x02), + (6, 218, 0x02), + (10, 218, 0x02), + (15, 218, 0x02), + (24, 218, 0x02), + (31, 218, 0x02), + (41, 218, 0x02), + (56, 218, 0x03), + (3, 219, 0x02), + (6, 219, 0x02), + (10, 219, 0x02), + (15, 219, 0x02), + (24, 219, 0x02), + (31, 219, 0x02), + (41, 219, 0x02), + (56, 219, 0x03), + ], + // 202 + [ + (3, 238, 0x02), + (6, 238, 0x02), + (10, 238, 0x02), + (15, 238, 0x02), + (24, 238, 0x02), + (31, 238, 0x02), + (41, 238, 0x02), + (56, 238, 0x03), + (3, 240, 0x02), + (6, 240, 0x02), + (10, 240, 0x02), + (15, 240, 0x02), + (24, 240, 0x02), + (31, 240, 0x02), + (41, 240, 0x02), + (56, 240, 0x03), + ], + // 203 + [ + (2, 242, 0x02), + (9, 242, 0x02), + (23, 242, 0x02), + (40, 242, 0x03), + (2, 243, 0x02), + (9, 243, 0x02), + (23, 243, 0x02), + (40, 243, 0x03), + (2, 255, 0x02), + (9, 255, 0x02), + (23, 255, 0x02), + (40, 255, 0x03), + (1, 203, 0x02), + (22, 203, 0x03), + (1, 204, 0x02), + (22, 204, 0x03), + ], + // 204 + [ + (3, 242, 0x02), + (6, 242, 0x02), + (10, 242, 0x02), + (15, 242, 0x02), + (24, 242, 0x02), + (31, 242, 0x02), + (41, 242, 0x02), + (56, 242, 0x03), + (3, 243, 0x02), + (6, 243, 0x02), + (10, 243, 0x02), + (15, 243, 0x02), + (24, 243, 0x02), + (31, 243, 0x02), + (41, 243, 0x02), + (56, 243, 0x03), + ], + // 205 + [ + (3, 255, 0x02), + (6, 255, 0x02), + (10, 255, 0x02), + (15, 255, 0x02), + (24, 255, 0x02), + (31, 255, 0x02), + (41, 255, 0x02), + (56, 255, 0x03), + (2, 203, 0x02), + (9, 203, 0x02), + (23, 203, 0x02), + (40, 203, 0x03), + (2, 204, 0x02), + (9, 204, 0x02), + (23, 204, 0x02), + (40, 204, 0x03), + ], + // 206 + [ + (3, 203, 0x02), + (6, 203, 0x02), + (10, 203, 0x02), + (15, 203, 0x02), + (24, 203, 0x02), + (31, 203, 0x02), + (41, 203, 0x02), + (56, 203, 0x03), + (3, 204, 0x02), + (6, 204, 0x02), + (10, 204, 0x02), + (15, 204, 0x02), + (24, 204, 0x02), + (31, 204, 0x02), + (41, 204, 0x02), + (56, 204, 0x03), + ], + // 207 + [ + (211, 0, 0x00), + (212, 0, 0x00), + (214, 0, 0x00), + (215, 0, 0x00), + (218, 0, 0x00), + (219, 0, 0x00), + (221, 0, 0x00), + (222, 0, 0x00), + (226, 0, 0x00), + (228, 0, 0x00), + (232, 0, 0x00), + (235, 0, 0x00), + (240, 0, 0x00), + (243, 0, 0x00), + (247, 0, 0x00), + (250, 0, 0x00), + ], + // 208 + [ + (0, 211, 0x02), + (0, 212, 0x02), + (0, 214, 0x02), + (0, 221, 0x02), + (0, 222, 0x02), + (0, 223, 0x02), + (0, 241, 0x02), + (0, 244, 0x02), + (0, 245, 0x02), + (0, 246, 0x02), + (0, 247, 0x02), + (0, 248, 0x02), + (0, 250, 0x02), + (0, 251, 0x02), + (0, 252, 0x02), + (0, 253, 0x02), + ], + // 209 + [ + (1, 211, 0x02), + (22, 211, 0x03), + (1, 212, 0x02), + (22, 212, 0x03), + (1, 214, 0x02), + (22, 214, 0x03), + (1, 221, 0x02), + (22, 221, 0x03), + (1, 222, 0x02), + (22, 222, 0x03), + (1, 223, 0x02), + (22, 223, 0x03), + (1, 241, 0x02), + (22, 241, 0x03), + (1, 244, 0x02), + (22, 244, 0x03), + ], + // 210 + [ + (2, 211, 0x02), + (9, 211, 0x02), + (23, 211, 0x02), + (40, 211, 0x03), + (2, 212, 0x02), + (9, 212, 0x02), + (23, 212, 0x02), + (40, 212, 0x03), + (2, 214, 0x02), + (9, 214, 0x02), + (23, 214, 0x02), + (40, 214, 0x03), + (2, 221, 0x02), + (9, 221, 0x02), + (23, 221, 0x02), + (40, 221, 0x03), + ], + // 211 + [ + (3, 211, 0x02), + (6, 211, 0x02), + (10, 211, 0x02), + (15, 211, 0x02), + (24, 211, 0x02), + (31, 211, 0x02), + (41, 211, 0x02), + (56, 211, 0x03), + (3, 212, 0x02), + (6, 212, 0x02), + (10, 212, 0x02), + (15, 212, 0x02), + (24, 212, 0x02), + (31, 212, 0x02), + (41, 212, 0x02), + (56, 212, 0x03), + ], + // 212 + [ + (3, 214, 0x02), + (6, 214, 0x02), + (10, 214, 0x02), + (15, 214, 0x02), + (24, 214, 0x02), + (31, 214, 0x02), + (41, 214, 0x02), + (56, 214, 0x03), + (3, 221, 0x02), + (6, 221, 0x02), + (10, 221, 0x02), + (15, 221, 0x02), + (24, 221, 0x02), + (31, 221, 0x02), + (41, 221, 0x02), + (56, 221, 0x03), + ], + // 213 + [ + (2, 222, 0x02), + (9, 222, 0x02), + (23, 222, 0x02), + (40, 222, 0x03), + (2, 223, 0x02), + (9, 223, 0x02), + (23, 223, 0x02), + (40, 223, 0x03), + (2, 241, 0x02), + (9, 241, 0x02), + (23, 241, 0x02), + (40, 241, 0x03), + (2, 244, 0x02), + (9, 244, 0x02), + (23, 244, 0x02), + (40, 244, 0x03), + ], + // 214 + [ + (3, 222, 0x02), + (6, 222, 0x02), + (10, 222, 0x02), + (15, 222, 0x02), + (24, 222, 0x02), + (31, 222, 0x02), + (41, 222, 0x02), + (56, 222, 0x03), + (3, 223, 0x02), + (6, 223, 0x02), + (10, 223, 0x02), + (15, 223, 0x02), + (24, 223, 0x02), + (31, 223, 0x02), + (41, 223, 0x02), + (56, 223, 0x03), + ], + // 215 + [ + (3, 241, 0x02), + (6, 241, 0x02), + (10, 241, 0x02), + (15, 241, 0x02), + (24, 241, 0x02), + (31, 241, 0x02), + (41, 241, 0x02), + (56, 241, 0x03), + (3, 244, 0x02), + (6, 244, 0x02), + (10, 244, 0x02), + (15, 244, 0x02), + (24, 244, 0x02), + (31, 244, 0x02), + (41, 244, 0x02), + (56, 244, 0x03), + ], + // 216 + [ + (1, 245, 0x02), + (22, 245, 0x03), + (1, 246, 0x02), + (22, 246, 0x03), + (1, 247, 0x02), + (22, 247, 0x03), + (1, 248, 0x02), + (22, 248, 0x03), + (1, 250, 0x02), + (22, 250, 0x03), + (1, 251, 0x02), + (22, 251, 0x03), + (1, 252, 0x02), + (22, 252, 0x03), + (1, 253, 0x02), + (22, 253, 0x03), + ], + // 217 + [ + (2, 245, 0x02), + (9, 245, 0x02), + (23, 245, 0x02), + (40, 245, 0x03), + (2, 246, 0x02), + (9, 246, 0x02), + (23, 246, 0x02), + (40, 246, 0x03), + (2, 247, 0x02), + (9, 247, 0x02), + (23, 247, 0x02), + (40, 247, 0x03), + (2, 248, 0x02), + (9, 248, 0x02), + (23, 248, 0x02), + (40, 248, 0x03), + ], + // 218 + [ + (3, 245, 0x02), + (6, 245, 0x02), + (10, 245, 0x02), + (15, 245, 0x02), + (24, 245, 0x02), + (31, 245, 0x02), + (41, 245, 0x02), + (56, 245, 0x03), + (3, 246, 0x02), + (6, 246, 0x02), + (10, 246, 0x02), + (15, 246, 0x02), + (24, 246, 0x02), + (31, 246, 0x02), + (41, 246, 0x02), + (56, 246, 0x03), + ], + // 219 + [ + (3, 247, 0x02), + (6, 247, 0x02), + (10, 247, 0x02), + (15, 247, 0x02), + (24, 247, 0x02), + (31, 247, 0x02), + (41, 247, 0x02), + (56, 247, 0x03), + (3, 248, 0x02), + (6, 248, 0x02), + (10, 248, 0x02), + (15, 248, 0x02), + (24, 248, 0x02), + (31, 248, 0x02), + (41, 248, 0x02), + (56, 248, 0x03), + ], + // 220 + [ + (2, 250, 0x02), + (9, 250, 0x02), + (23, 250, 0x02), + (40, 250, 0x03), + (2, 251, 0x02), + (9, 251, 0x02), + (23, 251, 0x02), + (40, 251, 0x03), + (2, 252, 0x02), + (9, 252, 0x02), + (23, 252, 0x02), + (40, 252, 0x03), + (2, 253, 0x02), + (9, 253, 0x02), + (23, 253, 0x02), + (40, 253, 0x03), + ], + // 221 + [ + (3, 250, 0x02), + (6, 250, 0x02), + (10, 250, 0x02), + (15, 250, 0x02), + (24, 250, 0x02), + (31, 250, 0x02), + (41, 250, 0x02), + (56, 250, 0x03), + (3, 251, 0x02), + (6, 251, 0x02), + (10, 251, 0x02), + (15, 251, 0x02), + (24, 251, 0x02), + (31, 251, 0x02), + (41, 251, 0x02), + (56, 251, 0x03), + ], + // 222 + [ + (3, 252, 0x02), + (6, 252, 0x02), + (10, 252, 0x02), + (15, 252, 0x02), + (24, 252, 0x02), + (31, 252, 0x02), + (41, 252, 0x02), + (56, 252, 0x03), + (3, 253, 0x02), + (6, 253, 0x02), + (10, 253, 0x02), + (15, 253, 0x02), + (24, 253, 0x02), + (31, 253, 0x02), + (41, 253, 0x02), + (56, 253, 0x03), + ], + // 223 + [ + (0, 254, 0x02), + (227, 0, 0x00), + (229, 0, 0x00), + (230, 0, 0x00), + (233, 0, 0x00), + (234, 0, 0x00), + (236, 0, 0x00), + (237, 0, 0x00), + (241, 0, 0x00), + (242, 0, 0x00), + (244, 0, 0x00), + (245, 0, 0x00), + (248, 0, 0x00), + (249, 0, 0x00), + (251, 0, 0x00), + (252, 0, 0x00), + ], + // 224 + [ + (1, 254, 0x02), + (22, 254, 0x03), + (0, 2, 0x02), + (0, 3, 0x02), + (0, 4, 0x02), + (0, 5, 0x02), + (0, 6, 0x02), + (0, 7, 0x02), + (0, 8, 0x02), + (0, 11, 0x02), + (0, 12, 0x02), + (0, 14, 0x02), + (0, 15, 0x02), + (0, 16, 0x02), + (0, 17, 0x02), + (0, 18, 0x02), + ], + // 225 + [ + (2, 254, 0x02), + (9, 254, 0x02), + (23, 254, 0x02), + (40, 254, 0x03), + (1, 2, 0x02), + (22, 2, 0x03), + (1, 3, 0x02), + (22, 3, 0x03), + (1, 4, 0x02), + (22, 4, 0x03), + (1, 5, 0x02), + (22, 5, 0x03), + (1, 6, 0x02), + (22, 6, 0x03), + (1, 7, 0x02), + (22, 7, 0x03), + ], + // 226 + [ + (3, 254, 0x02), + (6, 254, 0x02), + (10, 254, 0x02), + (15, 254, 0x02), + (24, 254, 0x02), + (31, 254, 0x02), + (41, 254, 0x02), + (56, 254, 0x03), + (2, 2, 0x02), + (9, 2, 0x02), + (23, 2, 0x02), + (40, 2, 0x03), + (2, 3, 0x02), + (9, 3, 0x02), + (23, 3, 0x02), + (40, 3, 0x03), + ], + // 227 + [ + (3, 2, 0x02), + (6, 2, 0x02), + (10, 2, 0x02), + (15, 2, 0x02), + (24, 2, 0x02), + (31, 2, 0x02), + (41, 2, 0x02), + (56, 2, 0x03), + (3, 3, 0x02), + (6, 3, 0x02), + (10, 3, 0x02), + (15, 3, 0x02), + (24, 3, 0x02), + (31, 3, 0x02), + (41, 3, 0x02), + (56, 3, 0x03), + ], + // 228 + [ + (2, 4, 0x02), + (9, 4, 0x02), + (23, 4, 0x02), + (40, 4, 0x03), + (2, 5, 0x02), + (9, 5, 0x02), + (23, 5, 0x02), + (40, 5, 0x03), + (2, 6, 0x02), + (9, 6, 0x02), + (23, 6, 0x02), + (40, 6, 0x03), + (2, 7, 0x02), + (9, 7, 0x02), + (23, 7, 0x02), + (40, 7, 0x03), + ], + // 229 + [ + (3, 4, 0x02), + (6, 4, 0x02), + (10, 4, 0x02), + (15, 4, 0x02), + (24, 4, 0x02), + (31, 4, 0x02), + (41, 4, 0x02), + (56, 4, 0x03), + (3, 5, 0x02), + (6, 5, 0x02), + (10, 5, 0x02), + (15, 5, 0x02), + (24, 5, 0x02), + (31, 5, 0x02), + (41, 5, 0x02), + (56, 5, 0x03), + ], + // 230 + [ + (3, 6, 0x02), + (6, 6, 0x02), + (10, 6, 0x02), + (15, 6, 0x02), + (24, 6, 0x02), + (31, 6, 0x02), + (41, 6, 0x02), + (56, 6, 0x03), + (3, 7, 0x02), + (6, 7, 0x02), + (10, 7, 0x02), + (15, 7, 0x02), + (24, 7, 0x02), + (31, 7, 0x02), + (41, 7, 0x02), + (56, 7, 0x03), + ], + // 231 + [ + (1, 8, 0x02), + (22, 8, 0x03), + (1, 11, 0x02), + (22, 11, 0x03), + (1, 12, 0x02), + (22, 12, 0x03), + (1, 14, 0x02), + (22, 14, 0x03), + (1, 15, 0x02), + (22, 15, 0x03), + (1, 16, 0x02), + (22, 16, 0x03), + (1, 17, 0x02), + (22, 17, 0x03), + (1, 18, 0x02), + (22, 18, 0x03), + ], + // 232 + [ + (2, 8, 0x02), + (9, 8, 0x02), + (23, 8, 0x02), + (40, 8, 0x03), + (2, 11, 0x02), + (9, 11, 0x02), + (23, 11, 0x02), + (40, 11, 0x03), + (2, 12, 0x02), + (9, 12, 0x02), + (23, 12, 0x02), + (40, 12, 0x03), + (2, 14, 0x02), + (9, 14, 0x02), + (23, 14, 0x02), + (40, 14, 0x03), + ], + // 233 + [ + (3, 8, 0x02), + (6, 8, 0x02), + (10, 8, 0x02), + (15, 8, 0x02), + (24, 8, 0x02), + (31, 8, 0x02), + (41, 8, 0x02), + (56, 8, 0x03), + (3, 11, 0x02), + (6, 11, 0x02), + (10, 11, 0x02), + (15, 11, 0x02), + (24, 11, 0x02), + (31, 11, 0x02), + (41, 11, 0x02), + (56, 11, 0x03), + ], + // 234 + [ + (3, 12, 0x02), + (6, 12, 0x02), + (10, 12, 0x02), + (15, 12, 0x02), + (24, 12, 0x02), + (31, 12, 0x02), + (41, 12, 0x02), + (56, 12, 0x03), + (3, 14, 0x02), + (6, 14, 0x02), + (10, 14, 0x02), + (15, 14, 0x02), + (24, 14, 0x02), + (31, 14, 0x02), + (41, 14, 0x02), + (56, 14, 0x03), + ], + // 235 + [ + (2, 15, 0x02), + (9, 15, 0x02), + (23, 15, 0x02), + (40, 15, 0x03), + (2, 16, 0x02), + (9, 16, 0x02), + (23, 16, 0x02), + (40, 16, 0x03), + (2, 17, 0x02), + (9, 17, 0x02), + (23, 17, 0x02), + (40, 17, 0x03), + (2, 18, 0x02), + (9, 18, 0x02), + (23, 18, 0x02), + (40, 18, 0x03), + ], + // 236 + [ + (3, 15, 0x02), + (6, 15, 0x02), + (10, 15, 0x02), + (15, 15, 0x02), + (24, 15, 0x02), + (31, 15, 0x02), + (41, 15, 0x02), + (56, 15, 0x03), + (3, 16, 0x02), + (6, 16, 0x02), + (10, 16, 0x02), + (15, 16, 0x02), + (24, 16, 0x02), + (31, 16, 0x02), + (41, 16, 0x02), + (56, 16, 0x03), + ], + // 237 + [ + (3, 17, 0x02), + (6, 17, 0x02), + (10, 17, 0x02), + (15, 17, 0x02), + (24, 17, 0x02), + (31, 17, 0x02), + (41, 17, 0x02), + (56, 17, 0x03), + (3, 18, 0x02), + (6, 18, 0x02), + (10, 18, 0x02), + (15, 18, 0x02), + (24, 18, 0x02), + (31, 18, 0x02), + (41, 18, 0x02), + (56, 18, 0x03), + ], + // 238 + [ + (0, 19, 0x02), + (0, 20, 0x02), + (0, 21, 0x02), + (0, 23, 0x02), + (0, 24, 0x02), + (0, 25, 0x02), + (0, 26, 0x02), + (0, 27, 0x02), + (0, 28, 0x02), + (0, 29, 0x02), + (0, 30, 0x02), + (0, 31, 0x02), + (0, 127, 0x02), + (0, 220, 0x02), + (0, 249, 0x02), + (253, 0, 0x00), + ], + // 239 + [ + (1, 19, 0x02), + (22, 19, 0x03), + (1, 20, 0x02), + (22, 20, 0x03), + (1, 21, 0x02), + (22, 21, 0x03), + (1, 23, 0x02), + (22, 23, 0x03), + (1, 24, 0x02), + (22, 24, 0x03), + (1, 25, 0x02), + (22, 25, 0x03), + (1, 26, 0x02), + (22, 26, 0x03), + (1, 27, 0x02), + (22, 27, 0x03), + ], + // 240 + [ + (2, 19, 0x02), + (9, 19, 0x02), + (23, 19, 0x02), + (40, 19, 0x03), + (2, 20, 0x02), + (9, 20, 0x02), + (23, 20, 0x02), + (40, 20, 0x03), + (2, 21, 0x02), + (9, 21, 0x02), + (23, 21, 0x02), + (40, 21, 0x03), + (2, 23, 0x02), + (9, 23, 0x02), + (23, 23, 0x02), + (40, 23, 0x03), + ], + // 241 + [ + (3, 19, 0x02), + (6, 19, 0x02), + (10, 19, 0x02), + (15, 19, 0x02), + (24, 19, 0x02), + (31, 19, 0x02), + (41, 19, 0x02), + (56, 19, 0x03), + (3, 20, 0x02), + (6, 20, 0x02), + (10, 20, 0x02), + (15, 20, 0x02), + (24, 20, 0x02), + (31, 20, 0x02), + (41, 20, 0x02), + (56, 20, 0x03), + ], + // 242 + [ + (3, 21, 0x02), + (6, 21, 0x02), + (10, 21, 0x02), + (15, 21, 0x02), + (24, 21, 0x02), + (31, 21, 0x02), + (41, 21, 0x02), + (56, 21, 0x03), + (3, 23, 0x02), + (6, 23, 0x02), + (10, 23, 0x02), + (15, 23, 0x02), + (24, 23, 0x02), + (31, 23, 0x02), + (41, 23, 0x02), + (56, 23, 0x03), + ], + // 243 + [ + (2, 24, 0x02), + (9, 24, 0x02), + (23, 24, 0x02), + (40, 24, 0x03), + (2, 25, 0x02), + (9, 25, 0x02), + (23, 25, 0x02), + (40, 25, 0x03), + (2, 26, 0x02), + (9, 26, 0x02), + (23, 26, 0x02), + (40, 26, 0x03), + (2, 27, 0x02), + (9, 27, 0x02), + (23, 27, 0x02), + (40, 27, 0x03), + ], + // 244 + [ + (3, 24, 0x02), + (6, 24, 0x02), + (10, 24, 0x02), + (15, 24, 0x02), + (24, 24, 0x02), + (31, 24, 0x02), + (41, 24, 0x02), + (56, 24, 0x03), + (3, 25, 0x02), + (6, 25, 0x02), + (10, 25, 0x02), + (15, 25, 0x02), + (24, 25, 0x02), + (31, 25, 0x02), + (41, 25, 0x02), + (56, 25, 0x03), + ], + // 245 + [ + (3, 26, 0x02), + (6, 26, 0x02), + (10, 26, 0x02), + (15, 26, 0x02), + (24, 26, 0x02), + (31, 26, 0x02), + (41, 26, 0x02), + (56, 26, 0x03), + (3, 27, 0x02), + (6, 27, 0x02), + (10, 27, 0x02), + (15, 27, 0x02), + (24, 27, 0x02), + (31, 27, 0x02), + (41, 27, 0x02), + (56, 27, 0x03), + ], + // 246 + [ + (1, 28, 0x02), + (22, 28, 0x03), + (1, 29, 0x02), + (22, 29, 0x03), + (1, 30, 0x02), + (22, 30, 0x03), + (1, 31, 0x02), + (22, 31, 0x03), + (1, 127, 0x02), + (22, 127, 0x03), + (1, 220, 0x02), + (22, 220, 0x03), + (1, 249, 0x02), + (22, 249, 0x03), + (254, 0, 0x00), + (255, 0, 0x00), + ], + // 247 + [ + (2, 28, 0x02), + (9, 28, 0x02), + (23, 28, 0x02), + (40, 28, 0x03), + (2, 29, 0x02), + (9, 29, 0x02), + (23, 29, 0x02), + (40, 29, 0x03), + (2, 30, 0x02), + (9, 30, 0x02), + (23, 30, 0x02), + (40, 30, 0x03), + (2, 31, 0x02), + (9, 31, 0x02), + (23, 31, 0x02), + (40, 31, 0x03), + ], + // 248 + [ + (3, 28, 0x02), + (6, 28, 0x02), + (10, 28, 0x02), + (15, 28, 0x02), + (24, 28, 0x02), + (31, 28, 0x02), + (41, 28, 0x02), + (56, 28, 0x03), + (3, 29, 0x02), + (6, 29, 0x02), + (10, 29, 0x02), + (15, 29, 0x02), + (24, 29, 0x02), + (31, 29, 0x02), + (41, 29, 0x02), + (56, 29, 0x03), + ], + // 249 + [ + (3, 30, 0x02), + (6, 30, 0x02), + (10, 30, 0x02), + (15, 30, 0x02), + (24, 30, 0x02), + (31, 30, 0x02), + (41, 30, 0x02), + (56, 30, 0x03), + (3, 31, 0x02), + (6, 31, 0x02), + (10, 31, 0x02), + (15, 31, 0x02), + (24, 31, 0x02), + (31, 31, 0x02), + (41, 31, 0x02), + (56, 31, 0x03), + ], + // 250 + [ + (2, 127, 0x02), + (9, 127, 0x02), + (23, 127, 0x02), + (40, 127, 0x03), + (2, 220, 0x02), + (9, 220, 0x02), + (23, 220, 0x02), + (40, 220, 0x03), + (2, 249, 0x02), + (9, 249, 0x02), + (23, 249, 0x02), + (40, 249, 0x03), + (0, 10, 0x02), + (0, 13, 0x02), + (0, 22, 0x02), + (0, 0, 0x04), + ], + // 251 + [ + (3, 127, 0x02), + (6, 127, 0x02), + (10, 127, 0x02), + (15, 127, 0x02), + (24, 127, 0x02), + (31, 127, 0x02), + (41, 127, 0x02), + (56, 127, 0x03), + (3, 220, 0x02), + (6, 220, 0x02), + (10, 220, 0x02), + (15, 220, 0x02), + (24, 220, 0x02), + (31, 220, 0x02), + (41, 220, 0x02), + (56, 220, 0x03), + ], + // 252 + [ + (3, 249, 0x02), + (6, 249, 0x02), + (10, 249, 0x02), + (15, 249, 0x02), + (24, 249, 0x02), + (31, 249, 0x02), + (41, 249, 0x02), + (56, 249, 0x03), + (1, 10, 0x02), + (22, 10, 0x03), + (1, 13, 0x02), + (22, 13, 0x03), + (1, 22, 0x02), + (22, 22, 0x03), + (0, 0, 0x04), + (0, 0, 0x05), + ], + // 253 + [ + (2, 10, 0x02), + (9, 10, 0x02), + (23, 10, 0x02), + (40, 10, 0x03), + (2, 13, 0x02), + (9, 13, 0x02), + (23, 13, 0x02), + (40, 13, 0x03), + (2, 22, 0x02), + (9, 22, 0x02), + (23, 22, 0x02), + (40, 22, 0x03), + (0, 0, 0x04), + (0, 0, 0x04), + (0, 0, 0x04), + (0, 0, 0x05), + ], + // 254 + [ + (3, 10, 0x02), + (6, 10, 0x02), + (10, 10, 0x02), + (15, 10, 0x02), + (24, 10, 0x02), + (31, 10, 0x02), + (41, 10, 0x02), + (56, 10, 0x03), + (3, 13, 0x02), + (6, 13, 0x02), + (10, 13, 0x02), + (15, 13, 0x02), + (24, 13, 0x02), + (31, 13, 0x02), + (41, 13, 0x02), + (56, 13, 0x03), + ], + // 255 + [ + (3, 22, 0x02), + (6, 22, 0x02), + (10, 22, 0x02), + (15, 22, 0x02), + (24, 22, 0x02), + (31, 22, 0x02), + (41, 22, 0x02), + (56, 22, 0x03), + (0, 0, 0x04), + (0, 0, 0x04), + (0, 0, 0x04), + (0, 0, 0x04), + (0, 0, 0x04), + (0, 0, 0x04), + (0, 0, 0x04), + (0, 0, 0x05), + ], +]; diff --git a/third_party/rust/h2/src/hpack/mod.rs b/third_party/rust/h2/src/hpack/mod.rs new file mode 100644 index 0000000000..12c75d5535 --- /dev/null +++ b/third_party/rust/h2/src/hpack/mod.rs @@ -0,0 +1,12 @@ +mod decoder; +mod encoder; +pub(crate) mod header; +pub(crate) mod huffman; +mod table; + +#[cfg(test)] +mod test; + +pub use self::decoder::{Decoder, DecoderError, NeedMore}; +pub use self::encoder::Encoder; +pub use self::header::{BytesStr, Header}; diff --git a/third_party/rust/h2/src/hpack/table.rs b/third_party/rust/h2/src/hpack/table.rs new file mode 100644 index 0000000000..3e45f413b8 --- /dev/null +++ b/third_party/rust/h2/src/hpack/table.rs @@ -0,0 +1,766 @@ +use super::Header; + +use fnv::FnvHasher; +use http::header; +use http::method::Method; + +use std::collections::VecDeque; +use std::hash::{Hash, Hasher}; +use std::{cmp, mem, usize}; + +/// HPACK encoder table +#[derive(Debug)] +pub struct Table { + mask: usize, + indices: Vec<Option<Pos>>, + slots: VecDeque<Slot>, + inserted: usize, + // Size is in bytes + size: usize, + max_size: usize, +} + +#[derive(Debug)] +pub enum Index { + // The header is already fully indexed + Indexed(usize, Header), + + // The name is indexed, but not the value + Name(usize, Header), + + // The full header has been inserted into the table. + Inserted(usize), + + // Only the value has been inserted (hpack table idx, slots idx) + InsertedValue(usize, usize), + + // The header is not indexed by this table + NotIndexed(Header), +} + +#[derive(Debug)] +struct Slot { + hash: HashValue, + header: Header, + next: Option<usize>, +} + +#[derive(Debug, Clone, Copy, Eq, PartialEq)] +struct Pos { + index: usize, + hash: HashValue, +} + +#[derive(Debug, Copy, Clone, Eq, PartialEq)] +struct HashValue(usize); + +const MAX_SIZE: usize = 1 << 16; +const DYN_OFFSET: usize = 62; + +macro_rules! probe_loop { + ($probe_var: ident < $len: expr, $body: expr) => { + debug_assert!($len > 0); + loop { + if $probe_var < $len { + $body + $probe_var += 1; + } else { + $probe_var = 0; + } + } + }; +} + +impl Table { + pub fn new(max_size: usize, capacity: usize) -> Table { + if capacity == 0 { + Table { + mask: 0, + indices: vec![], + slots: VecDeque::new(), + inserted: 0, + size: 0, + max_size, + } + } else { + let capacity = cmp::max(to_raw_capacity(capacity).next_power_of_two(), 8); + + Table { + mask: capacity.wrapping_sub(1), + indices: vec![None; capacity], + slots: VecDeque::with_capacity(usable_capacity(capacity)), + inserted: 0, + size: 0, + max_size, + } + } + } + + #[inline] + pub fn capacity(&self) -> usize { + usable_capacity(self.indices.len()) + } + + pub fn max_size(&self) -> usize { + self.max_size + } + + /// Gets the header stored in the table + pub fn resolve<'a>(&'a self, index: &'a Index) -> &'a Header { + use self::Index::*; + + match *index { + Indexed(_, ref h) => h, + Name(_, ref h) => h, + Inserted(idx) => &self.slots[idx].header, + InsertedValue(_, idx) => &self.slots[idx].header, + NotIndexed(ref h) => h, + } + } + + pub fn resolve_idx(&self, index: &Index) -> usize { + use self::Index::*; + + match *index { + Indexed(idx, ..) => idx, + Name(idx, ..) => idx, + Inserted(idx) => idx + DYN_OFFSET, + InsertedValue(_name_idx, slot_idx) => slot_idx + DYN_OFFSET, + NotIndexed(_) => panic!("cannot resolve index"), + } + } + + /// Index the header in the HPACK table. + pub fn index(&mut self, header: Header) -> Index { + // Check the static table + let statik = index_static(&header); + + // Don't index certain headers. This logic is borrowed from nghttp2. + if header.skip_value_index() { + // Right now, if this is true, the header name is always in the + // static table. At some point in the future, this might not be true + // and this logic will need to be updated. + debug_assert!(statik.is_some(), "skip_value_index requires a static name",); + return Index::new(statik, header); + } + + // If the header is already indexed by the static table, return that + if let Some((n, true)) = statik { + return Index::Indexed(n, header); + } + + // Don't index large headers + if header.len() * 4 > self.max_size * 3 { + return Index::new(statik, header); + } + + self.index_dynamic(header, statik) + } + + fn index_dynamic(&mut self, header: Header, statik: Option<(usize, bool)>) -> Index { + debug_assert!(self.assert_valid_state("one")); + + if header.len() + self.size < self.max_size || !header.is_sensitive() { + // Only grow internal storage if needed + self.reserve_one(); + } + + if self.indices.is_empty() { + // If `indices` is not empty, then it is impossible for all + // `indices` entries to be `Some`. So, we only need to check for the + // empty case. + return Index::new(statik, header); + } + + let hash = hash_header(&header); + + let desired_pos = desired_pos(self.mask, hash); + let mut probe = desired_pos; + let mut dist = 0; + + // Start at the ideal position, checking all slots + probe_loop!(probe < self.indices.len(), { + if let Some(pos) = self.indices[probe] { + // The slot is already occupied, but check if it has a lower + // displacement. + let their_dist = probe_distance(self.mask, pos.hash, probe); + + let slot_idx = pos.index.wrapping_add(self.inserted); + + if their_dist < dist { + // Index robinhood + return self.index_vacant(header, hash, dist, probe, statik); + } else if pos.hash == hash && self.slots[slot_idx].header.name() == header.name() { + // Matching name, check values + return self.index_occupied(header, hash, pos.index, statik.map(|(n, _)| n)); + } + } else { + return self.index_vacant(header, hash, dist, probe, statik); + } + + dist += 1; + }); + } + + fn index_occupied( + &mut self, + header: Header, + hash: HashValue, + mut index: usize, + statik: Option<usize>, + ) -> Index { + debug_assert!(self.assert_valid_state("top")); + + // There already is a match for the given header name. Check if a value + // matches. The header will also only be inserted if the table is not at + // capacity. + loop { + // Compute the real index into the VecDeque + let real_idx = index.wrapping_add(self.inserted); + + if self.slots[real_idx].header.value_eq(&header) { + // We have a full match! + return Index::Indexed(real_idx + DYN_OFFSET, header); + } + + if let Some(next) = self.slots[real_idx].next { + index = next; + continue; + } + + if header.is_sensitive() { + // Should we assert this? + // debug_assert!(statik.is_none()); + return Index::Name(real_idx + DYN_OFFSET, header); + } + + self.update_size(header.len(), Some(index)); + + // Insert the new header + self.insert(header, hash); + + // Recompute real_idx as it just changed. + let new_real_idx = index.wrapping_add(self.inserted); + + // The previous node in the linked list may have gotten evicted + // while making room for this header. + if new_real_idx < self.slots.len() { + let idx = 0usize.wrapping_sub(self.inserted); + + self.slots[new_real_idx].next = Some(idx); + } + + debug_assert!(self.assert_valid_state("bottom")); + + // Even if the previous header was evicted, we can still reference + // it when inserting the new one... + return if let Some(n) = statik { + // If name is in static table, use it instead + Index::InsertedValue(n, 0) + } else { + Index::InsertedValue(real_idx + DYN_OFFSET, 0) + }; + } + } + + fn index_vacant( + &mut self, + header: Header, + hash: HashValue, + mut dist: usize, + mut probe: usize, + statik: Option<(usize, bool)>, + ) -> Index { + if header.is_sensitive() { + return Index::new(statik, header); + } + + debug_assert!(self.assert_valid_state("top")); + debug_assert!(dist == 0 || self.indices[probe.wrapping_sub(1) & self.mask].is_some()); + + // Passing in `usize::MAX` for prev_idx since there is no previous + // header in this case. + if self.update_size(header.len(), None) { + while dist != 0 { + let back = probe.wrapping_sub(1) & self.mask; + + if let Some(pos) = self.indices[back] { + let their_dist = probe_distance(self.mask, pos.hash, back); + + if their_dist < (dist - 1) { + probe = back; + dist -= 1; + } else { + break; + } + } else { + probe = back; + dist -= 1; + } + } + } + + debug_assert!(self.assert_valid_state("after update")); + + self.insert(header, hash); + + let pos_idx = 0usize.wrapping_sub(self.inserted); + + let prev = mem::replace( + &mut self.indices[probe], + Some(Pos { + index: pos_idx, + hash, + }), + ); + + if let Some(mut prev) = prev { + // Shift forward + let mut probe = probe + 1; + + probe_loop!(probe < self.indices.len(), { + let pos = &mut self.indices[probe]; + + prev = match mem::replace(pos, Some(prev)) { + Some(p) => p, + None => break, + }; + }); + } + + debug_assert!(self.assert_valid_state("bottom")); + + if let Some((n, _)) = statik { + Index::InsertedValue(n, 0) + } else { + Index::Inserted(0) + } + } + + fn insert(&mut self, header: Header, hash: HashValue) { + self.inserted = self.inserted.wrapping_add(1); + + self.slots.push_front(Slot { + hash, + header, + next: None, + }); + } + + pub fn resize(&mut self, size: usize) { + self.max_size = size; + + if size == 0 { + self.size = 0; + + for i in &mut self.indices { + *i = None; + } + + self.slots.clear(); + self.inserted = 0; + } else { + self.converge(None); + } + } + + fn update_size(&mut self, len: usize, prev_idx: Option<usize>) -> bool { + self.size += len; + self.converge(prev_idx) + } + + fn converge(&mut self, prev_idx: Option<usize>) -> bool { + let mut ret = false; + + while self.size > self.max_size { + ret = true; + self.evict(prev_idx); + } + + ret + } + + fn evict(&mut self, prev_idx: Option<usize>) { + let pos_idx = (self.slots.len() - 1).wrapping_sub(self.inserted); + + debug_assert!(!self.slots.is_empty()); + debug_assert!(self.assert_valid_state("one")); + + // Remove the header + let slot = self.slots.pop_back().unwrap(); + let mut probe = desired_pos(self.mask, slot.hash); + + // Update the size + self.size -= slot.header.len(); + + debug_assert_eq!( + self.indices + .iter() + .filter_map(|p| *p) + .filter(|p| p.index == pos_idx) + .count(), + 1 + ); + + // Find the associated position + probe_loop!(probe < self.indices.len(), { + debug_assert!(self.indices[probe].is_some()); + + let mut pos = self.indices[probe].unwrap(); + + if pos.index == pos_idx { + if let Some(idx) = slot.next { + pos.index = idx; + self.indices[probe] = Some(pos); + } else if Some(pos.index) == prev_idx { + pos.index = 0usize.wrapping_sub(self.inserted + 1); + self.indices[probe] = Some(pos); + } else { + self.indices[probe] = None; + self.remove_phase_two(probe); + } + + break; + } + }); + + debug_assert!(self.assert_valid_state("two")); + } + + // Shifts all indices that were displaced by the header that has just been + // removed. + fn remove_phase_two(&mut self, probe: usize) { + let mut last_probe = probe; + let mut probe = probe + 1; + + probe_loop!(probe < self.indices.len(), { + if let Some(pos) = self.indices[probe] { + if probe_distance(self.mask, pos.hash, probe) > 0 { + self.indices[last_probe] = self.indices[probe].take(); + } else { + break; + } + } else { + break; + } + + last_probe = probe; + }); + + debug_assert!(self.assert_valid_state("two")); + } + + fn reserve_one(&mut self) { + let len = self.slots.len(); + + if len == self.capacity() { + if len == 0 { + let new_raw_cap = 8; + self.mask = 8 - 1; + self.indices = vec![None; new_raw_cap]; + } else { + let raw_cap = self.indices.len(); + self.grow(raw_cap << 1); + } + } + } + + #[inline] + fn grow(&mut self, new_raw_cap: usize) { + // This path can never be reached when handling the first allocation in + // the map. + + debug_assert!(self.assert_valid_state("top")); + + // find first ideally placed element -- start of cluster + let mut first_ideal = 0; + + for (i, pos) in self.indices.iter().enumerate() { + if let Some(pos) = *pos { + if 0 == probe_distance(self.mask, pos.hash, i) { + first_ideal = i; + break; + } + } + } + + // visit the entries in an order where we can simply reinsert them + // into self.indices without any bucket stealing. + let old_indices = mem::replace(&mut self.indices, vec![None; new_raw_cap]); + self.mask = new_raw_cap.wrapping_sub(1); + + for &pos in &old_indices[first_ideal..] { + self.reinsert_entry_in_order(pos); + } + + for &pos in &old_indices[..first_ideal] { + self.reinsert_entry_in_order(pos); + } + + debug_assert!(self.assert_valid_state("bottom")); + } + + fn reinsert_entry_in_order(&mut self, pos: Option<Pos>) { + if let Some(pos) = pos { + // Find first empty bucket and insert there + let mut probe = desired_pos(self.mask, pos.hash); + + probe_loop!(probe < self.indices.len(), { + if self.indices[probe].is_none() { + // empty bucket, insert here + self.indices[probe] = Some(pos); + return; + } + + debug_assert!({ + let them = self.indices[probe].unwrap(); + let their_distance = probe_distance(self.mask, them.hash, probe); + let our_distance = probe_distance(self.mask, pos.hash, probe); + + their_distance >= our_distance + }); + }); + } + } + + #[cfg(not(test))] + fn assert_valid_state(&self, _: &'static str) -> bool { + true + } + + #[cfg(test)] + fn assert_valid_state(&self, _msg: &'static str) -> bool { + /* + // Checks that the internal map structure is valid + // + // Ensure all hash codes in indices match the associated slot + for pos in &self.indices { + if let Some(pos) = *pos { + let real_idx = pos.index.wrapping_add(self.inserted); + + if real_idx.wrapping_add(1) != 0 { + assert!(real_idx < self.slots.len(), + "out of index; real={}; len={}, msg={}", + real_idx, self.slots.len(), msg); + + assert_eq!(pos.hash, self.slots[real_idx].hash, + "index hash does not match slot; msg={}", msg); + } + } + } + + // Every index is only available once + for i in 0..self.indices.len() { + if self.indices[i].is_none() { + continue; + } + + for j in i+1..self.indices.len() { + assert_ne!(self.indices[i], self.indices[j], + "duplicate indices; msg={}", msg); + } + } + + for (index, slot) in self.slots.iter().enumerate() { + let mut indexed = None; + + // First, see if the slot is indexed + for (i, pos) in self.indices.iter().enumerate() { + if let Some(pos) = *pos { + let real_idx = pos.index.wrapping_add(self.inserted); + if real_idx == index { + indexed = Some(i); + // Already know that there is no dup, so break + break; + } + } + } + + if let Some(actual) = indexed { + // Ensure that it is accessible.. + let desired = desired_pos(self.mask, slot.hash); + let mut probe = desired; + let mut dist = 0; + + probe_loop!(probe < self.indices.len(), { + assert!(self.indices[probe].is_some(), + "unexpected empty slot; probe={}; hash={:?}; msg={}", + probe, slot.hash, msg); + + let pos = self.indices[probe].unwrap(); + + let their_dist = probe_distance(self.mask, pos.hash, probe); + let real_idx = pos.index.wrapping_add(self.inserted); + + if real_idx == index { + break; + } + + assert!(dist <= their_dist, + "could not find entry; actual={}; desired={}" + + "probe={}, dist={}; their_dist={}; index={}; msg={}", + actual, desired, probe, dist, their_dist, + index.wrapping_sub(self.inserted), msg); + + dist += 1; + }); + } else { + // There is exactly one next link + let cnt = self.slots.iter().map(|s| s.next) + .filter(|n| *n == Some(index.wrapping_sub(self.inserted))) + .count(); + + assert_eq!(1, cnt, "more than one node pointing here; msg={}", msg); + } + } + */ + + // TODO: Ensure linked lists are correct: no cycles, etc... + + true + } +} + +#[cfg(test)] +impl Table { + /// Returns the number of headers in the table + pub fn len(&self) -> usize { + self.slots.len() + } + + /// Returns the table size + pub fn size(&self) -> usize { + self.size + } +} + +impl Index { + fn new(v: Option<(usize, bool)>, e: Header) -> Index { + match v { + None => Index::NotIndexed(e), + Some((n, true)) => Index::Indexed(n, e), + Some((n, false)) => Index::Name(n, e), + } + } +} + +#[inline] +fn usable_capacity(cap: usize) -> usize { + cap - cap / 4 +} + +#[inline] +fn to_raw_capacity(n: usize) -> usize { + n + n / 3 +} + +#[inline] +fn desired_pos(mask: usize, hash: HashValue) -> usize { + hash.0 & mask +} + +#[inline] +fn probe_distance(mask: usize, hash: HashValue, current: usize) -> usize { + current.wrapping_sub(desired_pos(mask, hash)) & mask +} + +fn hash_header(header: &Header) -> HashValue { + const MASK: u64 = (MAX_SIZE as u64) - 1; + + let mut h = FnvHasher::default(); + header.name().hash(&mut h); + HashValue((h.finish() & MASK) as usize) +} + +/// Checks the static table for the header. If found, returns the index and a +/// boolean representing if the value matched as well. +fn index_static(header: &Header) -> Option<(usize, bool)> { + match *header { + Header::Field { + ref name, + ref value, + } => match *name { + header::ACCEPT_CHARSET => Some((15, false)), + header::ACCEPT_ENCODING => { + if value == "gzip, deflate" { + Some((16, true)) + } else { + Some((16, false)) + } + } + header::ACCEPT_LANGUAGE => Some((17, false)), + header::ACCEPT_RANGES => Some((18, false)), + header::ACCEPT => Some((19, false)), + header::ACCESS_CONTROL_ALLOW_ORIGIN => Some((20, false)), + header::AGE => Some((21, false)), + header::ALLOW => Some((22, false)), + header::AUTHORIZATION => Some((23, false)), + header::CACHE_CONTROL => Some((24, false)), + header::CONTENT_DISPOSITION => Some((25, false)), + header::CONTENT_ENCODING => Some((26, false)), + header::CONTENT_LANGUAGE => Some((27, false)), + header::CONTENT_LENGTH => Some((28, false)), + header::CONTENT_LOCATION => Some((29, false)), + header::CONTENT_RANGE => Some((30, false)), + header::CONTENT_TYPE => Some((31, false)), + header::COOKIE => Some((32, false)), + header::DATE => Some((33, false)), + header::ETAG => Some((34, false)), + header::EXPECT => Some((35, false)), + header::EXPIRES => Some((36, false)), + header::FROM => Some((37, false)), + header::HOST => Some((38, false)), + header::IF_MATCH => Some((39, false)), + header::IF_MODIFIED_SINCE => Some((40, false)), + header::IF_NONE_MATCH => Some((41, false)), + header::IF_RANGE => Some((42, false)), + header::IF_UNMODIFIED_SINCE => Some((43, false)), + header::LAST_MODIFIED => Some((44, false)), + header::LINK => Some((45, false)), + header::LOCATION => Some((46, false)), + header::MAX_FORWARDS => Some((47, false)), + header::PROXY_AUTHENTICATE => Some((48, false)), + header::PROXY_AUTHORIZATION => Some((49, false)), + header::RANGE => Some((50, false)), + header::REFERER => Some((51, false)), + header::REFRESH => Some((52, false)), + header::RETRY_AFTER => Some((53, false)), + header::SERVER => Some((54, false)), + header::SET_COOKIE => Some((55, false)), + header::STRICT_TRANSPORT_SECURITY => Some((56, false)), + header::TRANSFER_ENCODING => Some((57, false)), + header::USER_AGENT => Some((58, false)), + header::VARY => Some((59, false)), + header::VIA => Some((60, false)), + header::WWW_AUTHENTICATE => Some((61, false)), + _ => None, + }, + Header::Authority(_) => Some((1, false)), + Header::Method(ref v) => match *v { + Method::GET => Some((2, true)), + Method::POST => Some((3, true)), + _ => Some((2, false)), + }, + Header::Scheme(ref v) => match &**v { + "http" => Some((6, true)), + "https" => Some((7, true)), + _ => Some((6, false)), + }, + Header::Path(ref v) => match &**v { + "/" => Some((4, true)), + "/index.html" => Some((5, true)), + _ => Some((4, false)), + }, + Header::Protocol(..) => None, + Header::Status(ref v) => match u16::from(*v) { + 200 => Some((8, true)), + 204 => Some((9, true)), + 206 => Some((10, true)), + 304 => Some((11, true)), + 400 => Some((12, true)), + 404 => Some((13, true)), + 500 => Some((14, true)), + _ => Some((8, false)), + }, + } +} diff --git a/third_party/rust/h2/src/hpack/test/fixture.rs b/third_party/rust/h2/src/hpack/test/fixture.rs new file mode 100644 index 0000000000..d3f76e3bf8 --- /dev/null +++ b/third_party/rust/h2/src/hpack/test/fixture.rs @@ -0,0 +1,615 @@ +use crate::hpack::{Decoder, Encoder, Header}; + +use bytes::BytesMut; +use hex::FromHex; +use serde_json::Value; + +use std::fs::File; +use std::io::prelude::*; +use std::io::Cursor; +use std::path::Path; +use std::str; + +fn test_fixture(path: &Path) { + let mut file = File::open(path).unwrap(); + let mut data = String::new(); + file.read_to_string(&mut data).unwrap(); + + let story: Value = serde_json::from_str(&data).unwrap(); + test_story(story); +} + +fn test_story(story: Value) { + let story = story.as_object().unwrap(); + + if let Some(cases) = story.get("cases") { + let mut cases: Vec<_> = cases + .as_array() + .unwrap() + .iter() + .map(|case| { + let case = case.as_object().unwrap(); + + let size = case + .get("header_table_size") + .map(|v| v.as_u64().unwrap() as usize); + + let wire = case.get("wire").unwrap().as_str().unwrap(); + let wire: Vec<u8> = FromHex::from_hex(wire.as_bytes()).unwrap(); + + let expect: Vec<_> = case + .get("headers") + .unwrap() + .as_array() + .unwrap() + .iter() + .map(|h| { + let h = h.as_object().unwrap(); + let (name, val) = h.iter().next().unwrap(); + (name.clone(), val.as_str().unwrap().to_string()) + }) + .collect(); + + Case { + seqno: case.get("seqno").unwrap().as_u64().unwrap(), + wire, + expect, + header_table_size: size, + } + }) + .collect(); + + cases.sort_by_key(|c| c.seqno); + + let mut decoder = Decoder::default(); + + // First, check decoding against the fixtures + for case in &cases { + let mut expect = case.expect.clone(); + + if let Some(size) = case.header_table_size { + decoder.queue_size_update(size); + } + + let mut buf = BytesMut::with_capacity(case.wire.len()); + buf.extend_from_slice(&case.wire); + decoder + .decode(&mut Cursor::new(&mut buf), |e| { + let (name, value) = expect.remove(0); + assert_eq!(name, key_str(&e)); + assert_eq!(value, value_str(&e)); + }) + .unwrap(); + + assert_eq!(0, expect.len()); + } + + let mut encoder = Encoder::default(); + let mut decoder = Decoder::default(); + + // Now, encode the headers + for case in &cases { + let limit = 64 * 1024; + let mut buf = BytesMut::with_capacity(limit); + + if let Some(size) = case.header_table_size { + encoder.update_max_size(size); + decoder.queue_size_update(size); + } + + let mut input: Vec<_> = case + .expect + .iter() + .map(|(name, value)| { + Header::new(name.clone().into(), value.clone().into()) + .unwrap() + .into() + }) + .collect(); + + encoder.encode(&mut input.clone().into_iter(), &mut buf); + + decoder + .decode(&mut Cursor::new(&mut buf), |e| { + assert_eq!(e, input.remove(0).reify().unwrap()); + }) + .unwrap(); + + assert_eq!(0, input.len()); + } + } +} + +struct Case { + seqno: u64, + wire: Vec<u8>, + expect: Vec<(String, String)>, + header_table_size: Option<usize>, +} + +fn key_str(e: &Header) -> &str { + match *e { + Header::Field { ref name, .. } => name.as_str(), + Header::Authority(..) => ":authority", + Header::Method(..) => ":method", + Header::Scheme(..) => ":scheme", + Header::Path(..) => ":path", + Header::Protocol(..) => ":protocol", + Header::Status(..) => ":status", + } +} + +fn value_str(e: &Header) -> &str { + match *e { + Header::Field { ref value, .. } => value.to_str().unwrap(), + Header::Authority(ref v) => v, + Header::Method(ref m) => m.as_str(), + Header::Scheme(ref v) => v, + Header::Path(ref v) => v, + Header::Protocol(ref v) => v.as_str(), + Header::Status(ref v) => v.as_str(), + } +} + +macro_rules! fixture_mod { + ($module:ident => { + $( + ($fn:ident, $path:expr); + )+ + }) => { + mod $module { + $( + #[test] + fn $fn() { + let path = ::std::path::Path::new(env!("CARGO_MANIFEST_DIR")) + .join("fixtures/hpack") + .join($path); + + super::test_fixture(path.as_ref()); + } + )+ + } + } +} + +fixture_mod!( + haskell_http2_linear_huffman => { + (story_00, "haskell-http2-linear-huffman/story_00.json"); + (story_01, "haskell-http2-linear-huffman/story_01.json"); + (story_02, "haskell-http2-linear-huffman/story_02.json"); + (story_03, "haskell-http2-linear-huffman/story_03.json"); + (story_04, "haskell-http2-linear-huffman/story_04.json"); + (story_05, "haskell-http2-linear-huffman/story_05.json"); + (story_06, "haskell-http2-linear-huffman/story_06.json"); + (story_07, "haskell-http2-linear-huffman/story_07.json"); + (story_08, "haskell-http2-linear-huffman/story_08.json"); + (story_09, "haskell-http2-linear-huffman/story_09.json"); + (story_10, "haskell-http2-linear-huffman/story_10.json"); + (story_11, "haskell-http2-linear-huffman/story_11.json"); + (story_12, "haskell-http2-linear-huffman/story_12.json"); + (story_13, "haskell-http2-linear-huffman/story_13.json"); + (story_14, "haskell-http2-linear-huffman/story_14.json"); + (story_15, "haskell-http2-linear-huffman/story_15.json"); + (story_16, "haskell-http2-linear-huffman/story_16.json"); + (story_17, "haskell-http2-linear-huffman/story_17.json"); + (story_18, "haskell-http2-linear-huffman/story_18.json"); + (story_19, "haskell-http2-linear-huffman/story_19.json"); + (story_20, "haskell-http2-linear-huffman/story_20.json"); + (story_21, "haskell-http2-linear-huffman/story_21.json"); + (story_22, "haskell-http2-linear-huffman/story_22.json"); + (story_23, "haskell-http2-linear-huffman/story_23.json"); + (story_24, "haskell-http2-linear-huffman/story_24.json"); + (story_25, "haskell-http2-linear-huffman/story_25.json"); + (story_26, "haskell-http2-linear-huffman/story_26.json"); + (story_27, "haskell-http2-linear-huffman/story_27.json"); + (story_28, "haskell-http2-linear-huffman/story_28.json"); + (story_29, "haskell-http2-linear-huffman/story_29.json"); + (story_30, "haskell-http2-linear-huffman/story_30.json"); + (story_31, "haskell-http2-linear-huffman/story_31.json"); + } +); + +fixture_mod!( + python_hpack => { + (story_00, "python-hpack/story_00.json"); + (story_01, "python-hpack/story_01.json"); + (story_02, "python-hpack/story_02.json"); + (story_03, "python-hpack/story_03.json"); + (story_04, "python-hpack/story_04.json"); + (story_05, "python-hpack/story_05.json"); + (story_06, "python-hpack/story_06.json"); + (story_07, "python-hpack/story_07.json"); + (story_08, "python-hpack/story_08.json"); + (story_09, "python-hpack/story_09.json"); + (story_10, "python-hpack/story_10.json"); + (story_11, "python-hpack/story_11.json"); + (story_12, "python-hpack/story_12.json"); + (story_13, "python-hpack/story_13.json"); + (story_14, "python-hpack/story_14.json"); + (story_15, "python-hpack/story_15.json"); + (story_16, "python-hpack/story_16.json"); + (story_17, "python-hpack/story_17.json"); + (story_18, "python-hpack/story_18.json"); + (story_19, "python-hpack/story_19.json"); + (story_20, "python-hpack/story_20.json"); + (story_21, "python-hpack/story_21.json"); + (story_22, "python-hpack/story_22.json"); + (story_23, "python-hpack/story_23.json"); + (story_24, "python-hpack/story_24.json"); + (story_25, "python-hpack/story_25.json"); + (story_26, "python-hpack/story_26.json"); + (story_27, "python-hpack/story_27.json"); + (story_28, "python-hpack/story_28.json"); + (story_29, "python-hpack/story_29.json"); + (story_30, "python-hpack/story_30.json"); + (story_31, "python-hpack/story_31.json"); + } +); + +fixture_mod!( + nghttp2_16384_4096 => { + (story_00, "nghttp2-16384-4096/story_00.json"); + (story_01, "nghttp2-16384-4096/story_01.json"); + (story_02, "nghttp2-16384-4096/story_02.json"); + (story_03, "nghttp2-16384-4096/story_03.json"); + (story_04, "nghttp2-16384-4096/story_04.json"); + (story_05, "nghttp2-16384-4096/story_05.json"); + (story_06, "nghttp2-16384-4096/story_06.json"); + (story_07, "nghttp2-16384-4096/story_07.json"); + (story_08, "nghttp2-16384-4096/story_08.json"); + (story_09, "nghttp2-16384-4096/story_09.json"); + (story_10, "nghttp2-16384-4096/story_10.json"); + (story_11, "nghttp2-16384-4096/story_11.json"); + (story_12, "nghttp2-16384-4096/story_12.json"); + (story_13, "nghttp2-16384-4096/story_13.json"); + (story_14, "nghttp2-16384-4096/story_14.json"); + (story_15, "nghttp2-16384-4096/story_15.json"); + (story_16, "nghttp2-16384-4096/story_16.json"); + (story_17, "nghttp2-16384-4096/story_17.json"); + (story_18, "nghttp2-16384-4096/story_18.json"); + (story_19, "nghttp2-16384-4096/story_19.json"); + (story_20, "nghttp2-16384-4096/story_20.json"); + (story_21, "nghttp2-16384-4096/story_21.json"); + (story_22, "nghttp2-16384-4096/story_22.json"); + (story_23, "nghttp2-16384-4096/story_23.json"); + (story_24, "nghttp2-16384-4096/story_24.json"); + (story_25, "nghttp2-16384-4096/story_25.json"); + (story_26, "nghttp2-16384-4096/story_26.json"); + (story_27, "nghttp2-16384-4096/story_27.json"); + (story_28, "nghttp2-16384-4096/story_28.json"); + (story_29, "nghttp2-16384-4096/story_29.json"); + (story_30, "nghttp2-16384-4096/story_30.json"); + } +); + +fixture_mod!( + node_http2_hpack => { + (story_00, "node-http2-hpack/story_00.json"); + (story_01, "node-http2-hpack/story_01.json"); + (story_02, "node-http2-hpack/story_02.json"); + (story_03, "node-http2-hpack/story_03.json"); + (story_04, "node-http2-hpack/story_04.json"); + (story_05, "node-http2-hpack/story_05.json"); + (story_06, "node-http2-hpack/story_06.json"); + (story_07, "node-http2-hpack/story_07.json"); + (story_08, "node-http2-hpack/story_08.json"); + (story_09, "node-http2-hpack/story_09.json"); + (story_10, "node-http2-hpack/story_10.json"); + (story_11, "node-http2-hpack/story_11.json"); + (story_12, "node-http2-hpack/story_12.json"); + (story_13, "node-http2-hpack/story_13.json"); + (story_14, "node-http2-hpack/story_14.json"); + (story_15, "node-http2-hpack/story_15.json"); + (story_16, "node-http2-hpack/story_16.json"); + (story_17, "node-http2-hpack/story_17.json"); + (story_18, "node-http2-hpack/story_18.json"); + (story_19, "node-http2-hpack/story_19.json"); + (story_20, "node-http2-hpack/story_20.json"); + (story_21, "node-http2-hpack/story_21.json"); + (story_22, "node-http2-hpack/story_22.json"); + (story_23, "node-http2-hpack/story_23.json"); + (story_24, "node-http2-hpack/story_24.json"); + (story_25, "node-http2-hpack/story_25.json"); + (story_26, "node-http2-hpack/story_26.json"); + (story_27, "node-http2-hpack/story_27.json"); + (story_28, "node-http2-hpack/story_28.json"); + (story_29, "node-http2-hpack/story_29.json"); + (story_30, "node-http2-hpack/story_30.json"); + (story_31, "node-http2-hpack/story_31.json"); + } +); + +fixture_mod!( + nghttp2_change_table_size => { + (story_00, "nghttp2-change-table-size/story_00.json"); + (story_01, "nghttp2-change-table-size/story_01.json"); + (story_02, "nghttp2-change-table-size/story_02.json"); + (story_03, "nghttp2-change-table-size/story_03.json"); + (story_04, "nghttp2-change-table-size/story_04.json"); + (story_05, "nghttp2-change-table-size/story_05.json"); + (story_06, "nghttp2-change-table-size/story_06.json"); + (story_07, "nghttp2-change-table-size/story_07.json"); + (story_08, "nghttp2-change-table-size/story_08.json"); + (story_09, "nghttp2-change-table-size/story_09.json"); + (story_10, "nghttp2-change-table-size/story_10.json"); + (story_11, "nghttp2-change-table-size/story_11.json"); + (story_12, "nghttp2-change-table-size/story_12.json"); + (story_13, "nghttp2-change-table-size/story_13.json"); + (story_14, "nghttp2-change-table-size/story_14.json"); + (story_15, "nghttp2-change-table-size/story_15.json"); + (story_16, "nghttp2-change-table-size/story_16.json"); + (story_17, "nghttp2-change-table-size/story_17.json"); + (story_18, "nghttp2-change-table-size/story_18.json"); + (story_19, "nghttp2-change-table-size/story_19.json"); + (story_20, "nghttp2-change-table-size/story_20.json"); + (story_21, "nghttp2-change-table-size/story_21.json"); + (story_22, "nghttp2-change-table-size/story_22.json"); + (story_23, "nghttp2-change-table-size/story_23.json"); + (story_24, "nghttp2-change-table-size/story_24.json"); + (story_25, "nghttp2-change-table-size/story_25.json"); + (story_26, "nghttp2-change-table-size/story_26.json"); + (story_27, "nghttp2-change-table-size/story_27.json"); + (story_28, "nghttp2-change-table-size/story_28.json"); + (story_29, "nghttp2-change-table-size/story_29.json"); + (story_30, "nghttp2-change-table-size/story_30.json"); + } +); + +fixture_mod!( + haskell_http2_static_huffman => { + (story_00, "haskell-http2-static-huffman/story_00.json"); + (story_01, "haskell-http2-static-huffman/story_01.json"); + (story_02, "haskell-http2-static-huffman/story_02.json"); + (story_03, "haskell-http2-static-huffman/story_03.json"); + (story_04, "haskell-http2-static-huffman/story_04.json"); + (story_05, "haskell-http2-static-huffman/story_05.json"); + (story_06, "haskell-http2-static-huffman/story_06.json"); + (story_07, "haskell-http2-static-huffman/story_07.json"); + (story_08, "haskell-http2-static-huffman/story_08.json"); + (story_09, "haskell-http2-static-huffman/story_09.json"); + (story_10, "haskell-http2-static-huffman/story_10.json"); + (story_11, "haskell-http2-static-huffman/story_11.json"); + (story_12, "haskell-http2-static-huffman/story_12.json"); + (story_13, "haskell-http2-static-huffman/story_13.json"); + (story_14, "haskell-http2-static-huffman/story_14.json"); + (story_15, "haskell-http2-static-huffman/story_15.json"); + (story_16, "haskell-http2-static-huffman/story_16.json"); + (story_17, "haskell-http2-static-huffman/story_17.json"); + (story_18, "haskell-http2-static-huffman/story_18.json"); + (story_19, "haskell-http2-static-huffman/story_19.json"); + (story_20, "haskell-http2-static-huffman/story_20.json"); + (story_21, "haskell-http2-static-huffman/story_21.json"); + (story_22, "haskell-http2-static-huffman/story_22.json"); + (story_23, "haskell-http2-static-huffman/story_23.json"); + (story_24, "haskell-http2-static-huffman/story_24.json"); + (story_25, "haskell-http2-static-huffman/story_25.json"); + (story_26, "haskell-http2-static-huffman/story_26.json"); + (story_27, "haskell-http2-static-huffman/story_27.json"); + (story_28, "haskell-http2-static-huffman/story_28.json"); + (story_29, "haskell-http2-static-huffman/story_29.json"); + (story_30, "haskell-http2-static-huffman/story_30.json"); + (story_31, "haskell-http2-static-huffman/story_31.json"); + } +); + +fixture_mod!( + haskell_http2_naive_huffman => { + (story_00, "haskell-http2-naive-huffman/story_00.json"); + (story_01, "haskell-http2-naive-huffman/story_01.json"); + (story_02, "haskell-http2-naive-huffman/story_02.json"); + (story_03, "haskell-http2-naive-huffman/story_03.json"); + (story_04, "haskell-http2-naive-huffman/story_04.json"); + (story_05, "haskell-http2-naive-huffman/story_05.json"); + (story_06, "haskell-http2-naive-huffman/story_06.json"); + (story_07, "haskell-http2-naive-huffman/story_07.json"); + (story_08, "haskell-http2-naive-huffman/story_08.json"); + (story_09, "haskell-http2-naive-huffman/story_09.json"); + (story_10, "haskell-http2-naive-huffman/story_10.json"); + (story_11, "haskell-http2-naive-huffman/story_11.json"); + (story_12, "haskell-http2-naive-huffman/story_12.json"); + (story_13, "haskell-http2-naive-huffman/story_13.json"); + (story_14, "haskell-http2-naive-huffman/story_14.json"); + (story_15, "haskell-http2-naive-huffman/story_15.json"); + (story_16, "haskell-http2-naive-huffman/story_16.json"); + (story_17, "haskell-http2-naive-huffman/story_17.json"); + (story_18, "haskell-http2-naive-huffman/story_18.json"); + (story_19, "haskell-http2-naive-huffman/story_19.json"); + (story_20, "haskell-http2-naive-huffman/story_20.json"); + (story_21, "haskell-http2-naive-huffman/story_21.json"); + (story_22, "haskell-http2-naive-huffman/story_22.json"); + (story_23, "haskell-http2-naive-huffman/story_23.json"); + (story_24, "haskell-http2-naive-huffman/story_24.json"); + (story_25, "haskell-http2-naive-huffman/story_25.json"); + (story_26, "haskell-http2-naive-huffman/story_26.json"); + (story_27, "haskell-http2-naive-huffman/story_27.json"); + (story_28, "haskell-http2-naive-huffman/story_28.json"); + (story_29, "haskell-http2-naive-huffman/story_29.json"); + (story_30, "haskell-http2-naive-huffman/story_30.json"); + (story_31, "haskell-http2-naive-huffman/story_31.json"); + } +); + +fixture_mod!( + haskell_http2_naive => { + (story_00, "haskell-http2-naive/story_00.json"); + (story_01, "haskell-http2-naive/story_01.json"); + (story_02, "haskell-http2-naive/story_02.json"); + (story_03, "haskell-http2-naive/story_03.json"); + (story_04, "haskell-http2-naive/story_04.json"); + (story_05, "haskell-http2-naive/story_05.json"); + (story_06, "haskell-http2-naive/story_06.json"); + (story_07, "haskell-http2-naive/story_07.json"); + (story_08, "haskell-http2-naive/story_08.json"); + (story_09, "haskell-http2-naive/story_09.json"); + (story_10, "haskell-http2-naive/story_10.json"); + (story_11, "haskell-http2-naive/story_11.json"); + (story_12, "haskell-http2-naive/story_12.json"); + (story_13, "haskell-http2-naive/story_13.json"); + (story_14, "haskell-http2-naive/story_14.json"); + (story_15, "haskell-http2-naive/story_15.json"); + (story_16, "haskell-http2-naive/story_16.json"); + (story_17, "haskell-http2-naive/story_17.json"); + (story_18, "haskell-http2-naive/story_18.json"); + (story_19, "haskell-http2-naive/story_19.json"); + (story_20, "haskell-http2-naive/story_20.json"); + (story_21, "haskell-http2-naive/story_21.json"); + (story_22, "haskell-http2-naive/story_22.json"); + (story_23, "haskell-http2-naive/story_23.json"); + (story_24, "haskell-http2-naive/story_24.json"); + (story_25, "haskell-http2-naive/story_25.json"); + (story_26, "haskell-http2-naive/story_26.json"); + (story_27, "haskell-http2-naive/story_27.json"); + (story_28, "haskell-http2-naive/story_28.json"); + (story_29, "haskell-http2-naive/story_29.json"); + (story_30, "haskell-http2-naive/story_30.json"); + (story_31, "haskell-http2-naive/story_31.json"); + } +); + +fixture_mod!( + haskell_http2_static => { + (story_00, "haskell-http2-static/story_00.json"); + (story_01, "haskell-http2-static/story_01.json"); + (story_02, "haskell-http2-static/story_02.json"); + (story_03, "haskell-http2-static/story_03.json"); + (story_04, "haskell-http2-static/story_04.json"); + (story_05, "haskell-http2-static/story_05.json"); + (story_06, "haskell-http2-static/story_06.json"); + (story_07, "haskell-http2-static/story_07.json"); + (story_08, "haskell-http2-static/story_08.json"); + (story_09, "haskell-http2-static/story_09.json"); + (story_10, "haskell-http2-static/story_10.json"); + (story_11, "haskell-http2-static/story_11.json"); + (story_12, "haskell-http2-static/story_12.json"); + (story_13, "haskell-http2-static/story_13.json"); + (story_14, "haskell-http2-static/story_14.json"); + (story_15, "haskell-http2-static/story_15.json"); + (story_16, "haskell-http2-static/story_16.json"); + (story_17, "haskell-http2-static/story_17.json"); + (story_18, "haskell-http2-static/story_18.json"); + (story_19, "haskell-http2-static/story_19.json"); + (story_20, "haskell-http2-static/story_20.json"); + (story_21, "haskell-http2-static/story_21.json"); + (story_22, "haskell-http2-static/story_22.json"); + (story_23, "haskell-http2-static/story_23.json"); + (story_24, "haskell-http2-static/story_24.json"); + (story_25, "haskell-http2-static/story_25.json"); + (story_26, "haskell-http2-static/story_26.json"); + (story_27, "haskell-http2-static/story_27.json"); + (story_28, "haskell-http2-static/story_28.json"); + (story_29, "haskell-http2-static/story_29.json"); + (story_30, "haskell-http2-static/story_30.json"); + (story_31, "haskell-http2-static/story_31.json"); + } +); + +fixture_mod!( + nghttp2 => { + (story_00, "nghttp2/story_00.json"); + (story_01, "nghttp2/story_01.json"); + (story_02, "nghttp2/story_02.json"); + (story_03, "nghttp2/story_03.json"); + (story_04, "nghttp2/story_04.json"); + (story_05, "nghttp2/story_05.json"); + (story_06, "nghttp2/story_06.json"); + (story_07, "nghttp2/story_07.json"); + (story_08, "nghttp2/story_08.json"); + (story_09, "nghttp2/story_09.json"); + (story_10, "nghttp2/story_10.json"); + (story_11, "nghttp2/story_11.json"); + (story_12, "nghttp2/story_12.json"); + (story_13, "nghttp2/story_13.json"); + (story_14, "nghttp2/story_14.json"); + (story_15, "nghttp2/story_15.json"); + (story_16, "nghttp2/story_16.json"); + (story_17, "nghttp2/story_17.json"); + (story_18, "nghttp2/story_18.json"); + (story_19, "nghttp2/story_19.json"); + (story_20, "nghttp2/story_20.json"); + (story_21, "nghttp2/story_21.json"); + (story_22, "nghttp2/story_22.json"); + (story_23, "nghttp2/story_23.json"); + (story_24, "nghttp2/story_24.json"); + (story_25, "nghttp2/story_25.json"); + (story_26, "nghttp2/story_26.json"); + (story_27, "nghttp2/story_27.json"); + (story_28, "nghttp2/story_28.json"); + (story_29, "nghttp2/story_29.json"); + (story_30, "nghttp2/story_30.json"); + (story_31, "nghttp2/story_31.json"); + } +); + +fixture_mod!( + haskell_http2_linear => { + (story_00, "haskell-http2-linear/story_00.json"); + (story_01, "haskell-http2-linear/story_01.json"); + (story_02, "haskell-http2-linear/story_02.json"); + (story_03, "haskell-http2-linear/story_03.json"); + (story_04, "haskell-http2-linear/story_04.json"); + (story_05, "haskell-http2-linear/story_05.json"); + (story_06, "haskell-http2-linear/story_06.json"); + (story_07, "haskell-http2-linear/story_07.json"); + (story_08, "haskell-http2-linear/story_08.json"); + (story_09, "haskell-http2-linear/story_09.json"); + (story_10, "haskell-http2-linear/story_10.json"); + (story_11, "haskell-http2-linear/story_11.json"); + (story_12, "haskell-http2-linear/story_12.json"); + (story_13, "haskell-http2-linear/story_13.json"); + (story_14, "haskell-http2-linear/story_14.json"); + (story_15, "haskell-http2-linear/story_15.json"); + (story_16, "haskell-http2-linear/story_16.json"); + (story_17, "haskell-http2-linear/story_17.json"); + (story_18, "haskell-http2-linear/story_18.json"); + (story_19, "haskell-http2-linear/story_19.json"); + (story_20, "haskell-http2-linear/story_20.json"); + (story_21, "haskell-http2-linear/story_21.json"); + (story_22, "haskell-http2-linear/story_22.json"); + (story_23, "haskell-http2-linear/story_23.json"); + (story_24, "haskell-http2-linear/story_24.json"); + (story_25, "haskell-http2-linear/story_25.json"); + (story_26, "haskell-http2-linear/story_26.json"); + (story_27, "haskell-http2-linear/story_27.json"); + (story_28, "haskell-http2-linear/story_28.json"); + (story_29, "haskell-http2-linear/story_29.json"); + (story_30, "haskell-http2-linear/story_30.json"); + (story_31, "haskell-http2-linear/story_31.json"); + } +); + +fixture_mod!( + go_hpack => { + (story_00, "go-hpack/story_00.json"); + (story_01, "go-hpack/story_01.json"); + (story_02, "go-hpack/story_02.json"); + (story_03, "go-hpack/story_03.json"); + (story_04, "go-hpack/story_04.json"); + (story_05, "go-hpack/story_05.json"); + (story_06, "go-hpack/story_06.json"); + (story_07, "go-hpack/story_07.json"); + (story_08, "go-hpack/story_08.json"); + (story_09, "go-hpack/story_09.json"); + (story_10, "go-hpack/story_10.json"); + (story_11, "go-hpack/story_11.json"); + (story_12, "go-hpack/story_12.json"); + (story_13, "go-hpack/story_13.json"); + (story_14, "go-hpack/story_14.json"); + (story_15, "go-hpack/story_15.json"); + (story_16, "go-hpack/story_16.json"); + (story_17, "go-hpack/story_17.json"); + (story_18, "go-hpack/story_18.json"); + (story_19, "go-hpack/story_19.json"); + (story_20, "go-hpack/story_20.json"); + (story_21, "go-hpack/story_21.json"); + (story_22, "go-hpack/story_22.json"); + (story_23, "go-hpack/story_23.json"); + (story_24, "go-hpack/story_24.json"); + (story_25, "go-hpack/story_25.json"); + (story_26, "go-hpack/story_26.json"); + (story_27, "go-hpack/story_27.json"); + (story_28, "go-hpack/story_28.json"); + (story_29, "go-hpack/story_29.json"); + (story_30, "go-hpack/story_30.json"); + (story_31, "go-hpack/story_31.json"); + } +); diff --git a/third_party/rust/h2/src/hpack/test/fuzz.rs b/third_party/rust/h2/src/hpack/test/fuzz.rs new file mode 100644 index 0000000000..af9e8ea23a --- /dev/null +++ b/third_party/rust/h2/src/hpack/test/fuzz.rs @@ -0,0 +1,365 @@ +use crate::hpack::{Decoder, Encoder, Header}; + +use http::header::{HeaderName, HeaderValue}; + +use bytes::BytesMut; +use quickcheck::{Arbitrary, Gen, QuickCheck, TestResult}; +use rand::distributions::Slice; +use rand::rngs::StdRng; +use rand::{thread_rng, Rng, SeedableRng}; + +use std::io::Cursor; + +const MAX_CHUNK: usize = 2 * 1024; + +#[test] +fn hpack_fuzz() { + let _ = env_logger::try_init(); + fn prop(fuzz: FuzzHpack) -> TestResult { + fuzz.run(); + TestResult::from_bool(true) + } + + QuickCheck::new() + .tests(100) + .quickcheck(prop as fn(FuzzHpack) -> TestResult) +} + +/* +// If wanting to test with a specific feed, uncomment and fill in the seed. +#[test] +fn hpack_fuzz_seeded() { + let _ = env_logger::try_init(); + let seed = [/* fill me in*/]; + FuzzHpack::new(seed).run(); +} +*/ + +#[derive(Debug, Clone)] +struct FuzzHpack { + // The set of headers to encode / decode + frames: Vec<HeaderFrame>, +} + +#[derive(Debug, Clone)] +struct HeaderFrame { + resizes: Vec<usize>, + headers: Vec<Header<Option<HeaderName>>>, +} + +impl FuzzHpack { + fn new(seed: [u8; 32]) -> FuzzHpack { + // Seed the RNG + let mut rng = StdRng::from_seed(seed); + + // Generates a bunch of source headers + let mut source: Vec<Header<Option<HeaderName>>> = vec![]; + + for _ in 0..2000 { + source.push(gen_header(&mut rng)); + } + + // Actual test run headers + let num: usize = rng.gen_range(40..500); + + let mut frames: Vec<HeaderFrame> = vec![]; + let mut added = 0; + + let skew: i32 = rng.gen_range(1..5); + + // Rough number of headers to add + while added < num { + let mut frame = HeaderFrame { + resizes: vec![], + headers: vec![], + }; + + match rng.gen_range(0..20) { + 0 => { + // Two resizes + let high = rng.gen_range(128..MAX_CHUNK * 2); + let low = rng.gen_range(0..high); + + frame.resizes.extend([low, high]); + } + 1..=3 => { + frame.resizes.push(rng.gen_range(128..MAX_CHUNK * 2)); + } + _ => {} + } + + let mut is_name_required = true; + + for _ in 0..rng.gen_range(1..(num - added) + 1) { + let x: f64 = rng.gen_range(0.0..1.0); + let x = x.powi(skew); + + let i = (x * source.len() as f64) as usize; + + let header = &source[i]; + match header { + Header::Field { name: None, .. } => { + if is_name_required { + continue; + } + } + Header::Field { .. } => { + is_name_required = false; + } + _ => { + // pseudos can't be followed by a header with no name + is_name_required = true; + } + } + + frame.headers.push(header.clone()); + + added += 1; + } + + frames.push(frame); + } + + FuzzHpack { frames } + } + + fn run(self) { + let frames = self.frames; + let mut expect = vec![]; + + let mut encoder = Encoder::default(); + let mut decoder = Decoder::default(); + + for frame in frames { + // build "expected" frames, such that decoding headers always + // includes a name + let mut prev_name = None; + for header in &frame.headers { + match header.clone().reify() { + Ok(h) => { + prev_name = match h { + Header::Field { ref name, .. } => Some(name.clone()), + _ => None, + }; + expect.push(h); + } + Err(value) => { + expect.push(Header::Field { + name: prev_name.as_ref().cloned().expect("previous header name"), + value, + }); + } + } + } + + let mut buf = BytesMut::new(); + + if let Some(max) = frame.resizes.iter().max() { + decoder.queue_size_update(*max); + } + + // Apply resizes + for resize in &frame.resizes { + encoder.update_max_size(*resize); + } + + encoder.encode(frame.headers, &mut buf); + + // Decode the chunk! + decoder + .decode(&mut Cursor::new(&mut buf), |h| { + let e = expect.remove(0); + assert_eq!(h, e); + }) + .expect("full decode"); + } + + assert_eq!(0, expect.len()); + } +} + +impl Arbitrary for FuzzHpack { + fn arbitrary(_: &mut Gen) -> Self { + FuzzHpack::new(thread_rng().gen()) + } +} + +fn gen_header(g: &mut StdRng) -> Header<Option<HeaderName>> { + use http::{Method, StatusCode}; + + if g.gen_ratio(1, 10) { + match g.gen_range(0u32..5) { + 0 => { + let value = gen_string(g, 4, 20); + Header::Authority(to_shared(value)) + } + 1 => { + let method = match g.gen_range(0u32..6) { + 0 => Method::GET, + 1 => Method::POST, + 2 => Method::PUT, + 3 => Method::PATCH, + 4 => Method::DELETE, + 5 => { + let n: usize = g.gen_range(3..7); + let bytes: Vec<u8> = (0..n) + .map(|_| *g.sample(Slice::new(b"ABCDEFGHIJKLMNOPQRSTUVWXYZ").unwrap())) + .collect(); + + Method::from_bytes(&bytes).unwrap() + } + _ => unreachable!(), + }; + + Header::Method(method) + } + 2 => { + let value = match g.gen_range(0u32..2) { + 0 => "http", + 1 => "https", + _ => unreachable!(), + }; + + Header::Scheme(to_shared(value.to_string())) + } + 3 => { + let value = match g.gen_range(0u32..100) { + 0 => "/".to_string(), + 1 => "/index.html".to_string(), + _ => gen_string(g, 2, 20), + }; + + Header::Path(to_shared(value)) + } + 4 => { + let status = (g.gen::<u16>() % 500) + 100; + + Header::Status(StatusCode::from_u16(status).unwrap()) + } + _ => unreachable!(), + } + } else { + let name = if g.gen_ratio(1, 10) { + None + } else { + Some(gen_header_name(g)) + }; + let mut value = gen_header_value(g); + + if g.gen_ratio(1, 30) { + value.set_sensitive(true); + } + + Header::Field { name, value } + } +} + +fn gen_header_name(g: &mut StdRng) -> HeaderName { + use http::header; + + if g.gen_ratio(1, 2) { + g.sample( + Slice::new(&[ + header::ACCEPT, + header::ACCEPT_CHARSET, + header::ACCEPT_ENCODING, + header::ACCEPT_LANGUAGE, + header::ACCEPT_RANGES, + header::ACCESS_CONTROL_ALLOW_CREDENTIALS, + header::ACCESS_CONTROL_ALLOW_HEADERS, + header::ACCESS_CONTROL_ALLOW_METHODS, + header::ACCESS_CONTROL_ALLOW_ORIGIN, + header::ACCESS_CONTROL_EXPOSE_HEADERS, + header::ACCESS_CONTROL_MAX_AGE, + header::ACCESS_CONTROL_REQUEST_HEADERS, + header::ACCESS_CONTROL_REQUEST_METHOD, + header::AGE, + header::ALLOW, + header::ALT_SVC, + header::AUTHORIZATION, + header::CACHE_CONTROL, + header::CONNECTION, + header::CONTENT_DISPOSITION, + header::CONTENT_ENCODING, + header::CONTENT_LANGUAGE, + header::CONTENT_LENGTH, + header::CONTENT_LOCATION, + header::CONTENT_RANGE, + header::CONTENT_SECURITY_POLICY, + header::CONTENT_SECURITY_POLICY_REPORT_ONLY, + header::CONTENT_TYPE, + header::COOKIE, + header::DNT, + header::DATE, + header::ETAG, + header::EXPECT, + header::EXPIRES, + header::FORWARDED, + header::FROM, + header::HOST, + header::IF_MATCH, + header::IF_MODIFIED_SINCE, + header::IF_NONE_MATCH, + header::IF_RANGE, + header::IF_UNMODIFIED_SINCE, + header::LAST_MODIFIED, + header::LINK, + header::LOCATION, + header::MAX_FORWARDS, + header::ORIGIN, + header::PRAGMA, + header::PROXY_AUTHENTICATE, + header::PROXY_AUTHORIZATION, + header::PUBLIC_KEY_PINS, + header::PUBLIC_KEY_PINS_REPORT_ONLY, + header::RANGE, + header::REFERER, + header::REFERRER_POLICY, + header::REFRESH, + header::RETRY_AFTER, + header::SERVER, + header::SET_COOKIE, + header::STRICT_TRANSPORT_SECURITY, + header::TE, + header::TRAILER, + header::TRANSFER_ENCODING, + header::USER_AGENT, + header::UPGRADE, + header::UPGRADE_INSECURE_REQUESTS, + header::VARY, + header::VIA, + header::WARNING, + header::WWW_AUTHENTICATE, + header::X_CONTENT_TYPE_OPTIONS, + header::X_DNS_PREFETCH_CONTROL, + header::X_FRAME_OPTIONS, + header::X_XSS_PROTECTION, + ]) + .unwrap(), + ) + .clone() + } else { + let value = gen_string(g, 1, 25); + HeaderName::from_bytes(value.as_bytes()).unwrap() + } +} + +fn gen_header_value(g: &mut StdRng) -> HeaderValue { + let value = gen_string(g, 0, 70); + HeaderValue::from_bytes(value.as_bytes()).unwrap() +} + +fn gen_string(g: &mut StdRng, min: usize, max: usize) -> String { + let bytes: Vec<_> = (min..max) + .map(|_| { + // Chars to pick from + *g.sample(Slice::new(b"ABCDEFGHIJKLMNOPQRSTUVabcdefghilpqrstuvwxyz----").unwrap()) + }) + .collect(); + + String::from_utf8(bytes).unwrap() +} + +fn to_shared(src: String) -> crate::hpack::BytesStr { + crate::hpack::BytesStr::from(src.as_str()) +} diff --git a/third_party/rust/h2/src/hpack/test/mod.rs b/third_party/rust/h2/src/hpack/test/mod.rs new file mode 100644 index 0000000000..9b1f27169d --- /dev/null +++ b/third_party/rust/h2/src/hpack/test/mod.rs @@ -0,0 +1,2 @@ +mod fixture; +mod fuzz; |