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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
//! 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);
}
}