devker/
huffman.rs

1//! # Huffman's Coding
2
3// Imports.
4use crate::bits::Bits;
5use crate::code::Code;
6use crate::prelude::BlockType;
7// Structures.
8#[derive(Debug)]
9struct Writer {
10    v_out: Vec<u8>,
11    buf: u32,
12    width: u8,
13}
14#[derive(Debug)]
15struct HuffmanEncoder<'a> {
16    literal: &'a mut [i32],
17    distance: &'a mut [i32],
18}
19// Implementations.
20impl Writer {
21    fn new() -> Self {
22        Self {
23            v_out: Vec::new(),
24            buf: 0,
25            width: 0,
26        }
27    }
28    fn write_bits(&mut self, bits: Bits) {
29        self.buf |= (bits.data as u32) << self.width;
30        self.width += bits.width;
31
32        if self.width >= 16 {
33            self.v_out.push(self.buf as u8);
34            self.v_out.push((self.buf >> 8) as u8);
35            self.width -= 16;
36            self.buf >>= 16;
37        }
38    }
39    fn finish(mut self) -> Vec<u8> {
40        if self.width > 8 {
41            self.v_out.push(self.buf as u8);
42            self.v_out.push((self.buf >> 8) as u8);
43        } else if self.width > 0 {
44            self.v_out.push(self.buf as u8);
45        }
46        self.buf >>= 16;
47        self.width = self.width.saturating_sub(16);
48        self.v_out
49    }
50}
51impl<'a> HuffmanEncoder<'a> {
52    fn new(btype: BlockType, _v_in: &[Code], buf: &'a mut [i32; 0x10000]) -> Self {
53        match btype {
54            BlockType::Fixed => {
55                let (literal, buf) = buf.split_at_mut(286);
56                let (distance, _) = buf.split_at_mut(30);
57
58                // Fixed Huffman Tree
59                for i in 0..144 {
60                    let (data, width) = (0b0_0011_0000 + i as u16, 8);
61                    literal[i] = Bits { data, width }.reverse().as_i32();
62                }
63                for (i, j) in (144..256).enumerate() {
64                    let (data, width) = (0b1_1001_0000 + i as u16, 9);
65                    literal[j] = Bits { data, width }.reverse().as_i32();
66                }
67                for (i, j) in (256..280).enumerate() {
68                    let (data, width) = (0b0_0000_0000 + i as u16, 7);
69                    literal[j] = Bits { data, width }.reverse().as_i32();
70                }
71                for (i, j) in (280..286).enumerate() {
72                    let (data, width) = (0b0_1100_0000 + i as u16, 8);
73                    literal[j] = Bits { data, width }.reverse().as_i32();
74                }
75                for i in 0..30 {
76                    let (width, data) = (5, i as u16);
77                    distance[i] = Bits { data, width }.reverse().as_i32();
78                }
79
80                Self { literal, distance }
81            }
82            _ => unimplemented!(),
83        }
84    }
85    fn encode(&self, writer: &mut Writer, code: Code) {
86        let lcode = self.literal[code.literal_code() as usize];
87        let bits = Bits::from(lcode);
88        writer.write_bits(bits);
89
90        if let Some((width, data)) = code.extra_length() {
91            writer.write_bits(Bits { data, width });
92        }
93        if let Some((code, width, data)) = code.distance_code() {
94            let dcode = self.distance[code as usize];
95            let bits = Bits::from(dcode);
96            writer.write_bits(bits);
97            writer.write_bits(Bits { data, width });
98        }
99    }
100}
101// Main functions.
102pub fn huffman_encode(v_in: &[Code], btype: BlockType, buf: &mut [i32; 0x10000]) -> Vec<u8> {
103    // Variable Initialization.
104    let mut writer = Writer::new();
105
106    // Algorithms.
107    let data = btype as u16;
108    writer.write_bits(Bits { data: 1, width: 1 });
109    writer.write_bits(Bits { data, width: 2 });
110    let encoder = HuffmanEncoder::new(btype, v_in, buf);
111    for code in v_in {
112        encoder.encode(&mut writer, *code);
113    }
114    writer.finish()
115}
devker/huffman.rs

devker/
huffman.rs
