Skip to main content

ahu/
index.rs

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
18/// Algorithm discriminator — the u16 at index-record bytes 46–47
19/// (ahu-format-spec.md §2.4.1).
20///
21/// The discriminator distinguishes signature-algorithm variants of the same
22/// certificate. Records are sorted ascending by `(entry_key, discriminator)`
23/// and a duplicate pair is invalid. In single-algorithm bundles every record
24/// uses 0; in dual-algorithm bundles the classical response uses 0 and the
25/// post-quantum variant uses its algorithm-specific value.
26///
27/// Value 1 is unassigned in this profile. The decoder preserves any other
28/// u16 value and includes it in ordering, but preservation is not
29/// endorsement: an unknown value implies no support for the producer's
30/// intended signature algorithm.
31pub 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
92/// Validate that records are sorted ascending by `(entry_key, discriminator)`
93/// with no duplicate pair (ahu-format-spec.md §2.4.1). Equal entry keys must
94/// carry strictly ascending discriminators; a repeated pair is a
95/// `DuplicateEntryKey` error, any descending order an `IndexNotSorted` error.
96pub 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
131/// Search for a record with the given key and discriminator 0 (default).
132pub fn binary_search(records: &[IndexRecord], entry_key: &[u8; 32]) -> Option<usize> {
133    binary_search_with_discriminator(records, entry_key, ALG_DISC_DEFAULT)
134}
135
136/// Search for a record with the given key and specific discriminator.
137pub 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
151/// Search for the best-matching record given a list of preferred discriminators.
152/// Tries each discriminator in order; returns the first hit. Falls back to
153/// discriminator 0 if none of the preferences match.
154pub 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        // Falls back to default when preference not found
313        assert_eq!(
314            binary_search_preferred(&records, &key, &[ALG_DISC_ML_DSA_44]),
315            Some(0)
316        );
317        // Empty preferences → default
318        assert_eq!(binary_search_preferred(&records, &key, &[]), Some(0));
319    }
320}