//! Extracts aligned top 64-bit approximations from the remainder pair.

use super::GcdState;

impl GcdState {
    /// Extracts aligned top-bit approximations from `r0` and `r1`.
    ///
    /// Computes the shift via [`top_bits_shift`](Self::top_bits_shift) and
    /// extracts 64 bits from both remainders at the same offset, so that
    /// `a` uses 63 significant bits and `b` is aligned to the same scale.
    ///
    /// When `r0` fits in 64 bits the low limbs are returned directly.
    /// Returns `(a, 0)` when `r1` is too small relative to `r0` for any
    /// Lehmer step.
    #[inline]
    pub fn extract_top_bits(&self) -> (u64, u64) {
        let shift = self.top_bits_shift();
        let a = self.r0.extract_u64(shift);
        let b = self.r1.extract_u64(shift);
        (a, b)
    }
}

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

    use super::*;

    /// Small values return low limbs directly.
    #[test]
    fn small_values() {
        let state = GcdState::new(
            U256::from_be_limbs([0, 0, 0, 100]),
            U256::from_be_limbs([0, 0, 0, 37]),
        );
        let (a, b) = state.extract_top_bits();
        assert_eq!(a, 100);
        assert_eq!(b, 37);
    }

    /// When r1 is zero, b is zero.
    #[test]
    fn r1_zero() {
        let state = GcdState::new(U256::from_be_limbs([0, 0, 0, 42]), U256::ZERO);
        let (a, b) = state.extract_top_bits();
        assert_eq!(a, 42);
        assert_eq!(b, 0);
    }

    /// Large 256-bit values extract 63-bit approximations.
    #[test]
    fn large_values() {
        let state = GcdState::new(
            U256::from_be_limbs([u64::MAX, 0, 0, 0]),
            U256::from_be_limbs([u64::MAX >> 1, 0, 0, 0]),
        );
        let (a, b) = state.extract_top_bits();
        // a should use 63 bits (top bit is bit 62)
        assert!(a < (1u64 << 63));
        assert!(a >= (1u64 << 62));
        // b should be roughly half of a
        assert!(b < a);
        assert!(b > 0);
    }

    /// Both values in the same limb range extract correctly.
    #[test]
    fn two_limb_values() {
        let state = GcdState::new(
            U256::from_be_limbs([0, 0, 3, 0]),
            U256::from_be_limbs([0, 0, 2, 0]),
        );
        // bit_len(r0) = 66, shift = 66 - 63 = 3
        let (a, b) = state.extract_top_bits();
        // a = 3 << 64 >> 3 = 3 << 61 ... actually extract_u64(3) from [0,0,3,0]
        // limb index = 3/64 = 0, bit = 3%64 = 3
        // lo = limbs[3-0] = limbs[3] = 0, hi = limbs[2] = 3
        // result = (0 >> 3) | (3 << 61)
        assert_eq!(a, 3 << 61);
        assert_eq!(b, 2 << 61);
    }

    /// secp256k1 prime extracts a 63-bit approximation.
    #[test]
    fn secp256k1_prime() {
        const P: U256 = U256::from_be_limbs([0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFEFFFFFC2F]);
        let state = GcdState::new(P, U256::ONE);
        let (a, b) = state.extract_top_bits();
        // P is 256 bits, shift = 193. a should be 63 significant bits.
        assert!(a >= (1u64 << 62));
        assert!(a < (1u64 << 63));
        // r1 = 1, much smaller than r0, so b ≈ 0 after shift
        assert_eq!(b, 0);
    }
}
