1use alloc::vec;
20use alloc::vec::Vec;
21
22use crate::{Error, Result};
23
24const HASH_COUNT: usize = 3;
26const POSITION_SEEDS: [u64; HASH_COUNT] = [
28 0x9e37_79b9_7f4a_7c15,
29 0xbf58_476d_1ce4_e5b9,
30 0x94d0_49bb_1331_11eb,
31];
32
33pub fn splitmix64(mut value: u64) -> u64 {
35 value = value.wrapping_add(0x9e37_79b9_7f4a_7c15);
36 value = (value ^ (value >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
37 value = (value ^ (value >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
38 value ^ (value >> 31)
39}
40
41#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
43pub struct Cell {
44 pub count: i32,
46 pub key_sum: u64,
48 pub value_sum: u64,
50 pub hash_sum: u64,
52}
53
54#[derive(Clone, Copy, Debug, Eq, PartialEq)]
56pub struct IbltEntry {
57 pub key: u64,
59 pub value: u64,
61 pub present_in_self: bool,
63}
64
65#[derive(Clone, Debug, Eq, PartialEq)]
67pub struct Iblt {
68 cells: Vec<Cell>,
69}
70
71impl Iblt {
72 pub fn new(num_cells: usize) -> Self {
78 Self {
79 cells: vec![Cell::default(); num_cells.max(1)],
80 }
81 }
82
83 pub fn num_cells(&self) -> usize {
85 self.cells.len()
86 }
87
88 pub fn occupied(&self) -> usize {
90 self.cells.iter().filter(|cell| cell.count != 0).count()
91 }
92
93 pub fn is_empty(&self) -> bool {
95 self.cells.iter().all(|cell| cell.count == 0)
96 }
97
98 pub fn insert(&mut self, key: u64, value: u64) {
100 let hash = splitmix64(key);
101 for seed in POSITION_SEEDS {
102 let position = (splitmix64(key ^ seed) as usize) % self.cells.len();
103 let cell = &mut self.cells[position];
104 cell.count += 1;
105 cell.key_sum ^= key;
106 cell.value_sum ^= value;
107 cell.hash_sum ^= hash;
108 }
109 }
110
111 pub fn delete(&mut self, key: u64, value: u64) {
113 let hash = splitmix64(key);
114 for seed in POSITION_SEEDS {
115 let position = (splitmix64(key ^ seed) as usize) % self.cells.len();
116 let cell = &mut self.cells[position];
117 cell.count -= 1;
118 cell.key_sum ^= key;
119 cell.value_sum ^= value;
120 cell.hash_sum ^= hash;
121 }
122 }
123
124 pub fn subtract(&mut self, other: &Iblt) -> Result<()> {
129 if self.cells.len() != other.cells.len() {
130 return Err(Error::Iblt("IBLT size mismatch in subtract"));
131 }
132 for (left, right) in self.cells.iter_mut().zip(&other.cells) {
133 left.count -= right.count;
134 left.key_sum ^= right.key_sum;
135 left.value_sum ^= right.value_sum;
136 left.hash_sum ^= right.hash_sum;
137 }
138 Ok(())
139 }
140
141 pub fn decode(&self) -> Result<Vec<IbltEntry>> {
147 let mut table = self.clone();
148 let mut entries = Vec::new();
149 loop {
150 let mut progress = false;
151 for position in 0..table.cells.len() {
152 let count = table.cells[position].count;
153 if count == 1 || count == -1 {
154 let key = table.cells[position].key_sum;
155 let value = table.cells[position].value_sum;
156 if splitmix64(key) != table.cells[position].hash_sum {
157 return Err(Error::Iblt("IBLT cell hash does not verify"));
158 }
159 if count == 1 {
160 table.delete(key, value);
161 entries.push(IbltEntry {
162 key,
163 value,
164 present_in_self: true,
165 });
166 } else {
167 table.insert(key, value);
168 entries.push(IbltEntry {
169 key,
170 value,
171 present_in_self: false,
172 });
173 }
174 progress = true;
175 break;
176 }
177 }
178 if !progress {
179 break;
180 }
181 }
182 if !table.is_empty() {
183 return Err(Error::Iblt("IBLT decode incomplete (table too small?)"));
184 }
185 Ok(entries)
186 }
187
188 pub fn cells(&self) -> &[Cell] {
190 &self.cells
191 }
192}
193
194pub fn encode_set(entries: &[(u64, u64)], num_cells: usize) -> Iblt {
196 let mut table = Iblt::new(num_cells);
197 for &(key, value) in entries {
198 table.insert(key, value);
199 }
200 table
201}
202
203pub fn reconcile(mine: &Iblt, theirs: &Iblt) -> Result<Vec<IbltEntry>> {
209 let mut difference = mine.clone();
210 difference.subtract(theirs)?;
211 difference.decode()
212}
213
214#[cfg(test)]
215mod tests {
216 use super::*;
217
218 fn random_pairs(seed: u64, count: usize) -> Vec<(u64, u64)> {
219 let mut state = seed;
220 let mut pairs = Vec::with_capacity(count);
221 for index in 0..count {
222 state = splitmix64(state);
223 let key = state ^ (index as u64).wrapping_mul(0x9e37_79b9);
224 pairs.push((key, state.wrapping_mul(3) + index as u64));
225 }
226 pairs
227 }
228
229 #[test]
230 fn insert_delete_roundtrips_and_decodes_empty() {
231 let mut table = Iblt::new(16);
232 let pairs = random_pairs(0x1234, 8);
233 for &(key, value) in &pairs {
234 table.insert(key, value);
235 }
236 assert!(!table.is_empty());
237 for &(key, value) in &pairs {
238 table.delete(key, value);
239 }
240 assert!(table.is_empty());
241 assert_eq!(table.decode().unwrap(), Vec::new());
242 }
243
244 #[test]
245 fn reconcile_recovers_exact_difference() {
246 let common = random_pairs(0xabcd, 200);
247 let mut mine_set = common.clone();
248 mine_set.extend(random_pairs(0x1111, 10));
249 let mut theirs_set = common.clone();
250 theirs_set.extend(random_pairs(0x2222, 7));
251
252 let mine = encode_set(&mine_set, 256);
253 let theirs = encode_set(&theirs_set, 256);
254 let difference = reconcile(&mine, &theirs).unwrap();
255
256 let only_mine: Vec<(u64, u64)> = difference
257 .iter()
258 .filter(|entry| entry.present_in_self)
259 .map(|entry| (entry.key, entry.value))
260 .collect();
261 let only_theirs: Vec<(u64, u64)> = difference
262 .iter()
263 .filter(|entry| !entry.present_in_self)
264 .map(|entry| (entry.key, entry.value))
265 .collect();
266
267 let mut expected_mine = random_pairs(0x1111, 10);
268 expected_mine.sort_unstable();
269 let mut expected_theirs = random_pairs(0x2222, 7);
270 expected_theirs.sort_unstable();
271 let mut actual_mine = only_mine;
272 actual_mine.sort_unstable();
273 let mut actual_theirs = only_theirs;
274 actual_theirs.sort_unstable();
275 assert_eq!(actual_mine, expected_mine);
276 assert_eq!(actual_theirs, expected_theirs);
277 }
278
279 #[test]
280 fn undersized_table_reports_incomplete_decode() {
281 let mine_set = random_pairs(0x3333, 30);
283 let theirs_set: Vec<(u64, u64)> = Vec::new();
284 let mine = encode_set(&mine_set, 8);
285 let theirs = encode_set(&theirs_set, 8);
286 assert!(matches!(
287 reconcile(&mine, &theirs),
288 Err(Error::Iblt("IBLT decode incomplete (table too small?)"))
289 ));
290 }
291
292 #[test]
293 fn identical_sets_reconcile_to_empty() {
294 let pairs = random_pairs(0x5555, 64);
295 let mine = encode_set(&pairs, 128);
296 let theirs = encode_set(&pairs, 128);
297 assert!(reconcile(&mine, &theirs).unwrap().is_empty());
298 }
299}