#![forbid(unsafe_code)]
#![deny(missing_docs)]
mod spec;
pub use spec::*;
const _: () = assert!(version_matches(env!("CARGO_PKG_VERSION"), KDI_VERSION));
const fn version_matches(pkg: &str, kdi: &str) -> bool {
let (p, k) = (pkg.as_bytes(), kdi.as_bytes());
if p.len() <= k.len() || p[k.len()] != b'.' {
return false;
}
let mut i = 0;
while i < k.len() {
if p[i] != k[i] {
return false;
}
i += 1;
}
true
}
#[derive(Copy, Clone, PartialEq, Eq, Debug)]
pub struct RejectAt {
pub reason: Reject,
pub offset: usize,
}
impl RejectAt {
const fn at(reason: Reject, offset: usize) -> Self {
Self { reason, offset }
}
}
#[derive(Copy, Clone, PartialEq, Eq, Debug)]
pub struct Ambiguous {
pub kind: u8,
pub count: u16,
}
impl Ambiguous {
pub const fn token(self) -> &'static str {
"ambiguous_kind"
}
}
impl Reject {
pub fn resyncable(self) -> bool {
match self {
Reject::CrcErr => true,
Reject::BadLength => true,
Reject::SectionWords => false,
Reject::LaneIds => false,
Reject::ReservedBits => false,
Reject::TickSane => false,
Reject::TimestampTop16 => false,
Reject::FirstOfRunDup => false,
Reject::DescWords => false,
Reject::HdrWordsFits => false,
Reject::BodyFitsFrame => false,
}
}
}
#[derive(Copy, Clone, PartialEq, Eq, Debug)]
pub struct Flags(pub u16);
impl Flags {
pub const fn first_of_run(self) -> bool {
self.0 & FLAG_FIRST_OF_RUN != 0
}
pub const fn words_dropped(self) -> bool {
self.0 & FLAG_WORDS_DROPPED != 0
}
pub const fn rate_event(self) -> bool {
self.0 & FLAG_RATE_EVENT != 0
}
}
#[derive(Copy, Clone, PartialEq, Eq, Debug)]
pub struct Header {
pub timestamp: u64,
pub flags: Flags,
pub run_id: u16,
pub layout: u16,
pub frame_words: u32,
pub hdr_words: u16,
pub n_sections: u16,
pub contract_rev: u16,
pub desc_words: u16,
}
#[derive(Copy, Clone, PartialEq, Eq, Debug)]
pub struct SectionDesc {
pub kind: u8,
pub n_lanes: u16,
pub rows: u16,
pub element_bits: u8,
pub section_words: u16,
pub tick_num: u32,
pub tick_den: u16,
}
fn rd16(b: &[u8], off: usize) -> Option<u16> {
Some(u16::from_le_bytes(b.get(off..off + 2)?.try_into().ok()?))
}
fn rd32(b: &[u8], off: usize) -> Option<u32> {
Some(u32::from_le_bytes(b.get(off..off + 4)?.try_into().ok()?))
}
fn rd64(b: &[u8], off: usize) -> Option<u64> {
Some(u64::from_le_bytes(b.get(off..off + 8)?.try_into().ok()?))
}
fn desc_at(f: &[u8], desc_words: u16, i: u16) -> Option<SectionDesc> {
let off = DESCRIPTORS_AT + i as usize * desc_words as usize * 2;
let dflags = *f.get(off + DOFF_DFLAGS)?;
Some(SectionDesc {
kind: *f.get(off + DOFF_KIND)?,
n_lanes: rd16(f, off + DOFF_N_LANES)?,
rows: rd16(f, off + DOFF_WORDS_PER_LANE)?,
element_bits: ELEM_BITS[(dflags >> 1) as usize & 3],
section_words: rd16(f, off + DOFF_SECTION_WORDS)?,
tick_num: rd32(f, off + DOFF_TICK_NUM)?,
tick_den: rd16(f, off + DOFF_TICK_DEN)?,
})
}
#[derive(Copy, Clone)]
pub struct Frame<'a> {
bytes: &'a [u8],
hdr: Header,
}
impl<'a> Frame<'a> {
pub fn parse(bytes: &'a [u8]) -> Result<Frame<'a>, RejectAt> {
if bytes.len() < HDR_BYTES {
return Err(RejectAt::at(Reject::BadLength, 0));
}
let frame_words =
rd32(bytes, OFF_FRAME_WORDS).ok_or(RejectAt::at(Reject::BadLength, OFF_FRAME_WORDS))?;
let min_words = (HDR_BYTES + CRC_BYTES) as u32 / 2;
if frame_words % 4 != 0 || frame_words < min_words {
return Err(RejectAt::at(Reject::BadLength, OFF_FRAME_WORDS));
}
let total = frame_words as u64 * 2;
let f = usize::try_from(total)
.ok()
.and_then(|t| bytes.get(..t))
.ok_or(RejectAt::at(Reject::BadLength, OFF_FRAME_WORDS))?;
let total = f.len();
if crc32(f) != CRC_RESIDUE {
return Err(RejectAt::at(Reject::CrcErr, total - CRC_BYTES));
}
let ts = rd64(f, OFF_TIMESTAMP).ok_or(RejectAt::at(Reject::BadLength, OFF_TIMESTAMP))?;
if ts >> 48 != 0 {
return Err(RejectAt::at(Reject::TimestampTop16, OFF_TIMESTAMP));
}
let flags = rd16(f, OFF_FLAGS).ok_or(RejectAt::at(Reject::BadLength, OFF_FLAGS))?;
if flags & !FLAGS_DEFINED != 0 {
return Err(RejectAt::at(Reject::ReservedBits, OFF_FLAGS));
}
let hdr = Header {
timestamp: ts,
flags: Flags(flags),
run_id: rd16(f, OFF_RUN_ID).ok_or(RejectAt::at(Reject::BadLength, OFF_RUN_ID))?,
layout: rd16(f, OFF_LAYOUT).ok_or(RejectAt::at(Reject::BadLength, OFF_LAYOUT))?,
frame_words,
hdr_words: rd16(f, OFF_HDR_WORDS)
.ok_or(RejectAt::at(Reject::BadLength, OFF_HDR_WORDS))?,
n_sections: rd16(f, OFF_N_SECTIONS)
.ok_or(RejectAt::at(Reject::BadLength, OFF_N_SECTIONS))?,
contract_rev: rd16(f, OFF_CONTRACT_REV)
.ok_or(RejectAt::at(Reject::BadLength, OFF_CONTRACT_REV))?,
desc_words: rd16(f, OFF_DESC_WORDS)
.ok_or(RejectAt::at(Reject::BadLength, OFF_DESC_WORDS))?,
};
if hdr.desc_words < DESC_WORDS_MIN {
return Err(RejectAt::at(Reject::DescWords, OFF_DESC_WORDS));
}
let hdr_bytes = hdr.hdr_words as usize * 2;
if hdr_bytes > total - CRC_BYTES {
return Err(RejectAt::at(Reject::HdrWordsFits, OFF_HDR_WORDS));
}
if !hdr.hdr_words.is_multiple_of(4) {
return Err(RejectAt::at(Reject::HdrWordsFits, OFF_HDR_WORDS));
}
let descs_end = DESCRIPTORS_AT as u64 + hdr.n_sections as u64 * hdr.desc_words as u64 * 2;
if descs_end > hdr_bytes as u64 {
return Err(RejectAt::at(Reject::HdrWordsFits, OFF_HDR_WORDS));
}
let descs_end = descs_end as usize;
let mut lane_off = descs_end;
for i in 0..hdr.n_sections {
let off = DESCRIPTORS_AT + i as usize * hdr.desc_words as usize * 2;
let dflags = *f
.get(off + DOFF_DFLAGS)
.ok_or(RejectAt::at(Reject::HdrWordsFits, off))?;
if dflags & !0b110 != 0 {
return Err(RejectAt::at(Reject::ReservedBits, off + DOFF_DFLAGS));
}
if rd16(f, off + DOFF_PAD).ok_or(RejectAt::at(Reject::HdrWordsFits, off))? != 0 {
return Err(RejectAt::at(Reject::ReservedBits, off + DOFF_PAD));
}
let d = desc_at(f, hdr.desc_words, i).ok_or(RejectAt::at(Reject::HdrWordsFits, off))?;
if d.tick_num < 1 || d.tick_den < 1 {
return Err(RejectAt::at(Reject::TickSane, off + DOFF_TICK_NUM));
}
if d.section_words as u32 != section_words(d.n_lanes, d.rows, d.element_bits) {
return Err(RejectAt::at(Reject::SectionWords, off + DOFF_SECTION_WORDS));
}
if lane_off > f.len() {
return Err(RejectAt::at(Reject::HdrWordsFits, OFF_HDR_WORDS));
}
let mut prev: Option<u16> = None;
for l in 0..d.n_lanes as usize {
let id = rd16(f, lane_off + l * 2)
.ok_or(RejectAt::at(Reject::HdrWordsFits, lane_off + l * 2))?;
if prev.is_some_and(|p| id <= p) {
return Err(RejectAt::at(Reject::LaneIds, lane_off + l * 2));
}
prev = Some(id);
}
lane_off = lane_off.saturating_add(d.n_lanes as usize * 2);
}
if lane_off > hdr_bytes {
return Err(RejectAt::at(Reject::HdrWordsFits, OFF_HDR_WORDS));
}
let mut body = hdr_bytes;
for i in 0..hdr.n_sections {
let off = DESCRIPTORS_AT + i as usize * hdr.desc_words as usize * 2;
let d = desc_at(f, hdr.desc_words, i).ok_or(RejectAt::at(Reject::HdrWordsFits, off))?;
body += d.section_words as usize * 2;
if body > total - CRC_BYTES {
return Err(RejectAt::at(
Reject::BodyFitsFrame,
off + DOFF_SECTION_WORDS,
));
}
}
Ok(Frame { bytes: f, hdr })
}
pub fn header(&self) -> &Header {
&self.hdr
}
pub fn bytes(&self) -> &'a [u8] {
self.bytes
}
pub fn sections(&self) -> SectionIter<'a> {
SectionIter { frame: *self, i: 0 }
}
pub fn section_at(&self, i: u16) -> Option<Section<'a>> {
if i >= self.hdr.n_sections {
return None;
}
let mut lane_off =
DESCRIPTORS_AT + self.hdr.n_sections as usize * self.hdr.desc_words as usize * 2;
let mut body_off = self.hdr.hdr_words as usize * 2;
let mut j = 0u16;
let desc = loop {
let d = desc_at(self.bytes, self.hdr.desc_words, j)?;
if j == i {
break d;
}
lane_off += d.n_lanes as usize * 2;
body_off += d.section_words as usize * 2;
j += 1;
};
Some(Section {
desc,
lanes: self
.bytes
.get(lane_off..lane_off + desc.n_lanes as usize * 2)?,
body: self
.bytes
.get(body_off..body_off + desc.section_words as usize * 2)?,
})
}
pub fn section(&self, kind: u8) -> Result<Option<Section<'a>>, Ambiguous> {
let count = self.sections_of(kind).count();
if count > 1 {
return Err(Ambiguous {
kind,
count: count as u16,
});
}
Ok(self.sections_of(kind).next())
}
pub fn sections_of(&self, kind: u8) -> impl Iterator<Item = Section<'a>> + 'a {
self.sections().filter(move |s| s.desc.kind == kind)
}
}
pub struct SectionIter<'a> {
frame: Frame<'a>,
i: u16,
}
impl<'a> Iterator for SectionIter<'a> {
type Item = Section<'a>;
fn next(&mut self) -> Option<Section<'a>> {
let s = self.frame.section_at(self.i)?;
self.i += 1;
Some(s)
}
}
#[derive(Copy, Clone)]
pub struct Section<'a> {
desc: SectionDesc,
lanes: &'a [u8],
body: &'a [u8],
}
impl<'a> Section<'a> {
pub fn desc(&self) -> &SectionDesc {
&self.desc
}
pub fn kind(&self) -> Option<Kind> {
Kind::from_code(self.desc.kind)
}
pub fn lane_ids(&self) -> impl ExactSizeIterator<Item = u16> + 'a {
self.lanes
.chunks_exact(2)
.map(|c| u16::from_le_bytes([c[0], c[1]]))
}
pub fn lane_id(&self, i: u16) -> Option<u16> {
rd16(self.lanes, i as usize * 2)
}
pub fn element(&self, row: u16, lane: u16) -> Option<u64> {
if row >= self.desc.rows || lane >= self.desc.n_lanes {
return None;
}
let (row, lane, n) = (row as usize, lane as usize, self.desc.n_lanes as usize);
if self.desc.element_bits == 1 {
let per_row = n.div_ceil(16);
let w = rd16(self.body, (row * per_row + (lane >> 4)) * 2)?;
return Some(((w >> (lane & 15)) & 1) as u64);
}
let step = self.desc.element_bits as usize / 8;
let at = (row * n + lane) * step;
let s = self.body.get(at..at + step)?;
Some(
s.iter()
.enumerate()
.fold(0u64, |v, (k, b)| v | (*b as u64) << (8 * k)),
)
}
pub fn row(&self, row: u16) -> Option<impl ExactSizeIterator<Item = u64> + 'a> {
if row >= self.desc.rows {
return None;
}
let s = *self;
Some((0..self.desc.n_lanes).map(move |l| s.element(row, l).unwrap_or(0)))
}
pub fn body(&self) -> &'a [u8] {
self.body
}
pub fn cadence(&self) -> (u32, u16) {
(self.desc.tick_num, self.desc.tick_den)
}
}
#[derive(Copy, Clone, PartialEq, Eq, Debug, Default)]
pub struct Counters {
pub resync_bytes: usize,
pub unknown_kind: usize,
pub format_skipped: usize,
}
pub struct Walk<'a> {
blob: &'a [u8],
pos: usize,
counters: Counters,
}
impl<'a> Walk<'a> {
pub fn new(blob: &'a [u8]) -> Walk<'a> {
Walk {
blob,
pos: 0,
counters: Counters::default(),
}
}
pub fn tail(&self) -> &'a [u8] {
&self.blob[self.pos..]
}
pub fn counters(&self) -> Counters {
self.counters
}
}
fn find_magic(b: &[u8], from: usize) -> Option<usize> {
let m = MAGIC.to_le_bytes();
let last = b.len().checked_sub(m.len())?;
(from..=last).find(|&i| b[i..i + m.len()] == m)
}
impl<'a> Iterator for Walk<'a> {
type Item = Result<Frame<'a>, RejectAt>;
fn next(&mut self) -> Option<Self::Item> {
loop {
if self.pos + HDR_BYTES > self.blob.len() {
return None;
}
if rd32(self.blob, self.pos)? != MAGIC {
match find_magic(self.blob, self.pos + 1) {
Some(next) => {
self.counters.resync_bytes += next - self.pos;
self.pos = next;
continue;
}
None => {
self.counters.resync_bytes += self.blob.len() - self.pos;
self.pos = self.blob.len();
return None;
}
}
}
let base = self.pos;
let f = &self.blob[base..];
let frame_words = rd32(f, OFF_FRAME_WORDS)?;
if frame_words % 4 != 0 || frame_words < (HDR_BYTES + CRC_BYTES) as u32 / 2 {
self.pos = base + 1;
self.counters.resync_bytes += 1;
return Some(Err(RejectAt::at(Reject::BadLength, base + OFF_FRAME_WORDS)));
}
let end = base as u64 + frame_words as u64 * 2;
if end > self.blob.len() as u64 {
return None; }
let end = end as usize;
if rd16(f, OFF_FORMAT)? != FORMAT {
self.counters.format_skipped += 1;
self.pos = end;
continue;
}
return Some(match Frame::parse(&self.blob[base..end]) {
Ok(frame) => {
self.counters.unknown_kind +=
frame.sections().filter(|s| s.kind().is_none()).count();
self.pos = end;
Ok(frame)
}
Err(e) => {
if e.reason.resyncable() {
self.pos = base + 1;
self.counters.resync_bytes += 1;
} else {
self.pos = end;
}
Err(RejectAt::at(e.reason, base + e.offset))
}
});
}
}
}
pub fn check_run_announcements(headers: &[Header]) -> Result<(), Reject> {
for (i, h) in headers.iter().enumerate() {
if !h.flags.first_of_run() {
continue;
}
let prev = headers[..i]
.iter()
.rev()
.find(|p| p.flags.first_of_run() && p.run_id == h.run_id);
if prev.is_some_and(|p| h.timestamp <= p.timestamp) {
return Err(Reject::FirstOfRunDup);
}
}
Ok(())
}
pub fn lost_frames(dt_ticks: u64, tick_num: u32, tick_den: u16) -> Result<i64, Reject> {
if tick_num < 1 || tick_den < 1 {
return Err(Reject::TickSane);
}
let (n, d) = (dt_ticks as u128 * tick_den as u128, tick_num as u128);
let (q, r) = (n / d, n % d);
let q = match (2 * r).cmp(&d) {
core::cmp::Ordering::Greater => q + 1,
core::cmp::Ordering::Less => q,
core::cmp::Ordering::Equal => q + (q & 1), };
Ok(q.min(i64::MAX as u128) as i64 - 1)
}
pub fn section_words(n_lanes: u16, rows: u16, element_bits: u8) -> u32 {
let w = rows as u64 * (n_lanes as u64 * element_bits as u64).div_ceil(16);
w.min(u32::MAX as u64) as u32
}
pub fn aligned_burst(frame_bytes: u32, want: u32, alignment: u32) -> Option<u32> {
let step = alignment_step(frame_bytes, want, alignment)?;
Some(((want / step) * step).max(step))
}
pub(crate) fn aligned_burst_at_least(frame_bytes: u32, want: u32, alignment: u32) -> Option<u32> {
let step = alignment_step(frame_bytes, want, alignment)?;
want.div_ceil(step).checked_mul(step)
}
fn alignment_step(frame_bytes: u32, want: u32, alignment: u32) -> Option<u32> {
if frame_bytes == 0 || want == 0 || alignment == 0 {
return None;
}
Some(alignment / gcd(frame_bytes, alignment))
}
fn gcd(mut a: u32, mut b: u32) -> u32 {
while b != 0 {
(a, b) = (b, a % b);
}
a
}
pub fn crc32(data: &[u8]) -> u32 {
let mut c = !0u32;
for b in data {
c = CRC_TABLE[((c ^ *b as u32) & 0xff) as usize] ^ (c >> 8);
}
!c
}
const CRC_TABLE: [u32; 256] = {
let mut t = [0u32; 256];
let mut i = 0;
while i < 256 {
let mut c = i as u32;
let mut k = 0;
while k < 8 {
c = if c & 1 != 0 {
0xEDB8_8320 ^ (c >> 1)
} else {
c >> 1
};
k += 1;
}
t[i] = c;
i += 1;
}
t
};
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn lost_frames_ties_go_to_even() {
assert_eq!(lost_frames(5_000, 10_000, 3), Ok(1));
assert_eq!(lost_frames(15_000, 10_000, 3), Ok(3));
assert_eq!(lost_frames(10_000, 10_000, 3), Ok(2));
assert_eq!(lost_frames(6_667, 10_000, 3), Ok(1));
assert_eq!(lost_frames(3_333, 10_000, 3), Ok(0));
assert_eq!(lost_frames(0, 1, 1), Ok(-1));
assert_eq!(lost_frames(1, 0, 1), Err(Reject::TickSane));
assert_eq!(lost_frames(1, 1, 0), Err(Reject::TickSane));
}
#[test]
fn a_hostile_frame_words_is_rejected_not_slice_indexed() {
let mut b = [0u8; 64];
b[..4].copy_from_slice(&MAGIC.to_le_bytes());
for fw in [0xFFFF_FFFCu32, 0x8000_0000, 0x4000_0000] {
b[OFF_FRAME_WORDS..OFF_FRAME_WORDS + 4].copy_from_slice(&fw.to_le_bytes());
assert_eq!(
Frame::parse(&b).map(|_| ()),
Err(RejectAt::at(Reject::BadLength, OFF_FRAME_WORDS))
);
let mut w = Walk::new(&b);
assert!(w.next().is_none());
assert_eq!(w.tail().len(), b.len());
}
}
#[test]
fn run_announcements_are_scoped_to_their_run_id() {
fn ann(run_id: u16, timestamp: u64, first: bool) -> Header {
Header {
timestamp,
flags: Flags(if first { FLAG_FIRST_OF_RUN } else { 0 }),
run_id,
layout: 0,
frame_words: 32,
hdr_words: 28,
n_sections: 1,
contract_rev: CONTRACT_REV,
desc_words: DESC_WORDS_MIN,
}
}
let two_runs = [ann(1, 10, true), ann(2, 5, true), ann(1, 20, true)];
assert_eq!(check_run_announcements(&two_runs), Ok(()));
let repeat = [ann(1, 7, true), ann(2, 99, true), ann(1, 7, true)];
assert_eq!(check_run_announcements(&repeat), Err(Reject::FirstOfRunDup));
let quiet = [ann(1, 10, true), ann(1, 3, false), ann(1, 11, true)];
assert_eq!(check_run_announcements(&quiet), Ok(()));
}
#[test]
fn version_matches_needs_a_component_boundary() {
assert!(version_matches("0.4.0", "0.4"));
assert!(version_matches("0.4.17", "0.4"));
assert!(!version_matches("0.40", "0.4"));
assert!(!version_matches("0.5.0", "0.4"));
assert!(!version_matches("0.4", "0.4")); }
#[test]
fn aligned_burst_and_section_words() {
assert_eq!(aligned_burst(88, 100, 16), Some(100)); assert_eq!(aligned_burst(136, 10, 16), Some(10)); assert_eq!(aligned_burst(64, 3, 16), Some(3)); assert_eq!(aligned_burst(88, 1, 16), Some(2)); assert_eq!(aligned_burst(88, 100, 0), None);
assert_eq!(aligned_burst_at_least(88, 3, 16), Some(4));
assert_eq!(aligned_burst_at_least(88, 0, 16), None);
assert_eq!(aligned_burst_at_least(88, u32::MAX, 16), None);
assert_eq!(section_words(20, 1, 1), 2); assert_eq!(section_words(2, 35, 16), 70);
assert_eq!(section_words(3, 2, 32), 12);
assert_eq!(section_words(u16::MAX, u16::MAX, 64), u32::MAX);
assert_eq!(section_words(32769, u16::MAX, 32), u32::MAX);
}
}