Skip to main content

qualia_core_db/q42/m64_matter/
brick3d.rs

1//! 3D Volumetric Bricks and Spatial Indexing for M64 Matter Containers.
2//!
3//! Provides 3D Hilbert curve spatial addressing for macro-level chunk clustering
4//! and 3D Morton (Z-order) bit-interleaving for intra-brick `16×16×16` (4,096-voxel)
5//! cache locality in L1/L2 caches.
6
7/// Side dimension of an M64 3D volumetric brick (16 voxels along each axis).
8pub const M64_BRICK3D_SIDE: usize = 16;
9
10/// Total number of 64-byte records in one 16×16×16 brick (4,096 records).
11pub const M64_BRICK3D_RECORDS: usize = 4096;
12
13/// Total byte size of one 16×16×16 brick payload (256 KB = 262,144 bytes).
14pub const M64_BRICK3D_BYTES: usize = 4096 * 64;
15
16/// Transform in-place from geometrical axes to Hilbert transposed bits.
17///
18/// Implements John Skilling's compact algorithm (2004) for dimension N = 3.
19#[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/// Transform in-place from Hilbert transposed bits back to geometrical axes.
57///
58/// Implements John Skilling's compact algorithm (2004) for dimension N = 3.
59#[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/// Encode 3D brick coordinates `(bx, by, bz)` to a 64-bit Hilbert index.
88///
89/// Supports up to order 21 (21 bits per axis, $21 \times 3 = 63$ bits $\le 64$ bits).
90#[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/// Decode a 64-bit Hilbert index back to 3D brick coordinates `(bx, by, bz)`.
111///
112/// Supports up to order 21 (21 bits per axis).
113#[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/// Computes the linear 1D index `0..4096` of a voxel inside a 16×16×16 brick.
131///
132/// Uses 3D Morton (Z-order) interleaving across the 4-bit local coordinates
133/// (`lx, ly, lz` in `0..16`), maximizing cache-line spatial locality.
134#[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/// Computes local 3D coordinates `(lx, ly, lz)` from an intra-brick linear index `0..4096`.
149#[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}