Debian Codegraph @

.cargo/vendor/bzip2-rs/src/huffman.rs

raw
1 use tinyvec::ArrayVec;
2
3 pub struct HuffmanTree {
4 nodes: [HuffmanNode; 258],
5 }
6
7 #[derive(Default, Copy, Clone)]
8 struct HuffmanNode {
9 // [right, left]
10 right_left: [HuffmanNodeState; 2],
11 }
12
13 #[derive(Copy, Clone)]
14 enum HuffmanNodeState {
15 Next(u16),
16 Done(u16),
17 }
18
19 #[derive(Default)]
20 struct LengthPair {
21 value: u16,
22 length: u8,
23 }
24
25 #[derive(Default)]
26 struct HuffmanCode {
27 code: u32,
28 value: u16,
29 }
30
31 impl HuffmanTree {
32 pub fn new(lengths: &[u8]) -> Result<Self, &'static str> {
33 assert!(lengths.len() >= 2, "too few symbols");
34
35 let mut pairs = lengths
36 .iter()
37 .enumerate()
38 .map(|(i, &length)| LengthPair {
39 value: i as u16,
40 length,
41 })
42 .collect::<ArrayVec<[LengthPair; crate::LEN_258]>>();
43
44 pairs.sort_unstable_by(|a, b| {
45 a.length
46 .cmp(&b.length)
47 .then_with(|| a.value.cmp(&b.value))
48 .reverse()
49 });
50
51 let mut code = 0u32;
52 let mut length = 32u8;
53
54 let mut codes = pairs
55 .into_iter()
56 .map(|pair| {
57 length = length.min(pair.length);
58
59 let c = HuffmanCode {
60 code,
61 value: pair.value,
62 };
63
64 code = code.wrapping_add(1 << (32 - length));
65 c
66 })
67 .collect::<ArrayVec<[HuffmanCode; crate::LEN_258]>>();
68
69 codes.sort_unstable_by(|a, b| a.code.cmp(&b.code));
70
71 let mut this = HuffmanTree::default();
72 Self::build_huffman_node(&mut this.nodes[..codes.len()], &mut 0, &codes, 0)?;
73 Ok(this)
74 }
75
76 pub fn decode<I>(&self, bits_iter: &mut I) -> Option<u16>
77 where
78 I: Iterator<Item = bool>,
79 {
80 let mut node = &self.nodes[0];
81
82 for bit in bits_iter {
83 let val = &node.right_left[usize::from(bit)];
84 match val {
85 HuffmanNodeState::Next(node_index) => node = &self.nodes[usize::from(*node_index)],
86 HuffmanNodeState::Done(value) => return Some(*value),
87 };
88 }
89
90 None
91 }
92
93 fn build_huffman_node(
94 nodes: &mut [HuffmanNode],
95 next_node: &mut usize,
96 codes: &[HuffmanCode],
97 level: u32,
98 ) -> Result<u16, &'static str> {
99 let test = 1u32.rotate_right(level);
100
101 let first_right_index = codes
102 .iter()
103 .enumerate()
104 .find(|(_, code)| code.code & test != 0)
105 .map_or(codes.len(), |(i, _)| i);
106
107 let left = &codes[..first_right_index];
108 let right = &codes[first_right_index..];
109
110 if left.is_empty() || right.is_empty() {
111 if codes.len() < 2 {
112 return Err("empty huffman tree");
113 }
114
115 if level == 31 {
116 return Err("equal symbols in huffman tree");
117 }
118
119 if left.is_empty() {
120 Self::build_huffman_node(nodes, next_node, right, level + 1)
121 } else {
122 Self::build_huffman_node(nodes, next_node, left, level + 1)
123 }
124 } else {
125 let node_index = *next_node;
126 // remove downstream bounds checking
127 assert!(node_index < nodes.len());
128 *next_node += 1;
129
130 if left.len() == 1 {
131 let node = &mut nodes[node_index];
132 node.right_left[1] = HuffmanNodeState::Done(left[0].value);
133 } else {
134 let val = Self::build_huffman_node(nodes, next_node, left, level + 1)?;
135
136 let node = &mut nodes[node_index];
137 node.right_left[1] = HuffmanNodeState::Next(val);
138 }
139
140 if right.len() == 1 {
141 let node = &mut nodes[node_index];
142 node.right_left[0] = HuffmanNodeState::Done(right[0].value);
143 } else {
144 let val = Self::build_huffman_node(nodes, next_node, right, level + 1)?;
145
146 let node = &mut nodes[node_index];
147 node.right_left[0] = HuffmanNodeState::Next(val);
148 }
149
150 Ok(node_index as u16)
151 }
152 }
153 }
154
155 impl Default for HuffmanTree {
156 fn default() -> Self {
157 Self {
158 nodes: [HuffmanNode::default(); 258],
159 }
160 }
161 }
162
163 impl Default for HuffmanNodeState {
164 fn default() -> Self {
165 HuffmanNodeState::Next(0)
166 }
167 }