From 1b6a04ca5504955c571d1c97504fb45ea0befee4 Mon Sep 17 00:00:00 2001
From: Valentin Popov <valentin@popov.link>
Date: Mon, 8 Jan 2024 01:21:28 +0400
Subject: Initial vendor packages
Signed-off-by: Valentin Popov <valentin@popov.link>
---
vendor/image/src/codecs/webp/huffman.rs | 202 ++++++++++++++++++++++++++++++++
1 file changed, 202 insertions(+)
create mode 100644 vendor/image/src/codecs/webp/huffman.rs
(limited to 'vendor/image/src/codecs/webp/huffman.rs')
diff --git a/vendor/image/src/codecs/webp/huffman.rs b/vendor/image/src/codecs/webp/huffman.rs
new file mode 100644
index 0000000..986eee6
--- /dev/null
+++ b/vendor/image/src/codecs/webp/huffman.rs
@@ -0,0 +1,202 @@
+use std::convert::TryInto;
+
+use super::lossless::BitReader;
+use super::lossless::DecoderError;
+use crate::ImageResult;
+
+/// Rudimentary utility for reading Canonical Huffman Codes.
+/// Based off https://github.com/webmproject/libwebp/blob/7f8472a610b61ec780ef0a8873cd954ac512a505/src/utils/huffman.c
+///
+
+const MAX_ALLOWED_CODE_LENGTH: usize = 15;
+
+#[derive(Clone, Copy, Debug, PartialEq, Eq)]
+enum HuffmanTreeNode {
+ Branch(usize), //offset in vector to children
+ Leaf(u16), //symbol stored in leaf
+ Empty,
+}
+
+/// Huffman tree
+#[derive(Clone, Debug, Default)]
+pub(crate) struct HuffmanTree {
+ tree: Vec<HuffmanTreeNode>,
+ max_nodes: usize,
+ num_nodes: usize,
+}
+
+impl HuffmanTree {
+ fn is_full(&self) -> bool {
+ self.num_nodes == self.max_nodes
+ }
+
+ /// Turns a node from empty into a branch and assigns its children
+ fn assign_children(&mut self, node_index: usize) -> usize {
+ let offset_index = self.num_nodes - node_index;
+ self.tree[node_index] = HuffmanTreeNode::Branch(offset_index);
+ self.num_nodes += 2;
+
+ offset_index
+ }
+
+ /// Init a huffman tree
+ fn init(num_leaves: usize) -> ImageResult<HuffmanTree> {
+ if num_leaves == 0 {
+ return Err(DecoderError::HuffmanError.into());
+ }
+
+ let max_nodes = 2 * num_leaves - 1;
+ let tree = vec![HuffmanTreeNode::Empty; max_nodes];
+ let num_nodes = 1;
+
+ let tree = HuffmanTree {
+ tree,
+ max_nodes,
+ num_nodes,
+ };
+
+ Ok(tree)
+ }
+
+ /// Converts code lengths to codes
+ fn code_lengths_to_codes(code_lengths: &[u16]) -> ImageResult<Vec<Option<u16>>> {
+ let max_code_length = *code_lengths
+ .iter()
+ .reduce(|a, b| if a >= b { a } else { b })
+ .unwrap();
+
+ if max_code_length > MAX_ALLOWED_CODE_LENGTH.try_into().unwrap() {
+ return Err(DecoderError::HuffmanError.into());
+ }
+
+ let mut code_length_hist = vec![0; MAX_ALLOWED_CODE_LENGTH + 1];
+
+ for &length in code_lengths.iter() {
+ code_length_hist[usize::from(length)] += 1;
+ }
+
+ code_length_hist[0] = 0;
+
+ let mut curr_code = 0;
+ let mut next_codes = vec![None; MAX_ALLOWED_CODE_LENGTH + 1];
+
+ for code_len in 1..=usize::from(max_code_length) {
+ curr_code = (curr_code + code_length_hist[code_len - 1]) << 1;
+ next_codes[code_len] = Some(curr_code);
+ }
+
+ let mut huff_codes = vec![None; code_lengths.len()];
+
+ for (symbol, &length) in code_lengths.iter().enumerate() {
+ let length = usize::from(length);
+ if length > 0 {
+ huff_codes[symbol] = next_codes[length];
+ if let Some(value) = next_codes[length].as_mut() {
+ *value += 1;
+ }
+ } else {
+ huff_codes[symbol] = None;
+ }
+ }
+
+ Ok(huff_codes)
+ }
+
+ /// Adds a symbol to a huffman tree
+ fn add_symbol(&mut self, symbol: u16, code: u16, code_length: u16) -> ImageResult<()> {
+ let mut node_index = 0;
+ let code = usize::from(code);
+
+ for length in (0..code_length).rev() {
+ if node_index >= self.max_nodes {
+ return Err(DecoderError::HuffmanError.into());
+ }
+
+ let node = self.tree[node_index];
+
+ let offset = match node {
+ HuffmanTreeNode::Empty => {
+ if self.is_full() {
+ return Err(DecoderError::HuffmanError.into());
+ }
+ self.assign_children(node_index)
+ }
+ HuffmanTreeNode::Leaf(_) => return Err(DecoderError::HuffmanError.into()),
+ HuffmanTreeNode::Branch(offset) => offset,
+ };
+
+ node_index += offset + ((code >> length) & 1);
+ }
+
+ match self.tree[node_index] {
+ HuffmanTreeNode::Empty => self.tree[node_index] = HuffmanTreeNode::Leaf(symbol),
+ HuffmanTreeNode::Leaf(_) => return Err(DecoderError::HuffmanError.into()),
+ HuffmanTreeNode::Branch(_offset) => return Err(DecoderError::HuffmanError.into()),
+ }
+
+ Ok(())
+ }
+
+ /// Builds a tree implicitly, just from code lengths
+ pub(crate) fn build_implicit(code_lengths: Vec<u16>) -> ImageResult<HuffmanTree> {
+ let mut num_symbols = 0;
+ let mut root_symbol = 0;
+
+ for (symbol, length) in code_lengths.iter().enumerate() {
+ if *length > 0 {
+ num_symbols += 1;
+ root_symbol = symbol.try_into().unwrap();
+ }
+ }
+
+ let mut tree = HuffmanTree::init(num_symbols)?;
+
+ if num_symbols == 1 {
+ tree.add_symbol(root_symbol, 0, 0)?;
+ } else {
+ let codes = HuffmanTree::code_lengths_to_codes(&code_lengths)?;
+
+ for (symbol, &length) in code_lengths.iter().enumerate() {
+ if length > 0 && codes[symbol].is_some() {
+ tree.add_symbol(symbol.try_into().unwrap(), codes[symbol].unwrap(), length)?;
+ }
+ }
+ }
+
+ Ok(tree)
+ }
+
+ /// Builds a tree explicitly from lengths, codes and symbols
+ pub(crate) fn build_explicit(
+ code_lengths: Vec<u16>,
+ codes: Vec<u16>,
+ symbols: Vec<u16>,
+ ) -> ImageResult<HuffmanTree> {
+ let mut tree = HuffmanTree::init(symbols.len())?;
+
+ for i in 0..symbols.len() {
+ tree.add_symbol(symbols[i], codes[i], code_lengths[i])?;
+ }
+
+ Ok(tree)
+ }
+
+ /// Reads a symbol using the bitstream
+ pub(crate) fn read_symbol(&self, bit_reader: &mut BitReader) -> ImageResult<u16> {
+ let mut index = 0;
+ let mut node = self.tree[index];
+
+ while let HuffmanTreeNode::Branch(children_offset) = node {
+ index += children_offset + bit_reader.read_bits::<usize>(1)?;
+ node = self.tree[index];
+ }
+
+ let symbol = match node {
+ HuffmanTreeNode::Branch(_) => unreachable!(),
+ HuffmanTreeNode::Empty => return Err(DecoderError::HuffmanError.into()),
+ HuffmanTreeNode::Leaf(symbol) => symbol,
+ };
+
+ Ok(symbol)
+ }
+}
--
cgit v1.2.3