//! Morton undilation extracting even bit positions from a [`U256`] into a `u128`.
use super::U256;

impl U256 {
    /// Extracts bits at even positions (0, 2, 4, ..., 254) and compacts them
    /// into a `u128`.
    ///
    /// Bit `2i` of the [`U256`] maps to bit `i` of the result. This is the
    /// inverse of [`from_u128_dilated_even`](U256::from_u128_dilated_even):
    /// `U256::from_u128_dilated_even(v).undilate_even() == v`.
    ///
    /// Each of the four `u64` limbs is undilated into a `u32` via a 5-stage
    /// binary magic number cascade, then the four quarters are reassembled
    /// into a `u128`.
    ///
    /// # Examples
    ///
    /// ```
    /// use cnfy_uint::u256::U256;
    ///
    /// let v = U256::from_u128_dilated_even(0xDEAD_BEEF);
    /// assert_eq!(v.undilate_even(), 0xDEAD_BEEF);
    /// ```
    #[inline]
    pub const fn undilate_even(&self) -> u128 {
        let q0 = Self::undilate_u64_to_u32(self.0[0]);
        let q1 = Self::undilate_u64_to_u32(self.0[1]);
        let q2 = Self::undilate_u64_to_u32(self.0[2]);
        let q3 = Self::undilate_u64_to_u32(self.0[3]);

        (q0 as u128) | ((q1 as u128) << 32) | ((q2 as u128) << 64) | ((q3 as u128) << 96)
    }

    /// Undilates even bit positions from a `u64` into a `u32` using a 5-stage
    /// binary magic number cascade.
    ///
    /// Bit `2i` of the input maps to bit `i` of the output. Odd bit positions
    /// in the input are masked out.
    #[inline]
    pub(crate) const fn undilate_u64_to_u32(v: u64) -> u32 {
        let mut x = v & 0x5555_5555_5555_5555;
        x = (x | (x >> 1)) & 0x3333_3333_3333_3333;
        x = (x | (x >> 2)) & 0x0F0F_0F0F_0F0F_0F0F;
        x = (x | (x >> 4)) & 0x00FF_00FF_00FF_00FF;
        x = (x | (x >> 8)) & 0x0000_FFFF_0000_FFFF;
        x = (x | (x >> 16)) & 0x0000_0000_FFFF_FFFF;
        x as u32
    }
}

#[cfg(test)]
mod ai_tests {
    use super::*;

    /// Undilating zero produces zero.
    #[test]
    fn zero() {
        assert_eq!(U256::ZERO.undilate_even(), 0u128);
    }

    /// Round-trip: dilate then undilate recovers the original value.
    #[test]
    fn round_trip_one() {
        assert_eq!(U256::from_u128_dilated_even(1).undilate_even(), 1);
    }

    /// Round-trip with a value spanning all four quarters.
    #[test]
    fn round_trip_cross_quarter() {
        let v: u128 = 0xDEAD_BEEF_CAFE_BABE_1234_5678_9ABC_DEF0;
        assert_eq!(U256::from_u128_dilated_even(v).undilate_even(), v);
    }

    /// Round-trip with u128::MAX.
    #[test]
    fn round_trip_max() {
        assert_eq!(
            U256::from_u128_dilated_even(u128::MAX).undilate_even(),
            u128::MAX,
        );
    }

    /// Odd-only dilated value undilates to zero from even positions.
    #[test]
    fn odd_input_gives_zero() {
        let v = U256::from_u128_dilated_odd(u128::MAX);
        assert_eq!(v.undilate_even(), 0);
    }

    /// Single high bit: bit 254 (even) → bit 127.
    #[test]
    fn bit_254_to_127() {
        let v = U256::from_u128_dilated_even(1u128 << 127);
        assert_eq!(v.undilate_even(), 1u128 << 127);
    }
}
