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
//! Morton dilation of a `u128` into odd bit positions of a [`U256`].
use super::U256;
impl U256 {
/// Creates a [`U256`] by dilating a `u128` value into odd bit positions
/// (1, 3, 5, ..., 255).
///
/// Each bit `i` of the input maps to bit `2i+1` of the result. Even bit
/// positions in the output are all zero. Combined with
/// [`from_u128_dilated_even`](U256::from_u128_dilated_even), this enables
/// Morton/Z-order interleaving of two coordinates.
///
/// # Examples
///
/// ```
/// use cnfy_uint::u256::U256;
///
/// // Bit 0 of input → bit 1 of output
/// let v = U256::from_u128_dilated_odd(1);
/// assert_eq!(v, U256::from_be_limbs([0, 0, 0, 2]));
///
/// // Bit 1 of input → bit 3 of output
/// let v = U256::from_u128_dilated_odd(0b11);
/// assert_eq!(v, U256::from_be_limbs([0, 0, 0, 0b1010]));
/// ```
#[inline]
pub const fn from_u128_dilated_odd(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) << 1;
let w1 = Self::dilate_u32_to_u64(q1) << 1;
let w2 = Self::dilate_u32_to_u64(q2) << 1;
let w3 = Self::dilate_u32_to_u64(q3) << 1;
U256([w0, w1, w2, w3])
}
}
#[cfg(test)]
mod ai_tests {
use super::*;
/// Dilating zero produces U256::ZERO.
#[test]
fn zero() {
assert_eq!(U256::from_u128_dilated_odd(0), U256::ZERO);
}
/// Bit 0 maps to position 1.
#[test]
fn bit_0() {
let v = U256::from_u128_dilated_odd(1);
assert_eq!(v, U256::from_be_limbs([0, 0, 0, 2]));
}
/// Bits 0-1 map to positions 1, 3.
#[test]
fn bits_0_1() {
let v = U256::from_u128_dilated_odd(0b11);
assert_eq!(v, U256::from_be_limbs([0, 0, 0, 0b1010]));
}
/// Bit 31 maps to position 63 (limb 0, bit 63).
#[test]
fn bit_31() {
let v = U256::from_u128_dilated_odd(1u128 << 31);
assert_eq!(v, U256::from_be_limbs([0, 0, 0, 1u64 << 63]));
}
/// Bit 32 maps to position 65 (limb 1, bit 1).
#[test]
fn bit_32() {
let v = U256::from_u128_dilated_odd(1u128 << 32);
assert_eq!(v, U256::from_be_limbs([0, 0, 2, 0]));
}
/// Bit 64 maps to position 129 (limb 2, bit 1).
#[test]
fn bit_64() {
let v = U256::from_u128_dilated_odd(1u128 << 64);
assert_eq!(v, U256::from_be_limbs([0, 2, 0, 0]));
}
/// Bit 96 maps to position 193 (limb 3, bit 1).
#[test]
fn bit_96() {
let v = U256::from_u128_dilated_odd(1u128 << 96);
assert_eq!(v, U256::from_be_limbs([2, 0, 0, 0]));
}
/// Bit 127 maps to position 255 (limb 3, bit 63).
#[test]
fn bit_127() {
let v = U256::from_u128_dilated_odd(1u128 << 127);
assert_eq!(v, U256::from_be_limbs([1u64 << 63, 0, 0, 0]));
}
/// All bits set: every odd position should be 1.
#[test]
fn all_bits_set() {
let v = U256::from_u128_dilated_odd(u128::MAX);
assert_eq!(
v,
U256::from_be_limbs([
0xAAAA_AAAA_AAAA_AAAA,
0xAAAA_AAAA_AAAA_AAAA,
0xAAAA_AAAA_AAAA_AAAA,
0xAAAA_AAAA_AAAA_AAAA,
])
);
}
/// Only odd positions are set (no even bits leak).
#[test]
fn no_even_bits() {
let v = U256::from_u128_dilated_odd(u128::MAX);
let even_mask = U256::from_be_limbs([
0x5555_5555_5555_5555,
0x5555_5555_5555_5555,
0x5555_5555_5555_5555,
0x5555_5555_5555_5555,
]);
assert_eq!(v & even_mask, U256::ZERO);
}
/// Even and odd dilations occupy disjoint bit positions.
#[test]
fn orthogonal_to_even() {
let even = U256::from_u128_dilated_even(u128::MAX);
let odd = U256::from_u128_dilated_odd(u128::MAX);
assert_eq!(even & odd, U256::ZERO);
}
}