broadcast_common/
seq.rs

1//! Wrap-safe modular sequence-number arithmetic (comparable to RFC 1982
2//! serial-number arithmetic) over a `bits`-wide sequence space.
3//!
4//! The one implementation behind `rist-runtime::arq::seq` (16-bit RTP
5//! sequence numbers, RFC 3550 §5.1) and `srt-runtime::arq::seq` (31-bit SRT
6//! packet sequence numbers, draft-sharabayko-srt-01 §3.1): the two crates
7//! carried the same algorithm over different moduli (audit r08-RIST-O1,
8//! #1141). Circular over the space; of the two directions between two numbers
9//! the shorter one decides "before"/"after". This is implementation policy,
10//! not spec-cited — neither protocol specifies a comparison algorithm.
11
12/// Widest supported space: a signed `i32` distance must fit, so 31 bits.
13pub const MAX_SEQ_BITS: u32 = 31;
14
15/// A modular sequence-number space of `bits` bits (`1..=31`).
16#[derive(Debug, Clone, Copy, PartialEq, Eq)]
17pub struct SeqSpace {
18    bits: u32,
19}
20
21impl SeqSpace {
22    /// A `bits`-wide space.
23    ///
24    /// # Panics
25    /// In a `const` context (compile error) or at runtime if `bits` is `0`
26    /// or exceeds [`MAX_SEQ_BITS`].
27    #[must_use]
28    pub const fn new(bits: u32) -> Self {
29        assert!(
30            bits >= 1 && bits <= MAX_SEQ_BITS,
31            "SeqSpace bits out of range"
32        );
33        Self { bits }
34    }
35
36    /// Number of distinct sequence numbers: `2^bits`.
37    #[must_use]
38    pub const fn modulus(self) -> u64 {
39        1u64 << self.bits
40    }
41
42    /// Bit mask selecting a sequence number: `2^bits - 1`.
43    #[must_use]
44    pub const fn mask(self) -> u32 {
45        (self.modulus() - 1) as u32
46    }
47
48    /// `seq + n`, wrapping at the space boundary.
49    #[must_use]
50    pub const fn add(self, seq: u32, n: u32) -> u32 {
51        // The sum of two `u32`s fits a `u64`; reduced modulo 2^bits it fits a `u32`.
52        ((seq as u64 + n as u64) % self.modulus()) as u32
53    }
54
55    /// Signed circular distance `a - b`, in `(-half, half]` where `half` is
56    /// half the space. Positive means `a` is ahead of `b`. Inputs are masked
57    /// to the space.
58    #[must_use]
59    pub const fn diff(self, a: u32, b: u32) -> i32 {
60        let modulus = self.modulus() as i64;
61        let half = modulus / 2;
62        let raw = ((a & self.mask()) as i64 - (b & self.mask()) as i64).rem_euclid(modulus);
63        // Either branch lands in `(-2^30, 2^30]` (bits <= 31), which fits an `i32`.
64        (if raw > half { raw - modulus } else { raw }) as i32
65    }
66
67    /// `a` precedes `b` in circular order.
68    #[must_use]
69    pub const fn lt(self, a: u32, b: u32) -> bool {
70        self.diff(a, b) < 0
71    }
72
73    /// `a` precedes or equals `b`.
74    #[must_use]
75    pub const fn leq(self, a: u32, b: u32) -> bool {
76        self.diff(a, b) <= 0
77    }
78
79    /// `a` follows `b` in circular order.
80    #[must_use]
81    pub const fn gt(self, a: u32, b: u32) -> bool {
82        self.diff(a, b) > 0
83    }
84
85    /// `a` follows or equals `b`.
86    #[must_use]
87    pub const fn geq(self, a: u32, b: u32) -> bool {
88        self.diff(a, b) >= 0
89    }
90
91    /// `seq` lies within the inclusive circular range `first..=last`,
92    /// walking forward from `first`. A `last` that precedes `first` in
93    /// circular order is an empty (malformed) range and never matches.
94    #[must_use]
95    pub const fn in_closed_range(self, seq: u32, first: u32, last: u32) -> bool {
96        let span = self.diff(last, first);
97        if span < 0 {
98            return false;
99        }
100        let offset = self.diff(seq, first);
101        offset >= 0 && offset <= span
102    }
103}
104
105#[cfg(test)]
106mod tests {
107    use super::*;
108
109    const S16: SeqSpace = SeqSpace::new(16);
110    const S31: SeqSpace = SeqSpace::new(31);
111
112    #[test]
113    fn wraps_at_the_space_boundary() {
114        assert_eq!(S16.add(0xFFFF, 1), 0);
115        assert_eq!(S16.add(0xFFFF, 5), 4);
116        assert_eq!(S31.add(0x7FFF_FFFF, 1), 0);
117        assert_eq!(S31.add(u32::MAX, u32::MAX), 0x7FFF_FFFE);
118    }
119
120    #[test]
121    fn ordering_is_circular_and_antisymmetric() {
122        assert!(S16.lt(0xFFFF, 0) && S16.gt(0, 0xFFFF));
123        assert_eq!(S16.diff(0, 0xFFFF), 1);
124        assert!(S31.lt(0x7FFF_FFFF, 0) && S31.geq(5, 5) && S31.leq(5, 5));
125        for (a, b) in [(0u32, 0u32), (5, 100), (0xFFFF, 3), (12345, 12340)] {
126            assert_eq!(S16.diff(a, b), -S16.diff(b, a));
127        }
128        // Half the space is the tie point: positive by convention.
129        assert_eq!(S16.diff(0x8000, 0), 0x8000);
130        assert_eq!(S16.diff(0, 0x8000), 0x8000);
131    }
132
133    #[test]
134    fn closed_range_walks_forward_across_the_wrap() {
135        assert!(S16.in_closed_range(0xFFFE, 0xFFFD, 1));
136        assert!(S16.in_closed_range(0, 0xFFFD, 1));
137        assert!(!S16.in_closed_range(2, 0xFFFD, 1));
138        // `last` before `first` is an empty range.
139        assert!(!S16.in_closed_range(5, 10, 3));
140    }
141
142    /// Before/after pin (#1141): the shared 16-bit diff equals the formula
143    /// `rist-runtime` carried before consolidation, over a strided sweep.
144    #[test]
145    fn sixteen_bit_diff_matches_the_pre_consolidation_formula() {
146        fn reference(a: u16, b: u16) -> i32 {
147            let raw = (i32::from(a) - i32::from(b)).rem_euclid(1 << 16);
148            if raw > 1 << 15 { raw - (1 << 16) } else { raw }
149        }
150        for a in (0..=u16::MAX).step_by(257) {
151            for b in (0..=u16::MAX).step_by(251) {
152                assert_eq!(S16.diff(u32::from(a), u32::from(b)), reference(a, b));
153            }
154        }
155    }
156
157    #[test]
158    fn diff_masks_out_of_range_inputs() {
159        // SRT's header word carries the F flag in bit 31.
160        assert_eq!(S31.diff(0x8000_0001, 0), 1);
161    }
162}
broadcast_common/seq.rs

broadcast_common/
seq.rs
