//! Computes the shift needed to extract aligned top 64 bits from `r0`.

use super::GcdState;

impl GcdState {
    /// Returns the bit shift needed to extract aligned top 64 bits from `r0`.
    ///
    /// The Lehmer algorithm operates on 63-bit approximations of the
    /// full-precision remainders. This method computes how many bits to
    /// right-shift `r0` (and `r1` at the same offset) so that the extracted
    /// value uses exactly 63 significant bits.
    ///
    /// Returns `0` when `r0` fits in 64 bits, meaning the low limb can be
    /// used directly without shifting.
    #[inline]
    pub fn top_bits_shift(&self) -> u32 {
        let bits = self.r0.bit_len();
        match bits <= 64 {
            true => 0,
            false => bits - 63,
        }
    }
}

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

    use super::*;

    /// Small r0 that fits in 64 bits returns shift of 0.
    #[test]
    fn small_r0() {
        let state = GcdState::new(
            U256::from_be_limbs([0, 0, 0, 100]),
            U256::from_be_limbs([0, 0, 0, 37]),
        );
        assert_eq!(state.top_bits_shift(), 0);
    }

    /// r0 with exactly 64 bits returns shift of 0.
    #[test]
    fn exactly_64_bits() {
        let state = GcdState::new(U256::from_be_limbs([0, 0, 0, u64::MAX]), U256::ONE);
        assert_eq!(state.top_bits_shift(), 0);
    }

    /// r0 with 65 bits returns shift of 2.
    #[test]
    fn just_over_64_bits() {
        let state = GcdState::new(U256::from_be_limbs([0, 0, 1, 0]), U256::ONE);
        // bit_len = 65, shift = 65 - 63 = 2
        assert_eq!(state.top_bits_shift(), 2);
    }

    /// r0 with 128 bits returns shift of 65.
    #[test]
    fn two_limbs() {
        let state = GcdState::new(U256::from_be_limbs([0, 0, u64::MAX, 0]), U256::ONE);
        // bit_len = 128, shift = 128 - 63 = 65
        assert_eq!(state.top_bits_shift(), 65);
    }

    /// Full 256-bit r0 returns shift of 193.
    #[test]
    fn full_256_bits() {
        let state = GcdState::new(U256::MAX, U256::ONE);
        // bit_len = 256, shift = 256 - 63 = 193
        assert_eq!(state.top_bits_shift(), 193);
    }

    /// secp256k1 prime (256 bits) returns shift of 193.
    #[test]
    fn secp256k1_prime() {
        const P: U256 = U256::from_be_limbs([0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFEFFFFFC2F]);
        let state = GcdState::new(P, U256::ONE);
        assert_eq!(state.top_bits_shift(), 193);
    }
}
