summaryrefslogtreecommitdiffstats
path: root/third_party/rust/neqo-qpack/src/huffman.rs
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/rust/neqo-qpack/src/huffman.rs')
-rw-r--r--third_party/rust/neqo-qpack/src/huffman.rs256
1 files changed, 256 insertions, 0 deletions
diff --git a/third_party/rust/neqo-qpack/src/huffman.rs b/third_party/rust/neqo-qpack/src/huffman.rs
new file mode 100644
index 0000000000..31657ca826
--- /dev/null
+++ b/third_party/rust/neqo-qpack/src/huffman.rs
@@ -0,0 +1,256 @@
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use crate::huffman_decode_helper::{HuffmanDecoderNode, HUFFMAN_DECODE_ROOT};
+use crate::huffman_table::HUFFMAN_TABLE;
+use crate::{Error, Res};
+use std::convert::TryFrom;
+
+struct BitReader<'a> {
+ input: &'a [u8],
+ offset: usize,
+ current_bit: u8,
+}
+
+impl<'a> BitReader<'a> {
+ pub fn new(input: &'a [u8]) -> Self {
+ BitReader {
+ input,
+ offset: 0,
+ current_bit: 8,
+ }
+ }
+
+ pub fn read_bit(&mut self) -> Res<u8> {
+ if self.input.len() == self.offset {
+ return Err(Error::NeedMoreData);
+ }
+
+ if self.current_bit == 0 {
+ self.offset += 1;
+ if self.offset == self.input.len() {
+ return Err(Error::NeedMoreData);
+ }
+ self.current_bit = 8;
+ }
+ self.current_bit -= 1;
+ Ok((self.input[self.offset] >> self.current_bit) & 0x01)
+ }
+
+ pub fn verify_ending(&mut self, i: u8) -> Res<()> {
+ if (i + self.current_bit) > 7 {
+ return Err(Error::HuffmanDecompressionFailed);
+ }
+
+ if self.input.is_empty() {
+ Ok(())
+ } else if self.offset != self.input.len() {
+ Err(Error::HuffmanDecompressionFailed)
+ } else if self.input[self.input.len() - 1] & ((0x1 << (i + self.current_bit)) - 1)
+ == ((0x1 << (i + self.current_bit)) - 1)
+ {
+ self.current_bit = 0;
+ Ok(())
+ } else {
+ Err(Error::HuffmanDecompressionFailed)
+ }
+ }
+
+ pub fn has_more_data(&self) -> bool {
+ !self.input.is_empty() && (self.offset != self.input.len() || (self.current_bit != 0))
+ }
+}
+
+/// Decodes huffman encoded input.
+/// # Errors
+/// This function may return `HuffmanDecompressionFailed` if `input` is not a correct huffman-encoded array of bits.
+/// # Panics
+/// Never, but rust can't know that.
+pub fn decode_huffman(input: &[u8]) -> Res<Vec<u8>> {
+ let mut reader = BitReader::new(input);
+ let mut output = Vec::new();
+ while reader.has_more_data() {
+ if let Some(c) = decode_character(&mut reader)? {
+ if c == 256 {
+ return Err(Error::HuffmanDecompressionFailed);
+ }
+ output.push(u8::try_from(c).unwrap());
+ }
+ }
+
+ Ok(output)
+}
+
+fn decode_character(reader: &mut BitReader) -> Res<Option<u16>> {
+ let mut node: &HuffmanDecoderNode = &HUFFMAN_DECODE_ROOT;
+ let mut i = 0;
+ while node.value.is_none() {
+ match reader.read_bit() {
+ Err(_) => {
+ reader.verify_ending(i)?;
+ return Ok(None);
+ }
+ Ok(b) => {
+ i += 1;
+ if let Some(next) = &node.next[usize::from(b)] {
+ node = next;
+ } else {
+ reader.verify_ending(i)?;
+ return Ok(None);
+ }
+ }
+ }
+ }
+ debug_assert!(node.value.is_some());
+ Ok(node.value)
+}
+
+/// # Panics
+/// Never, but rust doesn't know that.
+#[must_use]
+pub fn encode_huffman(input: &[u8]) -> Vec<u8> {
+ let mut output: Vec<u8> = Vec::new();
+ let mut left: u8 = 8;
+ let mut saved: u8 = 0;
+ for c in input {
+ let mut e = HUFFMAN_TABLE[*c as usize];
+
+ // Fill the previous byte
+ if e.len < left {
+ let b = u8::try_from(e.val & 0xFF).unwrap();
+ saved |= b << (left - e.len);
+ left -= e.len;
+ e.len = 0;
+ } else {
+ let v: u8 = u8::try_from(e.val >> (e.len - left)).unwrap();
+ saved |= v;
+ output.push(saved);
+ e.len -= left;
+ left = 8;
+ saved = 0;
+ }
+
+ // Write full bytes
+ while e.len >= 8 {
+ let v: u8 = u8::try_from((e.val >> (e.len - 8)) & 0xFF).unwrap();
+ output.push(v);
+ e.len -= 8;
+ }
+
+ // Write the rest into saved.
+ if e.len > 0 {
+ saved = u8::try_from(e.val & ((1 << e.len) - 1)).unwrap() << (8 - e.len);
+ left = 8 - e.len;
+ }
+ }
+
+ if left < 8 {
+ let v: u8 = (1 << left) - 1;
+ saved |= v;
+ output.push(saved);
+ }
+
+ output
+}
+
+#[cfg(test)]
+mod tests {
+ use super::{decode_huffman, encode_huffman, Error};
+
+ struct TestElement {
+ pub val: &'static [u8],
+ pub res: &'static [u8],
+ }
+ const TEST_CASES: &[TestElement] = &[
+ TestElement {
+ val: b"www.example.com",
+ res: &[
+ 0xf1, 0xe3, 0xc2, 0xe5, 0xf2, 0x3a, 0x6b, 0xa0, 0xab, 0x90, 0xf4, 0xff,
+ ],
+ },
+ TestElement {
+ val: b"no-cache",
+ res: &[0xa8, 0xeb, 0x10, 0x64, 0x9c, 0xbf],
+ },
+ TestElement {
+ val: b"custom-key",
+ res: &[0x25, 0xa8, 0x49, 0xe9, 0x5b, 0xa9, 0x7d, 0x7f],
+ },
+ TestElement {
+ val: b"custom-value",
+ res: &[0x25, 0xa8, 0x49, 0xe9, 0x5b, 0xb8, 0xe8, 0xb4, 0xbf],
+ },
+ TestElement {
+ val: b"private",
+ res: &[0xae, 0xc3, 0x77, 0x1a, 0x4b],
+ },
+ TestElement {
+ val: b"Mon, 21 Oct 2013 20:13:21 GMT",
+ res: &[
+ 0xd0, 0x7a, 0xbe, 0x94, 0x10, 0x54, 0xd4, 0x44, 0xa8, 0x20, 0x05, 0x95, 0x04, 0x0b,
+ 0x81, 0x66, 0xe0, 0x82, 0xa6, 0x2d, 0x1b, 0xff,
+ ],
+ },
+ TestElement {
+ val: b"https://www.example.com",
+ res: &[
+ 0x9d, 0x29, 0xad, 0x17, 0x18, 0x63, 0xc7, 0x8f, 0x0b, 0x97, 0xc8, 0xe9, 0xae, 0x82,
+ 0xae, 0x43, 0xd3,
+ ],
+ },
+ TestElement {
+ val: b"Mon, 21 Oct 2013 20:13:22 GMT",
+ res: &[
+ 0xd0, 0x7a, 0xbe, 0x94, 0x10, 0x54, 0xd4, 0x44, 0xa8, 0x20, 0x05, 0x95, 0x04, 0x0b,
+ 0x81, 0x66, 0xe0, 0x84, 0xa6, 0x2d, 0x1b, 0xff,
+ ],
+ },
+ TestElement {
+ val: b"gzip",
+ res: &[0x9b, 0xd9, 0xab],
+ },
+ TestElement {
+ val: b"foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1",
+ res: &[
+ 0x94, 0xe7, 0x82, 0x1d, 0xd7, 0xf2, 0xe6, 0xc7, 0xb3, 0x35, 0xdf, 0xdf, 0xcd, 0x5b,
+ 0x39, 0x60, 0xd5, 0xaf, 0x27, 0x08, 0x7f, 0x36, 0x72, 0xc1, 0xab, 0x27, 0x0f, 0xb5,
+ 0x29, 0x1f, 0x95, 0x87, 0x31, 0x60, 0x65, 0xc0, 0x03, 0xed, 0x4e, 0xe5, 0xb1, 0x06,
+ 0x3d, 0x50, 0x07,
+ ],
+ },
+ TestElement {
+ val: b"<?\\ >",
+ res: &[0xff, 0xf9, 0xfe, 0x7f, 0xff, 0x05, 0x3f, 0xef],
+ },
+ ];
+
+ const WRONG_END: &[u8] = &[0xa8, 0xeb, 0x10, 0x64, 0x9c, 0xaf];
+
+ #[test]
+ fn test_encoder() {
+ for e in TEST_CASES {
+ let out = encode_huffman(e.val);
+ assert_eq!(out[..], *e.res);
+ }
+ }
+
+ #[test]
+ fn test_decoder() {
+ for e in TEST_CASES {
+ let res = decode_huffman(e.res);
+ assert!(res.is_ok());
+ assert_eq!(res.unwrap()[..], *e.val);
+ }
+ }
+
+ #[test]
+ fn decoder_error_wrong_ending() {
+ assert_eq!(
+ decode_huffman(WRONG_END),
+ Err(Error::HuffmanDecompressionFailed)
+ );
+ }
+}