mismall 2.0.0

Streaming Huffman compression library with AES-256-GCM encryption and archive support
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
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

use std::{cmp::Ordering, collections::BinaryHeap};

pub fn build_huffman_tree(freq: &[u64; 256]) -> Option<Node> {
    let mut heap: BinaryHeap<Node> = BinaryHeap::new();

    for (i, b) in freq.iter().enumerate() {
        if *b > 0 {
            let node = Node {
                weight: *b,
                symbol: Some(i as u8),
                left: None,
                right: None,
            };
            heap.push(node);
        }
    }

    while heap.len() > 1 {
        debug_assert!(heap.len() >= 2);
        let low_1 = heap.pop().unwrap();
        let low_2 = heap.pop().unwrap();

        let parent = Node {
            weight: low_1.weight + low_2.weight,
            symbol: None,
            left: Some(Box::new(low_1)),
            right: Some(Box::new(low_2)),
        };

        heap.push(parent);
    }

    heap.pop()
}

#[derive(Clone, Debug)]
pub struct Node {
    pub weight: u64,
    pub symbol: Option<u8>,
    pub left: Option<Box<Node>>,
    pub right: Option<Box<Node>>,
}

impl PartialEq for Node {
    fn eq(&self, other: &Self) -> bool {
        self.weight == other.weight
    }
}

impl Eq for Node {}

impl Ord for Node {
    fn cmp(&self, other: &Node) -> Ordering {
        other.weight.cmp(&self.weight)
    }
}

impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

pub fn serialize_tree(node: &Node, out: &mut Vec<u8>) {
    if node.symbol.is_none() && (node.left.is_none() || node.right.is_none()) {
        // Do nothing, so early return
        return;
    }

    if let Some(symbol) = node.symbol {
        // Leaf node
        out.push(1);
        out.push(symbol);
    } else {
        // Internal node
        out.push(0);
        match (&node.left, &node.right) {
            (Some(left), Some(right)) => {
                serialize_tree(left, out);
                serialize_tree(right, out);
            }
            _ => {
                eprintln!("Corrupted node: {:?}", node);
                panic!("Internal node missing a child - invalid Huffman tree")
            }
        }
    }
}

pub fn deserialize_tree<I: Iterator<Item = u8> + ExactSizeIterator>(stream: &mut I) -> Node {
    if stream.len() < 1 {
        return Node {
            weight: 0,
            symbol: None,
            left: None,
            right: None,
        };
    }
    match stream.next() {
        Some(1) => {
            let symbol = stream.next().expect("Expected symbol after leaf marker");
            Node {
                weight: 0,
                symbol: Some(symbol),
                left: None,
                right: None,
            }
        }
        Some(0) => {
            let left = deserialize_tree(stream);
            let right = deserialize_tree(stream);
            Node {
                weight: 0,
                symbol: None,
                left: Some(Box::new(left)),
                right: Some(Box::new(right)),
            }
        }
        _ => {
            panic!("Invalid or corrupted tree data")
        }
    }
}