1use crate::container::header::HEADER_LEN;
32use crate::container::record::{RECORD_OVERHEAD, RecordTag};
33use crate::error::{Error, Result};
34use crate::limits::Limits;
35
36pub const SEEK_DIRECTORY_VERSION: u8 = 1;
38
39pub const SECTION_LOCATORS: u8 = 0x01;
41pub const SECTION_CLASS_INDEX: u8 = 0x02;
43pub const SECTION_CHANNEL_LENGTHS: u8 = 0x04;
45
46pub const SEEK_DIRECTORY_KNOWN_SECTION_FLAGS: u8 =
48 SECTION_LOCATORS | SECTION_CLASS_INDEX | SECTION_CHANNEL_LENGTHS;
49
50pub const SEEK_DIRECTORY_ALL_SECTIONS: u8 = SEEK_DIRECTORY_KNOWN_SECTION_FLAGS;
52
53pub const DIRECTORY_ENTRY_LEN: usize = 1 + 8 + 4;
55pub const CLASS_ENTRY_LEN: usize = 1 + 4 + 4;
57
58pub const CLASS_INDEX_TAGS: [RecordTag; 8] = [
63 RecordTag::Model,
64 RecordTag::EntropyChannel,
65 RecordTag::Object,
66 RecordTag::Graph,
67 RecordTag::ObservationIndex,
68 RecordTag::Checkpoint,
69 RecordTag::Integrity,
70 RecordTag::Trailer,
71];
72
73#[derive(Debug, Clone, Copy, PartialEq, Eq)]
76pub struct DirectoryEntry {
77 pub tag: u8,
79 pub offset: u64,
81 pub payload_len: u32,
83}
84
85#[derive(Debug, Clone, Copy, PartialEq, Eq)]
88pub struct ClassEntry {
89 pub tag: u8,
91 pub first: u32,
93 pub count: u32,
95}
96
97#[derive(Debug, Clone, PartialEq, Eq, Default)]
102pub struct SeekDirectory {
103 pub section_flags: u8,
105 pub entries: Vec<DirectoryEntry>,
107 pub classes: Vec<ClassEntry>,
109 pub channel_lengths: Vec<u64>,
112}
113
114#[derive(Debug, Clone, Copy, PartialEq, Eq)]
117pub struct RecordSite {
118 pub tag: u8,
120 pub offset: u64,
122 pub payload_len: u32,
124}
125
126impl SeekDirectory {
127 pub fn encode(&self) -> Result<Vec<u8>> {
133 if self.section_flags & !SEEK_DIRECTORY_KNOWN_SECTION_FLAGS != 0 {
134 return Err(Error::invalid_container(
135 "seek directory has unknown section flags",
136 ));
137 }
138 if self.section_flags & SECTION_LOCATORS == 0 && !self.entries.is_empty() {
139 return Err(Error::invalid_container(
140 "seek directory carries locators without the locator section flag",
141 ));
142 }
143 if self.section_flags & SECTION_CLASS_INDEX == 0 && !self.classes.is_empty() {
144 return Err(Error::invalid_container(
145 "seek directory carries classes without the class-index section flag",
146 ));
147 }
148 if self.section_flags & SECTION_CHANNEL_LENGTHS == 0 && !self.channel_lengths.is_empty() {
149 return Err(Error::invalid_container(
150 "seek directory carries channel lengths without the channel-lengths section flag",
151 ));
152 }
153
154 let mut out = Vec::new();
155 out.push(SEEK_DIRECTORY_VERSION);
156 out.push(self.section_flags);
157
158 if self.section_flags & SECTION_LOCATORS != 0 {
159 let count = u32::try_from(self.entries.len())
160 .map_err(|_| Error::resource_limit("seek directory entry_count exceeds u32"))?;
161 out.extend_from_slice(&count.to_le_bytes());
162 for e in &self.entries {
163 out.push(e.tag);
164 out.extend_from_slice(&e.offset.to_le_bytes());
165 out.extend_from_slice(&e.payload_len.to_le_bytes());
166 }
167 }
168 if self.section_flags & SECTION_CLASS_INDEX != 0 {
169 let count = u8::try_from(self.classes.len())
170 .map_err(|_| Error::resource_limit("seek directory class_count exceeds u8"))?;
171 out.push(count);
172 for c in &self.classes {
173 out.push(c.tag);
174 out.extend_from_slice(&c.first.to_le_bytes());
175 out.extend_from_slice(&c.count.to_le_bytes());
176 }
177 }
178 if self.section_flags & SECTION_CHANNEL_LENGTHS != 0 {
179 let count = u32::try_from(self.channel_lengths.len())
180 .map_err(|_| Error::resource_limit("seek directory channel_count exceeds u32"))?;
181 out.extend_from_slice(&count.to_le_bytes());
182 for &len in &self.channel_lengths {
183 out.extend_from_slice(&len.to_le_bytes());
184 }
185 }
186 Ok(out)
187 }
188
189 pub fn decode(bytes: &[u8], limits: Limits) -> Result<SeekDirectory> {
195 if bytes.len() as u64 > u64::from(limits.max_directory_bytes) {
196 return Err(Error::resource_limit(format!(
197 "seek directory payload {} exceeds limit {}",
198 bytes.len(),
199 limits.max_directory_bytes
200 )));
201 }
202 if bytes.len() < 2 {
203 return Err(Error::invalid_container("truncated SEEK_DIRECTORY header"));
204 }
205 let version = bytes[0];
206 if version != SEEK_DIRECTORY_VERSION {
207 return Err(Error::unsupported_version(format!(
208 "seek directory version {version} is not supported"
209 )));
210 }
211 let section_flags = bytes[1];
212 if section_flags & !SEEK_DIRECTORY_KNOWN_SECTION_FLAGS != 0 {
213 return Err(Error::invalid_container(
214 "SEEK_DIRECTORY has unknown section flags",
215 ));
216 }
217
218 let mut p = 2usize;
219
220 let mut entries = Vec::new();
221 if section_flags & SECTION_LOCATORS != 0 {
222 let count = read_u32(bytes, &mut p)?;
223 if count > limits.max_record_count {
224 return Err(Error::resource_limit(format!(
225 "seek directory entry_count {count} exceeds limit {}",
226 limits.max_record_count
227 )));
228 }
229 let count = count as usize;
230 require(bytes, p, count, DIRECTORY_ENTRY_LEN)?;
231 entries.reserve(count);
232 for _ in 0..count {
233 entries.push(DirectoryEntry {
234 tag: read_u8(bytes, &mut p)?,
235 offset: read_u64(bytes, &mut p)?,
236 payload_len: read_u32(bytes, &mut p)?,
237 });
238 }
239 }
240
241 let mut classes = Vec::new();
242 if section_flags & SECTION_CLASS_INDEX != 0 {
243 let count = read_u8(bytes, &mut p)? as usize;
244 require(bytes, p, count, CLASS_ENTRY_LEN)?;
245 classes.reserve(count);
246 for _ in 0..count {
247 classes.push(ClassEntry {
248 tag: read_u8(bytes, &mut p)?,
249 first: read_u32(bytes, &mut p)?,
250 count: read_u32(bytes, &mut p)?,
251 });
252 }
253 }
254
255 let mut channel_lengths = Vec::new();
256 if section_flags & SECTION_CHANNEL_LENGTHS != 0 {
257 let count = read_u32(bytes, &mut p)?;
258 if count > limits.max_channel_count {
259 return Err(Error::resource_limit(format!(
260 "seek directory channel_count {count} exceeds limit {}",
261 limits.max_channel_count
262 )));
263 }
264 let count = count as usize;
265 require(bytes, p, count, 8)?;
266 channel_lengths.reserve(count);
267 for _ in 0..count {
268 channel_lengths.push(read_u64(bytes, &mut p)?);
269 }
270 }
271
272 if p != bytes.len() {
273 return Err(Error::invalid_container(format!(
274 "SEEK_DIRECTORY has {} trailing bytes",
275 bytes.len() - p
276 )));
277 }
278
279 Ok(SeekDirectory {
280 section_flags,
281 entries,
282 classes,
283 channel_lengths,
284 })
285 }
286
287 pub fn validate(&self, records: &[RecordSite], file_len: u64, limits: Limits) -> Result<()> {
294 self.validate_structural(file_len, limits)?;
295
296 if self.section_flags & SECTION_LOCATORS == 0 {
297 return Err(Error::invalid_container(
298 "seek directory omits the locator section",
299 ));
300 }
301 if self.entries.len() != records.len() {
302 return Err(Error::invalid_container(format!(
303 "seek directory lists {} records but {} were framed",
304 self.entries.len(),
305 records.len()
306 )));
307 }
308 for (i, (entry, site)) in self.entries.iter().zip(records).enumerate() {
309 if entry.tag != site.tag
310 || entry.offset != site.offset
311 || entry.payload_len != site.payload_len
312 {
313 return Err(Error::invalid_container(format!(
314 "seek directory locator {i} disagrees with the record framing"
315 )));
316 }
317 }
318 Ok(())
319 }
320
321 pub fn validate_structural(&self, file_len: u64, limits: Limits) -> Result<()> {
326 if self.section_flags & !SEEK_DIRECTORY_KNOWN_SECTION_FLAGS != 0 {
327 return Err(Error::invalid_container(
328 "seek directory has unknown section flags",
329 ));
330 }
331 if self.entries.len() > limits.max_record_count as usize {
332 return Err(Error::resource_limit(
333 "seek directory entry_count exceeds the record-count limit",
334 ));
335 }
336 if self.channel_lengths.len() > limits.max_channel_count as usize {
337 return Err(Error::resource_limit(
338 "seek directory channel_count exceeds the channel-count limit",
339 ));
340 }
341
342 if self.section_flags & SECTION_LOCATORS != 0 {
343 if self.entries.is_empty() {
344 return Err(Error::invalid_container("seek directory has no locators"));
345 }
346 let first = self.entries[0];
348 if first.tag != RecordTag::Directory as u8 {
349 return Err(Error::invalid_container(
350 "seek directory locator 0 is not the DIRECTORY record",
351 ));
352 }
353 if first.offset != HEADER_LEN as u64 {
354 return Err(Error::invalid_container(
355 "seek directory locator 0 is not at the end of the header",
356 ));
357 }
358
359 let mut prev_end: Option<u64> = None;
362 for (i, e) in self.entries.iter().enumerate() {
363 let end = e
364 .offset
365 .checked_add(RECORD_OVERHEAD as u64)
366 .and_then(|v| v.checked_add(u64::from(e.payload_len)))
367 .ok_or_else(|| {
368 Error::invalid_container(format!(
369 "seek directory locator {i} end overflows"
370 ))
371 })?;
372 if let Some(pe) = prev_end
373 && e.offset != pe
374 {
375 return Err(Error::invalid_container(format!(
376 "seek directory locator {i} is not contiguous with the previous record"
377 )));
378 }
379 prev_end = Some(end);
380 }
381 let last = self.entries.last().expect("non-empty");
382 if last.tag != RecordTag::Trailer as u8 {
383 return Err(Error::invalid_container(
384 "seek directory does not end at the TRAILER record",
385 ));
386 }
387 match prev_end {
388 Some(end) if end == file_len => {}
389 Some(end) => {
390 return Err(Error::invalid_container(format!(
391 "seek directory ends at offset {end} but the file is {file_len} bytes"
392 )));
393 }
394 None => unreachable!("entries is non-empty"),
395 }
396
397 for tag in [
399 RecordTag::Graph,
400 RecordTag::ObservationIndex,
401 RecordTag::Checkpoint,
402 RecordTag::Integrity,
403 RecordTag::Trailer,
404 ] {
405 let n = self.entries.iter().filter(|e| e.tag == tag as u8).count();
406 if n > 1 {
407 return Err(Error::invalid_container(format!(
408 "seek directory lists the singleton {} {n} times",
409 tag.name()
410 )));
411 }
412 }
413 }
414
415 for (i, c) in self.classes.iter().enumerate() {
417 if c.count == 0 {
418 return Err(Error::invalid_container(format!(
419 "seek directory class entry {i} has a zero count"
420 )));
421 }
422 if self.classes[..i].iter().any(|o| o.tag == c.tag) {
423 return Err(Error::invalid_container(format!(
424 "seek directory has duplicate class entry for tag {:#04x}",
425 c.tag
426 )));
427 }
428 let first = c.first as usize;
429 let count = c.count as usize;
430 let end = first.checked_add(count).ok_or_else(|| {
431 Error::invalid_container(format!("seek directory class entry {i} range overflows"))
432 })?;
433 if end > self.entries.len() {
434 return Err(Error::invalid_container(format!(
435 "seek directory class entry {i} range {first}..{end} exceeds {} locators",
436 self.entries.len()
437 )));
438 }
439 if self.entries[first..end].iter().any(|e| e.tag != c.tag) {
440 return Err(Error::invalid_container(format!(
441 "seek directory class entry {i} spans a foreign tag"
442 )));
443 }
444 let scan_first = self.entries.iter().position(|e| e.tag == c.tag);
445 let scan_count = self.entries.iter().filter(|e| e.tag == c.tag).count();
446 if scan_first != Some(first) || scan_count != count {
447 return Err(Error::invalid_container(format!(
448 "seek directory class entry {i} disagrees with a scan of the locators"
449 )));
450 }
451 }
452
453 if self.section_flags & SECTION_CHANNEL_LENGTHS != 0 {
454 let channels = self
455 .entries
456 .iter()
457 .filter(|e| e.tag == RecordTag::EntropyChannel as u8)
458 .count();
459 if channels != self.channel_lengths.len() {
460 return Err(Error::invalid_container(format!(
461 "seek directory lists {} channel lengths for {channels} channel records",
462 self.channel_lengths.len()
463 )));
464 }
465 }
466
467 Ok(())
468 }
469}
470
471pub fn class_index(entries: &[DirectoryEntry]) -> Vec<ClassEntry> {
474 let mut classes = Vec::new();
475 for tag in CLASS_INDEX_TAGS {
476 let count = entries.iter().filter(|e| e.tag == tag as u8).count();
477 if count == 0 {
478 continue;
479 }
480 let first = entries
481 .iter()
482 .position(|e| e.tag == tag as u8)
483 .expect("count > 0 implies a first occurrence");
484 classes.push(ClassEntry {
485 tag: tag as u8,
486 first: first as u32,
487 count: count as u32,
488 });
489 }
490 classes
491}
492
493fn require(bytes: &[u8], p: usize, count: usize, entry_len: usize) -> Result<()> {
495 let need = count
496 .checked_mul(entry_len)
497 .ok_or_else(|| Error::invalid_container("SEEK_DIRECTORY section length overflow"))?;
498 let available = bytes
499 .len()
500 .checked_sub(p)
501 .ok_or_else(|| Error::invalid_container("SEEK_DIRECTORY cursor past end of payload"))?;
502 if need > available {
503 return Err(Error::invalid_container(format!(
504 "SEEK_DIRECTORY section needs {need} bytes but only {available} remain"
505 )));
506 }
507 Ok(())
508}
509
510fn read_u8(bytes: &[u8], p: &mut usize) -> Result<u8> {
511 let v = *bytes
512 .get(*p)
513 .ok_or_else(|| Error::invalid_container("truncated SEEK_DIRECTORY payload"))?;
514 *p += 1;
515 Ok(v)
516}
517
518fn read_u32(bytes: &[u8], p: &mut usize) -> Result<u32> {
519 let end = p
520 .checked_add(4)
521 .ok_or_else(|| Error::invalid_container("SEEK_DIRECTORY cursor overflow"))?;
522 let slice = bytes
523 .get(*p..end)
524 .ok_or_else(|| Error::invalid_container("truncated SEEK_DIRECTORY payload"))?;
525 *p = end;
526 Ok(u32::from_le_bytes([slice[0], slice[1], slice[2], slice[3]]))
527}
528
529fn read_u64(bytes: &[u8], p: &mut usize) -> Result<u64> {
530 let end = p
531 .checked_add(8)
532 .ok_or_else(|| Error::invalid_container("SEEK_DIRECTORY cursor overflow"))?;
533 let slice = bytes
534 .get(*p..end)
535 .ok_or_else(|| Error::invalid_container("truncated SEEK_DIRECTORY payload"))?;
536 *p = end;
537 Ok(u64::from_le_bytes([
538 slice[0], slice[1], slice[2], slice[3], slice[4], slice[5], slice[6], slice[7],
539 ]))
540}
541
542#[cfg(test)]
543mod tests {
544 use super::*;
545
546 fn entry(tag: RecordTag, offset: u64, payload_len: u32) -> DirectoryEntry {
547 DirectoryEntry {
548 tag: tag as u8,
549 offset,
550 payload_len,
551 }
552 }
553
554 fn sample_dir() -> SeekDirectory {
557 let entries = vec![
558 entry(RecordTag::Directory, HEADER_LEN as u64, 30),
559 entry(RecordTag::Integrity, 106, 40),
560 entry(RecordTag::Trailer, 158, 20),
561 ];
562 let classes = class_index(&entries);
563 SeekDirectory {
564 section_flags: SEEK_DIRECTORY_ALL_SECTIONS,
565 entries,
566 classes,
567 channel_lengths: Vec::new(),
568 }
569 }
570
571 #[test]
572 fn roundtrip() {
573 let dir = sample_dir();
574 let bytes = dir.encode().unwrap();
575 let decoded = SeekDirectory::decode(&bytes, Limits::DEFAULT).unwrap();
576 assert_eq!(decoded, dir);
577 }
578
579 #[test]
580 fn encoded_length_is_the_documented_sum() {
581 let dir = sample_dir();
582 let bytes = dir.encode().unwrap();
583 let expected = 2
584 + 4
585 + DIRECTORY_ENTRY_LEN * dir.entries.len()
586 + 1
587 + CLASS_ENTRY_LEN * dir.classes.len()
588 + 4
589 + 8 * dir.channel_lengths.len();
590 assert_eq!(bytes.len(), expected);
591 }
592
593 #[test]
594 fn unknown_version_and_flags_fail_closed() {
595 let dir = sample_dir();
596 let mut bytes = dir.encode().unwrap();
597 bytes[0] = 2;
598 assert_eq!(
599 SeekDirectory::decode(&bytes, Limits::DEFAULT)
600 .unwrap_err()
601 .class(),
602 crate::ErrorClass::UnsupportedVersion
603 );
604
605 let mut bytes = dir.encode().unwrap();
606 bytes[1] |= 0x80;
607 assert_eq!(
608 SeekDirectory::decode(&bytes, Limits::DEFAULT)
609 .unwrap_err()
610 .class(),
611 crate::ErrorClass::InvalidContainer
612 );
613 }
614
615 #[test]
616 fn truncated_section_is_rejected() {
617 let dir = sample_dir();
618 let bytes = dir.encode().unwrap();
619 for cut in 0..bytes.len() {
620 if cut < 2 {
622 continue;
623 }
624 let e = SeekDirectory::decode(&bytes[..cut], Limits::DEFAULT);
625 assert!(e.is_err(), "cut {cut} was accepted");
626 }
627 }
628
629 #[test]
630 fn trailing_bytes_are_rejected() {
631 let dir = sample_dir();
632 let mut bytes = dir.encode().unwrap();
633 bytes.push(0);
634 assert_eq!(
635 SeekDirectory::decode(&bytes, Limits::DEFAULT)
636 .unwrap_err()
637 .class(),
638 crate::ErrorClass::InvalidContainer
639 );
640 }
641
642 #[test]
643 fn over_limit_size_is_declined_before_allocation() {
644 let dir = sample_dir();
645 let bytes = dir.encode().unwrap();
646 let tiny = Limits {
647 max_directory_bytes: 4,
648 ..Limits::DEFAULT
649 };
650 assert_eq!(
651 SeekDirectory::decode(&bytes, tiny).unwrap_err().class(),
652 crate::ErrorClass::ResourceLimit
653 );
654 }
655
656 #[test]
657 fn structural_validation_accepts_a_contiguous_directory() {
658 let dir = sample_dir();
659 dir.validate_structural(190, Limits::DEFAULT).unwrap();
661 }
662
663 #[test]
664 fn structural_validation_rejects_bad_geometry() {
665 let mut dir = sample_dir();
667 dir.entries[2].offset += 1;
668 assert_eq!(
669 dir.validate_structural(190, Limits::DEFAULT)
670 .unwrap_err()
671 .class(),
672 crate::ErrorClass::InvalidContainer
673 );
674
675 let dir = sample_dir();
677 assert_eq!(
678 dir.validate_structural(191, Limits::DEFAULT)
679 .unwrap_err()
680 .class(),
681 crate::ErrorClass::InvalidContainer
682 );
683
684 let mut dir = sample_dir();
686 dir.classes[0].count += 1;
687 assert_eq!(
688 dir.validate_structural(190, Limits::DEFAULT)
689 .unwrap_err()
690 .class(),
691 crate::ErrorClass::InvalidContainer
692 );
693 }
694
695 #[test]
696 fn validate_cross_checks_the_record_framing() {
697 let dir = sample_dir();
698 let sites = vec![
699 RecordSite {
700 tag: RecordTag::Directory as u8,
701 offset: HEADER_LEN as u64,
702 payload_len: 30,
703 },
704 RecordSite {
705 tag: RecordTag::Integrity as u8,
706 offset: 106,
707 payload_len: 40,
708 },
709 RecordSite {
710 tag: RecordTag::Trailer as u8,
711 offset: 158,
712 payload_len: 20,
713 },
714 ];
715 dir.validate(&sites, 190, Limits::DEFAULT).unwrap();
716
717 let mut wrong = sites.clone();
719 wrong[1].payload_len = 41;
720 assert_eq!(
721 dir.validate(&wrong, 190, Limits::DEFAULT)
722 .unwrap_err()
723 .class(),
724 crate::ErrorClass::InvalidContainer
725 );
726 }
727}