ham_cats/whisker/
route.rs

1use arrayvec::ArrayVec;
2
3use crate::{error::AppendNodeError, identity::Identity};
4
5#[derive(Debug, PartialEq, Eq, Clone)]
6pub struct Route {
7    pub max_hops: u8,
8    path: ArrayVec<u8, 254>,
9    has_future: bool,
10}
11
12impl Route {
13    pub fn new(max_hops: u8) -> Self {
14        let path = ArrayVec::new();
15
16        Self {
17            max_hops,
18            path,
19            has_future: false,
20        }
21    }
22
23    /// Returns `None` if there isn't enough space for the callsign
24    /// Returns `None` if attempting to push past after future hop
25    /// See the specs for more information
26    #[must_use]
27    pub fn push_hop(&mut self, hop: RouteHop) -> Option<()> {
28        match hop {
29            RouteHop::Internet => self.push_internet(),
30            RouteHop::Past(past_hop) => self.push_past(past_hop),
31            RouteHop::Future(ident) => self.push_future(ident),
32        }
33    }
34
35    /// Returns `None` if there isn't enough space for the callsign
36    /// Returns `None` if attempting to push after future hop
37    /// See the specs for more information
38    #[must_use]
39    pub fn push_past(&mut self, past_hop: PastHop) -> Option<()> {
40        let ident = past_hop.identity();
41        let len = ident.callsign().len() + 3;
42        let free_space = self.path.capacity() - self.path.len();
43
44        if len > free_space {
45            return None;
46        }
47
48        if self.has_future {
49            return None;
50        }
51
52        // safe to unwrap since we already did a length check
53        self.path
54            .try_extend_from_slice(ident.callsign().as_bytes())
55            .unwrap();
56        self.path.push(0xFF);
57        self.path.push(ident.ssid());
58        self.path.push(past_hop.rssi);
59
60        Some(())
61    }
62
63    /// Returns `None` if there isn't enough space for the callsign
64    #[must_use]
65    pub fn push_future(&mut self, ident: Identity) -> Option<()> {
66        let len = ident.callsign().len() + 2;
67        let free_space = self.path.capacity() - self.path.len();
68
69        if len > free_space {
70            return None;
71        }
72
73        self.has_future = true;
74
75        // safe to unwrap since we already did a length check
76        self.path
77            .try_extend_from_slice(ident.callsign().as_bytes())
78            .unwrap();
79        self.path.push(0xFD);
80        self.path.push(ident.ssid());
81
82        Some(())
83    }
84
85    /// Returns `None` if there isn't enough space
86    pub fn push_internet(&mut self) -> Option<()> {
87        let free_space = self.path.capacity() - self.path.len();
88
89        if free_space < 1 {
90            return None;
91        }
92
93        self.path.push(0xFE);
94
95        Some(())
96    }
97
98    /// Append a callsign/ssid pair to the route, intelligently.
99    /// I.e. replace future node if possible
100    /// Returns an Err if the route is out of space, or appending the node doesn't make logical sense
101    /// (there's a future node that doesn't match)
102    /// This only appends past hops.
103    pub fn append_hop(&mut self, new_hop: PastHop) -> Result<(), AppendNodeError> {
104        let mut new_route = Route::new(self.max_hops);
105
106        let mut already_inserted = false;
107        for rn in self.iter() {
108            match rn {
109                RouteHop::Internet => new_route
110                    .push_internet()
111                    .ok_or(AppendNodeError::RouteOverflow)?,
112                RouteHop::Past(prev_past_hop) => {
113                    let us = prev_past_hop.identity() == new_hop.identity();
114
115                    if us {
116                        return Err(AppendNodeError::DuplicateNode);
117                    } else {
118                        new_route
119                            .push_past(prev_past_hop)
120                            .ok_or(AppendNodeError::RouteOverflow)?;
121                    }
122                }
123                RouteHop::Future(prev_ident) => {
124                    let us = prev_ident == new_hop.identity();
125
126                    if us {
127                        if already_inserted {
128                            return Err(AppendNodeError::DuplicateNode);
129                        } else {
130                            new_route
131                                .push_past(new_hop)
132                                .ok_or(AppendNodeError::RouteOverflow)?;
133                            already_inserted = true;
134                        }
135                    } else if already_inserted {
136                        new_route
137                            .push_future(prev_ident)
138                            .ok_or(AppendNodeError::RouteOverflow)?;
139                    } else {
140                        return Err(AppendNodeError::SetFuture);
141                    }
142                }
143            }
144        }
145
146        if !already_inserted {
147            new_route
148                .push_past(new_hop)
149                .ok_or(AppendNodeError::RouteOverflow)?;
150        }
151
152        if new_route.iter().count() > usize::from(new_route.max_hops) {
153            return Err(AppendNodeError::HopsOverflow);
154        }
155
156        *self = new_route;
157        Ok(())
158    }
159
160    pub fn iter(&'_ self) -> RouteIter<'_> {
161        RouteIter::new(self)
162    }
163
164    pub fn encode<'a>(&self, buf: &'a mut [u8]) -> Option<&'a [u8]> {
165        let packet_len = self.path.len() + 1;
166        let buf = buf.get_mut(0..(packet_len + 1))?;
167        buf[0] = packet_len.try_into().unwrap();
168        buf[1] = self.max_hops;
169        buf[2..(packet_len + 1)].copy_from_slice(&self.path);
170
171        Some(buf)
172    }
173
174    pub fn decode(data: &[u8]) -> Option<Self> {
175        let len: usize = (*data.first()?).into();
176        let data = data.get(1..(len + 1))?;
177
178        let max_hops = *data.first()?;
179
180        let mut path = ArrayVec::new();
181        path.try_extend_from_slice(&data[1..]).unwrap();
182
183        let has_future = data[1..].contains(&0xFD);
184
185        let s = Self {
186            max_hops,
187            path,
188            has_future,
189        };
190
191        if UntrustedRouteIter::new(&s).any(|v| v.is_err()) {
192            return None;
193        }
194
195        Some(s)
196    }
197}
198
199#[derive(Debug, Eq, PartialEq, Copy, Clone)]
200pub enum RouteHop<'a> {
201    Internet,
202    Past(PastHop<'a>),
203    Future(Identity<'a>),
204}
205
206#[derive(Debug, Eq, PartialEq, Copy, Clone)]
207pub struct PastHop<'a> {
208    identity: Identity<'a>,
209    rssi: u8,
210}
211
212impl<'a> PastHop<'a> {
213    pub fn new(identity: Identity<'a>, rssi: Option<f64>) -> Self {
214        let rssi = match rssi {
215            Some(rssi) => (rssi * 1.5 + 240.0).max(1.0) as u8,
216            None => 0,
217        };
218
219        Self { identity, rssi }
220    }
221
222    pub fn identity(&self) -> Identity<'_> {
223        self.identity
224    }
225
226    pub fn rssi(&self) -> Option<f64> {
227        if self.rssi == 0 {
228            None
229        } else {
230            Some(((self.rssi as f64) - 240.0) / 1.5)
231        }
232    }
233}
234
235#[derive(Debug, Clone)]
236struct UntrustedRouteIter<'a> {
237    route: &'a Route,
238    i: usize,
239    seen_future: bool,
240    dead: bool,
241}
242
243impl<'a> UntrustedRouteIter<'a> {
244    fn new(route: &'a Route) -> Self {
245        Self {
246            route,
247            i: 0,
248            seen_future: false,
249            dead: false,
250        }
251    }
252
253    // Returns Err(()) if invalid
254    fn maybe_next(&mut self) -> Result<RouteHop<'a>, ()> {
255        let i_start = self.i;
256        self.i += 1;
257
258        if *self.route.path.get(i_start).ok_or(())? == 0xFE {
259            return Ok(RouteHop::Internet);
260        }
261
262        while *self.route.path.get(self.i).ok_or(())? != 0xFD && self.route.path[self.i] != 0xFF {
263            self.i += 1;
264        }
265
266        let callsign = core::str::from_utf8(self.route.path.get(i_start..self.i).ok_or(())?)
267            .map_err(|_| ())?;
268
269        let is_future = *self.route.path.get(self.i).ok_or(())? == 0xFD;
270        if self.seen_future && !is_future {
271            // past after future - not allowed
272            return Err(());
273        }
274        self.seen_future |= is_future;
275
276        let ssid = *self.route.path.get(self.i + 1).ok_or(())?;
277        self.i += 2;
278
279        if is_future {
280            Ok(RouteHop::Future(Identity::new(callsign, ssid)))
281        } else {
282            let rssi = *self.route.path.get(self.i).ok_or(())?;
283            self.i += 1;
284
285            Ok(RouteHop::Past(PastHop {
286                identity: Identity::new(callsign, ssid),
287                rssi,
288            }))
289        }
290    }
291}
292
293impl<'a> Iterator for UntrustedRouteIter<'a> {
294    type Item = Result<RouteHop<'a>, ()>;
295
296    fn next(&mut self) -> Option<Self::Item> {
297        if self.dead {
298            return None;
299        }
300
301        if self.i == self.route.path.len() {
302            return None;
303        }
304
305        let r = self.maybe_next();
306
307        if r.is_err() {
308            self.dead = true;
309        }
310
311        Some(r)
312    }
313}
314
315#[derive(Clone)]
316pub struct RouteIter<'a> {
317    iter: UntrustedRouteIter<'a>,
318}
319
320impl<'a> RouteIter<'a> {
321    fn new(route: &'a Route) -> Self {
322        Self {
323            iter: UntrustedRouteIter::new(route),
324        }
325    }
326}
327
328impl<'a> Iterator for RouteIter<'a> {
329    type Item = RouteHop<'a>;
330
331    fn next(&mut self) -> Option<Self::Item> {
332        Some(self.iter.next()?.unwrap())
333    }
334}
335
336#[cfg(test)]
337mod tests {
338    use super::*;
339
340    #[test]
341    fn route_rssi() {
342        let x = -66.0;
343        let r = PastHop::new(Identity::new("C0", 23), Some(x));
344        assert_eq!(x, r.rssi().unwrap());
345
346        let x = 10.0;
347        let r = PastHop::new(Identity::new("C0", 23), Some(x));
348        assert_eq!(x, r.rssi().unwrap());
349
350        let x = -158.0;
351        let r = PastHop::new(Identity::new("C0", 23), Some(x));
352        assert_eq!(x, r.rssi().unwrap());
353
354        let r = PastHop::new(Identity::new("C0", 23), None);
355        assert_eq!(None, r.rssi());
356    }
357
358    #[test]
359    fn append_fails_when_existing_future() {
360        let mut r = Route::new(5);
361        r.push_past(PastHop::new(Identity::new("C1", 0), None))
362            .unwrap();
363        r.push_past(PastHop::new(Identity::new("C2", 0), None))
364            .unwrap();
365        r.push_future(Identity::new("C3", 0)).unwrap();
366
367        assert_eq!(
368            AppendNodeError::SetFuture,
369            r.append_hop(PastHop::new(Identity::new("C3", 1), None))
370                .unwrap_err()
371        );
372
373        assert_eq!(
374            AppendNodeError::SetFuture,
375            r.append_hop(PastHop::new(Identity::new("C4", 0), None))
376                .unwrap_err()
377        );
378    }
379
380    #[test]
381    fn append_fails_when_would_exceed_max_hops() {
382        let mut r = Route::new(3);
383        r.append_hop(PastHop::new(Identity::new("C1", 0), None))
384            .unwrap();
385        r.append_hop(PastHop::new(Identity::new("C2", 0), None))
386            .unwrap();
387        r.append_hop(PastHop::new(Identity::new("C2", 1), None))
388            .unwrap();
389        assert_eq!(
390            AppendNodeError::HopsOverflow,
391            r.append_hop(PastHop::new(Identity::new("C4", 0), None))
392                .unwrap_err()
393        );
394    }
395
396    #[test]
397    fn append_fails_when_already_in_route() {
398        let mut r = Route::new(3);
399        r.append_hop(PastHop::new(Identity::new("C1", 0), None))
400            .unwrap();
401
402        assert_eq!(
403            AppendNodeError::DuplicateNode,
404            r.append_hop(PastHop::new(Identity::new("C1", 0), None))
405                .unwrap_err()
406        );
407    }
408
409    #[test]
410    fn append_overwrites_future() {
411        let mut r = Route::new(5);
412        r.push_past(PastHop::new(Identity::new("C1", 0), None))
413            .unwrap();
414        r.push_past(PastHop::new(Identity::new("C2", 0), None))
415            .unwrap();
416        r.push_future(Identity::new("C3", 0)).unwrap();
417        r.push_future(Identity::new("C4", 0)).unwrap();
418
419        r.append_hop(PastHop::new(Identity::new("C3", 0), None))
420            .unwrap();
421
422        let mut iter = r.iter();
423        assert_eq!(
424            Some(RouteHop::Past(PastHop::new(Identity::new("C1", 0), None))),
425            iter.next()
426        );
427        assert_eq!(
428            Some(RouteHop::Past(PastHop::new(Identity::new("C2", 0), None))),
429            iter.next()
430        );
431        assert_eq!(
432            Some(RouteHop::Past(PastHop::new(Identity::new("C3", 0), None))),
433            iter.next()
434        );
435        assert_eq!(Some(RouteHop::Future(Identity::new("C4", 0))), iter.next());
436        assert_eq!(None, iter.next());
437    }
438
439    #[test]
440    fn append_overwrites_future_even_when_at_hop_limit() {
441        let mut r = Route::new(4);
442        r.push_past(PastHop::new(Identity::new("C1", 0), None))
443            .unwrap();
444        r.push_past(PastHop::new(Identity::new("C2", 0), None))
445            .unwrap();
446        r.push_future(Identity::new("C3", 0)).unwrap();
447        r.push_future(Identity::new("C4", 0)).unwrap();
448
449        r.append_hop(PastHop::new(Identity::new("C3", 0), None))
450            .unwrap();
451
452        let mut iter = r.iter();
453        assert_eq!(
454            Some(RouteHop::Past(PastHop::new(Identity::new("C1", 0), None))),
455            iter.next()
456        );
457        assert_eq!(
458            Some(RouteHop::Past(PastHop::new(Identity::new("C2", 0), None))),
459            iter.next()
460        );
461        assert_eq!(
462            Some(RouteHop::Past(PastHop::new(Identity::new("C3", 0), None))),
463            iter.next()
464        );
465        assert_eq!(Some(RouteHop::Future(Identity::new("C4", 0,))), iter.next());
466        assert_eq!(None, iter.next());
467    }
468
469    #[test]
470    fn append_appends_when_no_future() {
471        let mut r = Route::new(5);
472        r.push_past(PastHop::new(Identity::new("C1", 0), None))
473            .unwrap();
474        r.push_past(PastHop::new(Identity::new("C2", 0), None))
475            .unwrap();
476        r.push_past(PastHop::new(Identity::new("C3", 0), None))
477            .unwrap();
478
479        r.append_hop(PastHop::new(Identity::new("C4", 0), None))
480            .unwrap();
481
482        let mut iter = r.iter();
483        assert_eq!(
484            Some(RouteHop::Past(PastHop::new(Identity::new("C1", 0), None))),
485            iter.next()
486        );
487        assert_eq!(
488            Some(RouteHop::Past(PastHop::new(Identity::new("C2", 0), None))),
489            iter.next()
490        );
491        assert_eq!(
492            Some(RouteHop::Past(PastHop::new(Identity::new("C3", 0), None))),
493            iter.next()
494        );
495        assert_eq!(
496            Some(RouteHop::Past(PastHop::new(Identity::new("C4", 0), None))),
497            iter.next()
498        );
499        assert_eq!(None, iter.next());
500    }
501}
ham_cats/whisker/route.rs

ham_cats/whisker/
route.rs
