speck_core/delta/
mod.rs

1//! Binary delta encoding for efficient updates
2//! 
3//! Implements a variation of the bsdiff algorithm optimized for embedded systems:
4//! - COPY: Copy bytes from source at given offset
5//! - INSERT: Insert literal bytes
6//! 
7//! This produces smaller patches than simple diff for minor updates.
8
9use alloc::vec::Vec;
10use crate::error::{Error, Result};
11
12pub mod builder;
13pub mod applier;
14
15pub use builder::DeltaBuilder;
16pub use applier::DeltaApplier;
17
18/// Magic number for delta files
19pub const DELTA_MAGIC: &[u8] = b"SDF\x01";
20
21/// Current delta format version
22pub const DELTA_VERSION: u8 = 1;
23
24/// Maximum hunk size to prevent memory exhaustion
25pub const MAX_HUNK_SIZE: usize = 65536;
26
27/// Delta patch container
28#[derive(Clone, Debug, PartialEq)]
29pub struct Delta {
30    /// Source size (original file)
31    pub source_size: u64,
32    /// Target size (result file)
33    pub target_size: u64,
34    /// Sequence of operations
35    pub ops: Vec<Op>,
36}
37
38/// Delta operation
39#[derive(Clone, Debug, PartialEq, Eq)]
40pub enum Op {
41    /// Copy bytes from source
42    Copy {
43        /// Offset in source
44        src_offset: u64,
45        /// Length to copy
46        length: u64,
47    },
48    /// Insert literal bytes
49    Insert {
50        /// Literal data
51        data: Vec<u8>,
52    },
53}
54
55impl Delta {
56    /// Serialize to bytes
57    pub fn to_bytes(&self) -> Result<Vec<u8>> {
58        let mut result = Vec::new();
59        
60        // Header
61        result.extend_from_slice(DELTA_MAGIC);
62        result.push(DELTA_VERSION);
63        
64        // Sizes
65        result.extend_from_slice(&self.source_size.to_le_bytes());
66        result.extend_from_slice(&self.target_size.to_le_bytes());
67        
68        // Operations count
69        result.extend_from_slice(&(self.ops.len() as u32).to_le_bytes());
70        
71        // Operations
72        for op in &self.ops {
73            match op {
74                Op::Copy { src_offset, length } => {
75                    result.push(0x01); // COPY opcode
76                    result.extend_from_slice(&src_offset.to_le_bytes());
77                    result.extend_from_slice(&length.to_le_bytes());
78                }
79                Op::Insert { data } => {
80                    if data.len() > MAX_HUNK_SIZE {
81                        return Err(Error::delta(format!(
82                            "insert hunk too large: {}", data.len()
83                        )));
84                    }
85                    result.push(0x02); // INSERT opcode
86                    result.extend_from_slice(&(data.len() as u32).to_le_bytes());
87                    result.extend_from_slice(data);
88                }
89            }
90        }
91        
92        Ok(result)
93    }
94    
95    /// Deserialize from bytes
96    pub fn from_bytes(bytes: &[u8]) -> Result<Self> {
97        if bytes.len() < 30 {
98            return Err(Error::delta("delta too small for header"));
99        }
100        
101        if &bytes[0..4] != DELTA_MAGIC {
102            return Err(Error::delta("invalid delta magic"));
103        }
104        
105        if bytes[4] != DELTA_VERSION {
106            return Err(Error::delta(format!(
107                "unsupported delta version: {}", bytes[4]
108            )));
109        }
110        
111        let source_size = u64::from_le_bytes([
112            bytes[5], bytes[6], bytes[7], bytes[8],
113            bytes[9], bytes[10], bytes[11], bytes[12],
114        ]);
115        
116        let target_size = u64::from_le_bytes([
117            bytes[13], bytes[14], bytes[15], bytes[16],
118            bytes[17], bytes[18], bytes[19], bytes[20],
119        ]);
120        
121        let op_count = u32::from_le_bytes([bytes[21], bytes[22], bytes[23], bytes[24]]) as usize;
122        
123        let mut ops = Vec::with_capacity(op_count);
124        let mut pos = 25;
125        
126        for _ in 0..op_count {
127            if pos >= bytes.len() {
128                return Err(Error::delta("truncated delta ops"));
129            }
130            
131            let opcode = bytes[pos];
132            pos += 1;
133            
134            match opcode {
135                0x01 => { // COPY
136                    if pos + 16 > bytes.len() {
137                        return Err(Error::delta("truncated copy op"));
138                    }
139                    let src_offset = u64::from_le_bytes([
140                        bytes[pos], bytes[pos+1], bytes[pos+2], bytes[pos+3],
141                        bytes[pos+4], bytes[pos+5], bytes[pos+6], bytes[pos+7],
142                    ]);
143                    let length = u64::from_le_bytes([
144                        bytes[pos+8], bytes[pos+9], bytes[pos+10], bytes[pos+11],
145                        bytes[pos+12], bytes[pos+13], bytes[pos+14], bytes[pos+15],
146                    ]);
147                    pos += 16;
148                    ops.push(Op::Copy { src_offset, length });
149                }
150                0x02 => { // INSERT
151                    if pos + 4 > bytes.len() {
152                        return Err(Error::delta("truncated insert header"));
153                    }
154                    let len = u32::from_le_bytes([bytes[pos], bytes[pos+1], bytes[pos+2], bytes[pos+3]]) as usize;
155                    pos += 4;
156                    if pos + len > bytes.len() {
157                        return Err(Error::delta("truncated insert data"));
158                    }
159                    if len > MAX_HUNK_SIZE {
160                        return Err(Error::delta("insert hunk exceeds maximum"));
161                    }
162                    ops.push(Op::Insert {
163                        data: bytes[pos..pos+len].to_vec(),
164                    });
165                    pos += len;
166                }
167                _ => return Err(Error::delta(format!("unknown opcode: {}", opcode))),
168            }
169        }
170        
171        Ok(Self {
172            source_size,
173            target_size,
174            ops,
175        })
176    }
177    
178    /// Calculate approximate patch size
179    pub fn patch_size(&self) -> usize {
180        self.ops.iter().map(|op| match op {
181            Op::Copy { .. } => 17, // opcode + 2*u64
182            Op::Insert { data } => 5 + data.len(), // opcode + u32 + data
183        }).sum()
184    }
185}
186
187/// Simple delta creation for small payloads (fallback)
188pub fn create_simple_delta(old: &[u8], new: &[u8]) -> Vec<u8> {
189    DeltaBuilder::new()
190        .build(old, new)
191        .and_then(|d| d.to_bytes())
192        .unwrap_or_else(|_| {
193            // Fallback: just insert entire new file
194            let mut result = DELTA_MAGIC.to_vec();
195            result.push(DELTA_VERSION);
196            result.extend_from_slice(&(old.len() as u64).to_le_bytes());
197            result.extend_from_slice(&(new.len() as u64).to_le_bytes());
198            result.extend_from_slice(&1u32.to_le_bytes()); // 1 op
199            result.push(0x02); // INSERT
200            result.extend_from_slice(&(new.len() as u32).to_le_bytes());
201            result.extend_from_slice(new);
202            result
203        })
204}
205
206/// Apply delta to reconstruct target
207pub fn apply_delta(source: &[u8], delta: &Delta) -> Result<Vec<u8>> {
208    if source.len() as u64 != delta.source_size {
209        return Err(Error::delta(format!(
210            "source size mismatch: expected {}, got {}",
211            delta.source_size, source.len()
212        )));
213    }
214    
215    let mut result = Vec::with_capacity(delta.target_size as usize);
216    
217    for op in &delta.ops {
218        match op {
219            Op::Copy { src_offset, length } => {
220                let start = *src_offset as usize;
221                let end = start + *length as usize;
222                if end > source.len() {
223                    return Err(Error::delta("copy extends past source end"));
224                }
225                result.extend_from_slice(&source[start..end]);
226            }
227            Op::Insert { data } => {
228                result.extend_from_slice(data);
229            }
230        }
231    }
232    
233    if result.len() as u64 != delta.target_size {
234        return Err(Error::delta(format!(
235            "result size mismatch: expected {}, got {}",
236            delta.target_size, result.len()
237        )));
238    }
239    
240    Ok(result)
241}
speck_core/delta/mod.rs

speck_core/delta/
mod.rs
