qualia_core_db/q42/volume/
index.rs1use 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#[derive(Clone, Copy, Debug, Eq, PartialEq)]
21pub struct BidxBlockRange {
22 pub start: usize,
23 pub end: usize,
24}
25
26impl BidxBlockRange {
27 #[inline]
28 pub fn len(self) -> usize {
30 self.end - self.start
31 }
32
33 #[inline]
34 pub fn is_empty(self) -> bool {
36 self.start == self.end
37 }
38}
39
40#[derive(Clone, Copy, Debug, Eq, PartialEq)]
42pub struct BidxMatchPage {
43 pub range: BidxBlockRange,
45 pub returned: usize,
47 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
90pub(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#[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
159pub(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 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 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#[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}