Skip to main content

qualia_core_db/bundle/stream/protection/
coverage.rs

1//! Bounded source interval construction and a separate exact partition validator.
2use super::ProtectionError as Error;
3use crate::bundle::stream::descriptor::MAX_ENTRIES;
4use crate::bundle::stream::index::AdmittedIndex;
5use crate::crypto::network::object_stream::{MAX_METADATA, MAX_OBJECTS, MAX_OBJECT_BYTES};
6const _: () = assert!(MAX_ENTRIES == 4096 && MAX_OBJECTS == 2 * MAX_ENTRIES + 1);
7
8/// Private original index geometry; not a public descriptor row.
9#[derive(Clone, Copy, PartialEq, Eq)]
10pub struct EntryRange {
11    offset: u64,
12    length: u64,
13}
14impl EntryRange {
15    pub const EMPTY: Self = Self {
16        offset: 0,
17        length: 0,
18    };
19    pub(super) const fn new(offset: u64, length: u64) -> Self {
20        Self { offset, length }
21    }
22}
23#[derive(Clone, Copy, PartialEq, Eq)]
24pub enum ObjectKind {
25    Entry(u32),
26    Gap,
27}
28/// This contains private offsets/ordinals. It intentionally has no Debug implementation.
29#[derive(Clone, Copy, PartialEq, Eq)]
30pub struct SourceObject {
31    kind: ObjectKind,
32    range: EntryRange,
33}
34impl SourceObject {
35    pub const EMPTY: Self = Self {
36        kind: ObjectKind::Gap,
37        range: EntryRange::EMPTY,
38    };
39    pub(super) const fn entry(ordinal: u32, range: EntryRange) -> Self {
40        Self {
41            kind: ObjectKind::Entry(ordinal),
42            range,
43        }
44    }
45    pub(super) const fn gap(offset: u64, length: u64) -> Self {
46        Self {
47            kind: ObjectKind::Gap,
48            range: EntryRange::new(offset, length),
49        }
50    }
51    pub const fn kind(&self) -> ObjectKind {
52        self.kind
53    }
54    pub const fn offset(&self) -> u64 {
55        self.range.offset
56    }
57    pub const fn length(&self) -> u64 {
58        self.range.length
59    }
60}
61
62/// Fixed private metadata framing; checked before any metadata/key allocation.
63pub(super) fn metadata_length(objects: usize, index_length: u64) -> Result<usize, Error> {
64    if objects > MAX_OBJECTS {
65        return Err(Error::Limit);
66    }
67    let rows = u64::try_from(objects).map_err(|_| Error::Overflow)?;
68    let length = rows
69        .checked_mul(108)
70        .and_then(|n| n.checked_add(288 + 64))
71        .and_then(|n| n.checked_add(index_length))
72        .ok_or(Error::Overflow)?;
73    if length > MAX_METADATA {
74        return Err(Error::Limit);
75    }
76    usize::try_from(length).map_err(|_| Error::Overflow)
77}
78
79/// Object order is original index order followed by ascending maximal gaps.
80/// Later opaque-ID assignment must retain this private association.
81pub(super) fn prepare(
82    index: &AdmittedIndex<'_>,
83    entries: &mut [EntryRange],
84    objects: &mut [SourceObject],
85    order: &mut [u32],
86) -> Result<usize, Error> {
87    let count = index.sizing().entry_count();
88    if count > MAX_ENTRIES {
89        return Err(Error::Limit);
90    }
91    let entries = entries.get_mut(..count).ok_or(Error::Capacity)?;
92    let sorted = order.get_mut(..count).ok_or(Error::Capacity)?;
93    let mut found = 0;
94    for (ordinal, row) in index.entries().enumerate() {
95        let row = row.map_err(|_| Error::Source)?;
96        let out = entries.get_mut(ordinal).ok_or(Error::Coverage)?;
97        *out = EntryRange::new(row.offset(), row.length());
98        sorted[ordinal] = u32::try_from(ordinal).map_err(|_| Error::Overflow)?;
99        found += 1;
100    }
101    if found != count {
102        return Err(Error::Coverage);
103    }
104    sorted.sort_unstable_by_key(|i| (entries[*i as usize].offset, entries[*i as usize].length, *i));
105    let end = index.header().index_offset();
106    let mut frontier = 64;
107    let mut gaps = 0usize;
108    for ordinal in sorted.iter() {
109        let row = entries[*ordinal as usize];
110        if row.length == 0 {
111            continue;
112        }
113        if row.offset < frontier {
114            return Err(Error::Coverage);
115        }
116        if row.offset > frontier {
117            gaps += 1;
118        }
119        frontier = row.offset.checked_add(row.length).ok_or(Error::Overflow)?;
120        if frontier > end {
121            return Err(Error::Coverage);
122        }
123    }
124    if frontier < end {
125        gaps += 1;
126    }
127    let total = count.checked_add(gaps).ok_or(Error::Overflow)?;
128    if total > MAX_OBJECTS {
129        return Err(Error::Limit);
130    }
131    if order.len() < total || objects.len() < total {
132        return Err(Error::Capacity);
133    }
134    // Reborrow after capacity checks: sort order still contains the source ordinals.
135    for (ordinal, row) in entries.iter().enumerate() {
136        objects[ordinal] = SourceObject::entry(ordinal as u32, *row);
137    }
138    frontier = 64;
139    let mut next = count;
140    for ordinal in &order[..count] {
141        let row = entries[*ordinal as usize];
142        if row.length == 0 {
143            continue;
144        }
145        if row.offset > frontier {
146            objects[next] = SourceObject::gap(frontier, row.offset - frontier);
147            next += 1;
148        }
149        frontier = row.offset.checked_add(row.length).ok_or(Error::Overflow)?;
150    }
151    if frontier < end {
152        objects[next] = SourceObject::gap(frontier, end - frontier);
153        next += 1;
154    }
155    if next != total {
156        return Err(Error::Coverage);
157    }
158    validate(end, entries, &objects[..total], order)?;
159    Ok(total)
160}
161
162/// Independently checks a proposed mapping against original admitted ordinal ranges.
163/// Sorting uses caller scratch, with a fixed 4096-bit ordinal set; no recursion/heap.
164pub(super) fn validate(
165    index_offset: u64,
166    entries: &[EntryRange],
167    objects: &[SourceObject],
168    order: &mut [u32],
169) -> Result<(), Error> {
170    if entries.len() > MAX_ENTRIES || objects.len() > MAX_OBJECTS || index_offset > MAX_OBJECT_BYTES
171    {
172        return Err(Error::Limit);
173    }
174    if index_offset < 64 {
175        return Err(Error::Coverage);
176    }
177    let order = order.get_mut(..objects.len()).ok_or(Error::Capacity)?;
178    let mut seen = [0u64; MAX_ENTRIES / 64];
179    let mut entry_count = 0;
180    for (i, row) in objects.iter().enumerate() {
181        let end = row
182            .offset()
183            .checked_add(row.length())
184            .ok_or(Error::Overflow)?;
185        if row.offset() < 64 || end > index_offset {
186            return Err(Error::Coverage);
187        }
188        match row.kind {
189            ObjectKind::Entry(ordinal) => {
190                let ordinal = usize::try_from(ordinal).map_err(|_| Error::Overflow)?;
191                let expected = entries.get(ordinal).ok_or(Error::Coverage)?;
192                let bit = 1u64 << (ordinal % 64);
193                if row.range != *expected || seen[ordinal / 64] & bit != 0 {
194                    return Err(Error::Coverage);
195                }
196                seen[ordinal / 64] |= bit;
197                entry_count += 1;
198            }
199            ObjectKind::Gap if row.length() == 0 => return Err(Error::Coverage),
200            ObjectKind::Gap => {}
201        }
202        order[i] = i as u32;
203    }
204    if entry_count != entries.len() {
205        return Err(Error::Coverage);
206    }
207    order.sort_unstable_by_key(|i| {
208        (
209            objects[*i as usize].offset(),
210            objects[*i as usize].length(),
211            *i,
212        )
213    });
214    let mut frontier = 64;
215    let mut previous_gap = false;
216    for i in order {
217        let row = objects[*i as usize];
218        // Empty entries may sit inside occupied intervals or gaps. Neither changes
219        // the frontier nor separates two adjacent positive gap objects.
220        if row.length() == 0 {
221            continue;
222        }
223        if row.offset() != frontier {
224            return Err(Error::Coverage);
225        }
226        let gap = row.kind == ObjectKind::Gap;
227        if gap && previous_gap {
228            return Err(Error::Coverage);
229        }
230        previous_gap = gap;
231        frontier = frontier.checked_add(row.length()).ok_or(Error::Overflow)?;
232    }
233    if frontier != index_offset {
234        return Err(Error::Coverage);
235    }
236    Ok(())
237}