use arrayvec::ArrayVec; use crate::{error::AppendNodeError, identity::Identity}; #[derive(Debug, PartialEq, Eq, Clone)] pub struct Route { pub max_hops: u8, path: ArrayVec<u8, 254>, has_future: bool, } impl Route { pub fn new(max_hops: u8) -> Self { let path = ArrayVec::new(); Self { max_hops, path, has_future: false, } } /// Returns `None` if there isn't enough space for the callsign /// Returns `None` if attempting to push past after future hop /// See the specs for more information #[must_use] pub fn push_hop(&mut self, hop: RouteHop) -> Option<()> { match hop { RouteHop::Internet => self.push_internet(), RouteHop::Past(past_hop) => self.push_past(past_hop), RouteHop::Future(ident) => self.push_future(ident), } } /// Returns `None` if there isn't enough space for the callsign /// Returns `None` if attempting to push after future hop /// See the specs for more information #[must_use] pub fn push_past(&mut self, past_hop: PastHop) -> Option<()> { let ident = past_hop.identity(); let len = ident.callsign().as_bytes().len() + 3; let free_space = self.path.capacity() - self.path.len(); if len > free_space { return None; } if self.has_future { return None; } // safe to unwrap since we already did a length check self.path .try_extend_from_slice(ident.callsign().as_bytes()) .unwrap(); self.path.push(0xFF); self.path.push(ident.ssid()); self.path.push(past_hop.rssi); Some(()) } /// Returns `None` if there isn't enough space for the callsign #[must_use] pub fn push_future(&mut self, ident: Identity) -> Option<()> { let len = ident.callsign().as_bytes().len() + 2; let free_space = self.path.capacity() - self.path.len(); if len > free_space { return None; } self.has_future = true; // safe to unwrap since we already did a length check self.path .try_extend_from_slice(ident.callsign().as_bytes()) .unwrap(); self.path.push(0xFD); self.path.push(ident.ssid()); Some(()) } /// Returns `None` if there isn't enough space pub fn push_internet(&mut self) -> Option<()> { let free_space = self.path.capacity() - self.path.len(); if free_space < 1 { return None; } self.path.push(0xFE); Some(()) } /// Append a callsign/ssid pair to the route, intelligently. /// I.e. replace future node if possible /// Returns an Err if the route is out of space, or appending the node doesn't make logical sense /// (there's a future node that doesn't match) /// This only appends past hops. pub fn append_hop(&mut self, new_hop: PastHop) -> Result<(), AppendNodeError> { let mut new_route = Route::new(self.max_hops); let mut already_inserted = false; for rn in self.iter() { match rn { RouteHop::Internet => new_route .push_internet() .ok_or(AppendNodeError::RouteOverflow)?, RouteHop::Past(prev_past_hop) => { let us = prev_past_hop.identity() == new_hop.identity(); if us { return Err(AppendNodeError::DuplicateNode); } else { new_route .push_past(prev_past_hop) .ok_or(AppendNodeError::RouteOverflow)?; } } RouteHop::Future(prev_ident) => { let us = prev_ident == new_hop.identity(); if us { if already_inserted { return Err(AppendNodeError::DuplicateNode); } else { new_route .push_past(new_hop) .ok_or(AppendNodeError::RouteOverflow)?; already_inserted = true; } } else if already_inserted { new_route .push_future(prev_ident) .ok_or(AppendNodeError::RouteOverflow)?; } else { return Err(AppendNodeError::SetFuture); } } } } if !already_inserted { new_route .push_past(new_hop) .ok_or(AppendNodeError::RouteOverflow)?; } if new_route.iter().count() > usize::from(new_route.max_hops) { return Err(AppendNodeError::HopsOverflow); } *self = new_route; Ok(()) } pub fn iter(&'_ self) -> RouteIter<'_> { RouteIter::new(self) } pub fn encode<'a>(&self, buf: &'a mut [u8]) -> Option<&'a [u8]> { let packet_len = self.path.len() + 1; let buf = buf.get_mut(0..(packet_len + 1))?; buf[0] = packet_len.try_into().unwrap(); buf[1] = self.max_hops; buf[2..(packet_len + 1)].copy_from_slice(&self.path); Some(buf) } pub fn decode(data: &[u8]) -> Option<Self> { let len: usize = (*data.first()?).into(); let data = data.get(1..(len + 1))?; let max_hops = *data.first()?; let mut path = ArrayVec::new(); path.try_extend_from_slice(&data[1..]).unwrap(); let has_future = data[1..].iter().any(|x| *x == 0xFD); let s = Self { max_hops, path, has_future, }; if UntrustedRouteIter::new(&s).any(|v| v.is_err()) { return None; } Some(s) } } #[derive(Debug, Eq, PartialEq, Copy, Clone)] pub enum RouteHop<'a> { Internet, Past(PastHop<'a>), Future(Identity<'a>), } #[derive(Debug, Eq, PartialEq, Copy, Clone)] pub struct PastHop<'a> { identity: Identity<'a>, rssi: u8, } impl<'a> PastHop<'a> { pub fn new(identity: Identity<'a>, rssi: Option<f64>) -> Self { let rssi = match rssi { Some(rssi) => (rssi * 1.5 + 240.0).max(1.0) as u8, None => 0, }; Self { identity, rssi } } pub fn identity(&self) -> Identity { self.identity } pub fn rssi(&self) -> Option<f64> { if self.rssi == 0 { None } else { Some(((self.rssi as f64) - 240.0) / 1.5) } } } #[derive(Debug)] struct UntrustedRouteIter<'a> { route: &'a Route, i: usize, seen_future: bool, dead: bool, } impl<'a> UntrustedRouteIter<'a> { fn new(route: &'a Route) -> Self { Self { route, i: 0, seen_future: false, dead: false, } } // Returns Err(()) if invalid fn maybe_next(&mut self) -> Result<RouteHop<'a>, ()> { let i_start = self.i; self.i += 1; if *self.route.path.get(i_start).ok_or(())? == 0xFE { return Ok(RouteHop::Internet); } while *self.route.path.get(self.i).ok_or(())? != 0xFD && self.route.path[self.i] != 0xFF { self.i += 1; } let callsign = core::str::from_utf8(self.route.path.get(i_start..self.i).ok_or(())?) .map_err(|_| ())?; let is_future = *self.route.path.get(self.i).ok_or(())? == 0xFD; if self.seen_future && !is_future { // past after future - not allowed return Err(()); } self.seen_future |= is_future; let ssid = *self.route.path.get(self.i + 1).ok_or(())?; self.i += 2; if is_future { Ok(RouteHop::Future(Identity::new(callsign, ssid))) } else { let rssi = *self.route.path.get(self.i).ok_or(())?; self.i += 1; Ok(RouteHop::Past(PastHop { identity: Identity::new(callsign, ssid), rssi, })) } } } impl<'a> Iterator for UntrustedRouteIter<'a> { type Item = Result<RouteHop<'a>, ()>; fn next(&mut self) -> Option<Self::Item> { if self.dead { return None; } if self.i == self.route.path.len() { return None; } let r = self.maybe_next(); if r.is_err() { self.dead = true; } Some(r) } } pub struct RouteIter<'a> { iter: UntrustedRouteIter<'a>, } impl<'a> RouteIter<'a> { fn new(route: &'a Route) -> Self { Self { iter: UntrustedRouteIter::new(route), } } } impl<'a> Iterator for RouteIter<'a> { type Item = RouteHop<'a>; fn next(&mut self) -> Option<Self::Item> { Some(self.iter.next()?.unwrap()) } } #[cfg(test)] mod tests { use super::*; #[test] fn route_rssi() { let x = -66.0; let r = PastHop::new(Identity::new("C0", 23), Some(x)); assert_eq!(x, r.rssi().unwrap()); let x = 10.0; let r = PastHop::new(Identity::new("C0", 23), Some(x)); assert_eq!(x, r.rssi().unwrap()); let x = -158.0; let r = PastHop::new(Identity::new("C0", 23), Some(x)); assert_eq!(x, r.rssi().unwrap()); let r = PastHop::new(Identity::new("C0", 23), None); assert_eq!(None, r.rssi()); } #[test] fn append_fails_when_existing_future() { let mut r = Route::new(5); r.push_past(PastHop::new(Identity::new("C1", 0), None)) .unwrap(); r.push_past(PastHop::new(Identity::new("C2", 0), None)) .unwrap(); r.push_future(Identity::new("C3", 0)).unwrap(); assert_eq!( AppendNodeError::SetFuture, r.append_hop(PastHop::new(Identity::new("C3", 1), None)) .unwrap_err() ); assert_eq!( AppendNodeError::SetFuture, r.append_hop(PastHop::new(Identity::new("C4", 0), None)) .unwrap_err() ); } #[test] fn append_fails_when_would_exceed_max_hops() { let mut r = Route::new(3); r.append_hop(PastHop::new(Identity::new("C1", 0), None)) .unwrap(); r.append_hop(PastHop::new(Identity::new("C2", 0), None)) .unwrap(); r.append_hop(PastHop::new(Identity::new("C2", 1), None)) .unwrap(); assert_eq!( AppendNodeError::HopsOverflow, r.append_hop(PastHop::new(Identity::new("C4", 0), None)) .unwrap_err() ); } #[test] fn append_fails_when_already_in_route() { let mut r = Route::new(3); r.append_hop(PastHop::new(Identity::new("C1", 0), None)) .unwrap(); assert_eq!( AppendNodeError::DuplicateNode, r.append_hop(PastHop::new(Identity::new("C1", 0), None)) .unwrap_err() ); } #[test] fn append_overwrites_future() { let mut r = Route::new(5); r.push_past(PastHop::new(Identity::new("C1", 0), None)) .unwrap(); r.push_past(PastHop::new(Identity::new("C2", 0), None)) .unwrap(); r.push_future(Identity::new("C3", 0)).unwrap(); r.push_future(Identity::new("C4", 0)).unwrap(); r.append_hop(PastHop::new(Identity::new("C3", 0), None)) .unwrap(); let mut iter = r.iter(); assert_eq!( Some(RouteHop::Past(PastHop::new(Identity::new("C1", 0), None))), iter.next() ); assert_eq!( Some(RouteHop::Past(PastHop::new(Identity::new("C2", 0), None))), iter.next() ); assert_eq!( Some(RouteHop::Past(PastHop::new(Identity::new("C3", 0), None))), iter.next() ); assert_eq!(Some(RouteHop::Future(Identity::new("C4", 0))), iter.next()); assert_eq!(None, iter.next()); } #[test] fn append_overwrites_future_even_when_at_hop_limit() { let mut r = Route::new(4); r.push_past(PastHop::new(Identity::new("C1", 0), None)) .unwrap(); r.push_past(PastHop::new(Identity::new("C2", 0), None)) .unwrap(); r.push_future(Identity::new("C3", 0)).unwrap(); r.push_future(Identity::new("C4", 0)).unwrap(); r.append_hop(PastHop::new(Identity::new("C3", 0), None)) .unwrap(); let mut iter = r.iter(); assert_eq!( Some(RouteHop::Past(PastHop::new(Identity::new("C1", 0), None))), iter.next() ); assert_eq!( Some(RouteHop::Past(PastHop::new(Identity::new("C2", 0), None))), iter.next() ); assert_eq!( Some(RouteHop::Past(PastHop::new(Identity::new("C3", 0), None))), iter.next() ); assert_eq!(Some(RouteHop::Future(Identity::new("C4", 0,))), iter.next()); assert_eq!(None, iter.next()); } #[test] fn append_appends_when_no_future() { let mut r = Route::new(5); r.push_past(PastHop::new(Identity::new("C1", 0), None)) .unwrap(); r.push_past(PastHop::new(Identity::new("C2", 0), None)) .unwrap(); r.push_past(PastHop::new(Identity::new("C3", 0), None)) .unwrap(); r.append_hop(PastHop::new(Identity::new("C4", 0), None)) .unwrap(); let mut iter = r.iter(); assert_eq!( Some(RouteHop::Past(PastHop::new(Identity::new("C1", 0), None))), iter.next() ); assert_eq!( Some(RouteHop::Past(PastHop::new(Identity::new("C2", 0), None))), iter.next() ); assert_eq!( Some(RouteHop::Past(PastHop::new(Identity::new("C3", 0), None))), iter.next() ); assert_eq!( Some(RouteHop::Past(PastHop::new(Identity::new("C4", 0), None))), iter.next() ); assert_eq!(None, iter.next()); } }