faultscope-core 0.2.12

Python-independent circuit, DEM, sampling, and decoder primitives for FaultScope
Documentation
use crate::Mask;
use smallvec::{smallvec, SmallVec};

#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub struct Expr {
    terms: SmallVec<[usize; 4]>,
    constant: bool,
}

impl Expr {
    pub fn constant(value: bool) -> Self {
        Self {
            terms: SmallVec::new(),
            constant: value,
        }
    }

    pub fn random(source: usize) -> Self {
        Self {
            terms: smallvec![source],
            constant: false,
        }
    }

    pub fn terms(&self) -> &[usize] {
        &self.terms
    }

    pub fn constant_value(&self) -> bool {
        self.constant
    }

    pub fn xor_assign(&mut self, other: &Expr) {
        self.constant ^= other.constant;
        if other.terms.is_empty() {
            return;
        }
        if self.terms.is_empty() {
            self.terms.clone_from(&other.terms);
            return;
        }
        if self.terms.len() + other.terms.len() <= 4 {
            for term in other.terms.iter().copied() {
                self.toggle_term(term);
            }
            return;
        }
        let left = std::mem::take(&mut self.terms);
        let mut out = SmallVec::with_capacity(left.len() + other.terms.len());
        let mut left_idx = 0;
        let mut right_idx = 0;
        while left_idx < left.len() && right_idx < other.terms.len() {
            match left[left_idx].cmp(&other.terms[right_idx]) {
                std::cmp::Ordering::Less => {
                    out.push(left[left_idx]);
                    left_idx += 1;
                }
                std::cmp::Ordering::Greater => {
                    out.push(other.terms[right_idx]);
                    right_idx += 1;
                }
                std::cmp::Ordering::Equal => {
                    left_idx += 1;
                    right_idx += 1;
                }
            }
        }
        out.extend_from_slice(&left[left_idx..]);
        out.extend_from_slice(&other.terms[right_idx..]);
        self.terms = out;
    }

    pub(crate) fn toggle_term(&mut self, term: usize) {
        match self.terms.binary_search(&term) {
            Ok(index) => {
                self.terms.remove(index);
            }
            Err(index) => self.terms.insert(index, term),
        }
    }

    pub fn toggle_constant(&mut self) {
        self.constant ^= true;
    }

    pub fn eval(&self, random_masks: &[Mask], words: usize, all_mask: &Mask) -> Mask {
        let mut out = Mask::zero(words);
        if self.constant {
            out.xor_assign(all_mask);
        }
        for source in &self.terms {
            out.xor_assign(&random_masks[*source]);
        }
        out
    }

    pub(crate) fn eval_flat(&self, random_masks: &[u64], words: usize, all_mask: &Mask) -> Mask {
        let mut out = Mask::zero(words);
        if self.constant {
            out.xor_assign(all_mask);
        }
        for source in &self.terms {
            let start = source * words;
            for (target, random) in out
                .words
                .iter_mut()
                .zip(&random_masks[start..start + words])
            {
                *target ^= random;
            }
        }
        out
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn xor_assign_cancels_duplicate_terms() {
        let mut expr = Expr::random(2);
        expr.xor_assign(&Expr::random(1));
        expr.xor_assign(&Expr::random(2));

        assert_eq!(expr.terms(), &[1]);
        assert!(!expr.constant_value());
    }

    #[test]
    fn xor_assign_merges_sorted_terms_by_symmetric_difference() {
        let mut left = Expr {
            terms: vec![1, 3, 5, 8].into(),
            constant: true,
        };
        let right = Expr {
            terms: vec![0, 3, 4, 8, 9].into(),
            constant: true,
        };

        left.xor_assign(&right);

        assert_eq!(left.terms(), &[0, 1, 4, 5, 9]);
        assert!(!left.constant_value());
    }

    #[test]
    fn xor_assign_matches_randomized_symmetric_differences() {
        let mut state = 0x9e37_79b9_7f4a_7c15u64;
        for _ in 0..128 {
            let mut left_terms = Vec::new();
            let mut right_terms = Vec::new();
            let mut expected = Vec::new();
            for term in 0..96 {
                state = state
                    .wrapping_mul(6_364_136_223_846_793_005)
                    .wrapping_add(1);
                let in_left = state >> 63 != 0;
                state = state
                    .wrapping_mul(6_364_136_223_846_793_005)
                    .wrapping_add(1);
                let in_right = state >> 63 != 0;
                if in_left {
                    left_terms.push(term);
                }
                if in_right {
                    right_terms.push(term);
                }
                if in_left ^ in_right {
                    expected.push(term);
                }
            }
            let mut left = Expr {
                terms: left_terms.into(),
                constant: false,
            };
            left.xor_assign(&Expr {
                terms: right_terms.into(),
                constant: true,
            });
            assert_eq!(left.terms(), expected);
            assert!(left.constant_value());
        }
    }

    #[test]
    fn eval_includes_constant_mask() {
        let expr = Expr::constant(true);
        let all = Mask { words: vec![0b101] };

        assert_eq!(expr.eval(&[], 1, &all), all);
    }
}