//! Extracts the modular inverse from a completed GCD state.

use crate::u256::U256;

use super::GcdState;

impl GcdState {
    /// Returns the modular inverse if the GCD computation terminated
    /// successfully (i.e. `r0 == 1`), or `None` if the inverse does not
    /// exist.
    ///
    /// When `r0 == 1`, the Bézout coefficient `t0` holds the inverse up to
    /// sign. Since coefficients are tracked using wrapping 256-bit arithmetic
    /// (no modular reduction during the loop), the final sign correction
    /// depends on the cumulative swap parity `even`:
    ///
    /// - **even parity** (`even == true`): `t0` is the negated inverse, so
    ///   the result is `modulus + t0` (wrapping add recovers the positive
    ///   representative).
    /// - **odd parity** (`even == false`): `t0` is already the correct
    ///   inverse.
    ///
    /// # Examples
    ///
    /// ```
    /// use cnfy_uint::gcd_state::GcdState;
    /// use cnfy_uint::u256::U256;
    /// let P = U256::from_be_limbs([
    ///     0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF,
    ///     0xFFFFFFFFFFFFFFFF, 0xFFFFFFFEFFFFFC2F,
    /// ]);
    ///
    /// let mut state = GcdState::new(P, U256::from_be_limbs([0, 0, 0, 7]));
    /// // ... run Lehmer GCD loop to completion ...
    /// // state.inverse() returns Some(inv) where 7 * inv ≡ 1 (mod P)
    /// ```
    #[inline]
    pub fn inverse(&self) -> Option<U256> {
        if self.r0 != U256::ONE {
            return None;
        }

        Some(if self.even {
            self.modulus.overflowing_add(&self.t0).0
        } else {
            self.t0
        })
    }
}

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

    use super::*;

    /// Returns None when r0 != 1 (GCD not found).
    #[test]
    fn returns_none_when_incomplete() {
        let state = GcdState::new(
            U256::from_be_limbs([0, 0, 0, 97]),
            U256::from_be_limbs([0, 0, 0, 42]),
        );
        assert!(state.inverse().is_none());
    }

    /// Returns None when r0 == 0.
    #[test]
    fn returns_none_for_zero() {
        let state = GcdState {
            modulus: P,
            r0: U256::ZERO,
            r1: U256::ZERO,
            t0: U256::ZERO,
            t1: U256::ONE,
            even: true,
        };
        assert!(state.inverse().is_none());
    }

    /// Odd parity returns t0 directly.
    #[test]
    fn odd_parity_returns_t0() {
        let t0 = U256::from_be_limbs([0, 0, 0, 42]);
        let state = GcdState {
            modulus: P,
            r0: U256::ONE,
            r1: U256::ZERO,
            t0,
            t1: U256::ZERO,
            even: false,
        };
        assert_eq!(state.inverse().unwrap(), t0);
    }

    /// Even parity returns modulus + t0 (wrapping).
    #[test]
    fn even_parity_adds_modulus() {
        let t0 = U256::from_be_limbs([0, 0, 0, 5]);
        let state = GcdState {
            modulus: P,
            r0: U256::ONE,
            r1: U256::ZERO,
            t0,
            t1: U256::ZERO,
            even: true,
        };
        let expected = P.overflowing_add(&t0).0;
        assert_eq!(state.inverse().unwrap(), expected);
    }

    /// Works with the `?` operator for early return.
    #[test]
    fn question_mark_propagation() {
        fn try_inverse() -> Option<U256> {
            let state = GcdState {
                modulus: U256::from_be_limbs([0, 0, 0, 97]),
                r0: U256::from_be_limbs([0, 0, 0, 2]),
                r1: U256::ZERO,
                t0: U256::ZERO,
                t1: U256::ONE,
                even: true,
            };
            state.inverse()?;
            unreachable!()
        }
        assert!(try_inverse().is_none());
    }
}
