qualia_core_db/bundle/stream/protection/
coverage.rs1use 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#[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#[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
62pub(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
79pub(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 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
162pub(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 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}