1use crate::bin;
16use crate::decoder::DynDecoder;
17use crate::decoder::blackbox_decoder;
18use crate::decoder::decoder_features::DecoderFeatures;
19use crate::misc::index::ErrorIndex;
20use crate::misc::util::{exclusive_probability_of, weight_of};
21use crate::util::BitVector;
22use serde::{Deserialize, Serialize};
23use std::ops::Index;
24use std::sync::Arc;
25use tonic::Status;
26
27pub(crate) async fn load_projected_decoder(
33 decoder: &DynDecoder,
34 projection: DecodeProjection,
35 prepared: PreparedDecoderInput,
36 retain_decoding_hypergraph: bool,
37 ignore_isolated_vertices: bool,
38) -> Result<LoadedDecoder, Status> {
39 let hypergraph = prepared.hypergraph;
40 let logical_flips = prepared.logical_flips;
41 let ignored_syndrome_vertices = if ignore_isolated_vertices {
42 Arc::new(edge_isolated_vertices(&hypergraph))
43 } else {
44 Arc::new(vec![])
45 };
46 let decoding_hypergraph = retain_decoding_hypergraph.then(|| Arc::new(hypergraph.clone()));
47 let edge_weights = Arc::new(hypergraph.hyperedges.iter().map(|edge| weight_of(edge.probability)).collect());
48 let hard_suppressed_edges = Arc::new(
49 hypergraph
50 .hyperedges
51 .iter()
52 .zip(logical_flips.iter())
53 .enumerate()
54 .filter(|(_, (hyperedge, flips))| requires_hard_decoding_suppression(hyperedge, flips))
55 .map(|(edge, _)| u64::try_from(edge).unwrap())
56 .collect(),
57 );
58 let hard_hypergraph = hard_decoding_hypergraph(hypergraph, &logical_flips);
59 let hid = decoder.load_hypergraph(hard_hypergraph).await?.hid;
60 Ok(LoadedDecoder {
61 hid,
62 decoding_hypergraph,
63 edge_weights,
64 hard_suppressed_edges,
65 logical_flips,
66 ignored_syndrome_vertices,
67 projection: Arc::new(projection),
68 })
69}
70
71pub(crate) fn hard_decoding_hypergraph(
75 mut hypergraph: blackbox_decoder::DecodingHypergraph,
76 logical_flips: &[Vec<u64>],
77) -> blackbox_decoder::DecodingHypergraph {
78 debug_assert_eq!(hypergraph.hyperedges.len(), logical_flips.len());
79 for (hyperedge, flips) in hypergraph.hyperedges.iter_mut().zip(logical_flips) {
80 if requires_hard_decoding_suppression(hyperedge, flips) {
81 hyperedge.probability = 0.0;
82 }
83 }
84 hypergraph
85}
86
87fn requires_hard_decoding_suppression(hyperedge: &blackbox_decoder::Hyperedge, logical_flips: &[u64]) -> bool {
88 hyperedge.observable_flips.is_none() && hyperedge.vertices.is_empty() && !logical_flips.is_empty()
89}
90
91pub(crate) fn prepare_decoder(
92 base_hypergraph: blackbox_decoder::DecodingHypergraph,
93 base_errors: Arc<Vec<ErrorIndex>>,
94 base_logical_flips: Vec<Vec<u64>>,
95 merge_hyperedges: bool,
96 merge_class: impl Fn(&ErrorIndex) -> usize,
97) -> (DecodeProjection, PreparedDecoderInput) {
98 debug_assert_eq!(base_hypergraph.hyperedges.len(), base_errors.len());
99 debug_assert_eq!(base_hypergraph.hyperedges.len(), base_logical_flips.len());
100 let error_edge_lookup = ErrorEdgeLookup::new(&base_errors);
101 let (prepared, edge_projection) = if merge_hyperedges {
102 deduplicate_by_syndrome(&base_hypergraph, &base_errors, &base_logical_flips, merge_class)
103 } else {
104 (
105 PreparedDecoderInput {
106 hypergraph: base_hypergraph.clone(),
107 representatives: Arc::clone(&base_errors),
108 logical_flips: Arc::new(base_logical_flips),
109 },
110 EdgeProjection::Identity,
111 )
112 };
113 (
114 DecodeProjection {
115 base_hypergraph,
116 base_errors,
117 decoder_errors: Arc::clone(&prepared.representatives),
118 error_edge_lookup,
119 edge_projection,
120 },
121 prepared,
122 )
123}
124
125fn edge_isolated_vertices(hypergraph: &blackbox_decoder::DecodingHypergraph) -> Vec<u64> {
126 let mut incident = vec![false; usize::try_from(hypergraph.vertex_num).unwrap()];
127 for hyperedge in &hypergraph.hyperedges {
128 for &vertex in &hyperedge.vertices {
129 incident[usize::try_from(vertex).unwrap()] = true;
130 }
131 }
132 incident
133 .into_iter()
134 .enumerate()
135 .filter_map(|(vertex, incident)| (!incident).then_some(u64::try_from(vertex).unwrap()))
136 .collect()
137}
138
139pub(crate) fn ignore_edge_isolated_history_vertices(
142 hypergraph: &blackbox_decoder::DecodingHypergraph,
143 syndrome: &mut BitVector,
144) {
145 for vertex in edge_isolated_vertices(hypergraph) {
146 crate::misc::bit_vector::set_bit(syndrome, vertex, false);
147 }
148}
149
150pub(crate) fn probability_reweights<'a>(
158 error_reference: &[ErrorIndex],
159 modifiers: impl IntoIterator<Item = (usize, &'a bin::ProbabilityModifier)>,
160) -> Vec<(u64, f64)> {
161 ErrorEdgeLookup::new(error_reference).project(modifiers)
162}
163
164#[derive(Debug)]
165pub(crate) struct ErrorEdgeLookup {
166 edges_by_eid: hashbrown::HashMap<usize, Vec<u64>>,
167}
168
169impl ErrorEdgeLookup {
170 const MISSING_EDGE: u64 = u64::MAX;
171
172 pub(crate) fn new(error_reference: &[ErrorIndex]) -> Self {
173 let mut edges_by_eid = hashbrown::HashMap::<usize, Vec<u64>>::new();
174 for (edge, error) in error_reference.iter().enumerate() {
175 let edges = edges_by_eid.entry(error.eid).or_default();
176 if edges.len() <= error.error_index {
177 edges.resize(error.error_index + 1, Self::MISSING_EDGE);
178 }
179 edges[error.error_index] = u64::try_from(edge).unwrap();
180 }
181 Self { edges_by_eid }
182 }
183
184 pub(crate) fn project<'a>(
185 &self,
186 modifiers: impl IntoIterator<Item = (usize, &'a bin::ProbabilityModifier)>,
187 ) -> Vec<(u64, f64)> {
188 let mut overrides = hashbrown::HashMap::new();
189 for (local_eid, modifier) in modifiers {
190 let Some(edges) = self.edges_by_eid.get(&local_eid) else {
191 continue;
192 };
193 for (error_index, &probability) in modifier.probabilities.iter().enumerate() {
194 if let Some(edge) = Self::edge(edges, error_index) {
195 overrides.insert(edge, probability);
196 }
197 }
198 for (&error_index, &probability) in modifier.sparse_indices.iter().zip(modifier.sparse_probabilities.iter()) {
199 if let Ok(error_index) = usize::try_from(error_index)
200 && let Some(edge) = Self::edge(edges, error_index)
201 {
202 overrides.insert(edge, probability);
203 }
204 }
205 }
206 let mut reweights: Vec<_> = overrides.into_iter().collect();
207 reweights.sort_unstable_by_key(|&(edge, _)| edge);
208 reweights
209 }
210
211 fn edge(edges: &[u64], error_index: usize) -> Option<u64> {
212 edges.get(error_index).copied().filter(|&edge| edge != Self::MISSING_EDGE)
213 }
214}
215
216pub(crate) fn apply_reweights(
218 hypergraph: &mut blackbox_decoder::DecodingHypergraph,
219 reweights: impl IntoIterator<Item = (u64, f64)>,
220) {
221 for (edge, probability) in reweights {
222 hypergraph.hyperedges[usize::try_from(edge).unwrap()].probability = probability;
223 }
224}
225
226#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, Serialize, Deserialize)]
228#[cfg_attr(feature = "cli", derive(structdoc::StructDoc))]
229#[serde(rename_all = "snake_case")]
230pub enum DecoderReweighting {
231 #[default]
234 Auto,
235 Enabled,
237 Disabled,
239}
240
241impl DecoderReweighting {
242 pub(crate) fn use_loaded(self, persistent_decoder: bool, features: DecoderFeatures) -> Result<bool, String> {
243 if !persistent_decoder {
244 return match self {
245 Self::Enabled => Err(
246 "decoder_reweighting is enabled but persistent_decoder is disabled; loaded reweights cannot be used"
247 .to_string(),
248 ),
249 Self::Auto | Self::Disabled => Ok(false),
250 };
251 }
252 match self {
253 Self::Auto => Ok(features.contains(DecoderFeatures::REWEIGHTS)),
254 Self::Enabled if features.contains(DecoderFeatures::REWEIGHTS) => Ok(true),
255 Self::Enabled => Err("decoder_reweighting is enabled but the decoder does not support reweights".to_string()),
256 Self::Disabled => Ok(false),
257 }
258 }
259}
260
261#[derive(Debug, Clone)]
263pub struct LoadedDecoder {
264 pub hid: u64,
266 pub decoding_hypergraph: Option<Arc<blackbox_decoder::DecodingHypergraph>>,
270 edge_weights: Arc<Vec<f64>>,
271 hard_suppressed_edges: Arc<Vec<u64>>,
274 pub(crate) logical_flips: Arc<Vec<Vec<u64>>>,
277 pub ignored_syndrome_vertices: Arc<Vec<u64>>,
281 pub projection: Arc<DecodeProjection>,
285}
286
287impl LoadedDecoder {
288 pub(crate) fn correction_weights(
289 &self,
290 correction: &blackbox_decoder::ParityFactor,
291 reweights: &[blackbox_decoder::EdgeReweight],
292 ) -> Vec<f64> {
293 let overrides: hashbrown::HashMap<_, _> = reweights
294 .iter()
295 .map(|reweight| (reweight.edge, reweight.probability))
296 .collect();
297 correction
298 .subgraph
299 .iter()
300 .map(|&edge| {
301 overrides.get(&edge).map_or_else(
302 || self.edge_weights[usize::try_from(edge).unwrap()],
303 |&probability| weight_of(probability),
304 )
305 })
306 .collect()
307 }
308
309 pub(crate) fn project_syndrome(&self, mut syndrome: BitVector) -> BitVector {
311 for &vertex in self.ignored_syndrome_vertices.iter() {
312 crate::misc::bit_vector::set_bit(&mut syndrome, vertex, false);
313 }
314 syndrome
315 }
316}
317
318pub(crate) fn correction_weights(
319 hypergraph: &blackbox_decoder::DecodingHypergraph,
320 correction: &blackbox_decoder::ParityFactor,
321) -> Vec<f64> {
322 correction
323 .subgraph
324 .iter()
325 .map(|&edge| weight_of(hypergraph.hyperedges[usize::try_from(edge).unwrap()].probability))
326 .collect()
327}
328
329pub(crate) async fn decode_projected(
333 decoder: &DynDecoder,
334 loaded: &LoadedDecoder,
335 syndrome: BitVector,
336 decoder_seed: Option<u64>,
337 reweights: Vec<blackbox_decoder::EdgeReweight>,
338 loss: Option<blackbox_decoder::LossInfo>,
339 use_loaded_reweights: bool,
340) -> Result<blackbox_decoder::ParityFactor, Status> {
341 let reweights: Vec<_> = reweights
342 .into_iter()
343 .filter(|reweight| loaded.hard_suppressed_edges.binary_search(&reweight.edge).is_err())
344 .collect();
345 if reweights.is_empty() || use_loaded_reweights {
346 return decoder
347 .decode_loaded(blackbox_decoder::LoadedDecodingProblem {
348 hid: loaded.hid,
349 syndrome: Some(syndrome),
350 reweights,
351 loss,
352 decoder_seed,
353 })
354 .await;
355 }
356
357 let hypergraph = (**loaded
360 .decoding_hypergraph
361 .as_ref()
362 .ok_or_else(|| Status::internal(format!("hid={} has no materializable hypergraph", loaded.hid)))?)
363 .clone();
364 let mut hypergraph = hard_decoding_hypergraph(hypergraph, &loaded.logical_flips);
365 for reweight in reweights {
366 let hyperedge = usize::try_from(reweight.edge)
367 .ok()
368 .and_then(|edge| hypergraph.hyperedges.get_mut(edge))
369 .ok_or_else(|| {
370 Status::invalid_argument(format!(
371 "reweighted edge {} is outside loaded hypergraph hid={}",
372 reweight.edge, loaded.hid
373 ))
374 })?;
375 hyperedge.probability = reweight.probability;
376 }
377 decoder
378 .decode(blackbox_decoder::DecodingProblem {
379 hypergraph: Some(hypergraph),
380 syndrome: Some(syndrome),
381 loss,
382 decoder_seed,
383 })
384 .await
385}
386
387#[derive(Debug)]
395pub struct DecodeProjection {
396 pub base_hypergraph: blackbox_decoder::DecodingHypergraph,
399 pub base_errors: Arc<Vec<ErrorIndex>>,
401 decoder_errors: Arc<Vec<ErrorIndex>>,
403 error_edge_lookup: ErrorEdgeLookup,
405 edge_projection: EdgeProjection,
407}
408
409#[derive(Debug, Clone)]
411pub(crate) struct ProjectedErrors {
412 baseline: Arc<Vec<ErrorIndex>>,
413 replacements: Vec<(usize, ErrorIndex)>,
414}
415
416impl ProjectedErrors {
417 pub(crate) fn shared(baseline: Arc<Vec<ErrorIndex>>) -> Self {
418 Self {
419 baseline,
420 replacements: vec![],
421 }
422 }
423
424 pub(crate) fn len(&self) -> usize {
425 self.baseline.len()
426 }
427}
428
429impl Index<usize> for ProjectedErrors {
430 type Output = ErrorIndex;
431
432 fn index(&self, index: usize) -> &Self::Output {
433 match self
434 .replacements
435 .binary_search_by_key(&index, |&(decoder_edge, _)| decoder_edge)
436 {
437 Ok(position) => &self.replacements[position].1,
438 Err(_) => &self.baseline[index],
439 }
440 }
441}
442
443impl From<Arc<Vec<ErrorIndex>>> for ProjectedErrors {
444 fn from(baseline: Arc<Vec<ErrorIndex>>) -> Self {
445 Self::shared(baseline)
446 }
447}
448
449#[derive(Debug)]
455pub(crate) struct PreparedDecoderInput {
456 pub(crate) hypergraph: blackbox_decoder::DecodingHypergraph,
457 pub(crate) representatives: Arc<Vec<ErrorIndex>>,
458 pub(crate) logical_flips: Arc<Vec<Vec<u64>>>,
459}
460
461#[derive(Debug)]
464enum EdgeProjection {
465 Identity,
466 Merged {
467 decoder_edge_of_original: Vec<usize>,
468 original_edges_of_decoder: Vec<Vec<usize>>,
469 },
470}
471
472fn deduplicate_by_syndrome(
476 hypergraph: &blackbox_decoder::DecodingHypergraph,
477 errors: &[ErrorIndex],
478 logical_flips: &[Vec<u64>],
479 merge_class: impl Fn(&ErrorIndex) -> usize,
480) -> (PreparedDecoderInput, EdgeProjection) {
481 debug_assert_eq!(hypergraph.hyperedges.len(), logical_flips.len());
482 let mut seen: hashbrown::HashMap<_, (usize, f64)> = hashbrown::HashMap::with_capacity(errors.len());
483 let mut hyperedges: Vec<blackbox_decoder::Hyperedge> = Vec::with_capacity(errors.len());
484 let mut prepared_logical_flips = Vec::with_capacity(errors.len());
485 let mut representatives = Vec::with_capacity(errors.len());
486 let mut decoder_edge_of_original = Vec::with_capacity(errors.len());
487 let mut original_edges_of_decoder: Vec<Vec<usize>> = Vec::with_capacity(errors.len());
488 for (position, ((hyperedge, error), flips)) in hypergraph.hyperedges.iter().zip(errors).zip(logical_flips).enumerate() {
489 let mut syndrome = hyperedge.vertices.clone();
490 syndrome.sort_unstable();
491 debug_assert!({
492 let degree = syndrome.len();
493 syndrome.dedup();
494 syndrome.len() == degree
495 });
496 let mut flips = flips.clone();
497 flips.sort_unstable();
498 flips.dedup();
499 let observable_flips = hyperedge.observable_flips.as_ref().map(|effects| {
500 let mut indices = effects.indices.clone();
501 indices.sort_unstable();
502 indices
503 });
504 let key = (syndrome.clone(), flips.clone(), observable_flips.clone(), merge_class(error));
505 if let Some((index, best_probability)) = seen.get_mut(&key) {
506 let combined = hyperedges[*index].probability;
507 hyperedges[*index].probability = exclusive_probability_of(combined, hyperedge.probability);
508 if hyperedge.probability > *best_probability {
509 *best_probability = hyperedge.probability;
510 representatives[*index] = error.clone();
511 }
512 original_edges_of_decoder[*index].push(position);
513 decoder_edge_of_original.push(*index);
514 } else {
515 let index = representatives.len();
516 hyperedges.push(blackbox_decoder::Hyperedge {
517 probability: hyperedge.probability,
518 vertices: syndrome.clone(),
519 observable_flips: observable_flips.map(|indices| blackbox_decoder::ObservableFlips { indices }),
520 });
521 prepared_logical_flips.push(flips);
522 representatives.push(error.clone());
523 original_edges_of_decoder.push(vec![position]);
524 decoder_edge_of_original.push(index);
525 seen.insert(key, (index, hyperedge.probability));
526 }
527 }
528 (
529 PreparedDecoderInput {
530 hypergraph: blackbox_decoder::DecodingHypergraph {
531 vertex_num: hypergraph.vertex_num,
532 hyperedges,
533 },
534 representatives: Arc::new(representatives),
535 logical_flips: Arc::new(prepared_logical_flips),
536 },
537 EdgeProjection::Merged {
538 decoder_edge_of_original,
539 original_edges_of_decoder,
540 },
541 )
542}
543
544pub(crate) fn deduplicate_decoder_input(
546 hypergraph: &blackbox_decoder::DecodingHypergraph,
547 errors: &[ErrorIndex],
548 logical_flips: &[Vec<u64>],
549 merge_class: impl Fn(&ErrorIndex) -> usize,
550) -> PreparedDecoderInput {
551 deduplicate_by_syndrome(hypergraph, errors, logical_flips, merge_class).0
552}
553
554impl DecodeProjection {
555 #[cfg(test)]
556 pub(crate) fn identity(
557 base_hypergraph: blackbox_decoder::DecodingHypergraph,
558 base_errors: Arc<Vec<ErrorIndex>>,
559 ) -> Self {
560 Self {
561 base_hypergraph,
562 decoder_errors: Arc::clone(&base_errors),
563 error_edge_lookup: ErrorEdgeLookup::new(&base_errors),
564 base_errors,
565 edge_projection: EdgeProjection::Identity,
566 }
567 }
568
569 pub(crate) fn probability_reweights<'a>(
570 &self,
571 modifiers: impl IntoIterator<Item = (usize, &'a bin::ProbabilityModifier)>,
572 ) -> Vec<(u64, f64)> {
573 self.error_edge_lookup.project(modifiers)
574 }
575
576 pub(crate) fn project_reweights(&self, reweights: &[(u64, f64)]) -> (Vec<(u64, f64)>, ProjectedErrors) {
579 self.edge_projection
580 .project_reweights(&self.base_hypergraph, &self.base_errors, &self.decoder_errors, reweights)
581 }
582}
583
584impl EdgeProjection {
585 fn project_reweights(
586 &self,
587 base_hypergraph: &blackbox_decoder::DecodingHypergraph,
588 base_errors: &[ErrorIndex],
589 decoder_errors: &Arc<Vec<ErrorIndex>>,
590 reweights: &[(u64, f64)],
591 ) -> (Vec<(u64, f64)>, ProjectedErrors) {
592 match self {
593 Self::Identity => {
594 let mut overrides = hashbrown::HashMap::with_capacity(reweights.len());
595 for &(edge, probability) in reweights {
596 overrides.insert(edge, probability);
597 }
598 let mut translated: Vec<_> = overrides.into_iter().collect();
599 translated.sort_unstable_by_key(|&(edge, _)| edge);
600 (translated, ProjectedErrors::shared(Arc::clone(decoder_errors)))
601 }
602 Self::Merged {
603 decoder_edge_of_original,
604 original_edges_of_decoder,
605 } => {
606 let mut overrides = hashbrown::HashMap::with_capacity(reweights.len());
607 let mut reweighted_decoder_edges = Vec::with_capacity(reweights.len());
608 for &(edge, probability) in reweights {
609 let original = usize::try_from(edge).unwrap();
610 overrides.insert(original, probability);
611 reweighted_decoder_edges.push(decoder_edge_of_original[original]);
612 }
613 reweighted_decoder_edges.sort_unstable();
614 reweighted_decoder_edges.dedup();
615 if reweighted_decoder_edges.is_empty() {
616 return (vec![], ProjectedErrors::shared(Arc::clone(decoder_errors)));
617 }
618 let mut replacements = Vec::with_capacity(reweighted_decoder_edges.len());
619 let translated = reweighted_decoder_edges
620 .into_iter()
621 .map(|decoder_edge| {
622 let mut combined = 0.0;
623 let mut elected = None;
624 for &original_edge in &original_edges_of_decoder[decoder_edge] {
625 let probability = overrides
626 .get(&original_edge)
627 .copied()
628 .unwrap_or(base_hypergraph.hyperedges[original_edge].probability);
629 combined = exclusive_probability_of(combined, probability);
630 let should_elect = match elected {
631 None => true,
632 Some((_, elected_probability)) => probability > elected_probability,
633 };
634 if should_elect {
635 elected = Some((original_edge, probability));
636 }
637 }
638 let (elected_original, _) = elected.expect("decoder edge must contain an original edge");
639 if decoder_errors[decoder_edge] != base_errors[elected_original] {
640 replacements.push((decoder_edge, base_errors[elected_original].clone()));
641 }
642 (u64::try_from(decoder_edge).unwrap(), combined)
643 })
644 .collect();
645 (
646 translated,
647 ProjectedErrors {
648 baseline: Arc::clone(decoder_errors),
649 replacements,
650 },
651 )
652 }
653 }
654 }
655}
656
657#[cfg(test)]
658#[path = "../../tests/unit/reweight_handler_test.rs"]
659mod tests;