| 1 |
/*! # Static Huffman Coding. |
| 2 |
|
| 3 |
In the following example, letters represent leaves and numbers represent branches. |
| 4 |
Branch numbers indicate their positions in a vector in which the tree is being stored. |
| 5 |
|
| 6 |
```text |
| 7 |
0 |
| 8 |
/ \ |
| 9 |
a 2 |
| 10 |
/ \ |
| 11 |
3 4 |
| 12 |
/ \ / \ |
| 13 |
b c 7 8 |
| 14 |
/ \ / \ |
| 15 |
d e 11 12 |
| 16 |
/ \ / \ |
| 17 |
f g h i |
| 18 |
``` |
| 19 |
|
| 20 |
The above tree can be built from the following `lengths`: |
| 21 |
|
| 22 |
```text |
| 23 |
a -> 1 |
| 24 |
b -> 3 |
| 25 |
c -> 3 |
| 26 |
d -> 4 |
| 27 |
e -> 4 |
| 28 |
f -> 5 |
| 29 |
g -> 5 |
| 30 |
h -> 5 |
| 31 |
i -> 5 |
| 32 |
``` |
| 33 |
|
| 34 |
When reading, the following bit paths will result in finding the particular leaves: |
| 35 |
|
| 36 |
```text |
| 37 |
0 -> a |
| 38 |
100 -> b |
| 39 |
101 -> c |
| 40 |
1100 -> d |
| 41 |
1101 -> e |
| 42 |
11100 -> f |
| 43 |
11101 -> g |
| 44 |
11110 -> h |
| 45 |
11111 -> i |
| 46 |
``` |
| 47 |
*/ |
| 48 |
use core::cmp::Ordering; |
| 49 |
use core::fmt; |
| 50 |
use crate::error::LhaError; |
| 51 |
use crate::bitstream::BitRead; |
| 52 |
#[cfg(not(feature = "std"))] |
| 53 |
use alloc::{vec::Vec, string::String}; |
| 54 |
|
| 55 |
pub mod entry; |
| 56 |
use entry::*; |
| 57 |
|
| 58 |
/// A static Huffman tree. |
| 59 |
#[derive(Debug, Clone)] |
| 60 |
pub struct HuffTree { |
| 61 |
tree: Vec<TreeEntry> |
| 62 |
} |
| 63 |
|
| 64 |
impl HuffTree { |
| 65 |
/// Creates a new and empty `HuffTree` with the reserved node capacity. |
| 66 |
/// |
| 67 |
/// Any attempt to read from a new tree will result in panic. |
| 68 |
pub fn with_capacity(capacity: usize) -> Self { |
| 69 |
let tree = Vec::with_capacity(capacity); |
| 70 |
HuffTree { tree } |
| 71 |
} |
| 72 |
/// Initializes a `HuffTree` in such a way that any attept to read from it will always |
| 73 |
/// result in the given value, without even reading any position bits. |
| 74 |
pub fn set_single(&mut self, value: u16) { |
| 75 |
self.tree.clear(); |
| 76 |
self.tree.push(TreeEntry::leaf(value)); |
| 77 |
} |
| 78 |
/// Builds the tree from the given array of lengths. |
| 79 |
/// |
| 80 |
/// Each entry's index represents the `value` stored in tree leaves. Each entry's content represents |
| 81 |
/// the `length` (or depth), measured in nodes from the tree root, at which the leaf is being created. |
| 82 |
/// |
| 83 |
/// * Entries containing `0` are being ignored. |
| 84 |
/// * If too many entries contain the same `length`, exceeding the given `length` capacity, an error |
| 85 |
/// is being returned. |
| 86 |
/// * If the size of the argument slice is larger than or equal to the [TreeEntry::MAX_INDEX] / 2, |
| 87 |
/// an error is being returned. |
| 88 |
/// * If the number of created nodes would exceed [TreeEntry::MAX_INDEX], an error is being returned. |
| 89 |
/// * An error is returned if a built tree is incomplete. |
| 90 |
pub fn build_tree(&mut self, value_lengths: &[u8]) -> Result<(), &'static str> { |
| 91 |
// println!("({}) {:?}", value_lengths.len(), value_lengths); |
| 92 |
if value_lengths.len() > TreeEntry::MAX_INDEX / 2 { |
| 93 |
return Err("too many code lengths"); |
| 94 |
} |
| 95 |
let tree = &mut self.tree; |
| 96 |
|
| 97 |
tree.clear(); |
| 98 |
// the number of allocated tree indices |
| 99 |
// the tree size should be equal to the value of this variable |
| 100 |
let mut max_allocated: usize = 1; // start with a single (root) node |
| 101 |
for current_len in 1u8.. { |
| 102 |
// add missing branches |
| 103 |
let max_limit = max_allocated; |
| 104 |
for _ in tree.len()..max_limit { |
| 105 |
match TreeEntry::branch(max_allocated) { |
| 106 |
Ok(branch) => tree.push(branch), |
| 107 |
Err(e) => { |
| 108 |
// make sure no outstanding branch indices exist |
| 109 |
tree.clear(); |
| 110 |
return Err(e); |
| 111 |
} |
| 112 |
} |
| 113 |
// for every branch node, two new child nodes are required |
| 114 |
max_allocated += 2; |
| 115 |
} |
| 116 |
// fill tree with leaves found in the lengths table at the current length |
| 117 |
let more_leaves = value_lengths.iter().copied().zip(0..) |
| 118 |
.fold(false, |mut more, (len, value)| { |
| 119 |
match len.cmp(¤t_len) { |
| 120 |
Ordering::Equal => { |
| 121 |
tree.push(TreeEntry::leaf(value)); |
| 122 |
} |
| 123 |
Ordering::Greater => { |
| 124 |
// there are more leaves to process |
| 125 |
more = true; |
| 126 |
} |
| 127 |
Ordering::Less => {} |
| 128 |
} |
| 129 |
more |
| 130 |
}); |
| 131 |
if tree.len() > max_allocated { |
| 132 |
return Err("too many leaves"); |
| 133 |
} |
| 134 |
if !more_leaves { |
| 135 |
break; |
| 136 |
} |
| 137 |
} |
| 138 |
// println!("tree missing leaves: {}", max_allocated - tree.len()); |
| 139 |
if tree.len() != max_allocated { |
| 140 |
return Err("missing some leaves") |
| 141 |
} |
| 142 |
// // make sure no outstanding indices exist, perhaps this should be reported as an error |
| 143 |
// tree.extend( |
| 144 |
// (tree.len()..max_allocated).map(|_| TreeEntry::leaf(0) ) |
| 145 |
// ); |
| 146 |
Ok(()) |
| 147 |
} |
| 148 |
/// Returns the `value` of the leaf by following the bit `path` read from the given bit reader. |
| 149 |
/// |
| 150 |
/// Bits are being read from the stream until a leaf is being encountered. The `value` stored in that |
| 151 |
/// leaf is being returned. |
| 152 |
/// |
| 153 |
/// If a branch is encountered a bit of value `0` indicates that the left node should be followed, |
| 154 |
/// and `1` to take the path to the right. |
| 155 |
/// |
| 156 |
/// If a tree has been initialized with [HuffTree::set_single] this method will always return the |
| 157 |
/// single `value`, without reading any bits from the stream. |
| 158 |
/// |
| 159 |
/// # Panics |
| 160 |
/// Panics if a tree has not been built or otherwise initialized as a single value tree. |
| 161 |
pub fn read_entry<R: BitRead>(&self, mut path: R) -> Result<u16, LhaError<R::Error>> { |
| 162 |
let tree = &self.tree; |
| 163 |
let mut node = &tree[0]; // panics if tree uninitialized |
| 164 |
loop { |
| 165 |
match node.as_type() { |
| 166 |
NodeType::Leaf(code) => return Ok(code), |
| 167 |
NodeType::Branch(index) => { |
| 168 |
let index = index as usize + path.read_bits::<usize>(1)?; |
| 169 |
debug_assert!(index < tree.len()); |
| 170 |
node = unsafe { |
| 171 |
// safe because tree was initialized in a sane way, |
| 172 |
// no outstanding child index has been used |
| 173 |
tree.get_unchecked(index) |
| 174 |
}; |
| 175 |
} |
| 176 |
} |
| 177 |
} |
| 178 |
} |
| 179 |
} |
| 180 |
|
| 181 |
impl fmt::Display for HuffTree { |
| 182 |
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
| 183 |
|
| 184 |
fn fmt_step(tree: &Vec<TreeEntry>, index: usize, f: &mut fmt::Formatter<'_>, prefix: &mut String) -> fmt::Result { |
| 185 |
match tree[index].as_type() { |
| 186 |
NodeType::Leaf(code) => writeln!(f, "{} -> {}", prefix, code)?, |
| 187 |
NodeType::Branch(index) => { |
| 188 |
prefix.push('0'); |
| 189 |
fmt_step(tree, index as usize, f, prefix)?; |
| 190 |
prefix.pop(); |
| 191 |
prefix.push('1'); |
| 192 |
fmt_step(tree, index as usize + 1, f, prefix)?; |
| 193 |
prefix.pop(); |
| 194 |
} |
| 195 |
} |
| 196 |
Ok(()) |
| 197 |
} |
| 198 |
|
| 199 |
if !self.tree.is_empty() { |
| 200 |
let mut prefix = String::new(); |
| 201 |
fmt_step(&self.tree, 0, f, &mut prefix)?; |
| 202 |
} |
| 203 |
Ok(()) |
| 204 |
} |
| 205 |
} |
| 206 |
|
| 207 |
#[cfg(feature = "std")] |
| 208 |
#[cfg(test)] |
| 209 |
mod tests { |
| 210 |
use crate::bitstream::BitStream; |
| 211 |
use std::collections::{HashSet, HashMap}; |
| 212 |
use super::*; |
| 213 |
|
| 214 |
fn validate_tree(tree: &HuffTree, num_leaves: usize) { |
| 215 |
let mut leaves: HashMap<u16, usize> = HashMap::with_capacity(num_leaves); |
| 216 |
let mut children: HashSet<u16> = HashSet::with_capacity(tree.tree.len()); |
| 217 |
for (index, node) in tree.tree.iter().enumerate() { |
| 218 |
match node.as_type() { |
| 219 |
NodeType::Leaf(value) => { |
| 220 |
// all leaves should be unique |
| 221 |
assert!(leaves.insert(value, index).is_none()); |
| 222 |
} |
| 223 |
NodeType::Branch(child_index) => { |
| 224 |
// invalid (default) node should not be present |
| 225 |
assert!(child_index != 0); |
| 226 |
// child_index should not exceed the tree length |
| 227 |
assert!((child_index as usize) < tree.tree.len() - 1); |
| 228 |
// all child indexes should be odd |
| 229 |
assert!(child_index & 1 == 1); |
| 230 |
// there must be no duplicate parents of the same children |
| 231 |
assert!(children.insert(child_index)); |
| 232 |
} |
| 233 |
} |
| 234 |
} |
| 235 |
// all leaves should be present |
| 236 |
assert_eq!(leaves.len(), num_leaves); |
| 237 |
// all leaves should be reachable and on the unique path |
| 238 |
fn into_branch(nodes: &[TreeEntry], index: usize, leaves: &mut HashSet<u16>) { |
| 239 |
match nodes[index].as_type() { |
| 240 |
NodeType::Leaf(code) => { |
| 241 |
assert!(leaves.insert(code)); |
| 242 |
} |
| 243 |
NodeType::Branch(index) => { |
| 244 |
into_branch(nodes, index as usize, leaves); |
| 245 |
into_branch(nodes, index as usize + 1, leaves); |
| 246 |
} |
| 247 |
} |
| 248 |
} |
| 249 |
let mut leaves: HashSet<u16> = HashSet::with_capacity(num_leaves); |
| 250 |
into_branch(&tree.tree, 0, &mut leaves); |
| 251 |
assert_eq!(leaves.len(), num_leaves); |
| 252 |
} |
| 253 |
|
| 254 |
#[test] |
| 255 |
fn hufftree_works() { |
| 256 |
let mut tree = HuffTree::with_capacity(0); |
| 257 |
println!("{}", tree); |
| 258 |
tree.set_single(42); |
| 259 |
validate_tree(&tree, 1); |
| 260 |
let path = BitStream::new([].as_ref()); |
| 261 |
assert_eq!(tree.read_entry(path).unwrap(), 42); |
| 262 |
println!("{}", tree); |
| 263 |
|
| 264 |
tree.build_tree(&[0, 1, 0, 1]).unwrap(); |
| 265 |
validate_tree(&tree, 2); |
| 266 |
println!("{}", tree); |
| 267 |
|
| 268 |
tree.build_tree(&[0, 0, 0, 1, 0, 3, 3, 0, 4, 4, 5, 0, 0, 5, 5, 5]).unwrap(); |
| 269 |
println!("{}", tree); |
| 270 |
validate_tree(&tree, 9); |
| 271 |
assert_eq!(tree.tree.len(), 9 + 8); |
| 272 |
let bits: &[u8] = &[0b01001011, 0b10011011, 0b11001110, 0b11111011, 0b11100000]; |
| 273 |
let mut path = BitStream::new(bits); |
| 274 |
let mut res = Vec::new(); |
| 275 |
for _ in 0..9 { |
| 276 |
res.push(tree.read_entry(&mut path).unwrap()); |
| 277 |
} |
| 278 |
assert_eq!(res, [3, 5, 6, 8, 9, 10, 13, 14, 15]); |
| 279 |
|
| 280 |
assert!(tree.build_tree(&[0, 1, 0, 1, 1]).is_err()); |
| 281 |
assert!(tree.build_tree(&[0, 1, 0, 1, 10]).is_err()); |
| 282 |
} |
| 283 |
} |