//! Morton dilation of a `u128` into even bit positions of a [`U256`].
use super::U256;

impl U256 {
    /// Creates a [`U256`] by dilating a `u128` value into even bit positions
    /// (0, 2, 4, ..., 254).
    ///
    /// Each bit `i` of the input maps to bit `2i` of the result. Odd bit
    /// positions in the output are all zero. This is the first step of
    /// Morton/Z-order interleaving: `interleave(x, y) = dilate_even(x) | dilate_odd(y)`.
    ///
    /// The input is split into four `u32` quarters, each dilated into one `u64`
    /// limb via a 5-stage binary magic number cascade (u32 → u64).
    ///
    /// # Examples
    ///
    /// ```
    /// use cnfy_uint::u256::U256;
    ///
    /// // Bit 0 of input → bit 0 of output
    /// let v = U256::from_u128_dilated_even(1);
    /// assert_eq!(v, U256::from_be_limbs([0, 0, 0, 1]));
    ///
    /// // Bit 1 of input → bit 2 of output
    /// let v = U256::from_u128_dilated_even(0b11);
    /// assert_eq!(v, U256::from_be_limbs([0, 0, 0, 0b0101]));
    /// ```
    #[inline]
    pub const fn from_u128_dilated_even(value: u128) -> U256 {
        let q0 = value as u32;
        let q1 = (value >> 32) as u32;
        let q2 = (value >> 64) as u32;
        let q3 = (value >> 96) as u32;

        let w0 = Self::dilate_u32_to_u64(q0);
        let w1 = Self::dilate_u32_to_u64(q1);
        let w2 = Self::dilate_u32_to_u64(q2);
        let w3 = Self::dilate_u32_to_u64(q3);

        U256([w0, w1, w2, w3])
    }

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

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

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

    /// Bit 0 maps to position 0.
    #[test]
    fn bit_0() {
        let v = U256::from_u128_dilated_even(1);
        assert_eq!(v, U256::from_be_limbs([0, 0, 0, 1]));
    }

    /// Bits 0-1 map to positions 0, 2.
    #[test]
    fn bits_0_1() {
        let v = U256::from_u128_dilated_even(0b11);
        assert_eq!(v, U256::from_be_limbs([0, 0, 0, 0b0101]));
    }

    /// Bit 31 maps to position 62 (still in limb 0).
    #[test]
    fn bit_31() {
        let v = U256::from_u128_dilated_even(1u128 << 31);
        // Position 62 = bit 62 of limb 0
        assert_eq!(v, U256::from_be_limbs([0, 0, 0, 1u64 << 62]));
    }

    /// Bit 32 maps to position 64 (limb 1, bit 0).
    #[test]
    fn bit_32() {
        let v = U256::from_u128_dilated_even(1u128 << 32);
        assert_eq!(v, U256::from_be_limbs([0, 0, 1, 0]));
    }

    /// Bit 64 maps to position 128 (limb 2, bit 0).
    #[test]
    fn bit_64() {
        let v = U256::from_u128_dilated_even(1u128 << 64);
        assert_eq!(v, U256::from_be_limbs([0, 1, 0, 0]));
    }

    /// Bit 96 maps to position 192 (limb 3, bit 0).
    #[test]
    fn bit_96() {
        let v = U256::from_u128_dilated_even(1u128 << 96);
        assert_eq!(v, U256::from_be_limbs([1, 0, 0, 0]));
    }

    /// Bit 127 maps to position 254 (limb 3, bit 62).
    #[test]
    fn bit_127() {
        let v = U256::from_u128_dilated_even(1u128 << 127);
        assert_eq!(v, U256::from_be_limbs([1u64 << 62, 0, 0, 0]));
    }

    /// All bits set: every even position should be 1.
    #[test]
    fn all_bits_set() {
        let v = U256::from_u128_dilated_even(u128::MAX);
        // Every limb should have the pattern 0x5555_5555_5555_5555
        assert_eq!(
            v,
            U256::from_be_limbs([
                0x5555_5555_5555_5555,
                0x5555_5555_5555_5555,
                0x5555_5555_5555_5555,
                0x5555_5555_5555_5555,
            ])
        );
    }

    /// Only even positions are set (no odd bits leak).
    #[test]
    fn no_odd_bits() {
        let v = U256::from_u128_dilated_even(u128::MAX);
        let odd_mask = U256::from_be_limbs([
            0xAAAA_AAAA_AAAA_AAAA,
            0xAAAA_AAAA_AAAA_AAAA,
            0xAAAA_AAAA_AAAA_AAAA,
            0xAAAA_AAAA_AAAA_AAAA,
        ]);
        assert_eq!(v & odd_mask, U256::ZERO);
    }
}
