//! Single iteration of the Lehmer extended GCD algorithm.

use super::GcdState;

impl GcdState {
    /// Performs one iteration of the Lehmer extended GCD algorithm,
    /// returning the updated state.
    ///
    /// Delegates to [`lehmer`](Self::lehmer) to decide the reduction
    /// strategy (full-precision, scalar, or Lehmer matrix). When a
    /// non-trivial Lehmer matrix is produced, applies it to both the
    /// remainder pair `(r0, r1)` and the coefficient pair `(t0, t1)`,
    /// and merges the Lehmer parity into the cumulative swap parity.
    ///
    /// After applying a Lehmer matrix, the remainder pair may be
    /// misordered (`r0 < r1`) on rare edge cases where the 63-bit
    /// approximation slightly diverges from the full-precision values
    /// at the last accumulated step. When this occurs, the remainders
    /// and coefficients are swapped and the parity is toggled.
    ///
    /// Takes `self` by value and returns the advanced state, so the
    /// caller sees a pure reassignment with no mutable aliasing.
    #[inline]
    pub fn step(mut self) -> Self {
        if let Some(lehmer) = self.lehmer() {
            (self.r0, self.r1) = lehmer.apply(self.r0, self.r1);
            (self.t0, self.t1) = lehmer.apply(self.t0, self.t1);
            self.even = self.even == lehmer.even;

            if self.r0 < self.r1 {
                core::mem::swap(&mut self.r0, &mut self.r1);
                core::mem::swap(&mut self.t0, &mut self.t1);
                self.even = !self.even;
            }
        }
        self
    }
}

#[cfg(test)]
mod ai_tests {
    use crate::u256::U256;
    const P: U256 = U256::from_be_limbs([0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFEFFFFFC2F]);

    use super::*;

    /// Step advances the state toward completion.
    #[test]
    fn advances_state() {
        let state = GcdState::new(P, U256::from_be_limbs([0, 0, 0, 7]));
        let next = state.step();
        assert_ne!(next.r0, state.r0);
    }

    /// Repeated steps eventually reach r1 == 0.
    #[test]
    fn reaches_termination() {
        let mut state = GcdState::new(P, U256::from_be_limbs([0, 0, 0, 7]));
        while !state.r1.is_zero() {
            state = state.step();
        }
        assert_eq!(state.r0, U256::ONE);
    }

    /// Full GCD via step loop produces correct inverse.
    #[test]
    fn correct_inverse_via_step() {
        let value = U256::from_be_limbs([0, 0, 0, 42]);
        let mut state = GcdState::new(P, value);
        while !state.r1.is_zero() {
            state = state.step();
        }
        let inv = state.inverse().unwrap();
        assert_eq!(value.mul_mod(&inv, &P), U256::ONE);
    }

    /// Original state is not modified (value semantics).
    #[test]
    fn value_semantics() {
        let state = GcdState::new(P, U256::from_be_limbs([0, 0, 0, 7]));
        let original = state;
        let _ = state.step();
        assert_eq!(state, original);
    }
}
