rstim 0.4.0

Stim-aligned stabilizer circuit simulator and detector error model toolkit
Documentation
use rand::RngCore;
#[cfg(any(debug_assertions, feature = "benchmark-telemetry"))]
use std::cell::Cell;

const F64_UNIT_INTERVAL_SCALE: f64 = 1.0 / ((1u64 << 53) as f64);

#[cfg(any(debug_assertions, feature = "benchmark-telemetry"))]
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct RareErrorTelemetry {
    pub iterator_builds: usize,
    pub rng_core_draws: usize,
}

#[cfg(any(debug_assertions, feature = "benchmark-telemetry"))]
thread_local! {
    static ITERATOR_BUILDS: Cell<usize> = const { Cell::new(0) };
    static RNG_CORE_DRAWS: Cell<usize> = const { Cell::new(0) };
}

#[cfg(any(debug_assertions, feature = "benchmark-telemetry"))]
#[doc(hidden)]
pub fn reset_rare_error_telemetry() {
    ITERATOR_BUILDS.with(|builds| builds.set(0));
    RNG_CORE_DRAWS.with(|draws| draws.set(0));
}

#[cfg(any(debug_assertions, feature = "benchmark-telemetry"))]
#[doc(hidden)]
pub fn rare_error_telemetry() -> RareErrorTelemetry {
    RareErrorTelemetry {
        iterator_builds: ITERATOR_BUILDS.with(Cell::get),
        rng_core_draws: RNG_CORE_DRAWS.with(Cell::get),
    }
}

#[cfg(any(debug_assertions, feature = "benchmark-telemetry"))]
fn record_iterator_build() {
    ITERATOR_BUILDS.with(|builds| builds.set(builds.get().saturating_add(1)));
}

#[cfg(any(debug_assertions, feature = "benchmark-telemetry"))]
fn record_rng_core_draw() {
    RNG_CORE_DRAWS.with(|draws| draws.set(draws.get().saturating_add(1)));
}

#[derive(Debug, Clone, Copy)]
enum RareErrorMode {
    Empty,
    Dense,
    Sparse { log_one_minus_p: f64 },
}

pub(crate) struct RareErrorIndexSampler {
    attempt_count: usize,
    next_candidate: usize,
    mode: RareErrorMode,
}

impl RareErrorIndexSampler {
    pub(crate) fn new(probability: f64, attempt_count: usize) -> Self {
        #[cfg(any(debug_assertions, feature = "benchmark-telemetry"))]
        record_iterator_build();

        let mode = if attempt_count == 0 || probability <= 0.0 || probability.is_nan() {
            RareErrorMode::Empty
        } else if probability >= 1.0 {
            RareErrorMode::Dense
        } else {
            RareErrorMode::Sparse {
                log_one_minus_p: (-probability).ln_1p(),
            }
        };

        Self {
            attempt_count,
            next_candidate: 0,
            mode,
        }
    }

    pub(crate) fn next_index<R: RngCore + ?Sized>(&mut self, rng: &mut R) -> Option<usize> {
        match self.mode {
            RareErrorMode::Empty => None,
            RareErrorMode::Dense => {
                if self.next_candidate >= self.attempt_count {
                    return None;
                }
                let index = self.next_candidate;
                self.next_candidate += 1;
                Some(index)
            }
            RareErrorMode::Sparse { log_one_minus_p } => {
                while self.next_candidate < self.attempt_count {
                    let uniform = draw_open_unit_f64(rng);
                    let skip = (uniform.ln() / log_one_minus_p).floor();
                    let skip = if skip.is_finite() && skip >= 0.0 {
                        skip as usize
                    } else {
                        usize::MAX
                    };
                    let index = self.next_candidate.saturating_add(skip);
                    if index >= self.attempt_count {
                        self.next_candidate = self.attempt_count;
                        return None;
                    }
                    self.next_candidate = index + 1;
                    return Some(index);
                }
                None
            }
        }
    }
}

pub struct RareErrorIterator<'a, R: RngCore + ?Sized> {
    rng: &'a mut R,
    sampler: RareErrorIndexSampler,
}

pub fn rare_error_indices<'a, R: RngCore + ?Sized>(
    probability: f64,
    attempt_count: usize,
    rng: &'a mut R,
) -> RareErrorIterator<'a, R> {
    RareErrorIterator::new(probability, attempt_count, rng)
}

impl<'a, R: RngCore + ?Sized> RareErrorIterator<'a, R> {
    pub fn new(probability: f64, attempt_count: usize, rng: &'a mut R) -> Self {
        Self {
            rng,
            sampler: RareErrorIndexSampler::new(probability, attempt_count),
        }
    }
}

impl<R: RngCore + ?Sized> Iterator for RareErrorIterator<'_, R> {
    type Item = usize;

    fn next(&mut self) -> Option<Self::Item> {
        self.sampler.next_index(self.rng)
    }
}

fn draw_open_unit_f64<R: RngCore + ?Sized>(rng: &mut R) -> f64 {
    loop {
        #[cfg(any(debug_assertions, feature = "benchmark-telemetry"))]
        record_rng_core_draw();
        let raw = rng.next_u64();
        let value = ((raw >> 11) as f64) * F64_UNIT_INTERVAL_SCALE;
        if value > 0.0 {
            return value;
        }
    }
}