hfmn 0.1.0

A flexible Huffman coding implementation
Documentation 
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

#![warn(clippy::all, clippy::pedantic, clippy::nursery, clippy::cargo)]

//! hfmn is a library for huffman encoding and decoding of arbitrary symbols. It
//! supports code lengths up to ```std::mem::size_of::<usize>() * 8``` bits.
//!
//! # Nomenclature
//! - *Symbol* refers to your data, which can be of an arbitrary type
//! - *Code* refers to the prefix-free huffman code
//!
//! # Examples
//! ```
//! use hfmn::CodeBook;
//!
//! let data_to_encode = "lorem ipsum dolor sit amet";
//!
//! let codebook = CodeBook::from_data(&data_to_encode).unwrap();
//!
//! let encoded_data = codebook.encode_data(&data_to_encode).unwrap();
//! let more_encoded_data = codebook.encode_data(&"optimum allied restrooms");
//! ````

mod code;
mod errors;
mod huffman;
mod table;
mod tree;

pub use crate::code::HfmnCode;
pub use errors::Error;
pub use huffman::CodeBook;

#[must_use]
/// A convenience function to chain hfmn symbols into bytes.
///
/// Packs the symbols together consecutively, minimising the size of the bytes.
/// Any unused bits in the last byte will be zeroed.
///
/// # Arguments
/// * `symbols` - A slice of symbol references encoding the data
///
/// # Examples
/// ```
/// use hfmn::{HfmnCode, chain};
///
/// let encoded_symbols = [&HfmnCode::from(0b1111, 4), &HfmnCode::from(0b0000, 4)];
/// let (bytes, length) = chain(&encoded_symbols);
///
/// assert_eq!(length, 2);
/// assert_eq!(bytes, vec![0b1111_0000]);
/// ```
pub fn chain(symbols: &[&HfmnCode]) -> (Vec<u8>, usize) {
    let mut bytes = Vec::new();

    let mut current_byte = 0_u8;
    let mut bit_index = 0_usize;
    for symbol in symbols {
        for bit in symbol.bits() {
            current_byte |= (bit as u8) << bit_index;

            // Symbol never has more than 64 bits, so this should be valid
            bit_index = bit_index.saturating_add(1);

            if bit_index == 8 {
                bytes.push(current_byte.reverse_bits());
                current_byte = 0;
                bit_index = 0;
            }
        }
    }

    if bit_index != 0 {
        bytes.push(current_byte.reverse_bits());
    }

    (bytes, symbols.len())
}

#[cfg(test)]
mod tests {
    use itertools::Itertools;

    use super::*;

    #[test]
    fn chaining() {
        let symbols = [
            HfmnCode::from(0b0000_1111, 8),
            HfmnCode::from(0b01011, 5),
            HfmnCode::from(0b110, 3),
        ];

        let (bytes, _) = chain(&symbols.iter().collect_vec());

        let expected = vec![0b0000_1111, 0b0101_1110];

        assert_eq!(bytes, expected);
    }
}