Debian Codegraph @

.cargo/vendor/delharc/src/statictree.rs

raw
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(&current_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 }