1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
//! 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);
}
}