leodos_protocols/network/isl/gossip/
bitmap.rs

1#[derive(Debug, Clone, Copy, Default)]
2struct Bitmap(u128);
3
4impl Bitmap {
5    const CAPACITY: u16 = u128::BITS as u16;
6
7    /// Shift the bits left by distance, filling with zeros.
8    fn shift(&mut self, distance: u16) {
9        if distance >= Self::CAPACITY {
10            self.0 = 0;
11        } else {
12            self.0 <<= distance;
13        }
14    }
15
16    /// Set bit at specific 0-based index.
17    fn mark(&mut self, index: u16) {
18        if index >= Self::CAPACITY {
19            return;
20        }
21        self.0 |= 1 << index;
22    }
23
24    /// Check bit at specific 0-based index.
25    fn is_marked(&self, index: u16) -> bool {
26        if index >= Self::CAPACITY {
27            return false;
28        }
29        (self.0 & (1 << index)) != 0
30    }
31}
32
33#[derive(Debug, Clone, Copy)]
34enum ShortestPath {
35    /// The points are identical.
36    Coincident,
37    /// The shortest path follows the direction of the sequence (Future/Newer).
38    Forward { distance: u16 },
39    /// The shortest path goes against the direction of the sequence (Past/Older).
40    Backward { distance: u16 },
41}
42
43impl ShortestPath {
44    /// Determines the position of `target` relative to `reference` on a u16 circle.
45    fn compute(from: u16, to: u16) -> Self {
46        let fwd_dist = to.wrapping_sub(from);
47
48        if fwd_dist == 0 {
49            return Self::Coincident;
50        }
51
52        let bwd_dist = from.wrapping_sub(to);
53
54        if fwd_dist < bwd_dist {
55            Self::Forward { distance: fwd_dist }
56        } else {
57            Self::Backward { distance: bwd_dist }
58        }
59    }
60}
61
62/// Capable of storing up to 129 unique u16 entries and identifying duplicates.
63/// * The `head` represents the most recent entry.
64/// * The `history` bitmap tracks the previous 128 entries relative to the head.
65///
66/// The filter works as follows:
67/// * Entries older than 128 positions from the head are considered duplicates.
68/// * Entries identical to the head are considered duplicates.
69/// * Newer entries update the head and adjust the history accordingly.
70/// * Older entries within the 128-position range are checked against the history.
71#[derive(Debug, Clone, Copy, Default)]
72pub struct DuplicateFilter {
73    head: u16,
74    history: Bitmap,
75    initialized: bool,
76}
77
78impl DuplicateFilter {
79    /// Creates a new empty duplicate filter.
80    pub fn new() -> Self {
81        Self::default()
82    }
83
84    /// Returns `true` if `new` has already been seen, otherwise records it.
85    pub fn is_duplicate(&mut self, new: u16) -> bool {
86        if !self.initialized {
87            self.head = new;
88            self.initialized = true;
89            return false;
90        }
91
92        match ShortestPath::compute(self.head, new) {
93            ShortestPath::Coincident => true,
94            ShortestPath::Forward { distance } => {
95                // `new` is a newer entry than `head`.
96                self.history.shift(distance); // Shift history to make room for `new`.
97                self.history.mark(distance - 1); // Mark the position of 'head'.
98                self.head = new;
99                false
100            }
101            ShortestPath::Backward { distance } => {
102                // `new` is an older entry than `head`.
103                if distance > Bitmap::CAPACITY {
104                    return true; // Too far back.
105                }
106                if self.history.is_marked(distance - 1) {
107                    return true; // Already marked.
108                }
109                self.history.mark(distance - 1); // Mark the position of 'new'.
110                false
111            }
112        }
113    }
114}
leodos_protocols/network/isl/gossip/bitmap.rs

leodos_protocols/network/isl/gossip/
bitmap.rs
