compression/huffman/
encoder.rs

1//! rust-compression
2//!
3//! # Licensing
4//! This Source Code is subject to the terms of the Mozilla Public License
5//! version 2.0 (the "License"). You can obtain a copy of the License at
6//! <http://mozilla.org/MPL/2.0/>.
7
8use crate::bitio::direction::Direction;
9use crate::bitio::small_bit_vec::{SmallBitVec, SmallBitVecReverse};
10use crate::core::marker::PhantomData;
11use crate::core::ops::{Add, Shl};
12use crate::huffman::create_huffman_table;
13#[cfg(not(feature = "std"))]
14use alloc::borrow::ToOwned;
15#[cfg(not(feature = "std"))]
16use alloc::string::String;
17#[cfg(not(feature = "std"))]
18#[allow(unused_imports)]
19use alloc::vec;
20#[cfg(not(feature = "std"))]
21use alloc::vec::Vec;
22use num_traits::{cast, NumCast};
23
24pub(crate) struct HuffmanEncoder<D: Direction, T> {
25    bit_vec_tab: Vec<Option<SmallBitVec<T>>>,
26    phantom: PhantomData<fn() -> D>,
27}
28
29impl<D, T> HuffmanEncoder<D, T>
30where
31    D: Direction,
32    T: Clone + PartialOrd<T> + Shl<u8, Output = T> + Add<Output = T> + From<u8>,
33    SmallBitVec<T>: SmallBitVecReverse,
34{
35    pub(crate) fn new(symb_len: &[u8]) -> Self {
36        Self {
37            bit_vec_tab: create_huffman_table(symb_len, D::is_reverse()),
38            phantom: PhantomData,
39        }
40    }
41
42    pub(crate) fn enc<U: NumCast + Clone>(
43        &self,
44        data: U,
45    ) -> Result<SmallBitVec<T>, String> {
46        if let Some(idx) = cast::<_, usize>(data.clone()) {
47            if idx < self.bit_vec_tab.len() {
48                if let Some(ref bv) = self.bit_vec_tab[idx] {
49                    return Ok(bv.clone());
50                }
51            }
52        }
53        Err("out of value(huffman encodeing)".to_owned())
54    }
55}
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60    use crate::bitio::direction::left::Left;
61    use crate::bitio::direction::right::Right;
62
63    #[test]
64    fn lefthuffman_encode_new() {
65        let hencoder =
66            HuffmanEncoder::<Left, u16>::new(&[0_u8, 4, 4, 4, 4, 3, 3, 2, 2]);
67        let tab = hencoder.bit_vec_tab;
68
69        assert_eq!(tab[0], None);
70        assert_eq!(tab[1], Some(SmallBitVec::new(0b1100, 4)));
71        assert_eq!(tab[2], Some(SmallBitVec::new(0b1101, 4)));
72        assert_eq!(tab[3], Some(SmallBitVec::new(0b1110, 4)));
73        assert_eq!(tab[4], Some(SmallBitVec::new(0b1111, 4)));
74        assert_eq!(tab[5], Some(SmallBitVec::new(0b100, 3)));
75        assert_eq!(tab[6], Some(SmallBitVec::new(0b101, 3)));
76        assert_eq!(tab[7], Some(SmallBitVec::new(0b00, 2)));
77        assert_eq!(tab[8], Some(SmallBitVec::new(0b01, 2)));
78        assert_eq!(tab.len(), 9);
79    }
80
81    #[test]
82    fn lefthuffman_encode_write() {
83        let hencoder =
84            HuffmanEncoder::<Left, u16>::new(&[0_u8, 4, 4, 4, 4, 3, 3, 2, 2]);
85
86        assert_eq!(
87            hencoder.enc(b'a' - 0x60).ok(),
88            Some(SmallBitVec::new(0b1100, 4))
89        );
90        assert_eq!(
91            hencoder.enc(b'b' - 0x60).ok(),
92            Some(SmallBitVec::new(0b1101, 4))
93        );
94        assert_eq!(
95            hencoder.enc(b'c' - 0x60).ok(),
96            Some(SmallBitVec::new(0b1110, 4))
97        );
98        assert_eq!(
99            hencoder.enc(b'd' - 0x60).ok(),
100            Some(SmallBitVec::new(0b1111, 4))
101        );
102        assert_eq!(
103            hencoder.enc(b'e' - 0x60).ok(),
104            Some(SmallBitVec::new(0b100, 3))
105        );
106        assert_eq!(
107            hencoder.enc(b'f' - 0x60).ok(),
108            Some(SmallBitVec::new(0b101, 3))
109        );
110        assert_eq!(
111            hencoder.enc(b'g' - 0x60).ok(),
112            Some(SmallBitVec::new(0b00, 2))
113        );
114        assert_eq!(
115            hencoder.enc(b'h' - 0x60).ok(),
116            Some(SmallBitVec::new(0b01, 2))
117        );
118    }
119
120    #[test]
121    fn lefthuffman_encode_new_zero() {
122        let hencoder =
123            HuffmanEncoder::<Left, u16>::new(&[0_u8, 0_u8, 0_u8, 0_u8]);
124        let tab = hencoder.bit_vec_tab;
125
126        assert_eq!(tab.len(), 0);
127    }
128
129    #[test]
130    fn lefthuffman_encode_all() {
131        let hencoder = HuffmanEncoder::<Left, u16>::new(&[8; 256]);
132        let tab = hencoder.bit_vec_tab;
133
134        for i in 0..256 {
135            assert_eq!(tab[i as usize], Some(SmallBitVec::new(i, 8)));
136        }
137        assert_eq!(tab.len(), 256);
138    }
139
140    #[test]
141    fn righthuffman_encode_new() {
142        let hencoder =
143            HuffmanEncoder::<Right, u16>::new(&[0_u8, 4, 4, 4, 4, 3, 3, 2, 2]);
144        let tab = hencoder.bit_vec_tab;
145
146        assert_eq!(tab[0], None);
147        assert_eq!(tab[1], Some(SmallBitVec::new(0b0011, 4)));
148        assert_eq!(tab[2], Some(SmallBitVec::new(0b1011, 4)));
149        assert_eq!(tab[3], Some(SmallBitVec::new(0b0111, 4)));
150        assert_eq!(tab[4], Some(SmallBitVec::new(0b1111, 4)));
151        assert_eq!(tab[5], Some(SmallBitVec::new(0b001, 3)));
152        assert_eq!(tab[6], Some(SmallBitVec::new(0b101, 3)));
153        assert_eq!(tab[7], Some(SmallBitVec::new(0b00, 2)));
154        assert_eq!(tab[8], Some(SmallBitVec::new(0b10, 2)));
155        assert_eq!(tab.len(), 9);
156    }
157
158    #[test]
159    fn righthuffman_encode_write() {
160        let hencoder =
161            HuffmanEncoder::<Right, u16>::new(&[0_u8, 4, 4, 4, 4, 3, 3, 2, 2]);
162
163        assert_eq!(
164            b"abcdefgh"
165                .iter()
166                .map(|x| x - 0x60)
167                .map(|x| hencoder.enc(x).unwrap())
168                .collect::<Vec<_>>(),
169            vec![
170                SmallBitVec::new(0b0011, 4),
171                SmallBitVec::new(0b1011, 4),
172                SmallBitVec::new(0b0111, 4),
173                SmallBitVec::new(0b1111, 4),
174                SmallBitVec::new(0b001, 3),
175                SmallBitVec::new(0b101, 3),
176                SmallBitVec::new(0b00, 2),
177                SmallBitVec::new(0b10, 2),
178            ]
179        );
180    }
181
182    #[test]
183    fn righthuffman_encode_new_zero() {
184        let hencoder = HuffmanEncoder::<Right, u16>::new(&[0_u8, 0, 0, 0]);
185        let tab = hencoder.bit_vec_tab;
186
187        assert_eq!(tab.len(), 0);
188    }
189}
compression/huffman/encoder.rs

compression/huffman/
encoder.rs
