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)
+        );
+    }
+}