veridian_kernel/pkg/
delta.rs

1//! Binary Delta Updates
2//!
3//! Provides block-matching binary diff and patch operations for incremental
4//! package updates. Uses 256-byte fixed blocks with FNV-1a hashing to detect
5//! matching regions, producing a compact delta representation.
6
7#[cfg(feature = "alloc")]
8extern crate alloc;
9
10#[cfg(feature = "alloc")]
11use alloc::vec::Vec;
12
13use crate::error::KernelError;
14
15/// Block size for delta computation (bytes).
16const BLOCK_SIZE: usize = 256;
17
18/// A single operation in a binary delta.
19#[cfg(feature = "alloc")]
20#[derive(Debug, Clone)]
21pub enum DeltaOp {
22    /// Copy `len` bytes from the source at `offset`.
23    Copy { offset: usize, len: usize },
24    /// Insert new data not present in the source.
25    Insert { data: Vec<u8> },
26}
27
28/// A binary delta between two versions of a file.
29///
30/// Applying the delta to the source produces the target.
31#[cfg(feature = "alloc")]
32#[derive(Debug, Clone)]
33pub struct BinaryDelta {
34    /// SHA-256 hash of the source file
35    pub source_hash: [u8; 32],
36    /// SHA-256 hash of the target file
37    pub target_hash: [u8; 32],
38    /// Ordered list of delta operations
39    pub operations: Vec<DeltaOp>,
40    /// Compressed size of the delta (for statistics)
41    pub compressed_size: usize,
42}
43
44/// Metadata describing a delta update between two versions.
45#[cfg(feature = "alloc")]
46#[derive(Debug, Clone)]
47pub struct DeltaMetadata {
48    /// Version this delta upgrades FROM
49    pub version_from: super::Version,
50    /// Version this delta upgrades TO
51    pub version_to: super::Version,
52    /// Size of the delta in bytes
53    pub delta_size: usize,
54    /// Size of the full package in bytes (for comparison)
55    pub full_size: usize,
56}
57
58#[cfg(feature = "alloc")]
59impl DeltaMetadata {
60    /// Return the space savings ratio (0.0 = no savings, 1.0 = 100% savings).
61    pub fn savings_ratio(&self) -> f64 {
62        if self.full_size == 0 {
63            return 0.0;
64        }
65        1.0 - (self.delta_size as f64 / self.full_size as f64)
66    }
67}
68
69/// Compute a binary delta between `old` and `new` data.
70///
71/// Uses a fixed 256-byte block matching algorithm:
72/// 1. Hash all blocks in `old` with FNV-1a
73/// 2. Slide through `new`, checking for matching blocks
74/// 3. Matching regions become `Copy` ops, non-matching become `Insert` ops
75#[cfg(feature = "alloc")]
76pub fn compute_delta(old: &[u8], new: &[u8]) -> BinaryDelta {
77    use alloc::collections::BTreeMap;
78
79    let source_hash = *crate::crypto::hash::sha256(old).as_bytes();
80    let target_hash = *crate::crypto::hash::sha256(new).as_bytes();
81
82    // Build a hash table of all blocks in the old data
83    let mut block_map: BTreeMap<u64, Vec<usize>> = BTreeMap::new();
84    let mut offset = 0;
85    while offset + BLOCK_SIZE <= old.len() {
86        let hash = super::manifest::fnv1a_hash(&old[offset..offset + BLOCK_SIZE]);
87        block_map.entry(hash).or_insert_with(Vec::new).push(offset);
88        offset += BLOCK_SIZE;
89    }
90
91    let mut operations: Vec<DeltaOp> = Vec::new();
92    let mut pos = 0;
93    let mut pending_insert: Vec<u8> = Vec::new();
94
95    while pos < new.len() {
96        let remaining = new.len() - pos;
97
98        if remaining >= BLOCK_SIZE {
99            let block_hash = super::manifest::fnv1a_hash(&new[pos..pos + BLOCK_SIZE]);
100
101            // Check if this block exists in the old data
102            let found = block_map.get(&block_hash).and_then(|offsets| {
103                offsets.iter().find(|&&old_offset| {
104                    old_offset + BLOCK_SIZE <= old.len()
105                        && old[old_offset..old_offset + BLOCK_SIZE] == new[pos..pos + BLOCK_SIZE]
106                })
107            });
108
109            if let Some(&old_offset) = found {
110                // Flush any pending insert data
111                if !pending_insert.is_empty() {
112                    operations.push(DeltaOp::Insert {
113                        data: core::mem::take(&mut pending_insert),
114                    });
115                }
116
117                // Extend the copy region as far as possible
118                let mut copy_len = BLOCK_SIZE;
119                while pos + copy_len < new.len()
120                    && old_offset + copy_len < old.len()
121                    && new[pos + copy_len] == old[old_offset + copy_len]
122                {
123                    copy_len += 1;
124                }
125
126                operations.push(DeltaOp::Copy {
127                    offset: old_offset,
128                    len: copy_len,
129                });
130                pos += copy_len;
131                continue;
132            }
133        }
134
135        // No match found, add to pending insert
136        pending_insert.push(new[pos]);
137        pos += 1;
138    }
139
140    // Flush remaining insert data
141    if !pending_insert.is_empty() {
142        operations.push(DeltaOp::Insert {
143            data: pending_insert,
144        });
145    }
146
147    // Compute compressed size (approximate: ops metadata + insert data)
148    let compressed_size = operations.iter().fold(0usize, |acc, op| match op {
149        DeltaOp::Copy { .. } => acc + 12, // 4 bytes tag + 4 bytes offset + 4 bytes len
150        DeltaOp::Insert { data } => acc + 4 + data.len(), // 4 bytes tag + data
151    });
152
153    BinaryDelta {
154        source_hash,
155        target_hash,
156        operations,
157        compressed_size,
158    }
159}
160
161/// Apply a binary delta to the source data, producing the target.
162///
163/// Returns an error if a Copy operation references out-of-bounds source data.
164#[cfg(feature = "alloc")]
165pub fn apply_delta(old: &[u8], delta: &BinaryDelta) -> Result<Vec<u8>, KernelError> {
166    let mut result = Vec::new();
167
168    for op in &delta.operations {
169        match op {
170            DeltaOp::Copy { offset, len } => {
171                if *offset + *len > old.len() {
172                    return Err(KernelError::InvalidArgument {
173                        name: "delta_copy",
174                        value: "source_out_of_bounds",
175                    });
176                }
177                result.extend_from_slice(&old[*offset..*offset + *len]);
178            }
179            DeltaOp::Insert { data } => {
180                result.extend_from_slice(data);
181            }
182        }
183    }
184
185    Ok(result)
186}
187
188/// Verify that a delta result matches the expected hash.
189#[cfg(feature = "alloc")]
190pub fn verify_delta_result(result: &[u8], expected_hash: &[u8; 32]) -> bool {
191    crate::crypto::hash::sha256(result).as_bytes() == expected_hash
192}
193
194/// Serialize a BinaryDelta to bytes for storage/transmission.
195///
196/// Format:
197/// ```text
198/// source_hash:  [u8; 32]
199/// target_hash:  [u8; 32]
200/// op_count:     u32 (little-endian)
201/// for each op:
202///   tag:        u8 (0 = Copy, 1 = Insert)
203///   Copy:       offset: u32 LE, len: u32 LE
204///   Insert:     len: u32 LE, data: [u8; len]
205/// ```
206#[cfg(feature = "alloc")]
207pub fn serialize_delta(delta: &BinaryDelta) -> Vec<u8> {
208    let mut buf = Vec::new();
209
210    buf.extend_from_slice(&delta.source_hash);
211    buf.extend_from_slice(&delta.target_hash);
212    buf.extend_from_slice(&(delta.operations.len() as u32).to_le_bytes());
213
214    for op in &delta.operations {
215        match op {
216            DeltaOp::Copy { offset, len } => {
217                buf.push(0); // tag
218                buf.extend_from_slice(&(*offset as u32).to_le_bytes());
219                buf.extend_from_slice(&(*len as u32).to_le_bytes());
220            }
221            DeltaOp::Insert { data } => {
222                buf.push(1); // tag
223                buf.extend_from_slice(&(data.len() as u32).to_le_bytes());
224                buf.extend_from_slice(data);
225            }
226        }
227    }
228
229    buf
230}
231
232/// Deserialize a BinaryDelta from bytes.
233#[cfg(feature = "alloc")]
234pub fn deserialize_delta(data: &[u8]) -> Result<BinaryDelta, KernelError> {
235    // Minimum size: 32 (source hash) + 32 (target hash) + 4 (op count)
236    if data.len() < 68 {
237        return Err(KernelError::InvalidArgument {
238            name: "delta_data",
239            value: "too_short",
240        });
241    }
242
243    let mut source_hash = [0u8; 32];
244    let mut target_hash = [0u8; 32];
245    source_hash.copy_from_slice(&data[0..32]);
246    target_hash.copy_from_slice(&data[32..64]);
247
248    let op_count = u32::from_le_bytes([data[64], data[65], data[66], data[67]]) as usize;
249
250    let mut operations = Vec::with_capacity(op_count);
251    let mut pos = 68;
252
253    for _ in 0..op_count {
254        if pos >= data.len() {
255            return Err(KernelError::InvalidArgument {
256                name: "delta_data",
257                value: "truncated_ops",
258            });
259        }
260
261        let tag = data[pos];
262        pos += 1;
263
264        match tag {
265            0 => {
266                // Copy
267                if pos + 8 > data.len() {
268                    return Err(KernelError::InvalidArgument {
269                        name: "delta_data",
270                        value: "truncated_copy",
271                    });
272                }
273                let offset =
274                    u32::from_le_bytes([data[pos], data[pos + 1], data[pos + 2], data[pos + 3]])
275                        as usize;
276                pos += 4;
277                let len =
278                    u32::from_le_bytes([data[pos], data[pos + 1], data[pos + 2], data[pos + 3]])
279                        as usize;
280                pos += 4;
281                operations.push(DeltaOp::Copy { offset, len });
282            }
283            1 => {
284                // Insert
285                if pos + 4 > data.len() {
286                    return Err(KernelError::InvalidArgument {
287                        name: "delta_data",
288                        value: "truncated_insert_len",
289                    });
290                }
291                let len =
292                    u32::from_le_bytes([data[pos], data[pos + 1], data[pos + 2], data[pos + 3]])
293                        as usize;
294                pos += 4;
295                if pos + len > data.len() {
296                    return Err(KernelError::InvalidArgument {
297                        name: "delta_data",
298                        value: "truncated_insert_data",
299                    });
300                }
301                let insert_data = data[pos..pos + len].to_vec();
302                pos += len;
303                operations.push(DeltaOp::Insert { data: insert_data });
304            }
305            _ => {
306                return Err(KernelError::InvalidArgument {
307                    name: "delta_tag",
308                    value: "unknown_op_type",
309                });
310            }
311        }
312    }
313
314    Ok(BinaryDelta {
315        source_hash,
316        target_hash,
317        operations,
318        compressed_size: data.len(),
319    })
320}
veridian_kernel/pkg/delta.rs

veridian_kernel/pkg/
delta.rs
