Debian Codegraph @

.cargo/vendor/delharc/src/decode/lhv1/dyntree.rs

raw
1 //! # Dynamic Huffman Coding.
2 use core::fmt;
3 #[cfg(not(feature = "std"))]
4 use alloc::{string::String};
5 use crate::error::LhaError;
6 use crate::bitstream::BitRead;
7 use crate::statictree::entry::*;
8
9 #[derive(Clone)]
10 pub struct DynHuffTree {
11 nodes: [TreeNode; NUM_NODES],
12 leaves: LeaveIndex,
13 groups: Groups,
14 }
15
16 const REORDER_LIMIT: u16 = 32 * 1024;
17 const NUM_LEAVES: usize = 314;
18 const NUM_NODES: usize = NUM_LEAVES * 2 - 1;
19
20 #[derive(Clone)]
21 struct Groups {
22 ngroups: u16,
23 groups: [u16; NUM_NODES], // there will be no more groups than tree nodes
24 leaders: [u16; NUM_NODES], // leaders[group] -> node_index
25 }
26
27 #[derive(Clone)]
28 struct LeaveIndex([u16; NUM_LEAVES]); // leaves[leaf_value] -> node_index
29
30 #[derive(Debug, Clone, Copy)]
31 struct TreeNode {
32 /// a leaf or a branch
33 entry: TreeEntry,
34 /// node frequency
35 freq: u16,
36 /// parent index
37 parent: u16,
38 /// frequency group id
39 group: u16,
40 }
41
42 impl Default for TreeNode {
43 /// Creates an invalid node (a branch pointing to the root) by default.
44 fn default() -> TreeNode {
45 TreeNode {
46 entry: TreeEntry::branch(0).unwrap(),
47 freq: 0,
48 parent: 0,
49 group: 0
50 }
51 }
52 }
53
54 impl fmt::Debug for DynHuffTree {
55 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
56 f.debug_struct("DynHuffTree")
57 .field("nodes", &&self.nodes[..])
58 .field("leaves", &&self.leaves.0[..])
59 .field("groups", &self.groups)
60 .finish()
61 }
62 }
63
64 impl fmt::Debug for Groups {
65 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
66 f.debug_struct("Groups")
67 .field("ngroups", &self.ngroups)
68 .field("groups", &&self.groups[..])
69 .field("leaders", &&self.leaders[..])
70 .finish()
71 }
72 }
73
74 impl Groups {
75 fn new() -> Self {
76 let groups = [0u16; NUM_NODES];
77 let mut res = Groups { ngroups: 0, groups, leaders: groups };
78 res.reset();
79 res
80 }
81
82 fn reset(&mut self) {
83 self.ngroups = 0;
84 for (p, n) in self.groups.iter_mut().zip(0u16..) {
85 *p = n;
86 }
87 }
88
89 #[inline]
90 fn allocate(&mut self) -> u16 {
91 let ngroups = self.ngroups;
92 let res = match self.groups.get(ngroups as usize) {
93 Some(&group) => group,
94 #[cfg(debug_assertions)]
95 None => unreachable!(),
96 #[cfg(not(debug_assertions))]
97 None => unsafe { core::hint::unreachable_unchecked() }
98 };
99 self.ngroups = ngroups + 1;
100 res
101 }
102
103 #[inline]
104 fn free(&mut self, group: u16) {
105 let ngroups = self.ngroups - 1;
106 match self.groups.get_mut(ngroups as usize) {
107 Some(p) => *p = group,
108 #[cfg(debug_assertions)]
109 None => unreachable!(),
110 #[cfg(not(debug_assertions))]
111 None => unsafe { core::hint::unreachable_unchecked() }
112 };
113 self.ngroups = ngroups;
114 }
115
116 #[inline]
117 fn set_leader_index(&mut self, group: u16, node_index: usize) {
118 debug_assert!(node_index < NUM_NODES);
119 match self.leaders.get_mut(group as usize) {
120 Some(l) => *l = node_index as u16,
121 #[cfg(debug_assertions)]
122 None => unreachable!(),
123 #[cfg(not(debug_assertions))]
124 None => unsafe { core::hint::unreachable_unchecked() }
125 };
126 }
127
128 #[inline]
129 fn get_leader_index(&self, group: u16) -> usize {
130 match self.leaders.get(group as usize) {
131 Some(&index) => index as usize,
132 #[cfg(debug_assertions)]
133 None => unreachable!(),
134 #[cfg(not(debug_assertions))]
135 None => unsafe { core::hint::unreachable_unchecked() }
136 }
137 }
138
139 #[inline]
140 fn set_next_node_as_leader(&mut self, group: u16) {
141 match self.leaders.get_mut(group as usize) {
142 Some(l) => {
143 debug_assert!((*l as usize) < NUM_NODES - 1);
144 *l += 1;
145 }
146 #[cfg(debug_assertions)]
147 None => unreachable!(),
148 #[cfg(not(debug_assertions))]
149 None => unsafe { core::hint::unreachable_unchecked() }
150 };
151 }
152 }
153
154 impl LeaveIndex {
155 #[inline]
156 fn set_leaf_node_index(&mut self, value: u16, node_index: usize) {
157 debug_assert!(node_index < NUM_NODES);
158 match self.0.get_mut(value as usize) {
159 Some(l) => *l = node_index as u16,
160 #[cfg(debug_assertions)]
161 None => unreachable!(),
162 #[cfg(not(debug_assertions))]
163 None => unsafe { core::hint::unreachable_unchecked() }
164 };
165 }
166
167 #[inline]
168 fn get_leaf_node_index(&self, value: u16) -> usize {
169 match self.0.get(value as usize) {
170 Some(&index) => index as usize,
171 #[cfg(debug_assertions)]
172 None => unreachable!(),
173 #[cfg(not(debug_assertions))]
174 None => unsafe { core::hint::unreachable_unchecked() }
175 }
176 }
177 }
178
179 impl TreeNode {
180 fn new_leaf(value: u16, group: u16) -> Self {
181 debug_assert!((value as usize) < NUM_LEAVES);
182 let entry = TreeEntry::leaf(value);
183 let freq = 1;
184 let parent = 0;
185 TreeNode { entry, freq, parent, group }
186 }
187
188 fn new_branch(child_index: usize, freq: u16, group: u16) -> Self {
189 debug_assert!(child_index < NUM_NODES);
190 let entry = TreeEntry::branch(child_index).unwrap();
191 let parent = 0;
192 TreeNode { entry, freq, parent, group }
193 }
194
195 #[inline(always)]
196 fn make_branch(&mut self, child_index: usize) {
197 debug_assert!(child_index < NUM_NODES);
198 self.entry.set_as_branch(child_index);
199 }
200
201 #[inline(always)]
202 fn is_leaf(&self) -> bool {
203 self.entry.is_leaf()
204 }
205
206 }
207
208 impl DynHuffTree {
209 pub fn new() -> Self {
210 let mut groups = Groups::new();
211 let mut nodes = [TreeNode::default(); NUM_NODES];
212 let leaves: [u16; NUM_LEAVES] = core::array::from_fn(|value| {
213 (NUM_NODES - 1) as u16 - value as u16
214 });
215
216 let mut last_group = groups.allocate();
217
218 for (node, value) in nodes[NUM_NODES - NUM_LEAVES..NUM_NODES]
219 .iter_mut().rev()
220 .zip(0..)
221 {
222 *node = TreeNode::new_leaf(value, last_group);
223 }
224
225 let mut tail_len = NUM_LEAVES;
226 let mut rest = &mut nodes[..];
227 let mut last_freq = 0;
228
229 while tail_len > 1 {
230 let rest_len = rest.len();
231 let parent_len = tail_len / 2;
232 let (head, children) = rest.split_at_mut(rest_len - parent_len * 2);
233 let head_end = head.len() - (tail_len & 1);
234 for ((child_nodes, child_index),
235 (index, parent_node)) in children.rchunks_exact_mut(2)
236 .zip((0..rest_len).rev().step_by(2)
237 ).zip(head[..head_end].iter_mut()
238 .enumerate().rev())
239 {
240 let mut freq = 0;
241 for child in child_nodes.iter_mut() {
242 freq += child.freq;
243 child.parent = index as u16;
244 }
245 if freq != last_freq {
246 groups.set_leader_index(last_group, index + 1);
247 last_freq = freq;
248 last_group = groups.allocate();
249 }
250 *parent_node = TreeNode::new_branch(child_index, freq, last_group);
251 }
252 tail_len -= parent_len;
253 rest = head;
254 }
255
256 DynHuffTree {
257 nodes,
258 leaves: LeaveIndex(leaves),
259 groups,
260 }
261 }
262
263 #[inline(never)]
264 fn rebuild_tree(&mut self) {
265 // move leave entries away maintaining order and dampen down frequency
266 // we can't use leaf index, as the current order of leaves should be preserved
267 let mut node_filter = self.nodes.iter().filter(|&n| n.is_leaf());
268 let leave_nodes: [(TreeEntry, u16); NUM_LEAVES] = core::array::from_fn(|_| {
269 let node = node_filter.next().unwrap();
270 (node.entry, (node.freq + 1) / 2)
271 });
272 // an iterator of leaves from last to first
273 let mut leaves_riter = leave_nodes.into_iter().rev();
274 // maybe get a next leaf
275 let mut next_leaf = leaves_riter.next();
276 let mut target_len = NUM_NODES;
277 let mut nodes = &mut self.nodes[..];
278 while nodes.len() > 2 {
279 let child_index = nodes.len() - 1;
280 // 1. copy at least 2 more leaves if not enough children
281 let num_children = child_index + 1 - target_len;
282 if num_children < 2 {
283 for node in nodes[..target_len].iter_mut().rev().take(2 - num_children) {
284 let (entry, freq) = next_leaf.unwrap();
285 target_len -= 1;
286 self.leaves.set_leaf_node_index(entry.as_value(), target_len);
287 node.entry = entry;
288 node.freq = freq;
289 next_leaf = leaves_riter.next();
290 }
291 }
292
293 let (head, children) = nodes.split_at_mut(target_len);
294
295 let branch_freq = children.iter().rev().take(2).map(|n| n.freq).sum();
296 let mut target_mut = head.iter_mut().rev();
297
298 // 2. copy more leaves until frequency is less
299 while let Some((entry, freq)) = next_leaf {
300 if branch_freq < freq {
301 break;
302 }
303 let node = target_mut.next().unwrap();
304 self.leaves.set_leaf_node_index(entry.as_value(), target_mut.len());
305 node.entry = entry;
306 node.freq = freq;
307 next_leaf = leaves_riter.next();
308 }
309
310 // 3. insert branch
311 let node = target_mut.next().unwrap();
312 node.make_branch(child_index);
313 node.freq = branch_freq;
314 target_len = target_mut.len();
315 for p in children.iter_mut().rev().take(2) {
316 p.parent = target_len as u16;
317 }
318
319 // 4. repeat until root
320 nodes = &mut nodes[..child_index - 1];
321 }
322
323 // rebuild groups
324 self.groups.reset();
325 let mut group = self.groups.allocate();
326 let mut freq = self.nodes[0].freq;
327 self.nodes[0].group = group;
328 self.groups.set_leader_index(group, 0);
329
330 for (node, index) in self.nodes[1..].iter_mut().zip(1..) {
331 if node.freq == freq {
332 node.group = group;
333 } else {
334 freq = node.freq;
335 group = self.groups.allocate();
336 node.group = group;
337 self.groups.set_leader_index(group, index);
338 }
339 }
340 }
341
342 #[inline]
343 fn set_as_parent(&mut self, child_index: u16, parent_index: usize) {
344 let child_index = child_index as usize;
345 debug_assert!(parent_index < NUM_NODES);
346 #[cfg(debug_assertions)]
347 let child_nodes = &mut self.nodes[child_index - 1..child_index + 1];
348 #[cfg(not(debug_assertions))]
349 let child_nodes = unsafe { self.nodes.get_unchecked_mut(child_index - 1..child_index + 1) };
350 for child in child_nodes.iter_mut() {
351 child.parent = parent_index as u16;
352 }
353 }
354
355 #[allow(clippy::manual_swap)]
356 #[inline]
357 fn promote_to_leader(&mut self, node_index: usize) -> usize {
358 let (node, head) = self.nodes[..node_index + 1].split_last_mut().unwrap();
359 let leader_index = self.groups.get_leader_index(node.group);
360
361 if leader_index == node_index {
362 return node_index
363 }
364 // swap the new leader with the old one
365 let prev_leader = &mut head[leader_index];
366 let entry = node.entry;
367 node.entry = prev_leader.entry;
368 prev_leader.entry = entry;
369 // update old leader
370 match node.entry.as_type() {
371 NodeType::Leaf(value) => {
372 self.leaves.set_leaf_node_index(value, node_index);
373 }
374 NodeType::Branch(child_index) => {
375 self.set_as_parent(child_index, node_index);
376 }
377 }
378 // update new leader
379 match entry.as_type() {
380 NodeType::Leaf(value) => {
381 self.leaves.set_leaf_node_index(value, leader_index);
382 }
383 NodeType::Branch(child_index) => {
384 self.set_as_parent(child_index, leader_index);
385 }
386 }
387 leader_index
388 }
389
390 #[inline]
391 fn increment_frequency(&mut self, node_index: usize) -> &TreeNode {
392 let (prev, tail) = self.nodes[node_index - 1..].split_first_mut().unwrap();
393 let (node, tail) = tail.split_first_mut().unwrap();
394
395 node.freq += 1;
396
397 // node was part of the group with next nodes
398 if let Some(next) = tail.first() {
399 if node.group == next.group {
400 // the next node is now a leader
401 self.groups.set_next_node_as_leader(node.group);
402 if node.freq == prev.freq {
403 // join group of previous node
404 node.group = prev.group;
405 }
406 else {
407 // create node's own group
408 node.group = self.groups.allocate();
409 self.groups.set_leader_index(node.group, node_index);
410 }
411
412 return node
413 }
414 }
415
416 // node had its own group
417 if node.freq == prev.freq {
418 self.groups.free(node.group);
419 // join group of previous node
420 node.group = prev.group;
421 }
422 node
423 }
424
425 #[inline]
426 fn increment_for_value(&mut self, value: u16) {
427 // reorder tree when limit reached
428 if self.nodes[0].freq >= REORDER_LIMIT {
429 self.rebuild_tree();
430 }
431
432 self.nodes[0].freq += 1;
433
434 let mut node_index = self.leaves.get_leaf_node_index(value);
435 // walk up from leaf and re-arrange nodes
436 while node_index != 0 {
437 node_index = self.promote_to_leader(node_index);
438 node_index = self.increment_frequency(node_index).parent as usize;
439 }
440 }
441
442 pub fn read_entry<R: BitRead>(&mut self, mut path: R) -> Result<u16, LhaError<R::Error>> {
443 let nodes = &self.nodes;
444 let mut node = &nodes[0];
445 loop {
446 match node.entry.as_type() {
447 NodeType::Leaf(value) => {
448 self.increment_for_value(value);
449 return Ok(value)
450 }
451 NodeType::Branch(index) => {
452 let index = index as usize - path.read_bits::<usize>(1)?;
453 debug_assert!(index < nodes.len());
454 node = unsafe { nodes.get_unchecked(index) };
455 // safe because tree was initialized in a sane way
456 }
457 }
458 }
459 }
460 }
461
462 impl fmt::Display for DynHuffTree {
463 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
464
465 fn fmt_step(nodes: &[TreeNode], index: usize, f: &mut fmt::Formatter<'_>, prefix: &mut String) -> fmt::Result {
466 let node = nodes[index];
467 match node.entry.as_type() {
468 NodeType::Leaf(code) => writeln!(f, "{} -> {} f: {} g: {}", prefix, code, node.freq, node.group)?,
469 NodeType::Branch(index) => {
470 prefix.push('0');
471 fmt_step(nodes, index as usize, f, prefix)?;
472 prefix.pop();
473 prefix.push('1');
474 fmt_step(nodes, index as usize - 1, f, prefix)?;
475 prefix.pop();
476 }
477 }
478 Ok(())
479 }
480
481 let mut prefix = String::new();
482 fmt_step(&self.nodes, 0, f, &mut prefix)
483 }
484 }
485
486 #[cfg(feature = "std")]
487 #[cfg(test)]
488 mod tests {
489 use rand::{Rng, RngCore, thread_rng};
490 use rand::distributions::{Uniform, WeightedIndex};
491 use crate::bitstream::BitStream;
492 use std::collections::{HashSet, HashMap};
493 use super::*;
494
495 fn validate_tree(tree: &DynHuffTree) {
496 let mut leaves: HashMap<u16, usize> = HashMap::with_capacity(NUM_LEAVES);
497 let mut children: HashSet<u16> = HashSet::with_capacity(NUM_NODES);
498 let mut groups: HashSet<u16> = HashSet::with_capacity(NUM_NODES);
499 let mut freq = u16::max_value();
500 let mut group = u16::max_value();
501 // root is a branch
502 assert!(!tree.nodes[0].is_leaf());
503 assert_eq!(tree.nodes[0].parent, 0);
504 for (index, node) in tree.nodes.iter().enumerate() {
505 match node.entry.as_type() {
506 NodeType::Leaf(value) => {
507 // all leaves should be unique
508 assert!((value as usize) < NUM_LEAVES);
509 assert!(leaves.insert(value, index).is_none());
510 }
511 NodeType::Branch(child_index) => {
512 // invalid (default) node should not be present
513 assert!(child_index != 0);
514 // all child indexes should be even
515 assert!(child_index & 1 == 0);
516 // there must be no duplicate parents of the same children
517 assert!(children.insert(child_index));
518 // parent index should match
519 let child0 = &tree.nodes[child_index as usize - 1];
520 let child1 = &tree.nodes[child_index as usize];
521 assert_eq!(child0.parent as usize, index);
522 assert_eq!(child1.parent as usize, index);
523 // freq should be a sum of children's frequency
524 assert_eq!(child0.freq + child1.freq, node.freq);
525 }
526 }
527 // check frequencies are descending and groups are consistent
528 assert!(node.freq <= freq);
529 if node.freq == freq {
530 assert_eq!(node.group, group);
531 }
532 else {
533 assert_ne!(node.group, group);
534 }
535 if node.group == group {
536 assert_eq!(node.freq, freq);
537 }
538 else {
539 assert_ne!(node.freq, freq);
540 assert!((node.group as usize) < NUM_NODES);
541 // groups should be unique
542 assert!(groups.insert(node.group));
543 // this must be a group leader
544 assert_eq!(tree.groups.get_leader_index(node.group), index);
545 group = node.group;
546 freq = node.freq;
547 }
548 // parents should all meet at root
549 let mut parent_index = node.parent as usize;
550 while parent_index != 0 {
551 let parent_node = tree.nodes[parent_index];
552 assert!(!parent_node.is_leaf());
553 assert!(parent_node.freq > node.freq);
554 assert_ne!(parent_node.group, node.group);
555 parent_index = parent_node.parent as usize;
556 }
557 }
558 // all leaves should be present
559 assert_eq!(leaves.len(), NUM_LEAVES);
560 for (&value, &index) in leaves.iter() {
561 assert_eq!(tree.leaves.get_leaf_node_index(value), index);
562 }
563 // all leaves should be reachable and on the unique path
564 fn into_branch(nodes: &[TreeNode], index: usize, leaves: &mut HashSet<u16>) {
565 match nodes[index].entry.as_type() {
566 NodeType::Leaf(code) => {
567 assert!(leaves.insert(code));
568 }
569 NodeType::Branch(index) => {
570 into_branch(nodes, index as usize - 1, leaves);
571 into_branch(nodes, index as usize, leaves);
572 }
573 }
574 }
575 let mut leaves: HashSet<u16> = HashSet::with_capacity(NUM_LEAVES);
576 into_branch(&tree.nodes, 0, &mut leaves);
577 assert_eq!(leaves.len(), NUM_LEAVES);
578 }
579
580 #[test]
581 fn dyntree_works() {
582 let mut tree = DynHuffTree::new();
583 validate_tree(&tree);
584 println!("{}", tree);
585 for i in 0..NUM_LEAVES {
586 for _ in 0..i {
587 tree.increment_for_value(i as u16);
588 }
589 }
590 validate_tree(&tree);
591 println!("--------------\n{}", tree);
592
593 let mut trng = thread_rng();
594 let rng = &mut trng;
595 // spam tree with random values
596 let mut tree = DynHuffTree::new();
597 for sample in rng.sample_iter(Uniform::new(0, NUM_LEAVES)).take(1_000_000) {
598 tree.increment_for_value(sample as u16);
599 }
600 validate_tree(&tree);
601 println!("--------------\n{}", tree);
602
603 // spam tree with some random, and non-uniformly distributed values
604 let mut weights = [0u16;NUM_LEAVES];
605 rng.fill(&mut weights[..]);
606 let dist = WeightedIndex::new(
607 weights.iter().map(|&n| (n as u64)*(n as u64)) // boost weights
608 ).unwrap();
609 for sample in rng.sample_iter(dist).take(1_000_000) {
610 tree.increment_for_value(sample as u16);
611 }
612 validate_tree(&tree);
613 println!("--------------\n{}", tree);
614
615 // now with some random bit stream
616 let rnd_stream: &mut (dyn RngCore) = rng;
617 let mut rndstream = BitStream::new(rnd_stream);
618 for _ in 0..1_000_000 {
619 tree.read_entry(&mut rndstream).unwrap();
620 }
621 validate_tree(&tree);
622 println!("--------------\n{}", tree);
623 }
624 }