Onset: version control where nobody waits and nothing gets lost. The on command, its core and onset-server.
| 1 | //! Deltas: an object as copies from an earlier version of it and the bytes |
| 2 | //! that are new, in git's delta format (`git::apply_delta` reads them). |
| 3 | //! |
| 4 | //! A host keeps what landings make this way: a landing writes each folder on |
| 5 | //! its paths again, and the new tree is the old one with an entry or two |
| 6 | //! changed, so its delta is tens of bytes where the tree is kilobytes. |
| 7 |
| 8 | use std::collections::HashMap; |
| 9 | use std::hash::{BuildHasherDefault, Hasher}; |
| 10 |
| 11 | /// Bytes matched at a time: shorter runs in common aren't worth a copy. |
| 12 | const BLOCK: usize = 16; |
| 13 |
| 14 | /// Keys that are hashes already, used as they are. |
| 15 | #[derive(Default)] |
| 16 | struct Passed(u64); |
| 17 |
| 18 | impl Hasher for Passed { |
| 19 | fn finish(&self) -> u64 { |
| 20 | self.0 |
| 21 | } |
| 22 | fn write(&mut self, bytes: &[u8]) { |
| 23 | for &b in bytes { |
| 24 | self.0 = (self.0 << 8) | u64::from(b); |
| 25 | } |
| 26 | } |
| 27 | fn write_u64(&mut self, n: u64) { |
| 28 | self.0 = n; |
| 29 | } |
| 30 | } |
| 31 |
| 32 | /// A delta making `target` from `base`, when it's under half the size of |
| 33 | /// `target` (None otherwise: keeping the object whole is as good). |
| 34 | pub fn encode(base: &[u8], target: &[u8]) -> Option<Vec<u8>> { |
| 35 | if target.len() < 2 * BLOCK || base.len() < BLOCK || base.len() > u32::MAX as usize { |
| 36 | return None; |
| 37 | } |
| 38 | let limit = target.len() / 2; |
| 39 | // A folder with an entry or two changed is the base's start, new bytes, |
| 40 | // and the base's end: that much needs no search. |
| 41 | let prefix = base.iter().zip(target).take_while(|(a, b)| a == b).count(); |
| 42 | let room = base.len().min(target.len()) - prefix; |
| 43 | let suffix = base.iter().rev().zip(target.iter().rev()).take(room).take_while(|(a, b)| a == b).count(); |
| 44 | if target.len() - prefix - suffix <= target.len() / 4 { |
| 45 | let mut out = Vec::with_capacity(target.len() - prefix - suffix + 32); |
| 46 | size(&mut out, base.len()); |
| 47 | size(&mut out, target.len()); |
| 48 | copy(&mut out, 0, prefix); |
| 49 | insert(&mut out, &target[prefix..target.len() - suffix]); |
| 50 | copy(&mut out, base.len() - suffix, suffix); |
| 51 | return (out.len() < limit).then_some(out); |
| 52 | } |
| 53 | // Where each block of the base starts, by its bytes' hash. |
| 54 | let mut starts: HashMap<u64, u32, BuildHasherDefault<Passed>> = HashMap::with_capacity_and_hasher(base.len() / BLOCK + 1, Default::default()); |
| 55 | for off in (0..=base.len() - BLOCK).step_by(BLOCK) { |
| 56 | starts.entry(hash(&base[off..off + BLOCK])).or_insert(off as u32); |
| 57 | } |
| 58 | let mut out = Vec::with_capacity(target.len() / 4 + 16); |
| 59 | size(&mut out, base.len()); |
| 60 | size(&mut out, target.len()); |
| 61 | // Target bytes not copied yet start at `pending`. |
| 62 | let mut pending = 0; |
| 63 | let mut at = 0; |
| 64 | while at + BLOCK <= target.len() { |
| 65 | let found = starts.get(&hash(&target[at..at + BLOCK])).map(|&o| o as usize).filter(|&o| base[o..o + BLOCK] == target[at..at + BLOCK]); |
| 66 | let Some(off) = found else { |
| 67 | at += 1; |
| 68 | continue; |
| 69 | }; |
| 70 | // The run in common, as far as it goes both ways. |
| 71 | let (mut start, mut from) = (at, off); |
| 72 | while start > pending && from > 0 && base[from - 1] == target[start - 1] { |
| 73 | start -= 1; |
| 74 | from -= 1; |
| 75 | } |
| 76 | let (mut end, mut to) = (at + BLOCK, off + BLOCK); |
| 77 | while end < target.len() && to < base.len() && base[to] == target[end] { |
| 78 | end += 1; |
| 79 | to += 1; |
| 80 | } |
| 81 | insert(&mut out, &target[pending..start]); |
| 82 | copy(&mut out, from, end - start); |
| 83 | if out.len() >= limit { |
| 84 | return None; |
| 85 | } |
| 86 | pending = end; |
| 87 | at = end; |
| 88 | } |
| 89 | insert(&mut out, &target[pending..]); |
| 90 | (out.len() < limit).then_some(out) |
| 91 | } |
| 92 |
| 93 | fn hash(block: &[u8]) -> u64 { |
| 94 | let a = u64::from_le_bytes(block[..8].try_into().unwrap()); |
| 95 | let b = u64::from_le_bytes(block[8..16].try_into().unwrap()); |
| 96 | (a.wrapping_mul(0x9e37_79b9_7f4a_7c15) ^ b).wrapping_mul(0xc2b2_ae3d_27d4_eb4f) |
| 97 | } |
| 98 |
| 99 | fn size(out: &mut Vec<u8>, mut n: usize) { |
| 100 | loop { |
| 101 | let byte = (n & 0x7f) as u8; |
| 102 | n >>= 7; |
| 103 | if n == 0 { |
| 104 | out.push(byte); |
| 105 | return; |
| 106 | } |
| 107 | out.push(byte | 0x80); |
| 108 | } |
| 109 | } |
| 110 |
| 111 | fn insert(out: &mut Vec<u8>, bytes: &[u8]) { |
| 112 | for part in bytes.chunks(127) { |
| 113 | out.push(part.len() as u8); |
| 114 | out.extend_from_slice(part); |
| 115 | } |
| 116 | } |
| 117 |
| 118 | fn copy(out: &mut Vec<u8>, mut off: usize, mut len: usize) { |
| 119 | while len > 0 { |
| 120 | let n = len.min(0xff_ffff); |
| 121 | let mut op = 0x80u8; |
| 122 | let at = out.len(); |
| 123 | out.push(0); |
| 124 | for i in 0..4 { |
| 125 | let b = ((off >> (8 * i)) & 0xff) as u8; |
| 126 | if b != 0 { |
| 127 | op |= 1 << i; |
| 128 | out.push(b); |
| 129 | } |
| 130 | } |
| 131 | for i in 0..3 { |
| 132 | let b = ((n >> (8 * i)) & 0xff) as u8; |
| 133 | if b != 0 { |
| 134 | op |= 0x10 << i; |
| 135 | out.push(b); |
| 136 | } |
| 137 | } |
| 138 | out[at] = op; |
| 139 | off += n; |
| 140 | len -= n; |
| 141 | } |
| 142 | } |
| 143 |
| 144 | #[cfg(test)] |
| 145 | mod tests { |
| 146 | use super::*; |
| 147 | use crate::git::apply_delta; |
| 148 |
| 149 | struct Rng(u64); |
| 150 | impl Rng { |
| 151 | fn next(&mut self) -> u64 { |
| 152 | self.0 ^= self.0 >> 12; |
| 153 | self.0 ^= self.0 << 25; |
| 154 | self.0 ^= self.0 >> 27; |
| 155 | self.0.wrapping_mul(0x2545f4914f6cdd1d) |
| 156 | } |
| 157 | fn below(&mut self, n: usize) -> usize { |
| 158 | (self.next() % n.max(1) as u64) as usize |
| 159 | } |
| 160 | fn bytes(&mut self, n: usize) -> Vec<u8> { |
| 161 | (0..n).map(|_| self.next() as u8).collect() |
| 162 | } |
| 163 | } |
| 164 |
| 165 | fn check(base: &[u8], target: &[u8]) -> Option<usize> { |
| 166 | let delta = encode(base, target)?; |
| 167 | assert_eq!(apply_delta(base, &delta, target.len()).unwrap(), target); |
| 168 | assert!(delta.len() < target.len() / 2); |
| 169 | Some(delta.len()) |
| 170 | } |
| 171 |
| 172 | #[test] |
| 173 | fn a_folder_with_one_entry_changed_is_a_few_bytes() { |
| 174 | let entry = |i: usize, v: u8| [vec![1u8, 12, 0], format!("file-{i:06}.rs").into_bytes(), vec![v; 32]].concat(); |
| 175 | let base: Vec<u8> = (0..200).flat_map(|i| entry(i, i as u8)).collect(); |
| 176 | let mut target = base.clone(); |
| 177 | let one = entry(77, 0xee); |
| 178 | let at = 77 * one.len(); |
| 179 | target[at..at + one.len()].copy_from_slice(&one); |
| 180 | let n = check(&base, &target).unwrap(); |
| 181 | assert!(n < 64, "{n} bytes for {}", target.len()); |
| 182 | // An entry added in the middle, and one taken out further on. |
| 183 | let mut moved = base[..at].to_vec(); |
| 184 | moved.extend(entry(1_000_000, 9)); |
| 185 | moved.extend(&base[at..150 * one.len()]); |
| 186 | moved.extend(&base[151 * one.len()..]); |
| 187 | assert!(check(&base, &moved).unwrap() < 96); |
| 188 | } |
| 189 |
| 190 | #[test] |
| 191 | fn edits_anywhere_come_back_exactly() { |
| 192 | let mut rng = Rng(0x1234_5678_9abc_def1); |
| 193 | let mut made = 0; |
| 194 | for _ in 0..3000 { |
| 195 | let n = rng.below(5000); |
| 196 | let base = if rng.below(3) == 0 { rng.bytes(n) } else { (0..n).map(|i| b"abcdefghij\n"[i % 11]).collect() }; |
| 197 | let mut target = base.clone(); |
| 198 | for _ in 0..rng.below(6) { |
| 199 | let at = rng.below(target.len() + 1); |
| 200 | match rng.below(3) { |
| 201 | 0 => { |
| 202 | let n = rng.below(80); |
| 203 | let new = rng.bytes(n); |
| 204 | target.splice(at..at, new); |
| 205 | } |
| 206 | 1 => { |
| 207 | let end = (at + rng.below(200)).min(target.len()); |
| 208 | target.drain(at..end); |
| 209 | } |
| 210 | _ => { |
| 211 | let end = (at + rng.below(40)).min(target.len()); |
| 212 | for b in &mut target[at..end] { |
| 213 | *b = rng.next() as u8; |
| 214 | } |
| 215 | } |
| 216 | } |
| 217 | } |
| 218 | if check(&base, &target).is_some() { |
| 219 | made += 1; |
| 220 | } |
| 221 | } |
| 222 | // Most small edits make a delta. |
| 223 | assert!(made > 1500, "{made}"); |
| 224 | } |
| 225 |
| 226 | #[test] |
| 227 | fn unrelated_or_tiny_objects_stay_whole() { |
| 228 | let mut rng = Rng(7); |
| 229 | assert_eq!(encode(&rng.bytes(4000), &rng.bytes(4000)), None); |
| 230 | assert_eq!(encode(b"short", b"shorter"), None); |
| 231 | assert_eq!(encode(&[], &rng.bytes(100)), None); |
| 232 | } |
| 233 | } |
| 234 |
