1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
use crate::{BitsPerFragment, Coding, DecodingResult, TreeDegree};
/// Decoder that decodes a value for given code, consuming one codeword fragment
/// (and going one level down the huffman tree) at a time.
///
/// Time complexity of decoding the whole code is:
/// - pessimistic: *O(length of the longest code)*
/// - expected: *O(log(number of values, i.e. length of `coding.values`))*
/// - optimistic: *O(1)*
///
/// Memory complexity: *O(1)*
pub struct Decoder<'huff, ValueType, D = BitsPerFragment> {
coding: &'huff Coding<ValueType, D>,
/// shift+fragment is a current position (node number, counting from the left) at current level.
shift: u32,
/// Number of leafs at all previous levels.
first_leaf_nr: u32,
/// Number of the current level.
level: u32,
/// Current level size = number of: internal nodes + leaves.
level_size: u32
}
impl<'huff, ValueType, D: TreeDegree> Decoder<'huff, ValueType, D> {
/// Constructs decoder for given `coding`.
pub fn new(coding: &'huff Coding<ValueType, D>) -> Self {
Self {
coding,
shift: 0,
first_leaf_nr: 0,
level: 0,
level_size: coding.degree.as_u32(),
}
}
/// Resets `self` to initial state and makes it ready to decode next value.
pub fn reset(&mut self) {
self.shift = 0;
self.first_leaf_nr = 0;
self.level = 0;
self.level_size = self.coding.degree.as_u32();
}
/// Returns the number of fragments consumed since construction or last reset.
#[inline(always)] pub fn consumed_fragments(&self) -> u32 { self.level }
/// Consumes a `fragment` of the codeword and returns:
/// - a value if the given `fragment` finishes the valid codeword;
/// - an [`DecodingResult::Incomplete`] if the codeword is incomplete and the next fragment is needed;
/// - or [`DecodingResult::Invalid`] if the codeword is invalid (possible only for bits per fragment > 1).
///
/// Result is undefined if `fragment` exceeds `tree_degree`.
pub fn consume(&mut self, fragment: u32) -> DecodingResult<&'huff ValueType> {
self.shift += fragment;
let internal_nodes_count = self.internal_nodes_count();
return if self.shift < internal_nodes_count { // internal node, go level down
self.shift = self.coding.degree * self.shift;
self.first_leaf_nr += self.level_size - internal_nodes_count; // increase by number of leafs at current level
self.level_size = self.coding.degree * internal_nodes_count;
self.level += 1;
DecodingResult::Incomplete
} else { // leaf, return value or Invalid
self.coding.values.get((self.first_leaf_nr + self.shift - internal_nodes_count) as usize).into()
//self.coding.values.get((self.first_leaf_nr + self.level_size + self.shift) as usize).into()
}
}
/// Consumes a `fragment` of the codeword and returns:
/// - a value if the given `fragment` finishes the valid codeword;
/// - an [`DecodingResult::Incomplete`] if the codeword is incomplete and the next fragment is needed;
/// - or [`DecodingResult::Invalid`] if the codeword is invalid (possible only for `degree` greater than 2)
/// or `fragment` is not less than `degree`.
#[inline(always)] pub fn consume_checked(&mut self, fragment: u32) -> DecodingResult<&'huff ValueType> {
if fragment < self.coding.degree.as_u32() {
self.consume(fragment)
} else {
DecodingResult::Invalid
}
}
/// Tries to decode and return a single value from the `fragments` iterator,
/// consuming as many fragments as needed.
///
/// To decode the next value, self must be [reset](Self::reset) first
/// (see also [Self::decode_next]).
///
/// In case of failure, returns:
/// - [`DecodingResult::Incomplete`] if the iterator exhausted before the value was decoded
/// ([`Self::consumed_fragments`] enables checking if the iterator yielded any fragment before exhausting).
/// - [`DecodingResult::Invalid`] if obtained invalid codeword (possible only for `degree` greater than 2).
#[inline] pub fn decode<F: Into<u32>, I: Iterator<Item = F>>(&mut self, fragments: &mut I) -> DecodingResult<&'huff ValueType> {
while let Some(fragment) = fragments.next() {
match self.consume(fragment.into()) {
DecodingResult::Incomplete => {},
result => { return result; }
}
}
DecodingResult::Incomplete
}
/// Tries to decode and return a single value from the `fragments` iterator,
/// consuming as many fragments as needed.
///
/// If successful, it [resets](Self::reset) `self` to be ready to decode the next value
/// (see also [Self::decode]).
///
/// In case of failure, returns:
/// - [`DecodingResult::Incomplete`] if the iterator exhausted before the value was decoded
/// ([`Self::consumed_fragments`] enables checking if the iterator yielded any fragment before exhausting).
/// - [`DecodingResult::Invalid`] if obtained invalid codeword (possible only for `degree` greater than 2).
#[inline] pub fn decode_next<F: Into<u32>, I: Iterator<Item = F>>(&mut self, fragments: &mut I) -> DecodingResult<&'huff ValueType> {
let result = self.decode(fragments);
if let DecodingResult::Value(_) = result { self.reset(); }
result
}
/*pub fn decode_next<F: Into<u32>, I: Iterator<Item = F>>(&mut self, fragments: &mut I) -> DecodingResult<&'huff ValueType> {
while let Some(fragment) = fragments.next() {
match self.consume(fragment.into()) {
DecodingResult::Incomplete => {},
result @ DecodingResult::Value(_) => {
self.reset();
return result;
},
result @ DecodingResult::Invalid => { return result; }
}
}
DecodingResult::Incomplete
}*/
/// Returns number of internal (i.e. non-leafs) nodes at the current level of the tree.
#[inline(always)] fn internal_nodes_count(&self) -> u32 {
self.coding.internal_nodes_count[self.level as usize]
}
}