1use std::hash::{DefaultHasher, Hash, Hasher};
19use std::sync::Arc;
20
21use hashbrown::HashMap;
22
23use crate::bin::error_model_type::RemoteCheckModel;
24use crate::bin::{ErrorModel, ErrorModelType, ProbabilityModifier};
25use crate::controller::jit_controller::hash_error_model_type_structural;
26use crate::misc::relative_program::{RelativeMapping, RelativeProgram};
27
28#[derive(Debug, Clone, PartialEq, Eq, Hash)]
36pub struct ProbabilityModifierBits {
37 pub probabilities: Vec<u64>,
38 pub sparse_indices: Vec<u64>,
39 pub sparse_probabilities: Vec<u64>,
40}
41
42impl From<&ProbabilityModifier> for ProbabilityModifierBits {
43 fn from(pm: &ProbabilityModifier) -> Self {
44 Self {
45 probabilities: pm.probabilities.iter().map(|p| p.to_bits()).collect(),
46 sparse_indices: pm.sparse_indices.clone(),
47 sparse_probabilities: pm.sparse_probabilities.iter().map(|p| p.to_bits()).collect(),
48 }
49 }
50}
51
52#[derive(Debug, Clone, PartialEq, Eq, Hash)]
69pub struct ErrorModelFingerprint {
70 pub etype_digest: u64,
71 pub pm: Option<ProbabilityModifierBits>,
72 pub remote_check_models: Arc<Vec<Option<RemoteCheckModel>>>,
73}
74
75impl ErrorModelFingerprint {
76 pub fn new(
81 instance: &ErrorModel,
82 modified_remote_check_models: Arc<Vec<Option<RemoteCheckModel>>>,
83 etype_digest: u64,
84 ) -> Self {
85 let pm = instance
86 .modifier
87 .as_ref()
88 .and_then(|m| m.probability_modifier.as_ref())
89 .map(ProbabilityModifierBits::from);
90 Self {
91 etype_digest,
92 pm,
93 remote_check_models: modified_remote_check_models,
94 }
95 }
96}
97
98pub fn etype_digest(emt: &ErrorModelType) -> u64 {
106 let mut hasher = DefaultHasher::new();
107 hash_error_model_type_structural(emt, &mut hasher);
108 hasher.finish()
109}
110
111#[derive(Debug, Clone, PartialEq, Eq, Hash)]
137pub struct DecoderCacheKey {
138 pub relative_program: RelativeProgram,
139 pub error_model_fingerprints: Vec<ErrorModelFingerprint>,
140 pub committing_local_cids: Vec<u32>,
141 pub logical_flip_signature: Vec<u64>,
142}
143
144pub trait FingerprintSource {
160 fn instance(&self) -> &ErrorModel;
161 fn modified_remote_check_models(&self) -> &Arc<Vec<Option<RemoteCheckModel>>>;
162}
163
164pub fn build_modifier_fingerprints<E: FingerprintSource>(
180 mapping: &RelativeMapping,
181 error_models: &HashMap<u64, E>,
182 error_model_types: &HashMap<u64, Arc<ErrorModelType>>,
183) -> Vec<ErrorModelFingerprint> {
184 let mut digest_cache: HashMap<u64, u64> = HashMap::with_capacity(error_model_types.len());
185 mapping
186 .global_eid_of
187 .iter()
188 .map(|eid| {
189 let em = error_models.get(eid).expect("error_model present for eid in window");
190 let etype = em.instance().etype;
191 let digest = *digest_cache.entry(etype).or_insert_with(|| {
192 let emt = error_model_types
193 .get(&etype)
194 .expect("error_model_type present for etype referenced by error_model");
195 etype_digest(emt)
196 });
197 ErrorModelFingerprint::new(em.instance(), em.modified_remote_check_models().clone(), digest)
198 })
199 .collect()
200}
201
202#[cfg(test)]
203mod tests {
204 use super::*;
217 use crate::bin::ProbabilityModifier;
218 use crate::bin::error_model::ErrorModelModifier;
219 use crate::bin::error_model_type::{Error, RemoteCheck, RemoteCheckModel, remote_check_model};
220 use crate::controller::jit_controller::ErrorModelTypeKey;
221
222 fn pm(probabilities: Vec<f64>) -> ProbabilityModifier {
225 ProbabilityModifier {
226 probabilities,
227 sparse_indices: vec![],
228 sparse_probabilities: vec![],
229 }
230 }
231
232 fn pm_sparse(sparse_indices: Vec<u64>, sparse_probabilities: Vec<f64>) -> ProbabilityModifier {
233 ProbabilityModifier {
234 probabilities: vec![],
235 sparse_indices,
236 sparse_probabilities,
237 }
238 }
239
240 fn error(probability: f64, check_index: u64) -> Error {
241 Error {
242 checks: vec![RemoteCheck {
243 remote_check_model: None,
244 check_index,
245 }],
246 probability,
247 ..Default::default()
248 }
249 }
250
251 fn emt(etype: u64, errors: Vec<Error>) -> ErrorModelType {
252 ErrorModelType {
253 etype,
254 ctype: 1,
255 errors,
256 remote_check_models: vec![],
257 ..Default::default()
258 }
259 }
260
261 fn em_with_modifier(eid: u64, etype: u64, modifier: Option<ProbabilityModifier>) -> ErrorModel {
262 ErrorModel {
263 eid,
264 etype,
265 cid: 1,
266 modifier: modifier.map(|p| ErrorModelModifier {
267 probability_modifier: Some(p),
268 reroute_remote_check_models: vec![],
269 }),
270 ..Default::default()
271 }
272 }
273
274 fn remote_check(check_bias: u64, output: u64) -> RemoteCheckModel {
275 RemoteCheckModel {
276 previous_remote_check_model: None,
277 port: Some(remote_check_model::Port::Output(output)),
278 expecting_ctype: 0,
279 check_bias,
280 absolute_cid: None,
281 ..Default::default()
282 }
283 }
284
285 fn fingerprint(instance: &ErrorModel, rcm: &[Option<RemoteCheckModel>], emt: &ErrorModelType) -> ErrorModelFingerprint {
292 ErrorModelFingerprint::new(instance, Arc::new(rcm.to_vec()), etype_digest(emt))
293 }
294
295 #[test]
298 fn probability_modifier_bits_distinguishes_different_dense_values() {
299 let a = ProbabilityModifierBits::from(&pm(vec![0.1, 0.2]));
300 let b = ProbabilityModifierBits::from(&pm(vec![0.1, 0.3]));
301 assert_ne!(a, b);
302 }
303
304 #[test]
305 fn probability_modifier_bits_distinguishes_different_sparse_values() {
306 let a = ProbabilityModifierBits::from(&pm_sparse(vec![0, 2], vec![0.1, 0.4]));
307 let b = ProbabilityModifierBits::from(&pm_sparse(vec![0, 2], vec![0.1, 0.5]));
308 assert_ne!(a, b);
309 }
310
311 #[test]
312 fn probability_modifier_bits_distinguishes_different_sparse_indices() {
313 let a = ProbabilityModifierBits::from(&pm_sparse(vec![0, 2], vec![0.1, 0.2]));
314 let b = ProbabilityModifierBits::from(&pm_sparse(vec![0, 3], vec![0.1, 0.2]));
315 assert_ne!(a, b);
316 }
317
318 #[test]
324 fn probability_modifier_bits_distinguishes_positive_and_negative_zero() {
325 assert_eq!(0.0_f64, -0.0_f64);
326 let a = ProbabilityModifierBits::from(&pm(vec![0.0]));
327 let b = ProbabilityModifierBits::from(&pm(vec![-0.0]));
328 assert_ne!(a, b);
329 }
330
331 #[test]
336 fn probability_modifier_bits_distinguishes_different_nan_payloads() {
337 let nan1 = f64::from_bits(0x7ff8_0000_0000_0001);
338 let nan2 = f64::from_bits(0x7ff8_0000_0000_0002);
339 assert!(nan1.is_nan() && nan2.is_nan());
340 let a = ProbabilityModifierBits::from(&pm(vec![nan1]));
341 let b = ProbabilityModifierBits::from(&pm(vec![nan2]));
342 assert_ne!(a, b);
343 }
344
345 #[test]
346 fn probability_modifier_bits_equal_for_identical_inputs() {
347 let a = ProbabilityModifierBits::from(&pm(vec![0.1, 0.2]));
348 let b = ProbabilityModifierBits::from(&pm(vec![0.1, 0.2]));
349 assert_eq!(a, b);
350 }
351
352 #[test]
355 fn fingerprint_differs_when_probability_modifier_differs() {
356 let etype = emt(1, vec![error(0.1, 0)]);
357 let em1 = em_with_modifier(1, 1, Some(pm(vec![0.1])));
358 let em2 = em_with_modifier(1, 1, Some(pm(vec![0.2])));
359 let f1 = fingerprint(&em1, &[], &etype);
360 let f2 = fingerprint(&em2, &[], &etype);
361 assert_ne!(f1, f2);
362 }
363
364 #[test]
365 fn fingerprint_differs_when_modifier_present_vs_absent() {
366 let etype = emt(1, vec![error(0.1, 0)]);
367 let em_no_mod = em_with_modifier(1, 1, None);
368 let em_with_mod = em_with_modifier(1, 1, Some(pm(vec![0.1])));
369 let f1 = fingerprint(&em_no_mod, &[], &etype);
370 let f2 = fingerprint(&em_with_mod, &[], &etype);
371 assert_ne!(f1, f2);
372 }
373
374 #[test]
375 fn fingerprint_differs_when_check_bias_differs() {
376 let etype = emt(1, vec![error(0.1, 0)]);
377 let em = em_with_modifier(1, 1, None);
378 let rcm_a = vec![Some(remote_check(0, 0))];
379 let rcm_b = vec![Some(remote_check(5, 0))];
380 let f1 = fingerprint(&em, &rcm_a, &etype);
381 let f2 = fingerprint(&em, &rcm_b, &etype);
382 assert_ne!(f1, f2);
383 }
384
385 #[test]
386 fn fingerprint_differs_when_remote_check_model_present_vs_absent() {
387 let etype = emt(1, vec![error(0.1, 0)]);
388 let em = em_with_modifier(1, 1, None);
389 let rcm_none = vec![None];
390 let rcm_some = vec![Some(remote_check(0, 0))];
391 let f1 = fingerprint(&em, &rcm_none, &etype);
392 let f2 = fingerprint(&em, &rcm_some, &etype);
393 assert_ne!(f1, f2);
394 }
395
396 #[test]
402 fn fingerprint_differs_when_same_etype_id_but_different_errors() {
403 let etype_v1 = emt(1, vec![error(0.1, 0)]);
404 let etype_v2 = emt(1, vec![error(0.1, 0), error(0.2, 1)]);
405 let em = em_with_modifier(1, 1, None);
406 let f1 = fingerprint(&em, &[], &etype_v1);
407 let f2 = fingerprint(&em, &[], &etype_v2);
408 assert_ne!(f1, f2);
409 assert_ne!(f1.etype_digest, f2.etype_digest);
410 }
411
412 #[test]
413 fn fingerprint_differs_when_same_etype_id_but_different_probability() {
414 let etype_v1 = emt(1, vec![error(0.1, 0)]);
415 let etype_v2 = emt(1, vec![error(0.2, 0)]);
416 let em = em_with_modifier(1, 1, None);
417 let f1 = fingerprint(&em, &[], &etype_v1);
418 let f2 = fingerprint(&em, &[], &etype_v2);
419 assert_ne!(f1.etype_digest, f2.etype_digest);
420 }
421
422 #[test]
423 fn fingerprint_equal_for_identical_inputs() {
424 let etype = emt(1, vec![error(0.1, 0)]);
425 let em = em_with_modifier(1, 1, Some(pm(vec![0.1])));
426 let rcm = vec![Some(remote_check(2, 0))];
427 let f1 = fingerprint(&em, &rcm, &etype);
428 let f2 = fingerprint(&em, &rcm, &etype);
429 assert_eq!(f1, f2);
430 }
431
432 #[test]
436 fn etype_digest_matches_error_model_type_key_hash() {
437 let et = emt(1, vec![error(0.1, 0), error(0.2, 1)]);
438 let digest = etype_digest(&et);
439 let mut hasher = DefaultHasher::new();
440 ErrorModelTypeKey(et.clone()).hash(&mut hasher);
441 assert_eq!(digest, hasher.finish());
442 }
443
444 fn empty_relative_program() -> RelativeProgram {
447 RelativeProgram {
448 local_gadgets: vec![],
449 count_checks: 0,
450 }
451 }
452
453 fn fp_with_etype_digest(d: u64) -> ErrorModelFingerprint {
454 ErrorModelFingerprint {
455 etype_digest: d,
456 pm: None,
457 remote_check_models: Arc::new(vec![]),
458 }
459 }
460
461 #[test]
462 fn cache_key_differs_when_fingerprints_differ() {
463 let r = empty_relative_program();
464 let k1 = DecoderCacheKey {
465 relative_program: r.clone(),
466 error_model_fingerprints: vec![fp_with_etype_digest(1)],
467 committing_local_cids: vec![],
468 logical_flip_signature: vec![],
469 };
470 let k2 = DecoderCacheKey {
471 relative_program: r,
472 error_model_fingerprints: vec![fp_with_etype_digest(2)],
473 committing_local_cids: vec![],
474 logical_flip_signature: vec![],
475 };
476 assert_ne!(k1, k2);
477
478 let mut map: HashMap<DecoderCacheKey, &'static str> = HashMap::new();
482 map.insert(k1.clone(), "first");
483 assert_eq!(map.get(&k2), None);
484 assert_eq!(map.get(&k1), Some(&"first"));
485 }
486
487 #[test]
488 fn cache_key_differs_when_committing_local_cids_differ() {
489 let r = empty_relative_program();
490 let k1 = DecoderCacheKey {
491 relative_program: r.clone(),
492 error_model_fingerprints: vec![],
493 committing_local_cids: vec![0, 1],
494 logical_flip_signature: vec![],
495 };
496 let k2 = DecoderCacheKey {
497 relative_program: r,
498 error_model_fingerprints: vec![],
499 committing_local_cids: vec![0, 2],
500 logical_flip_signature: vec![],
501 };
502 assert_ne!(k1, k2);
503
504 let mut map: HashMap<DecoderCacheKey, &'static str> = HashMap::new();
505 map.insert(k1.clone(), "first");
506 assert_eq!(map.get(&k2), None);
507 }
508
509 #[test]
516 fn cache_key_differs_when_only_commit_region_differs() {
517 let r = empty_relative_program();
518 let fp = fp_with_etype_digest(42);
519 let k1 = DecoderCacheKey {
520 relative_program: r.clone(),
521 error_model_fingerprints: vec![fp.clone()],
522 committing_local_cids: vec![0, 1, 2],
523 logical_flip_signature: vec![],
524 };
525 let k2 = DecoderCacheKey {
526 relative_program: r,
527 error_model_fingerprints: vec![fp],
528 committing_local_cids: vec![0, 1],
529 logical_flip_signature: vec![],
530 };
531 assert_ne!(k1, k2);
532 }
533
534 #[test]
535 fn cache_key_committing_local_cids_order_matters() {
536 let r = empty_relative_program();
542 let k1 = DecoderCacheKey {
543 relative_program: r.clone(),
544 error_model_fingerprints: vec![],
545 committing_local_cids: vec![0, 1, 2],
546 logical_flip_signature: vec![],
547 };
548 let k2 = DecoderCacheKey {
549 relative_program: r,
550 error_model_fingerprints: vec![],
551 committing_local_cids: vec![2, 1, 0],
552 logical_flip_signature: vec![],
553 };
554 assert_ne!(k1, k2);
555 }
556
557 #[test]
558 fn cache_key_equal_for_identical_inputs() {
559 let r = empty_relative_program();
560 let fp = fp_with_etype_digest(7);
561 let k1 = DecoderCacheKey {
562 relative_program: r.clone(),
563 error_model_fingerprints: vec![fp.clone()],
564 committing_local_cids: vec![0, 1],
565 logical_flip_signature: vec![],
566 };
567 let k2 = DecoderCacheKey {
568 relative_program: r,
569 error_model_fingerprints: vec![fp],
570 committing_local_cids: vec![0, 1],
571 logical_flip_signature: vec![],
572 };
573 assert_eq!(k1, k2);
574
575 let mut map: HashMap<DecoderCacheKey, &'static str> = HashMap::new();
576 map.insert(k1, "first");
577 assert_eq!(map.get(&k2), Some(&"first"));
578 }
579
580 #[test]
585 fn cache_key_distinguishes_fingerprint_position() {
586 let r = empty_relative_program();
587 let fp_a = fp_with_etype_digest(1);
588 let fp_b = fp_with_etype_digest(2);
589 let k1 = DecoderCacheKey {
590 relative_program: r.clone(),
591 error_model_fingerprints: vec![fp_a.clone(), fp_b.clone()],
592 committing_local_cids: vec![],
593 logical_flip_signature: vec![],
594 };
595 let k2 = DecoderCacheKey {
596 relative_program: r,
597 error_model_fingerprints: vec![fp_b, fp_a],
598 committing_local_cids: vec![],
599 logical_flip_signature: vec![],
600 };
601 assert_ne!(k1, k2);
602 }
603
604 #[test]
605 fn cache_key_distinguishes_logical_flip_signature() {
606 let r = empty_relative_program();
607 let k1 = DecoderCacheKey {
608 relative_program: r.clone(),
609 error_model_fingerprints: vec![],
610 committing_local_cids: vec![0],
611 logical_flip_signature: vec![1, 0, 0, 1],
612 };
613 let k2 = DecoderCacheKey {
614 relative_program: r,
615 error_model_fingerprints: vec![],
616 committing_local_cids: vec![0],
617 logical_flip_signature: vec![1, 0, 0, 3],
618 };
619 assert_ne!(k1, k2);
620 }
621}