qualia_core_db/q42/m64_matter/
brick3d.rs1pub const M64_BRICK3D_SIDE: usize = 16;
9
10pub const M64_BRICK3D_RECORDS: usize = 4096;
12
13pub const M64_BRICK3D_BYTES: usize = 4096 * 64;
15
16#[inline]
20fn axes_to_transpose_3d(x: &mut [u32; 3], b: u32) {
21 if b == 0 {
22 return;
23 }
24 let m = 1u32 << (b - 1);
25 let mut q = m;
26 while q > 1 {
27 let p = q - 1;
28 for i in 0..3 {
29 if (x[i] & q) != 0 {
30 x[0] ^= p;
31 } else {
32 let t = (x[0] ^ x[i]) & p;
33 x[0] ^= t;
34 x[i] ^= t;
35 }
36 }
37 q >>= 1;
38 }
39
40 for i in 1..3 {
41 x[i] ^= x[i - 1];
42 }
43 let mut t = 0u32;
44 let mut q = m;
45 while q > 1 {
46 if (x[2] & q) != 0 {
47 t ^= q - 1;
48 }
49 q >>= 1;
50 }
51 for i in 0..3 {
52 x[i] ^= t;
53 }
54}
55
56#[inline]
60fn transpose_to_axes_3d(x: &mut [u32; 3], b: u32) {
61 if b == 0 {
62 return;
63 }
64 let z = 2u32 << (b - 1);
65 let mut t = x[2] >> 1;
66 for i in (1..3).rev() {
67 x[i] ^= x[i - 1];
68 }
69 x[0] ^= t;
70
71 let mut q = 2u32;
72 while q != z {
73 let p = q - 1;
74 for i in (0..3).rev() {
75 if (x[i] & q) != 0 {
76 x[0] ^= p;
77 } else {
78 t = (x[0] ^ x[i]) & p;
79 x[0] ^= t;
80 x[i] ^= t;
81 }
82 }
83 q <<= 1;
84 }
85}
86
87#[inline]
91pub fn encode_hilbert3d_u64(bx: u32, by: u32, bz: u32, order: u32) -> u64 {
92 let order = order.min(21);
93 if order == 0 {
94 return 0;
95 }
96 let mask = (1u32 << order) - 1;
97 let mut x = [bx & mask, by & mask, bz & mask];
98 axes_to_transpose_3d(&mut x, order);
99
100 let mut h = 0u64;
101 for k in 0..order {
102 let bit_base = (k * 3) as usize;
103 h |= (((x[2] >> k) & 1) as u64) << bit_base;
104 h |= (((x[1] >> k) & 1) as u64) << (bit_base + 1);
105 h |= (((x[0] >> k) & 1) as u64) << (bit_base + 2);
106 }
107 h
108}
109
110#[inline]
114pub fn decode_hilbert3d_u64(h: u64, order: u32) -> (u32, u32, u32) {
115 let order = order.min(21);
116 if order == 0 {
117 return (0, 0, 0);
118 }
119 let mut x = [0u32; 3];
120 for k in 0..order {
121 let bit_base = (k * 3) as usize;
122 x[2] |= (((h >> bit_base) & 1) as u32) << k;
123 x[1] |= (((h >> (bit_base + 1)) & 1) as u32) << k;
124 x[0] |= (((h >> (bit_base + 2)) & 1) as u32) << k;
125 }
126 transpose_to_axes_3d(&mut x, order);
127 (x[0], x[1], x[2])
128}
129
130#[inline]
135pub fn brick_voxel_linear_index(lx: u8, ly: u8, lz: u8) -> usize {
136 let x = (lx as usize) & 0x0F;
137 let y = (ly as usize) & 0x0F;
138 let z = (lz as usize) & 0x0F;
139 let mut morton = 0usize;
140 for i in 0..4 {
141 morton |= ((x >> i) & 1) << (3 * i);
142 morton |= ((y >> i) & 1) << (3 * i + 1);
143 morton |= ((z >> i) & 1) << (3 * i + 2);
144 }
145 morton
146}
147
148#[inline]
150pub fn brick_voxel_coords(idx: usize) -> (u8, u8, u8) {
151 let mut x = 0u8;
152 let mut y = 0u8;
153 let mut z = 0u8;
154 for i in 0..4 {
155 x |= (((idx >> (3 * i)) & 1) as u8) << i;
156 y |= (((idx >> (3 * i + 1)) & 1) as u8) << i;
157 z |= (((idx >> (3 * i + 2)) & 1) as u8) << i;
158 }
159 (x, y, z)
160}
161
162#[cfg(test)]
163mod tests {
164 use super::*;
165
166 #[test]
167 fn test_brick3d_constants() {
168 assert_eq!(M64_BRICK3D_SIDE, 16);
169 assert_eq!(M64_BRICK3D_RECORDS, 4096);
170 assert_eq!(M64_BRICK3D_BYTES, 262_144);
171 }
172
173 #[test]
174 fn test_brick_voxel_morton_roundtrip() {
175 for lz in 0..16u8 {
176 for ly in 0..16u8 {
177 for lx in 0..16u8 {
178 let idx = brick_voxel_linear_index(lx, ly, lz);
179 assert!(idx < 4096);
180 let (rx, ry, rz) = brick_voxel_coords(idx);
181 assert_eq!((rx, ry, rz), (lx, ly, lz));
182 }
183 }
184 }
185 }
186
187 #[test]
188 fn test_hilbert3d_roundtrip_exhaustive() {
189 for order in 1..=3 {
190 let side = 1u32 << order;
191 for z in 0..side {
192 for y in 0..side {
193 for x in 0..side {
194 let h = encode_hilbert3d_u64(x, y, z, order);
195 let (rx, ry, rz) = decode_hilbert3d_u64(h, order);
196 assert_eq!((rx, ry, rz), (x, y, z));
197 }
198 }
199 }
200 }
201 }
202
203 #[test]
204 fn test_hilbert3d_roundtrip_samples() {
205 for order in [4, 8, 16, 21] {
206 let max_val = if order == 21 { 0x001F_FFFF } else { (1u32 << order) - 1 };
207 let test_points = [
208 (0, 0, 0),
209 (1, 0, 0),
210 (0, 1, 0),
211 (0, 0, 1),
212 (max_val, max_val, max_val),
213 (max_val / 2, max_val / 3, max_val / 4),
214 ];
215 for &(x, y, z) in &test_points {
216 let h = encode_hilbert3d_u64(x, y, z, order);
217 let (rx, ry, rz) = decode_hilbert3d_u64(h, order);
218 assert_eq!((rx, ry, rz), (x, y, z), "Failed for order {order}");
219 }
220 }
221 }
222
223 #[test]
224 fn test_hilbert3d_continuity() {
225 let order = 2;
226 let total = 1u64 << (3 * order);
227 let mut prev = decode_hilbert3d_u64(0, order);
228 for h in 1..total {
229 let curr = decode_hilbert3d_u64(h, order);
230 let dist = curr.0.abs_diff(prev.0) + curr.1.abs_diff(prev.1) + curr.2.abs_diff(prev.2);
231 assert_eq!(dist, 1, "Discontinuity at h={h}");
232 prev = curr;
233 }
234 }
235}