1use byteorder::{BigEndian, ReadBytesExt, WriteBytesExt};
2use sha2::{Digest, Sha256};
3use std::io::{Read, Write};
4
5use crate::error::{AhuError, Result};
6
7pub const INDEX_RECORD_SIZE: usize = 48;
8
9bitflags::bitflags! {
10 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
11 pub struct IndexFlags: u16 {
12 const MULTI = 0b0000_0000_0000_0001;
13 const ALIAS = 0b0000_0000_0000_0010;
14 const TOMBSTONE = 0b0000_0000_0000_0100;
15 }
16}
17
18pub const ALG_DISC_DEFAULT: u16 = 0;
32pub const ALG_DISC_ML_DSA_44: u16 = 2;
33pub const ALG_DISC_ML_DSA_65: u16 = 3;
34pub const ALG_DISC_ML_DSA_87: u16 = 4;
35
36#[derive(Debug, Clone, PartialEq, Eq)]
37pub struct IndexRecord {
38 pub entry_key: [u8; 32],
39 pub data_offset: u64,
40 pub data_length: u32,
41 pub flags: IndexFlags,
42 pub discriminator: u16,
43}
44
45impl IndexRecord {
46 pub fn read_from<R: Read>(reader: &mut R) -> Result<Self> {
47 let mut entry_key = [0u8; 32];
48 reader.read_exact(&mut entry_key)?;
49 let data_offset = reader.read_u64::<BigEndian>()?;
50 let data_length = reader.read_u32::<BigEndian>()?;
51 let flags_raw = reader.read_u16::<BigEndian>()?;
52 let discriminator = reader.read_u16::<BigEndian>()?;
53 let flags = IndexFlags::from_bits_truncate(flags_raw);
54
55 Ok(IndexRecord {
56 entry_key,
57 data_offset,
58 data_length,
59 flags,
60 discriminator,
61 })
62 }
63
64 pub fn write_to<W: Write>(&self, writer: &mut W) -> Result<()> {
65 writer.write_all(&self.entry_key)?;
66 writer.write_u64::<BigEndian>(self.data_offset)?;
67 writer.write_u32::<BigEndian>(self.data_length)?;
68 writer.write_u16::<BigEndian>(self.flags.bits())?;
69 writer.write_u16::<BigEndian>(self.discriminator)?;
70 Ok(())
71 }
72
73 pub fn is_tombstone(&self) -> bool {
74 self.flags.contains(IndexFlags::TOMBSTONE)
75 }
76
77 pub fn is_alias(&self) -> bool {
78 self.flags.contains(IndexFlags::ALIAS)
79 }
80
81 pub fn is_multi(&self) -> bool {
82 self.flags.contains(IndexFlags::MULTI)
83 }
84}
85
86pub fn compute_entry_key(certid_der: &[u8]) -> [u8; 32] {
87 let mut hasher = Sha256::new();
88 hasher.update(certid_der);
89 hasher.finalize().into()
90}
91
92pub fn validate_sort_order(records: &[IndexRecord]) -> Result<()> {
97 for i in 0..records.len().saturating_sub(1) {
98 let key_ord = records[i].entry_key.cmp(&records[i + 1].entry_key);
99 match key_ord {
100 std::cmp::Ordering::Greater => {
101 return Err(AhuError::IndexNotSorted {
102 index: i,
103 key: hex::encode(records[i].entry_key),
104 next_key: hex::encode(records[i + 1].entry_key),
105 });
106 }
107 std::cmp::Ordering::Equal => {
108 match records[i].discriminator.cmp(&records[i + 1].discriminator) {
109 std::cmp::Ordering::Equal => {
110 return Err(AhuError::DuplicateEntryKey {
111 index: i,
112 key: hex::encode(records[i].entry_key),
113 });
114 }
115 std::cmp::Ordering::Greater => {
116 return Err(AhuError::IndexNotSorted {
117 index: i,
118 key: hex::encode(records[i].entry_key),
119 next_key: hex::encode(records[i + 1].entry_key),
120 });
121 }
122 std::cmp::Ordering::Less => {}
123 }
124 }
125 std::cmp::Ordering::Less => {}
126 }
127 }
128 Ok(())
129}
130
131pub fn binary_search(records: &[IndexRecord], entry_key: &[u8; 32]) -> Option<usize> {
133 binary_search_with_discriminator(records, entry_key, ALG_DISC_DEFAULT)
134}
135
136pub fn binary_search_with_discriminator(
138 records: &[IndexRecord],
139 entry_key: &[u8; 32],
140 discriminator: u16,
141) -> Option<usize> {
142 records
143 .binary_search_by(|r| {
144 r.entry_key
145 .cmp(entry_key)
146 .then(r.discriminator.cmp(&discriminator))
147 })
148 .ok()
149}
150
151pub fn binary_search_preferred(
155 records: &[IndexRecord],
156 entry_key: &[u8; 32],
157 preferences: &[u16],
158) -> Option<usize> {
159 for &disc in preferences {
160 if let Some(idx) = binary_search_with_discriminator(records, entry_key, disc) {
161 return Some(idx);
162 }
163 }
164 if !preferences.contains(&ALG_DISC_DEFAULT) {
165 binary_search_with_discriminator(records, entry_key, ALG_DISC_DEFAULT)
166 } else {
167 None
168 }
169}
170
171#[cfg(test)]
172mod tests {
173 use super::*;
174 use std::io::Cursor;
175
176 fn rec(key_byte: u8, disc: u16) -> IndexRecord {
177 IndexRecord {
178 entry_key: {
179 let mut k = [0u8; 32];
180 k[0] = key_byte;
181 k
182 },
183 data_offset: 0,
184 data_length: 100,
185 flags: IndexFlags::empty(),
186 discriminator: disc,
187 }
188 }
189
190 #[test]
191 fn record_round_trip() {
192 let r = IndexRecord {
193 entry_key: [0xAB; 32],
194 data_offset: 1024,
195 data_length: 512,
196 flags: IndexFlags::MULTI | IndexFlags::ALIAS,
197 discriminator: 0,
198 };
199
200 let mut buf = Vec::new();
201 r.write_to(&mut buf).unwrap();
202 assert_eq!(buf.len(), INDEX_RECORD_SIZE);
203
204 let mut cursor = Cursor::new(&buf);
205 let read_back = IndexRecord::read_from(&mut cursor).unwrap();
206 assert_eq!(r, read_back);
207 }
208
209 #[test]
210 fn record_round_trip_with_discriminator() {
211 let r = IndexRecord {
212 entry_key: [0xCD; 32],
213 data_offset: 2048,
214 data_length: 256,
215 flags: IndexFlags::empty(),
216 discriminator: ALG_DISC_ML_DSA_87,
217 };
218
219 let mut buf = Vec::new();
220 r.write_to(&mut buf).unwrap();
221
222 let mut cursor = Cursor::new(&buf);
223 let read_back = IndexRecord::read_from(&mut cursor).unwrap();
224 assert_eq!(r, read_back);
225 assert_eq!(read_back.discriminator, ALG_DISC_ML_DSA_87);
226 }
227
228 #[test]
229 fn sort_order_validation() {
230 let r1 = rec(0x01, 0);
231 let r2 = rec(0x02, 0);
232
233 validate_sort_order(&[r1.clone(), r2.clone()]).unwrap();
234
235 let err = validate_sort_order(&[r2, r1]).unwrap_err();
236 assert!(matches!(err, AhuError::IndexNotSorted { .. }));
237 }
238
239 #[test]
240 fn sort_order_same_key_different_discriminators() {
241 let r1 = rec(0x01, 0);
242 let r2 = rec(0x01, ALG_DISC_ML_DSA_87);
243 validate_sort_order(&[r1, r2]).unwrap();
244 }
245
246 #[test]
247 fn sort_order_same_key_same_discriminator_rejected() {
248 let r1 = rec(0x01, ALG_DISC_ML_DSA_87);
249 let r2 = rec(0x01, ALG_DISC_ML_DSA_87);
250 let err = validate_sort_order(&[r1, r2]).unwrap_err();
251 assert!(matches!(err, AhuError::DuplicateEntryKey { .. }));
252 }
253
254 #[test]
255 fn sort_order_same_key_wrong_discriminator_order() {
256 let r1 = rec(0x01, ALG_DISC_ML_DSA_87);
257 let r2 = rec(0x01, 0);
258 let err = validate_sort_order(&[r1, r2]).unwrap_err();
259 assert!(matches!(err, AhuError::IndexNotSorted { .. }));
260 }
261
262 #[test]
263 fn binary_search_finds_key() {
264 let records: Vec<IndexRecord> = (0..10u8).map(|i| rec(i * 10, 0)).collect();
265
266 let mut target = [0u8; 32];
267 target[0] = 50;
268 assert_eq!(binary_search(&records, &target), Some(5));
269
270 target[0] = 55;
271 assert_eq!(binary_search(&records, &target), None);
272 }
273
274 #[test]
275 fn binary_search_with_discriminator_finds_variant() {
276 let records = vec![rec(0x01, 0), rec(0x01, ALG_DISC_ML_DSA_87), rec(0x02, 0)];
277
278 let mut key = [0u8; 32];
279 key[0] = 0x01;
280
281 assert_eq!(binary_search(&records, &key), Some(0));
282 assert_eq!(
283 binary_search_with_discriminator(&records, &key, ALG_DISC_ML_DSA_87),
284 Some(1)
285 );
286 assert_eq!(
287 binary_search_with_discriminator(&records, &key, ALG_DISC_ML_DSA_44),
288 None
289 );
290 }
291
292 #[test]
293 fn binary_search_preferred_tries_in_order() {
294 let records = vec![
295 rec(0x01, 0),
296 rec(0x01, ALG_DISC_ML_DSA_87),
297 rec(0x02, 0),
298 rec(0x02, ALG_DISC_ML_DSA_87),
299 ];
300
301 let mut key = [0u8; 32];
302 key[0] = 0x01;
303
304 assert_eq!(
305 binary_search_preferred(&records, &key, &[ALG_DISC_ML_DSA_87]),
306 Some(1)
307 );
308 assert_eq!(
309 binary_search_preferred(&records, &key, &[ALG_DISC_ML_DSA_44, ALG_DISC_ML_DSA_87]),
310 Some(1)
311 );
312 assert_eq!(
314 binary_search_preferred(&records, &key, &[ALG_DISC_ML_DSA_44]),
315 Some(0)
316 );
317 assert_eq!(binary_search_preferred(&records, &key, &[]), Some(0));
319 }
320}