pixie_anim_lib/lzw/
mod.rs

1//! LZW Encoder for GIF89a.
2//!
3//! Implements variable-length LZW compression with Clear and EOI codes.
4
5use crate::bits::BitWriter;
6use crate::error::Result;
7
8const MAX_CODES: u16 = 4096;
9
10/// A Lempel-Ziv-Welch encoder specialized for GIF89a.
11pub struct LzwEncoder {
12    min_code_size: u8,
13    dictionary: Vec<i32>,
14    /// Degree of lossiness (0 = lossless, >0 = allow neighbor matching).
15    pub lossiness: u8,
16}
17
18impl LzwEncoder {
19    /// Creates a new LzwEncoder with the specified minimum code size.
20    pub fn new(min_code_size: u8) -> Self {
21        Self {
22            min_code_size,
23            dictionary: vec![-1i32; MAX_CODES as usize * 256],
24            lossiness: 0,
25        }
26    }
27
28    /// Compresses a stream of palette indices into the provided buffer.
29    pub fn encode(&mut self, data: &[u8], buffer: &mut Vec<u8>) -> Result<()> {
30        let clear_code = 1 << self.min_code_size;
31        let eoi_code = clear_code + 1;
32
33        let mut bit_writer = BitWriter::new(buffer);
34        let mut code_size = self.min_code_size + 1;
35        let mut next_code = eoi_code + 1;
36
37        self.dictionary.fill(-1);
38
39        bit_writer.write_bits(clear_code, code_size);
40
41        if data.is_empty() {
42            bit_writer.write_bits(eoi_code, code_size);
43            bit_writer.flush();
44            return Ok(());
45        }
46
47        let mut prefix = data[0] as u16;
48
49        for &byte in &data[1..] {
50            let character = byte;
51            let dict_idx = ((prefix as usize) << 8) | character as usize;
52            let code = self.dictionary[dict_idx];
53
54            if code != -1 {
55                prefix = code as u16;
56            } else {
57                // LOSSY OPTIMIZATION:
58                // Because we use Zeng Reordering, neighbors (idx-1, idx+1) are visually similar.
59                // If we can't find a match for the current byte, check if a neighbor allows
60                // us to continue the string.
61                let mut found_lossy = false;
62                if self.lossiness > 0 {
63                    // Try neighbors based on lossiness level
64                    for offset in 1..=(self.lossiness as i16) {
65                        for sign in &[-1, 1] {
66                            let neighbor = character as i16 + (offset * sign);
67                            if (0..=255).contains(&neighbor) {
68                                let n_idx = ((prefix as usize) << 8) | neighbor as usize;
69                                let n_code = self.dictionary[n_idx];
70                                if n_code != -1 {
71                                    prefix = n_code as u16;
72                                    found_lossy = true;
73                                    break;
74                                }
75                            }
76                        }
77                        if found_lossy {
78                            break;
79                        }
80                    }
81                }
82
83                if !found_lossy {
84                    bit_writer.write_bits(prefix, code_size);
85
86                    if next_code < MAX_CODES {
87                        self.dictionary[dict_idx] = next_code as i32;
88                        next_code += 1;
89
90                        if next_code > (1 << code_size) && code_size < 12 {
91                            code_size += 1;
92                        }
93                    } else {
94                        bit_writer.write_bits(clear_code, code_size);
95                        self.dictionary.fill(-1);
96                        code_size = self.min_code_size + 1;
97                        next_code = eoi_code + 1;
98                    }
99
100                    prefix = character as u16;
101                }
102            }
103        }
104
105        bit_writer.write_bits(prefix, code_size);
106        bit_writer.write_bits(eoi_code, code_size);
107        bit_writer.flush();
108
109        Ok(())
110    }
111}
112
113#[cfg(test)]
114mod tests {
115    use super::*;
116
117    #[test]
118    fn test_basic_lzw() {
119        let mut encoder = LzwEncoder::new(8);
120        let data = vec![1, 1, 1, 1, 1];
121        let mut out = Vec::new();
122        encoder.encode(&data, &mut out).unwrap();
123        assert!(!out.is_empty());
124    }
125}
pixie_anim_lib/lzw/mod.rs

pixie_anim_lib/lzw/
mod.rs
