qualia_core_db/container_10d/
topology_section.rs

1//! `.10d` Topology section — half-edge graph + CSR adjacency + connectivity
2//! summary serialized as a self-describing section (P2.8).
3//!
4//! Layout:
5//! ```text
6//! [TopologyMiniHeader: 32 bytes]
7//! [half_edges:  N * 16 bytes  (HalfEdge = 4 × u32)]
8//! [v_offsets:   (V+1) * 4 bytes]
9//! [v_neighbours: N * 4 bytes]
10//! [f_offsets:   (F+1) * 4 bytes]
11//! [f_neighbours: N * 4 bytes]
12//! ```
13//!
14//! All arrays are little-endian, 4-byte aligned. The section is deterministic:
15//! identical input yields byte-identical output. Per-section CRC-32C is
16//! handled by the container's section-table encoder.
17
18use bytemuck::{bytes_of, cast_slice, from_bytes, Pod, Zeroable};
19
20use crate::specialized_libs::computational_geometry::{
21    build_face_adjacency_csr, build_vertex_adjacency_csr, compute_connectivity, HalfEdge,
22    INVALID_INDEX,
23};
24
25/// Mini-header size in bytes.
26pub const TOPOLOGY_MINI_HEADER_SIZE: usize = 32;
27
28/// Maximum half-edge count (bounded by 42MB Sentinel: 42MB / 16B = 2.75M).
29pub const MAX_HALF_EDGE_COUNT: usize = 2_097_152; // 2^21
30
31/// The 32-byte Topology-section mini-header.
32///
33/// ```text
34/// offset  size  field
35/// 0       4     vertex_count:u32
36/// 4       4     face_count:u32
37/// 8       4     half_edge_count:u32
38/// 12      4     boundary_loop_count:u32
39/// 16      4     component_count:u32
40/// 20      4     euler_characteristic:i32
41/// 24      4     genus:u32           (0xFFFF_FFFF = None / non-orientable)
42/// 28      4     reserved_u32        (must be zero)
43/// ```
44#[repr(C)]
45#[derive(Debug, Clone, Copy, PartialEq, Pod, Zeroable)]
46pub struct TopologyMiniHeader {
47    pub vertex_count: u32,
48    pub face_count: u32,
49    pub half_edge_count: u32,
50    pub boundary_loop_count: u32,
51    pub component_count: u32,
52    pub euler_characteristic: i32,
53    pub genus: u32,
54    pub reserved_u32: u32,
55}
56
57impl Default for TopologyMiniHeader {
58    fn default() -> Self {
59        Self {
60            vertex_count: 0,
61            face_count: 0,
62            half_edge_count: 0,
63            boundary_loop_count: 0,
64            component_count: 0,
65            euler_characteristic: 0,
66            genus: INVALID_INDEX,
67            reserved_u32: 0,
68        }
69    }
70}
71
72/// Topology-section encode/decode error.
73#[derive(Debug, Clone, PartialEq, Eq)]
74pub enum TopologySectionError {
75    /// Payload too short for the mini-header.
76    PayloadTooShort { got: usize, need: usize },
77    /// Non-zero reserved field.
78    NonZeroReserved,
79    /// Half-edge count exceeds the max.
80    HalfEdgeCountTooLarge { got: u32, max: usize },
81    /// Payload truncated relative to declared counts.
82    PayloadTruncated { expected: usize, got: usize },
83    /// Output buffer too small.
84    OutputBufferTooSmall { needed: usize, have: usize },
85    /// Connectivity computation failed.
86    ConnectivityError,
87}
88
89impl std::fmt::Display for TopologySectionError {
90    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
91        match self {
92            Self::PayloadTooShort { got, need } => {
93                write!(f, "10d TOPOLOGY payload too short: got {got}, need {need}")
94            }
95            Self::NonZeroReserved => write!(f, "10d TOPOLOGY non-zero reserved field"),
96            Self::HalfEdgeCountTooLarge { got, max } => {
97                write!(f, "10d TOPOLOGY half_edge_count {got} exceeds max {max}")
98            }
99            Self::PayloadTruncated { expected, got } => write!(
100                f,
101                "10d TOPOLOGY payload truncated: expected {expected}, got {got}"
102            ),
103            Self::OutputBufferTooSmall { needed, have } => write!(
104                f,
105                "10d TOPOLOGY output buffer too small: need {needed}, have {have}"
106            ),
107            Self::ConnectivityError => write!(f, "10d TOPOLOGY connectivity computation failed"),
108        }
109    }
110}
111
112impl std::error::Error for TopologySectionError {}
113
114/// Compute the encoded byte length for a topology section.
115#[inline]
116pub fn encoded_len(vertex_count: u32, face_count: u32, half_edge_count: u32) -> usize {
117    let vc = vertex_count as usize;
118    let fc = face_count as usize;
119    let ec = half_edge_count as usize;
120    TOPOLOGY_MINI_HEADER_SIZE
121        + ec * 16          // half_edges
122        + (vc + 1) * 4     // v_offsets
123        + ec * 4           // v_neighbours
124        + (fc + 1) * 4     // f_offsets
125        + ec * 4 // f_neighbours
126}
127
128/// Encode a topology section from a half-edge array.
129///
130/// Builds the CSR adjacency views and connectivity summary, then serializes
131/// everything into `out`. The caller supplies the half-edge array and
132/// vertex/face counts. Workspace buffers (`labels`, `queue`, `visited`) are
133/// allocated here since this is the ingest path, not a hot path.
134///
135/// Returns the number of bytes written.
136pub fn encode_topology_section(
137    vertex_count: u32,
138    face_count: u32,
139    half_edges: &[HalfEdge],
140    out: &mut [u8],
141) -> Result<usize, TopologySectionError> {
142    let ec = half_edges.len();
143    if ec > MAX_HALF_EDGE_COUNT {
144        return Err(TopologySectionError::HalfEdgeCountTooLarge {
145            got: ec as u32,
146            max: MAX_HALF_EDGE_COUNT,
147        });
148    }
149    if ec > (u32::MAX as usize) / 4 {
150        return Err(TopologySectionError::HalfEdgeCountTooLarge {
151            got: ec as u32,
152            max: MAX_HALF_EDGE_COUNT,
153        });
154    }
155
156    let vc = vertex_count as usize;
157    let fc = face_count as usize;
158
159    // Build CSR adjacency views.
160    let mut v_offsets = vec![0u32; vc + 1];
161    let mut v_neighbours = vec![0u32; ec];
162    build_vertex_adjacency_csr(vertex_count, half_edges, &mut v_offsets, &mut v_neighbours)
163        .map_err(|_| TopologySectionError::ConnectivityError)?;
164
165    let mut f_offsets = vec![0u32; fc + 1];
166    let mut f_neighbours = vec![0u32; ec];
167    build_face_adjacency_csr(face_count, half_edges, &mut f_offsets, &mut f_neighbours)
168        .map_err(|_| TopologySectionError::ConnectivityError)?;
169
170    // Compute connectivity invariants.
171    let mut labels = vec![0u32; fc];
172    let mut queue = vec![0u32; fc];
173    let mut visited = vec![false; ec];
174    let summary = compute_connectivity(
175        vertex_count,
176        face_count,
177        half_edges,
178        &mut labels,
179        &mut queue,
180        &mut visited,
181    )
182    .map_err(|_| TopologySectionError::ConnectivityError)?;
183
184    let need = encoded_len(vertex_count, face_count, ec as u32);
185    if out.len() < need {
186        return Err(TopologySectionError::OutputBufferTooSmall {
187            needed: need,
188            have: out.len(),
189        });
190    }
191
192    let header = TopologyMiniHeader {
193        vertex_count,
194        face_count,
195        half_edge_count: ec as u32,
196        boundary_loop_count: summary.boundary_loop_count,
197        component_count: summary.component_count,
198        euler_characteristic: summary.euler_characteristic,
199        genus: summary.genus.unwrap_or(INVALID_INDEX),
200        reserved_u32: 0,
201    };
202
203    let mut off = 0usize;
204
205    // Mini-header.
206    out[off..off + TOPOLOGY_MINI_HEADER_SIZE].copy_from_slice(bytes_of(&header));
207    off += TOPOLOGY_MINI_HEADER_SIZE;
208
209    // Half-edges.
210    let he_bytes: &[u8] = cast_slice(half_edges);
211    out[off..off + he_bytes.len()].copy_from_slice(he_bytes);
212    off += he_bytes.len();
213
214    // Vertex-adjacency CSR: offsets then neighbours.
215    let vo_bytes: &[u8] = cast_slice(&v_offsets);
216    out[off..off + vo_bytes.len()].copy_from_slice(vo_bytes);
217    off += vo_bytes.len();
218    let vn_bytes: &[u8] = cast_slice(&v_neighbours);
219    out[off..off + vn_bytes.len()].copy_from_slice(vn_bytes);
220    off += vn_bytes.len();
221
222    // Face-adjacency CSR: offsets then neighbours.
223    let fo_bytes: &[u8] = cast_slice(&f_offsets);
224    out[off..off + fo_bytes.len()].copy_from_slice(fo_bytes);
225    off += fo_bytes.len();
226    let fn_bytes: &[u8] = cast_slice(&f_neighbours);
227    out[off..off + fn_bytes.len()].copy_from_slice(fn_bytes);
228    off += fn_bytes.len();
229
230    debug_assert_eq!(off, need);
231    Ok(off)
232}
233
234/// Decoded topology section data.
235#[derive(Debug, Clone, PartialEq)]
236pub struct TopologySectionData {
237    pub header: TopologyMiniHeader,
238    pub half_edges: Vec<HalfEdge>,
239    pub v_offsets: Vec<u32>,
240    pub v_neighbours: Vec<u32>,
241    pub f_offsets: Vec<u32>,
242    pub f_neighbours: Vec<u32>,
243}
244
245/// Decode a `.10d` Topology section payload.
246pub fn decode_topology_section(bytes: &[u8]) -> Result<TopologySectionData, TopologySectionError> {
247    if bytes.len() < TOPOLOGY_MINI_HEADER_SIZE {
248        return Err(TopologySectionError::PayloadTooShort {
249            got: bytes.len(),
250            need: TOPOLOGY_MINI_HEADER_SIZE,
251        });
252    }
253
254    let header: TopologyMiniHeader = *from_bytes(&bytes[..TOPOLOGY_MINI_HEADER_SIZE]);
255    if header.reserved_u32 != 0 {
256        return Err(TopologySectionError::NonZeroReserved);
257    }
258
259    let vc = header.vertex_count as usize;
260    let fc = header.face_count as usize;
261    let ec = header.half_edge_count as usize;
262
263    if ec > MAX_HALF_EDGE_COUNT {
264        return Err(TopologySectionError::HalfEdgeCountTooLarge {
265            got: header.half_edge_count,
266            max: MAX_HALF_EDGE_COUNT,
267        });
268    }
269
270    let need = encoded_len(
271        header.vertex_count,
272        header.face_count,
273        header.half_edge_count,
274    );
275    if bytes.len() < need {
276        return Err(TopologySectionError::PayloadTruncated {
277            expected: need,
278            got: bytes.len(),
279        });
280    }
281
282    let mut off = TOPOLOGY_MINI_HEADER_SIZE;
283
284    // Half-edges.
285    let he_bytes = &bytes[off..off + ec * 16];
286    let half_edges: Vec<HalfEdge> = cast_slice(he_bytes).to_vec();
287    off += ec * 16;
288
289    // Vertex-adjacency CSR.
290    let vo_bytes = &bytes[off..off + (vc + 1) * 4];
291    let v_offsets: Vec<u32> = cast_slice(vo_bytes).to_vec();
292    off += (vc + 1) * 4;
293    let vn_bytes = &bytes[off..off + ec * 4];
294    let v_neighbours: Vec<u32> = cast_slice(vn_bytes).to_vec();
295    off += ec * 4;
296
297    // Face-adjacency CSR.
298    let fo_bytes = &bytes[off..off + (fc + 1) * 4];
299    let f_offsets: Vec<u32> = cast_slice(fo_bytes).to_vec();
300    off += (fc + 1) * 4;
301    let fn_bytes = &bytes[off..off + ec * 4];
302    let f_neighbours: Vec<u32> = cast_slice(fn_bytes).to_vec();
303    off += ec * 4;
304
305    debug_assert_eq!(off, need);
306
307    Ok(TopologySectionData {
308        header,
309        half_edges,
310        v_offsets,
311        v_neighbours,
312        f_offsets,
313        f_neighbours,
314    })
315}
316
317#[cfg(test)]
318mod tests {
319    use super::*;
320    use crate::container_10d::header::Container10dHeader;
321    use crate::container_10d::integrity::{seal_whole_file_crc32c, verify_whole_file_crc32c};
322    use crate::container_10d::section::{
323        encode_container, parse_section_table, AlignmentTier, SectionInput, SectionType,
324    };
325    use crate::specialized_libs::computational_geometry::{
326        build_triangle_half_edges, required_edge_slots, EdgeSlot,
327    };
328
329    fn build_he(vertex_count: u32, triangles: &[[u32; 3]]) -> (Vec<HalfEdge>, u32, u32) {
330        let n = triangles.len() * 3;
331        let mut edges = vec![HalfEdge::default(); n];
332        let mut slots = vec![EdgeSlot::default(); required_edge_slots(triangles.len())];
333        let summary =
334            build_triangle_half_edges(vertex_count, triangles, &mut edges, &mut slots).unwrap();
335        assert_eq!(summary.vertex_count, vertex_count);
336        assert_eq!(summary.face_count, triangles.len() as u32);
337        (edges, vertex_count, triangles.len() as u32)
338    }
339
340    #[test]
341    fn mini_header_is_pod_with_exact_size() {
342        assert_eq!(
343            std::mem::size_of::<TopologyMiniHeader>(),
344            TOPOLOGY_MINI_HEADER_SIZE
345        );
346        assert_eq!(std::mem::offset_of!(TopologyMiniHeader, vertex_count), 0);
347        assert_eq!(std::mem::offset_of!(TopologyMiniHeader, face_count), 4);
348        assert_eq!(std::mem::offset_of!(TopologyMiniHeader, half_edge_count), 8);
349        assert_eq!(
350            std::mem::offset_of!(TopologyMiniHeader, boundary_loop_count),
351            12
352        );
353        assert_eq!(
354            std::mem::offset_of!(TopologyMiniHeader, component_count),
355            16
356        );
357        assert_eq!(
358            std::mem::offset_of!(TopologyMiniHeader, euler_characteristic),
359            20
360        );
361        assert_eq!(std::mem::offset_of!(TopologyMiniHeader, genus), 24);
362        assert_eq!(std::mem::offset_of!(TopologyMiniHeader, reserved_u32), 28);
363    }
364
365    #[test]
366    fn round_trip_tetrahedron() {
367        let (edges, vc, fc) = build_he(4, &[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 2]]);
368        let need = encoded_len(vc, fc, edges.len() as u32);
369        let mut buf = vec![0u8; need];
370        let n = encode_topology_section(vc, fc, &edges, &mut buf).unwrap();
371        assert_eq!(n, need);
372
373        let back = decode_topology_section(&buf).unwrap();
374        assert_eq!(back.header.vertex_count, 4);
375        assert_eq!(back.header.face_count, 4);
376        assert_eq!(back.header.half_edge_count, 12);
377        assert_eq!(back.header.boundary_loop_count, 0);
378        assert_eq!(back.header.component_count, 1);
379        assert_eq!(back.header.euler_characteristic, 2);
380        assert_eq!(back.header.genus, 0);
381        assert_eq!(back.half_edges, edges);
382        assert_eq!(back.v_offsets.len(), 5);
383        assert_eq!(back.v_neighbours.len(), 12);
384        assert_eq!(back.f_offsets.len(), 5);
385        assert_eq!(back.f_neighbours.len(), 12);
386    }
387
388    #[test]
389    fn round_trip_single_triangle() {
390        let (edges, vc, fc) = build_he(3, &[[0, 1, 2]]);
391        let need = encoded_len(vc, fc, edges.len() as u32);
392        let mut buf = vec![0u8; need];
393        encode_topology_section(vc, fc, &edges, &mut buf).unwrap();
394        let back = decode_topology_section(&buf).unwrap();
395        assert_eq!(back.header.boundary_loop_count, 1);
396        assert_eq!(back.header.euler_characteristic, 1);
397        assert_eq!(back.header.genus, 0);
398        assert_eq!(back.half_edges, edges);
399    }
400
401    #[test]
402    fn determinism_two_encodes_byte_identical() {
403        let (edges, vc, fc) = build_he(4, &[[0, 1, 2], [2, 1, 3]]);
404        let need = encoded_len(vc, fc, edges.len() as u32);
405        let mut a = vec![0u8; need];
406        let mut b = vec![0u8; need];
407        encode_topology_section(vc, fc, &edges, &mut a).unwrap();
408        encode_topology_section(vc, fc, &edges, &mut b).unwrap();
409        assert_eq!(a, b);
410    }
411
412    #[test]
413    fn rejects_non_zero_reserved() {
414        let (edges, vc, fc) = build_he(3, &[[0, 1, 2]]);
415        let need = encoded_len(vc, fc, edges.len() as u32);
416        let mut buf = vec![0u8; need];
417        encode_topology_section(vc, fc, &edges, &mut buf).unwrap();
418        buf[28] = 1; // reserved_u32
419        assert!(decode_topology_section(&buf).is_err());
420    }
421
422    #[test]
423    fn rejects_truncated_payload() {
424        let (edges, vc, fc) = build_he(3, &[[0, 1, 2]]);
425        let need = encoded_len(vc, fc, edges.len() as u32);
426        let mut buf = vec![0u8; need];
427        encode_topology_section(vc, fc, &edges, &mut buf).unwrap();
428        buf.truncate(TOPOLOGY_MINI_HEADER_SIZE + 4);
429        assert!(decode_topology_section(&buf).is_err());
430    }
431
432    #[test]
433    fn topology_section_round_trips_through_10d_container_with_crc() {
434        let (edges, vc, fc) = build_he(4, &[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 2]]);
435        let need = encoded_len(vc, fc, edges.len() as u32);
436        let mut topo_payload = vec![0u8; need];
437        encode_topology_section(vc, fc, &edges, &mut topo_payload).unwrap();
438
439        let h = Container10dHeader::proposed();
440        let inputs = [SectionInput {
441            section_type: SectionType::Topology,
442            alignment_tier: AlignmentTier::Word,
443            stride: 0,
444            element_count: 0,
445            payload: &topo_payload,
446        }];
447        let mut out = vec![0u8; 1024];
448        let n = encode_container(&h, &inputs, &mut out).unwrap();
449        seal_whole_file_crc32c(&mut out[..n]);
450        verify_whole_file_crc32c(&mut out[..n]).unwrap();
451
452        let parsed_h = Container10dHeader::parse(&out[..n]).unwrap();
453        let descs = parse_section_table(&out[..n], &parsed_h).unwrap();
454        assert_eq!(descs.len(), 1);
455        assert_eq!(descs[0].section_type, SectionType::Topology as u8);
456
457        let p_off = descs[0].byte_offset as usize;
458        let p_len = descs[0].byte_length as usize;
459        let back = decode_topology_section(&out[p_off..p_off + p_len]).unwrap();
460        assert_eq!(back.half_edges, edges);
461        assert_eq!(back.header.vertex_count, 4);
462        assert_eq!(back.header.face_count, 4);
463    }
464
465    #[test]
466    fn flipped_payload_bit_caught_by_per_section_crc() {
467        let (edges, vc, fc) = build_he(4, &[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 2]]);
468        let need = encoded_len(vc, fc, edges.len() as u32);
469        let mut topo_payload = vec![0u8; need];
470        encode_topology_section(vc, fc, &edges, &mut topo_payload).unwrap();
471
472        let h = Container10dHeader::proposed();
473        let inputs = [SectionInput {
474            section_type: SectionType::Topology,
475            alignment_tier: AlignmentTier::Word,
476            stride: 0,
477            element_count: 0,
478            payload: &topo_payload,
479        }];
480        let mut out = vec![0u8; 1024];
481        let n = encode_container(&h, &inputs, &mut out).unwrap();
482        let parsed_h = Container10dHeader::parse(&out[..n]).unwrap();
483        let descs = parse_section_table(&out[..n], &parsed_h).unwrap();
484        let p_off = descs[0].byte_offset as usize;
485        out[p_off + TOPOLOGY_MINI_HEADER_SIZE + 1] ^= 0x01;
486        let err = parse_section_table(&out[..n], &parsed_h).unwrap_err();
487        assert!(matches!(
488            err,
489            crate::container_10d::section::SectionTableError::CrcMismatch { .. }
490        ));
491    }
492}
qualia_core_db/container_10d/topology_section.rs

qualia_core_db/container_10d/
topology_section.rs
