tx2_iff/
compression.rs

1//! Simple compression utilities for integer data
2//!
3//! Implements Run-Length Encoding (RLE) combined with VByte and ZigZag encoding
4//! for efficient storage of sparse integer data (like wavelet coefficients).
5
6use std::io::{Cursor, Read, Write};
7use crate::error::{IffError, Result};
8
9/// ZigZag encode a signed integer to unsigned
10/// Maps small signed integers to small unsigned integers
11/// 0 -> 0, -1 -> 1, 1 -> 2, -2 -> 3, ...
12pub fn zigzag_encode(n: i32) -> u32 {
13    ((n << 1) ^ (n >> 31)) as u32
14}
15
16/// ZigZag decode an unsigned integer to signed
17pub fn zigzag_decode(n: u32) -> i32 {
18    ((n >> 1) as i32) ^ -((n & 1) as i32)
19}
20
21/// Encode a u32 using VByte (variable length) encoding
22/// Returns the number of bytes written
23pub fn encode_vbyte<W: Write>(writer: &mut W, mut n: u32) -> Result<usize> {
24    let mut bytes_written = 0;
25    loop {
26        let mut byte = (n & 0x7F) as u8;
27        n >>= 7;
28        if n != 0 {
29            byte |= 0x80;
30            writer.write_all(&[byte])?;
31            bytes_written += 1;
32        } else {
33            writer.write_all(&[byte])?;
34            bytes_written += 1;
35            break;
36        }
37    }
38    Ok(bytes_written)
39}
40
41/// Decode a u32 using VByte encoding
42pub fn decode_vbyte<R: Read>(reader: &mut R) -> Result<u32> {
43    let mut n = 0u32;
44    let mut shift = 0;
45    let mut byte = [0u8; 1];
46
47    loop {
48        reader.read_exact(&mut byte).map_err(|_| IffError::InsufficientData { expected: 1, got: 0 })?;
49        let b = byte[0];
50        n |= ((b & 0x7F) as u32) << shift;
51        if (b & 0x80) == 0 {
52            break;
53        }
54        shift += 7;
55        if shift >= 35 {
56            return Err(IffError::Other("VByte overflow".to_string()));
57        }
58    }
59    Ok(n)
60}
61
62/// Compress a slice of i32 using RLE + ZigZag + VByte
63/// Format:
64/// - 0 (VByte 0x00) -> Run of zeros. Next VByte is count.
65/// - >0 (VByte) -> Literal value (ZigZag encoded).
66pub fn compress_rle(data: &[i32]) -> Result<Vec<u8>> {
67    let mut output = Vec::new();
68    let mut i = 0;
69    while i < data.len() {
70        if data[i] == 0 {
71            // Run of zeros
72            let mut count = 0;
73            while i < data.len() && data[i] == 0 {
74                count += 1;
75                i += 1;
76            }
77            // Write 0 marker
78            encode_vbyte(&mut output, 0)?;
79            // Write count
80            encode_vbyte(&mut output, count)?;
81        } else {
82            // Literal value
83            let zz = zigzag_encode(data[i]);
84            encode_vbyte(&mut output, zz)?;
85            i += 1;
86        }
87    }
88    Ok(output)
89}
90
91/// Decompress RLE data to Vec<i32>
92/// `expected_len` is the expected number of integers (optional check)
93pub fn decompress_rle(data: &[u8], expected_len: Option<usize>) -> Result<Vec<i32>> {
94    let mut reader = Cursor::new(data);
95    let mut output = Vec::with_capacity(expected_len.unwrap_or(1024));
96
97    while reader.position() < data.len() as u64 {
98        let val = decode_vbyte(&mut reader)?;
99        if val == 0 {
100            // Run of zeros
101            let count = decode_vbyte(&mut reader)?;
102            for _ in 0..count {
103                output.push(0);
104            }
105        } else {
106            // Literal value
107            let n = zigzag_decode(val);
108            output.push(n);
109        }
110    }
111
112    if let Some(len) = expected_len {
113        if output.len() != len {
114             // It's possible the RLE stream ended early or went over if corrupted
115             // But for now we just return what we have, or maybe pad with zeros if short?
116             // Let's be strict for now.
117             if output.len() < len {
118                 // Pad with zeros if we are short (implicit zeros at end)
119                 output.resize(len, 0);
120             } else if output.len() > len {
121                 // Truncate? Or error?
122                 // Error is safer
123                 return Err(IffError::Other(format!(
124                     "Decompression length mismatch: expected {}, got {}",
125                     len, output.len()
126                 )));
127             }
128        }
129    }
130
131    Ok(output)
132}
133
134#[cfg(test)]
135mod tests {
136    use super::*;
137
138    #[test]
139    fn test_zigzag() {
140        assert_eq!(zigzag_encode(0), 0);
141        assert_eq!(zigzag_encode(-1), 1);
142        assert_eq!(zigzag_encode(1), 2);
143        assert_eq!(zigzag_encode(-2), 3);
144        assert_eq!(zigzag_encode(i32::MAX), 0xFFFFFFFE);
145        assert_eq!(zigzag_encode(i32::MIN), 0xFFFFFFFF);
146
147        assert_eq!(zigzag_decode(0), 0);
148        assert_eq!(zigzag_decode(1), -1);
149        assert_eq!(zigzag_decode(2), 1);
150        assert_eq!(zigzag_decode(3), -2);
151    }
152
153    #[test]
154    fn test_vbyte() {
155        let mut buf = Vec::new();
156        encode_vbyte(&mut buf, 0).unwrap();
157        encode_vbyte(&mut buf, 127).unwrap();
158        encode_vbyte(&mut buf, 128).unwrap();
159        encode_vbyte(&mut buf, 300).unwrap();
160
161        let mut reader = Cursor::new(buf);
162        assert_eq!(decode_vbyte(&mut reader).unwrap(), 0);
163        assert_eq!(decode_vbyte(&mut reader).unwrap(), 127);
164        assert_eq!(decode_vbyte(&mut reader).unwrap(), 128);
165        assert_eq!(decode_vbyte(&mut reader).unwrap(), 300);
166    }
167
168    #[test]
169    fn test_rle() {
170        let data = vec![0, 0, 0, 5, -3, 0, 0, 10, 0];
171        let compressed = compress_rle(&data).unwrap();
172        let decompressed = decompress_rle(&compressed, Some(data.len())).unwrap();
173        assert_eq!(data, decompressed);
174    }
175}
tx2_iff/compression.rs

tx2_iff/
compression.rs
