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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
//! Morton dilation of a [`U256`] into even bit positions of a [`U512`].
use super::U256;
use crate::u512::U512;
impl U256 {
/// Dilates this [`U256`] into the even bit positions (0, 2, 4, ..., 510)
/// of a [`U512`].
///
/// Each bit `i` of the input maps to bit `2i` of the result. Odd bit
/// positions in the output are all zero. Each of the four `u64` limbs is
/// split into two `u32` halves, and each half is dilated into one `u64`
/// limb of the [`U512`] via the 5-stage binary magic number cascade.
///
/// # Examples
///
/// ```
/// use cnfy_uint::u256::U256;
/// use cnfy_uint::u512::U512;
///
/// let v = U256::from_be_limbs([0, 0, 0, 1]);
/// let dilated = v.dilate_even();
/// assert_eq!(dilated, U512::from_be_limbs([0, 0, 0, 0, 0, 0, 0, 1]));
/// ```
#[inline]
pub const fn dilate_even(&self) -> U512 {
// Split each u64 limb into low/high u32, dilate each into u64.
// U256 limb[i] low → U512 limb[2i]
// U256 limb[i] high → U512 limb[2i+1]
let w0 = Self::dilate_u32_to_u64(self.0[0] as u32);
let w1 = Self::dilate_u32_to_u64((self.0[0] >> 32) as u32);
let w2 = Self::dilate_u32_to_u64(self.0[1] as u32);
let w3 = Self::dilate_u32_to_u64((self.0[1] >> 32) as u32);
let w4 = Self::dilate_u32_to_u64(self.0[2] as u32);
let w5 = Self::dilate_u32_to_u64((self.0[2] >> 32) as u32);
let w6 = Self::dilate_u32_to_u64(self.0[3] as u32);
let w7 = Self::dilate_u32_to_u64((self.0[3] >> 32) as u32);
U512([w0, w1, w2, w3, w4, w5, w6, w7])
}
}
#[cfg(test)]
mod ai_tests {
use super::*;
/// Dilating zero produces U512::ZERO.
#[test]
fn zero() {
assert_eq!(U256::ZERO.dilate_even(), U512::ZERO);
}
/// Bit 0 maps to position 0.
#[test]
fn bit_0() {
let v = U256::from_be_limbs([0, 0, 0, 1]);
assert_eq!(v.dilate_even(), U512::from_be_limbs([0, 0, 0, 0, 0, 0, 0, 1]));
}
/// Bit 31 maps to position 62 (U512 limb 0, bit 62).
#[test]
fn bit_31() {
let v = U256::from_be_limbs([0, 0, 0, 1u64 << 31]);
assert_eq!(
v.dilate_even(),
U512::from_be_limbs([0, 0, 0, 0, 0, 0, 0, 1u64 << 62]),
);
}
/// Bit 32 maps to position 64 (U512 limb 1, bit 0).
#[test]
fn bit_32() {
let v = U256::from_be_limbs([0, 0, 0, 1u64 << 32]);
assert_eq!(
v.dilate_even(),
U512::from_be_limbs([0, 0, 0, 0, 0, 0, 1, 0]),
);
}
/// Bit 64 maps to position 128 (U512 limb 2, bit 0).
#[test]
fn bit_64() {
let v = U256::from_be_limbs([0, 0, 1, 0]);
assert_eq!(
v.dilate_even(),
U512::from_be_limbs([0, 0, 0, 0, 0, 1, 0, 0]),
);
}
/// Bit 255 maps to position 510 (U512 limb 7, bit 62).
#[test]
fn bit_255() {
let v = U256::from_be_limbs([1u64 << 63, 0, 0, 0]);
assert_eq!(
v.dilate_even(),
U512::from_be_limbs([1u64 << 62, 0, 0, 0, 0, 0, 0, 0]),
);
}
/// All bits set: every even position in U512 should be 1.
#[test]
fn all_bits_set() {
let v = U256::MAX.dilate_even();
for i in 0..8 {
assert_eq!(v.0[i], 0x5555_5555_5555_5555);
}
}
/// No odd bits leak.
#[test]
fn no_odd_bits() {
let v = U256::MAX.dilate_even();
let odd_mask = U512::from_be_limbs([
0xAAAA_AAAA_AAAA_AAAA,
0xAAAA_AAAA_AAAA_AAAA,
0xAAAA_AAAA_AAAA_AAAA,
0xAAAA_AAAA_AAAA_AAAA,
0xAAAA_AAAA_AAAA_AAAA,
0xAAAA_AAAA_AAAA_AAAA,
0xAAAA_AAAA_AAAA_AAAA,
0xAAAA_AAAA_AAAA_AAAA,
]);
assert_eq!(v & odd_mask, U512::ZERO);
}
}