oxirs_tdb/compression/
frame_of_reference.rs

1//! Frame of Reference (FOR) compression for integer sequences
2//!
3//! Frame of Reference compression is designed for sequences of integers with small deltas.
4//! It stores a base value (reference frame) and encodes deltas from that base.
5
6use super::{
7    AdvancedCompressionType, CompressedData, CompressionAlgorithm, CompressionMetadata,
8    MAX_COMPRESSION_INPUT_SIZE,
9};
10use anyhow::{anyhow, Result};
11use std::collections::HashMap;
12use std::time::Instant;
13
14/// Frame of Reference encoder for integer sequences
15#[derive(Debug, Clone)]
16pub struct FrameOfReferenceEncoder {
17    /// Number of bits per delta value
18    pub bits_per_delta: u8,
19}
20
21impl Default for FrameOfReferenceEncoder {
22    fn default() -> Self {
23        Self {
24            bits_per_delta: 8, // Default to 8 bits per delta
25        }
26    }
27}
28
29impl FrameOfReferenceEncoder {
30    /// Create new FOR encoder with specified bits per delta
31    pub fn new(bits_per_delta: u8) -> Self {
32        Self {
33            bits_per_delta: bits_per_delta.min(32), // Cap at 32 bits
34        }
35    }
36
37    /// Compress sequence of u32 integers
38    pub fn compress_u32(&self, values: &[u32]) -> Result<CompressedData> {
39        if values.is_empty() {
40            return Ok(CompressedData {
41                data: vec![],
42                metadata: CompressionMetadata {
43                    algorithm: AdvancedCompressionType::FrameOfReference,
44                    original_size: 0,
45                    compressed_size: 0,
46                    compression_time_us: 0,
47                    metadata: HashMap::new(),
48                },
49            });
50        }
51
52        let start_time = Instant::now();
53
54        // Find base value (minimum)
55        let base = *values
56            .iter()
57            .min()
58            .expect("collection validated to be non-empty");
59
60        // Calculate deltas
61        let deltas: Vec<u32> = values.iter().map(|&v| v - base).collect();
62
63        // Find maximum delta to determine required bits
64        let max_delta = *deltas
65            .iter()
66            .max()
67            .expect("collection validated to be non-empty");
68        let required_bits = if max_delta == 0 {
69            1
70        } else {
71            32 - max_delta.leading_zeros() as u8
72        };
73
74        // Use smaller of required bits or configured bits
75        let bits_per_delta = required_bits.min(self.bits_per_delta);
76
77        // Encode: [base (4 bytes)] [bits_per_delta (1 byte)] [count (4 bytes)] [packed deltas]
78        let mut result = Vec::new();
79        result.extend_from_slice(&base.to_le_bytes());
80        result.push(bits_per_delta);
81        result.extend_from_slice(&(values.len() as u32).to_le_bytes());
82
83        // Pack deltas
84        if bits_per_delta > 0 {
85            let packed_deltas = self.pack_deltas(&deltas, bits_per_delta)?;
86            result.extend_from_slice(&packed_deltas);
87        }
88
89        let compression_time = start_time.elapsed().as_micros() as u64;
90
91        let mut metadata_map = HashMap::new();
92        metadata_map.insert("base".to_string(), base.to_string());
93        metadata_map.insert("bits_per_delta".to_string(), bits_per_delta.to_string());
94        metadata_map.insert("count".to_string(), values.len().to_string());
95
96        let compressed_size = result.len() as u64;
97        Ok(CompressedData {
98            data: result,
99            metadata: CompressionMetadata {
100                algorithm: AdvancedCompressionType::FrameOfReference,
101                original_size: (values.len() * 4) as u64,
102                compressed_size,
103                compression_time_us: compression_time,
104                metadata: metadata_map,
105            },
106        })
107    }
108
109    /// Pack deltas using specified bits per value
110    fn pack_deltas(&self, deltas: &[u32], bits_per_delta: u8) -> Result<Vec<u8>> {
111        if bits_per_delta == 0 {
112            return Ok(vec![]);
113        }
114
115        let mut result = Vec::new();
116        let mut current_byte = 0u8;
117        let mut bits_in_current_byte = 0u8;
118
119        for &delta in deltas {
120            // Ensure delta fits in specified bits
121            let masked_delta = delta & ((1u32 << bits_per_delta) - 1);
122
123            let mut remaining_bits = bits_per_delta;
124            let mut value = masked_delta;
125
126            while remaining_bits > 0 {
127                let bits_to_write = remaining_bits.min(8 - bits_in_current_byte);
128                let shift = remaining_bits - bits_to_write;
129                let bits_value = ((value >> shift) & ((1u32 << bits_to_write) - 1)) as u8;
130
131                current_byte |= bits_value << (8 - bits_in_current_byte - bits_to_write);
132                bits_in_current_byte += bits_to_write;
133                remaining_bits -= bits_to_write;
134                value &= (1u32 << shift) - 1;
135
136                if bits_in_current_byte == 8 {
137                    result.push(current_byte);
138                    current_byte = 0;
139                    bits_in_current_byte = 0;
140                }
141            }
142        }
143
144        // Add remaining partial byte
145        if bits_in_current_byte > 0 {
146            result.push(current_byte);
147        }
148
149        Ok(result)
150    }
151
152    /// Decompress sequence of u32 integers
153    pub fn decompress_u32(&self, data: &[u8]) -> Result<Vec<u32>> {
154        if data.is_empty() {
155            return Ok(vec![]);
156        }
157
158        if data.len() < 9 {
159            return Err(anyhow!("Invalid FOR compressed data: too short"));
160        }
161
162        // Read header
163        let base = u32::from_le_bytes([data[0], data[1], data[2], data[3]]);
164        let bits_per_delta = data[4];
165        let count = u32::from_le_bytes([data[5], data[6], data[7], data[8]]) as usize;
166
167        if count == 0 {
168            return Ok(vec![]);
169        }
170
171        // Unpack deltas
172        let deltas = if bits_per_delta == 0 {
173            vec![0; count]
174        } else {
175            self.unpack_deltas(&data[9..], bits_per_delta, count)?
176        };
177
178        // Reconstruct original values
179        let values: Vec<u32> = deltas.iter().map(|&delta| base + delta).collect();
180
181        Ok(values)
182    }
183
184    /// Unpack deltas from bit-packed data
185    fn unpack_deltas(&self, data: &[u8], bits_per_delta: u8, count: usize) -> Result<Vec<u32>> {
186        let mut result = Vec::with_capacity(count);
187        let mut byte_index = 0;
188        let mut bit_index = 0u8;
189
190        for _ in 0..count {
191            let mut value = 0u32;
192            let mut remaining_bits = bits_per_delta;
193
194            while remaining_bits > 0 && byte_index < data.len() {
195                let bits_available = 8 - bit_index;
196                let bits_to_read = remaining_bits.min(bits_available);
197
198                let byte_value = data[byte_index];
199                let shift = bits_available - bits_to_read;
200                let mask = if bits_to_read >= 8 {
201                    0xFFu8
202                } else {
203                    ((1u8 << bits_to_read) - 1) << shift
204                };
205                let extracted_bits = (byte_value & mask) >> shift;
206
207                value = (value << bits_to_read) | (extracted_bits as u32);
208                remaining_bits -= bits_to_read;
209                bit_index += bits_to_read;
210
211                if bit_index == 8 {
212                    byte_index += 1;
213                    bit_index = 0;
214                }
215            }
216
217            result.push(value);
218        }
219
220        Ok(result)
221    }
222}
223
224impl CompressionAlgorithm for FrameOfReferenceEncoder {
225    fn compress(&self, data: &[u8]) -> Result<CompressedData> {
226        if data.len() > MAX_COMPRESSION_INPUT_SIZE {
227            return Err(anyhow!("Input too large for compression"));
228        }
229
230        // Convert bytes to u32 sequence (assuming 4-byte alignment)
231        if data.len() % 4 != 0 {
232            return Err(anyhow!(
233                "Input data must be 4-byte aligned for FOR compression"
234            ));
235        }
236
237        let values: Vec<u32> = data
238            .chunks_exact(4)
239            .map(|chunk| u32::from_le_bytes([chunk[0], chunk[1], chunk[2], chunk[3]]))
240            .collect();
241
242        self.compress_u32(&values)
243    }
244
245    fn decompress(&self, compressed: &CompressedData) -> Result<Vec<u8>> {
246        let values = self.decompress_u32(&compressed.data)?;
247
248        let mut result = Vec::with_capacity(values.len() * 4);
249        for value in values {
250            result.extend_from_slice(&value.to_le_bytes());
251        }
252
253        Ok(result)
254    }
255
256    fn algorithm_type(&self) -> AdvancedCompressionType {
257        AdvancedCompressionType::FrameOfReference
258    }
259}
260
261#[cfg(test)]
262mod tests {
263    use super::*;
264
265    #[test]
266    fn test_compression_algorithm_trait() {
267        let encoder = FrameOfReferenceEncoder::default();
268
269        // Test with sequence: [100, 101, 102, 103] as bytes
270        let values = vec![100u32, 101u32, 102u32, 103u32];
271        let mut data = Vec::new();
272        for value in values {
273            data.extend_from_slice(&value.to_le_bytes());
274        }
275
276        let compressed = encoder.compress(&data).unwrap();
277        assert_eq!(
278            compressed.metadata.algorithm,
279            AdvancedCompressionType::FrameOfReference
280        );
281
282        let decompressed = encoder.decompress(&compressed).unwrap();
283        assert_eq!(data, decompressed);
284    }
285
286    #[test]
287    fn test_constant_sequence() {
288        let encoder = FrameOfReferenceEncoder::default();
289        let values = vec![42u32; 100];
290
291        let compressed = encoder.compress_u32(&values).unwrap();
292        let decompressed = encoder.decompress_u32(&compressed.data).unwrap();
293
294        assert_eq!(values, decompressed);
295        // Should achieve good compression for constant sequence
296        assert!(compressed.metadata.compressed_size < compressed.metadata.original_size);
297    }
298
299    #[test]
300    fn test_empty_sequence() {
301        let encoder = FrameOfReferenceEncoder::default();
302        let values = vec![];
303
304        let compressed = encoder.compress_u32(&values).unwrap();
305        let decompressed = encoder.decompress_u32(&compressed.data).unwrap();
306
307        assert_eq!(values, decompressed);
308        assert_eq!(compressed.metadata.compressed_size, 0);
309    }
310
311    #[test]
312    fn test_small_delta_sequence() {
313        let encoder = FrameOfReferenceEncoder::new(4); // 4 bits per delta
314        let values = vec![1000, 1001, 1002, 1003, 1004, 1005];
315
316        let compressed = encoder.compress_u32(&values).unwrap();
317        let decompressed = encoder.decompress_u32(&compressed.data).unwrap();
318
319        assert_eq!(values, decompressed);
320
321        // Verify metadata
322        assert_eq!(compressed.metadata.metadata.get("base").unwrap(), "1000");
323        assert_eq!(compressed.metadata.metadata.get("count").unwrap(), "6");
324    }
325
326    #[test]
327    fn test_large_delta_sequence() {
328        let encoder = FrameOfReferenceEncoder::new(16); // 16 bits per delta
329        let values = vec![1000, 5000, 10000, 15000];
330
331        let compressed = encoder.compress_u32(&values).unwrap();
332        let decompressed = encoder.decompress_u32(&compressed.data).unwrap();
333
334        assert_eq!(values, decompressed);
335    }
336}
oxirs_tdb/compression/frame_of_reference.rs

oxirs_tdb/compression/
frame_of_reference.rs
