qualia_core_db/net/qdnf/resolve/qsr/
compare.rs1use super::cover::CoverInterval;
11use super::kbucket::{KBucketTable, CONTACT_CAP, K};
12use super::key::keys_equal;
13use super::outcome::QsrOutcome;
14use super::traversal::{lookup_into, QsrSnapshot};
15use crate::net::qdnf::errors::QdnfError;
16use crate::net::qdnf::types::{Generation, StrongDigest};
17
18pub const LOCAL_XOR_CAP: usize = 8;
20
21pub fn in_process_kbucket_comparison_executed() -> bool {
23 true
24}
25
26pub fn networked_kademlia_comparison_executed() -> bool {
28 false
29}
30
31pub fn unmeasured_better_than_kademlia_claimed() -> bool {
33 false
34}
35
36pub fn kademlia_comparison_executed() -> bool {
38 in_process_kbucket_comparison_executed() && !unmeasured_better_than_kademlia_claimed()
39}
40
41#[repr(C)]
43#[derive(Clone, Copy, Debug, PartialEq, Eq)]
44pub struct ClosedWorldComparison {
45 pub key_count: u8,
46 pub budget: u8,
47 pub qsr_outcome: QsrOutcome,
48 pub qsr_work: u8,
49 pub xor_used: u8,
50 pub xor_matched_query: bool,
51 pub recorded: bool,
52}
53
54#[repr(C)]
56#[derive(Clone, Copy, Debug, PartialEq, Eq)]
57pub struct KBucketComparison {
58 pub key_count: u8,
59 pub budget: u8,
60 pub qsr_outcome: QsrOutcome,
61 pub qsr_work: u8,
62 pub kbucket_used: u8,
63 pub kbucket_matched_query: bool,
64 pub recorded: bool,
65}
66
67pub fn xor_distance(a: &StrongDigest, b: &StrongDigest, out: &mut [u8; 48]) {
69 let mut i = 0usize;
70 while i < 48 {
71 out[i] = a.0[i] ^ b.0[i];
72 i += 1;
73 }
74}
75
76pub fn local_xor_nearest(
81 table: &[StrongDigest],
82 target: &StrongDigest,
83 work_budget: u8,
84 out: &mut StrongDigest,
85) -> Result<u8, QdnfError> {
86 if table.len() > LOCAL_XOR_CAP {
87 return Err(QdnfError::Capacity);
88 }
89 if table.is_empty() {
90 return Err(QdnfError::Incomplete);
91 }
92 let mut best_i = 0usize;
93 let mut best = [0xffu8; 48];
94 let mut used: u8 = 0;
95 let mut i = 0usize;
96 while i < table.len() {
97 if used == work_budget {
98 return Err(QdnfError::BudgetExhausted);
99 }
100 used = used + 1;
101 let mut dist = [0u8; 48];
102 xor_distance(target, &table[i], &mut dist);
103 if distance_less(&dist, &best) {
104 best = dist;
105 best_i = i;
106 }
107 i += 1;
108 }
109 *out = table[best_i];
110 Ok(used)
111}
112
113fn distance_less(a: &[u8; 48], b: &[u8; 48]) -> bool {
114 let mut i = 0usize;
115 while i < 48 {
116 if a[i] < b[i] {
117 return true;
118 }
119 if a[i] > b[i] {
120 return false;
121 }
122 i += 1;
123 }
124 false
125}
126
127fn charge_slots(occupied: usize, work_budget: u8) -> Result<u8, QdnfError> {
128 if occupied > LOCAL_XOR_CAP {
129 return Err(QdnfError::Capacity);
130 }
131 let mut used: u8 = 0;
132 let mut i = 0usize;
133 while i < occupied {
134 if used == work_budget {
135 return Err(QdnfError::BudgetExhausted);
136 }
137 used = used + 1;
138 i += 1;
139 }
140 Ok(used)
141}
142
143fn comparison_local_id() -> StrongDigest {
144 let mut id = StrongDigest::ZERO;
145 id.0[0] = 0x80;
146 id
147}
148
149pub fn run_closed_world_comparison(
155 keys: &[StrongDigest],
156 values: &[StrongDigest],
157 query: &StrongDigest,
158 work_budget: u8,
159 qsr_out: &mut StrongDigest,
160 xor_out: &mut StrongDigest,
161) -> Result<ClosedWorldComparison, QdnfError> {
162 if keys.len() != values.len() {
163 return Err(QdnfError::Malformed);
164 }
165 if keys.len() > LOCAL_XOR_CAP {
166 return Err(QdnfError::Capacity);
167 }
168
169 let mut snap = QsrSnapshot::empty(Generation(1));
170 let mut i = 0usize;
171 while i < keys.len() {
172 snap.insert(keys[i], values[i])?;
173 i += 1;
174 }
175
176 let covers = [CoverInterval { start: 0, end: 15 }];
177 let qsr_work = charge_slots(snap.len(), work_budget)?;
178 let mut slot = [StrongDigest::ZERO; 1];
179 let qsr_outcome = lookup_into(&snap, query, &covers, Generation(1), &mut slot)?;
180 *qsr_out = slot[0];
181
182 let xor_used = local_xor_nearest(keys, query, work_budget, xor_out)?;
183 let xor_matched_query = keys_equal(xor_out, query);
184
185 Ok(ClosedWorldComparison {
186 key_count: keys.len() as u8,
187 budget: work_budget,
188 qsr_outcome,
189 qsr_work,
190 xor_used,
191 xor_matched_query,
192 recorded: true,
193 })
194}
195
196pub fn run_in_process_kbucket_comparison(
200 keys: &[StrongDigest],
201 values: &[StrongDigest],
202 query: &StrongDigest,
203 work_budget: u8,
204 qsr_out: &mut StrongDigest,
205 kbucket_out: &mut StrongDigest,
206) -> Result<KBucketComparison, QdnfError> {
207 if keys.len() != values.len() {
208 return Err(QdnfError::Malformed);
209 }
210 if keys.len() > LOCAL_XOR_CAP || keys.len() > CONTACT_CAP {
211 return Err(QdnfError::Capacity);
212 }
213
214 let mut snap = QsrSnapshot::empty(Generation(1));
215 let mut i = 0usize;
216 while i < keys.len() {
217 snap.insert(keys[i], values[i])?;
218 i += 1;
219 }
220
221 let covers = [CoverInterval { start: 0, end: 15 }];
222 let qsr_work = charge_slots(snap.len(), work_budget)?;
223 let mut slot = [StrongDigest::ZERO; 1];
224 let qsr_outcome = lookup_into(&snap, query, &covers, Generation(1), &mut slot)?;
225 *qsr_out = slot[0];
226
227 let mut table = KBucketTable::new(comparison_local_id());
228 table.bootstrap(keys)?;
229 let mut closest_buf = [StrongDigest::ZERO; K];
230 let kbucket_used = table.iterative_lookup(query, work_budget, &mut closest_buf)?;
231 *kbucket_out = closest_buf[0];
232 let kbucket_matched_query = keys_equal(kbucket_out, query);
233
234 Ok(KBucketComparison {
235 key_count: keys.len() as u8,
236 budget: work_budget,
237 qsr_outcome,
238 qsr_work,
239 kbucket_used,
240 kbucket_matched_query,
241 recorded: true,
242 })
243}
244
245#[cfg(test)]
246mod tests {
247 use super::*;
248
249 fn key_rest(rest: u8) -> StrongDigest {
250 let mut k = StrongDigest::ZERO;
251 k.0[0] = 0x10;
252 let mut i = 1usize;
253 while i < 48 {
254 k.0[i] = rest;
255 i += 1;
256 }
257 k
258 }
259
260 #[test]
261 fn kademlia_comparison_executed_is_in_process_only() {
262 assert!(in_process_kbucket_comparison_executed());
263 assert!(kademlia_comparison_executed());
264 assert!(!networked_kademlia_comparison_executed());
265 assert!(!unmeasured_better_than_kademlia_claimed());
266 }
267
268 #[test]
269 fn networked_kademlia_comparison_was_not_executed() {
270 assert!(!networked_kademlia_comparison_executed());
271 }
272
273 #[test]
274 fn unmeasured_better_than_kademlia_is_not_claimed() {
275 assert!(!unmeasured_better_than_kademlia_claimed());
276 }
277
278 #[test]
279 fn local_xor_finds_exact_key_without_being_kademlia() {
280 let mut a = StrongDigest::ZERO;
281 let mut b = StrongDigest::ZERO;
282 a.0[47] = 1;
283 b.0[47] = 9;
284 let table = [a, b];
285 let mut out = StrongDigest::ZERO;
286 let used = local_xor_nearest(&table, &a, 8, &mut out).unwrap();
287 assert_eq!(used, 2);
288 assert_eq!(out, a);
289 assert!(!networked_kademlia_comparison_executed());
290 assert!(!unmeasured_better_than_kademlia_claimed());
291 }
292
293 #[test]
294 fn local_xor_budget_exhaustion_is_not_a_dht_timeout() {
295 let table = [StrongDigest::ZERO, StrongDigest::ZERO];
296 let mut out = StrongDigest::ZERO;
297 assert_eq!(
298 local_xor_nearest(&table, &StrongDigest::ZERO, 1, &mut out),
299 Err(QdnfError::BudgetExhausted)
300 );
301 }
302
303 #[test]
304 fn closed_world_comparison_runs_results_recorded_no_kademlia_claim() {
305 let a = key_rest(0x01);
306 let b = key_rest(0x02);
307 assert_eq!(a.0[0], b.0[0]);
308 let mut va = StrongDigest::ZERO;
309 let mut vb = StrongDigest::ZERO;
310 va.0[47] = 0x11;
311 vb.0[47] = 0x22;
312 let keys = [a, b];
313 let values = [va, vb];
314 let mut qsr_out = StrongDigest::ZERO;
315 let mut xor_out = StrongDigest::ZERO;
316 let record = run_closed_world_comparison(
317 &keys,
318 &values,
319 &a,
320 LOCAL_XOR_CAP as u8,
321 &mut qsr_out,
322 &mut xor_out,
323 )
324 .unwrap();
325 assert!(record.recorded);
326 assert_eq!(record.key_count, 2);
327 assert_eq!(record.budget, LOCAL_XOR_CAP as u8);
328 assert_eq!(record.qsr_work, 2);
329 assert_eq!(record.xor_used, 2);
330 assert_eq!(record.qsr_outcome, QsrOutcome::Found { count: 1 });
331 assert!(record.xor_matched_query);
332 assert!(keys_equal(&qsr_out, &va));
333 assert!(keys_equal(&xor_out, &a));
334 assert!(!networked_kademlia_comparison_executed());
335 assert!(!unmeasured_better_than_kademlia_claimed());
336 }
337
338 #[test]
339 fn empty_in_snapshot_versus_xor_nearest_is_not_a_kademlia_claim() {
340 let present = key_rest(0x03);
341 let missing = key_rest(0x04);
342 let mut value = StrongDigest::ZERO;
343 value.0[47] = 0x99;
344 let keys = [present];
345 let values = [value];
346 let mut qsr_out = StrongDigest::ZERO;
347 let mut xor_out = StrongDigest::ZERO;
348 let record =
349 run_closed_world_comparison(&keys, &values, &missing, 8, &mut qsr_out, &mut xor_out)
350 .unwrap();
351 assert!(record.recorded);
352 assert_eq!(record.qsr_outcome, QsrOutcome::EmptyInSnapshot);
353 assert_ne!(record.qsr_outcome, QsrOutcome::Found { count: 1 });
354 assert!(!record.xor_matched_query);
355 assert!(keys_equal(&xor_out, &present));
356 assert!(!networked_kademlia_comparison_executed());
357 assert!(!unmeasured_better_than_kademlia_claimed());
358 }
359
360 #[test]
361 fn in_process_kbucket_comparison_records_qsr_and_kbucket_work() {
362 let a = key_rest(0x01);
363 let b = key_rest(0x02);
364 let mut va = StrongDigest::ZERO;
365 let mut vb = StrongDigest::ZERO;
366 va.0[47] = 0x11;
367 vb.0[47] = 0x22;
368 let keys = [a, b];
369 let values = [va, vb];
370 let mut qsr_out = StrongDigest::ZERO;
371 let mut kbucket_out = StrongDigest::ZERO;
372 let record = run_in_process_kbucket_comparison(
373 &keys,
374 &values,
375 &a,
376 LOCAL_XOR_CAP as u8,
377 &mut qsr_out,
378 &mut kbucket_out,
379 )
380 .unwrap();
381 assert!(record.recorded);
382 assert_eq!(record.key_count, 2);
383 assert_eq!(record.budget, LOCAL_XOR_CAP as u8);
384 assert_eq!(record.qsr_work, 2);
385 assert_eq!(record.kbucket_used, 2);
386 assert_eq!(record.qsr_outcome, QsrOutcome::Found { count: 1 });
387 assert!(record.kbucket_matched_query);
388 assert!(keys_equal(&qsr_out, &va));
389 assert!(keys_equal(&kbucket_out, &a));
390 assert!(kademlia_comparison_executed());
391 assert!(!networked_kademlia_comparison_executed());
392 assert!(!unmeasured_better_than_kademlia_claimed());
393 }
394}