Skip to main content

qualia_core_db/q42/volume/
index.rs

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