qualia_core_db/q42/volume/
index.rs

1//! Checked, bounded access to the object-range BIDX.
2
3use std::io;
4
5use super::super::{
6    BIDX_MAGIC, FIELD_RANGE_INDEX_ENTRY_BYTES, FIELD_RANGE_INDEX_HEADER_BYTES,
7    FIELD_RANGE_INDEX_MAGIC,
8};
9
10const BIDX_HEADER_BYTES: usize = 16;
11const BIDX_ENTRY_BYTES: usize = 16;
12
13/// A contiguous half-open block interval selected by an object hash.
14///
15/// The interval can be much larger than a caller output buffer.  Use
16/// [`BidxMatchPage`] to enumerate it without allocating one `Vec` entry per
17/// matching block.
18#[derive(Clone, Copy, Debug, Eq, PartialEq)]
19pub struct BidxBlockRange {
20    pub start: usize,
21    pub end: usize,
22}
23
24impl BidxBlockRange {
25    #[inline]
26    pub fn len(self) -> usize {
27        self.end - self.start
28    }
29
30    #[inline]
31    pub fn is_empty(self) -> bool {
32        self.start == self.end
33    }
34}
35
36/// One caller-buffered page from a BIDX match interval.
37#[derive(Clone, Copy, Debug, Eq, PartialEq)]
38pub struct BidxMatchPage {
39    /// The complete matching interval, for accounting and range coalescing.
40    pub range: BidxBlockRange,
41    /// Number of block indices written into the caller buffer.
42    pub returned: usize,
43    /// Resume with this offset relative to `range.start`; `None` means done.
44    pub next_cursor: Option<usize>,
45}
46
47fn invalid(message: impl Into<String>) -> io::Error {
48    io::Error::new(io::ErrorKind::InvalidData, message.into())
49}
50
51fn layout(bidx: &[u8]) -> io::Result<usize> {
52    if bidx.len() < BIDX_HEADER_BYTES {
53        return Err(invalid("BIDX section is shorter than its header"));
54    }
55    if bidx[0..4] != BIDX_MAGIC {
56        return Err(invalid("invalid BIDX magic"));
57    }
58    let version = u32::from_le_bytes(bidx[4..8].try_into().unwrap());
59    if version != 1 {
60        return Err(invalid(format!("unsupported BIDX version {version}")));
61    }
62    let block_count = u32::from_le_bytes(bidx[8..12].try_into().unwrap()) as usize;
63    let expected = BIDX_HEADER_BYTES
64        .checked_add(
65            block_count
66                .checked_mul(BIDX_ENTRY_BYTES)
67                .ok_or_else(|| invalid("BIDX entry count overflows usize"))?,
68        )
69        .ok_or_else(|| invalid("BIDX length overflows usize"))?;
70    if bidx.len() != expected {
71        return Err(invalid(format!(
72            "BIDX length {} does not match {block_count} entries ({expected} bytes)",
73            bidx.len()
74        )));
75    }
76    Ok(block_count)
77}
78
79fn range_at(bidx: &[u8], index: usize) -> (u64, u64) {
80    let offset = BIDX_HEADER_BYTES + index * BIDX_ENTRY_BYTES;
81    let min = u64::from_le_bytes(bidx[offset..offset + 8].try_into().unwrap());
82    let max = u64::from_le_bytes(bidx[offset + 8..offset + 16].try_into().unwrap());
83    (min, max)
84}
85
86/// Validate the complete BIDX layout and the monotonicity required for binary
87/// range lookup.  Equal boundaries are valid: a high-frequency object may span
88/// many adjacent SuperBlocks.
89pub(crate) fn validate_bidx(bidx: &[u8], expected_blocks: usize) -> io::Result<()> {
90    let block_count = layout(bidx)?;
91    if block_count != expected_blocks {
92        return Err(invalid(format!(
93            "BIDX block count {block_count} does not match directory count {expected_blocks}"
94        )));
95    }
96
97    let mut previous_min = 0u64;
98    let mut previous_max = 0u64;
99    for index in 0..block_count {
100        let (min, max) = range_at(bidx, index);
101        if min > max {
102            return Err(invalid(format!("BIDX entry {index} has min > max")));
103        }
104        if index != 0 && (min < previous_min || max < previous_max) {
105            return Err(invalid(format!(
106                "BIDX entry {index} is not monotonic by min/max object hash"
107            )));
108        }
109        previous_min = min;
110        previous_max = max;
111    }
112    Ok(())
113}
114
115pub(crate) fn validate_field_range_index(bytes: &[u8], expected_blocks: usize) -> io::Result<()> {
116    let expected = FIELD_RANGE_INDEX_HEADER_BYTES
117        .checked_add(
118            expected_blocks
119                .checked_mul(FIELD_RANGE_INDEX_ENTRY_BYTES)
120                .ok_or_else(|| invalid("field-range index length overflows"))?,
121        )
122        .ok_or_else(|| invalid("field-range index length overflows"))?;
123    if bytes.len() != expected {
124        return Err(invalid(format!(
125            "field-range index is {} bytes, expected {expected}",
126            bytes.len()
127        )));
128    }
129    if bytes[0..4] != FIELD_RANGE_INDEX_MAGIC {
130        return Err(invalid("field-range index has bad magic"));
131    }
132    if u32::from_le_bytes(bytes[4..8].try_into().unwrap()) != 1 {
133        return Err(invalid("unsupported field-range index version"));
134    }
135    if u32::from_le_bytes(bytes[8..12].try_into().unwrap()) as usize != expected_blocks {
136        return Err(invalid("field-range index block count mismatch"));
137    }
138    for index in 0..expected_blocks {
139        let offset = FIELD_RANGE_INDEX_HEADER_BYTES + index * FIELD_RANGE_INDEX_ENTRY_BYTES;
140        for field in 0..3 {
141            let min_offset = offset + field * 16;
142            let min = u64::from_le_bytes(bytes[min_offset..min_offset + 8].try_into().unwrap());
143            let max =
144                u64::from_le_bytes(bytes[min_offset + 8..min_offset + 16].try_into().unwrap());
145            if min > max {
146                return Err(invalid("field-range index has an inverted range"));
147            }
148        }
149    }
150    Ok(())
151}
152
153/// Return the full contiguous BIDX interval that can contain `object_hash`.
154///
155/// The caller must use a BIDX already validated by [`validate_bidx`].  This
156/// function still validates its header/length so standalone callers fail closed
157/// on truncated data.
158pub(crate) fn bidx_block_range_for_hash(
159    bidx: &[u8],
160    object_hash: u64,
161) -> io::Result<Option<BidxBlockRange>> {
162    let block_count = layout(bidx)?;
163    validate_bidx(bidx, block_count)?;
164    if block_count == 0 {
165        return Ok(None);
166    }
167
168    // First block whose maximum can contain the hash.
169    let mut lo = 0usize;
170    let mut hi = block_count;
171    while lo < hi {
172        let mid = lo + (hi - lo) / 2;
173        if range_at(bidx, mid).1 < object_hash {
174            lo = mid + 1;
175        } else {
176            hi = mid;
177        }
178    }
179    let start = lo;
180    if start == block_count || range_at(bidx, start).0 > object_hash {
181        return Ok(None);
182    }
183
184    // First block whose minimum is strictly greater than the hash.
185    lo = start;
186    hi = block_count;
187    while lo < hi {
188        let mid = lo + (hi - lo) / 2;
189        if range_at(bidx, mid).0 <= object_hash {
190            lo = mid + 1;
191        } else {
192            hi = mid;
193        }
194    }
195
196    Ok(Some(BidxBlockRange { start, end: lo }))
197}
198
199/// Fill one bounded page of matching BIDX block indices.
200pub(crate) fn bidx_blocks_for_hash_into(
201    bidx: &[u8],
202    object_hash: u64,
203    cursor: usize,
204    out: &mut [usize],
205) -> io::Result<Option<BidxMatchPage>> {
206    let Some(range) = bidx_block_range_for_hash(bidx, object_hash)? else {
207        return Ok(None);
208    };
209    if out.is_empty() && cursor < range.len() {
210        return Err(io::Error::new(
211            io::ErrorKind::InvalidInput,
212            "BIDX page buffer must contain at least one block index",
213        ));
214    }
215    if cursor > range.len() {
216        return Err(io::Error::new(
217            io::ErrorKind::InvalidInput,
218            "BIDX cursor is beyond the matching interval",
219        ));
220    }
221    let remaining = range.len() - cursor;
222    let returned = remaining.min(out.len());
223    for (offset, slot) in out.iter_mut().take(returned).enumerate() {
224        *slot = range.start + cursor + offset;
225    }
226    let next = cursor + returned;
227    Ok(Some(BidxMatchPage {
228        range,
229        returned,
230        next_cursor: (next < range.len()).then_some(next),
231    }))
232}
qualia_core_db/q42/volume/index.rs

qualia_core_db/q42/volume/
index.rs
