//! Runs the Lehmer extended GCD algorithm to completion.

use super::GcdState;

impl GcdState {
    /// Runs the Lehmer extended GCD algorithm until `r1` reaches zero,
    /// returning the terminal state.
    ///
    /// Repeatedly calls [`step`](Self::step) to advance the remainder
    /// and coefficient pairs. At termination, `r0` holds the GCD and
    /// `t0` holds the Bézout coefficient (up to sign). The caller
    /// typically follows with [`inverse`](Self::inverse) to extract the
    /// modular inverse.
    ///
    /// # Examples
    ///
    /// ```
    /// use cnfy_uint::gcd_state::GcdState;
    /// use cnfy_uint::u256::U256;
    /// let P = U256::from_be_limbs([
    ///     0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF,
    ///     0xFFFFFFFFFFFFFFFF, 0xFFFFFFFEFFFFFC2F,
    /// ]);
    ///
    /// let inv = GcdState::new(P, U256::from_be_limbs([0, 0, 0, 7]))
    ///     .run()
    ///     .inverse()
    ///     .unwrap();
    /// assert_eq!(U256::from_be_limbs([0, 0, 0, 7]).mul_mod(&inv, &P), U256::ONE);
    /// ```
    #[inline]
    pub fn run(mut self) -> Self {
        while !self.r1.is_zero() {
            self = self.step();
        }
        self
    }
}

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

    use super::*;

    /// Run terminates with r1 == 0.
    #[test]
    fn terminates() {
        let state = GcdState::new(P, U256::from_be_limbs([0, 0, 0, 7])).run();
        assert!(state.r1.is_zero());
    }

    /// Run finds GCD == 1 for coprime inputs.
    #[test]
    fn gcd_is_one() {
        let state = GcdState::new(P, U256::from_be_limbs([0, 0, 0, 42])).run();
        assert_eq!(state.r0, U256::ONE);
    }

    /// Run followed by inverse produces correct result.
    #[test]
    fn run_then_inverse() {
        let value = U256::from_be_limbs([0, 0, 0, 13]);
        let inv = GcdState::new(P, value).run().inverse().unwrap();
        assert_eq!(value.mul_mod(&inv, &P), U256::ONE);
    }

    /// Non-coprime inputs yield GCD != 1.
    #[test]
    fn non_coprime() {
        let state = GcdState::new(
            U256::from_be_limbs([0, 0, 0, 12]),
            U256::from_be_limbs([0, 0, 0, 8]),
        )
        .run();
        assert_eq!(state.r0, U256::from_be_limbs([0, 0, 0, 4]));
    }
}
