cnfy-uint 0.2.3

//! Single macroiteration (62 divsteps) for [`Divstep`].
use super::Divstep;
use crate::divstep_matrix::DivstepMatrix;

impl Divstep {
    /// Performs one macroiteration: 62 divsteps on the low 62 bits of `f`
    /// and `g`, building a 2×2 transition matrix, then applying it to the
    /// full-width `(f, g)` and Bézout `(d, e)` pairs.
    ///
    /// This is the core loop body. The low-bit divsteps produce a compact
    /// `i64` matrix that captures all 62 transitions. Applying it to the
    /// full-width values is a single matrix-vector multiply + shift.
    pub(crate) fn macrostep(&mut self) {
        // Extract low 62 bits of f and g as signed i64
        let mut f0 = self.extract_low62_signed(&self.f, self.f_neg);
        let mut g0 = self.extract_low62_signed(&self.g, self.g_neg);

        // Run 62 divsteps on the low bits, building the transition matrix
        let mut matrix = DivstepMatrix::identity();
        for _ in 0..62 {
            self.delta = matrix.step(self.delta, &mut f0, &mut g0);
        }

        // Apply the matrix to full-width (f, g)
        let (new_f, new_f_neg, new_g, new_g_neg) =
            matrix.apply_fg(&self.f, self.f_neg, &self.g, self.g_neg);
        self.f = new_f;
        self.f_neg = new_f_neg;
        self.g = new_g;
        self.g_neg = new_g_neg;

        // Apply the matrix to Bézout coefficients (d, e) with modular reduction
        let (new_d, new_e) = matrix.apply_de(&self.d, &self.e, &self.modulus);
        self.d = new_d;
        self.e = new_e;
    }

    /// Extracts the low 62 bits of a signed value as `i64`.
    ///
    /// Takes the low 62 bits of the magnitude and applies the sign. The
    /// result fits in i64 since 62 bits + sign = 63 bits < 64 bits.
    fn extract_low62_signed(&self, val: &crate::u256::U256, neg: bool) -> i64 {
        let low62 = (val.0[0] & ((1u64 << 62) - 1)) as i64;
        if neg { -low62 } else { low62 }
    }
}

#[cfg(test)]
mod ai_tests {
    use super::*;
    use crate::u256::U256;

    const P: U256 = U256::from_be_limbs([
        0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF,
        0xFFFFFFFFFFFFFFFF, 0xFFFFFFFEFFFFFC2F,
    ]);

    /// One macrostep does not panic and preserves the f/g bit-width.
    #[test]
    fn one_macrostep_no_panic() {
        let mut ds = Divstep::new(P, U256::from_be_limbs([0, 0, 0, 7]));
        ds.macrostep();
        // After one macrostep, g should be smaller (62 bits shifted out)
        // No specific value check — just verify no panic
    }

    /// After one macrostep, d and e are still in [0, modulus).
    #[test]
    fn bezout_coefficients_reduced() {
        let mut ds = Divstep::new(P, U256::from_be_limbs([0, 0, 0, 7]));
        ds.macrostep();
        assert!(ds.d < P);
        assert!(ds.e < P);
    }
}