use crate::error::{Error, ErrorCode, Result};
pub const MSG_COUNTER_WINDOW_SIZE: u32 = 32;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum CounterKind {
SecureUnicast,
Rollover,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum Verdict {
New,
Duplicate,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct CounterWindow {
kind: CounterKind,
max: u32,
bitmap: u32,
primed: bool,
}
impl CounterWindow {
#[must_use]
pub const fn new(kind: CounterKind) -> Self {
Self {
kind,
max: 0,
bitmap: 0,
primed: false,
}
}
#[must_use]
pub const fn primed_at(kind: CounterKind, max: u32) -> Self {
Self {
kind,
max,
bitmap: u32::MAX,
primed: true,
}
}
#[must_use]
pub const fn max(&self) -> u32 {
self.max
}
#[must_use]
pub const fn kind(&self) -> CounterKind {
self.kind
}
pub fn accept(&mut self, counter: u32) -> Verdict {
if !self.primed {
self.primed = true;
self.max = counter;
self.bitmap = 0;
return Verdict::New;
}
if counter == self.max {
return Verdict::Duplicate;
}
let ahead = match self.kind {
CounterKind::SecureUnicast => counter > self.max,
CounterKind::Rollover => {
let delta = counter.wrapping_sub(self.max);
delta != 0 && delta < 0x8000_0000
}
};
if ahead {
let shift = counter.wrapping_sub(self.max);
self.bitmap = if shift >= MSG_COUNTER_WINDOW_SIZE {
if shift == MSG_COUNTER_WINDOW_SIZE {
1u32.checked_shl(MSG_COUNTER_WINDOW_SIZE.saturating_sub(1))
.unwrap_or(0)
} else {
0
}
} else {
let moved = self.bitmap.checked_shl(shift).unwrap_or(0);
let old_max_bit = 1u32.checked_shl(shift.saturating_sub(1)).unwrap_or(0);
moved | old_max_bit
};
self.max = counter;
return Verdict::New;
}
let behind = self.max.wrapping_sub(counter);
if behind == 0 || behind > MSG_COUNTER_WINDOW_SIZE {
return Verdict::Duplicate;
}
let Some(bit) = 1u32.checked_shl(behind.saturating_sub(1)) else {
return Verdict::Duplicate;
};
if self.bitmap & bit != 0 {
Verdict::Duplicate
} else {
self.bitmap |= bit;
Verdict::New
}
}
#[must_use]
pub fn would_accept(&self, counter: u32) -> Verdict {
let mut probe = *self;
probe.accept(counter)
}
}
#[must_use]
pub const fn initial_counter(randomness: u32) -> u32 {
(randomness & 0x0FFF_FFFF).saturating_add(1)
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct MessageCounter {
next: u32,
exhausted: bool,
}
impl MessageCounter {
#[must_use]
pub const fn new(randomness: u32) -> Self {
Self::at(initial_counter(randomness))
}
#[must_use]
pub const fn at(value: u32) -> Self {
Self {
next: value,
exhausted: false,
}
}
#[must_use]
pub const fn peek(&self) -> u32 {
self.next
}
pub fn take(&mut self) -> Result<u32> {
if self.exhausted {
return Err(Error::new(ErrorCode::InvalidState));
}
let value = self.next;
match self.next.checked_add(1) {
Some(n) => self.next = n,
None => self.exhausted = true,
}
Ok(value)
}
pub fn take_with_rollover(&mut self) -> u32 {
let value = self.next;
self.next = self.next.wrapping_add(1);
self.exhausted = false;
value
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn the_first_counter_is_always_accepted() {
let mut w = CounterWindow::new(CounterKind::SecureUnicast);
assert_eq!(w.accept(0x8000_0000), Verdict::New);
assert_eq!(w.max(), 0x8000_0000);
}
#[test]
fn a_repeat_of_the_maximum_is_a_duplicate() {
let mut w = CounterWindow::new(CounterKind::SecureUnicast);
assert_eq!(w.accept(100), Verdict::New);
assert_eq!(w.accept(100), Verdict::Duplicate);
}
#[test]
fn in_order_delivery_is_all_new() {
let mut w = CounterWindow::new(CounterKind::SecureUnicast);
for c in 1..1000 {
assert_eq!(w.accept(c), Verdict::New, "counter {c}");
}
assert_eq!(w.max(), 999);
}
#[test]
fn out_of_order_inside_the_window_is_accepted_once() {
let mut w = CounterWindow::new(CounterKind::SecureUnicast);
assert_eq!(w.accept(100), Verdict::New);
assert_eq!(w.accept(105), Verdict::New);
for c in [101, 102, 103, 104] {
assert_eq!(w.accept(c), Verdict::New, "counter {c}");
assert_eq!(w.accept(c), Verdict::Duplicate, "counter {c} again");
}
assert_eq!(w.max(), 105, "a late arrival does not move the maximum");
}
#[test]
fn beyond_the_window_is_a_duplicate_even_if_it_is_new() {
let mut w = CounterWindow::new(CounterKind::SecureUnicast);
assert_eq!(w.accept(1000), Verdict::New);
assert_eq!(
w.accept(1000 - MSG_COUNTER_WINDOW_SIZE - 1),
Verdict::Duplicate
);
assert_eq!(w.accept(1), Verdict::Duplicate);
}
#[test]
fn the_window_edge_is_where_the_spec_puts_it() {
let mut w = CounterWindow::new(CounterKind::SecureUnicast);
assert_eq!(w.accept(1000), Verdict::New);
assert_eq!(
w.accept(1000 - 32),
Verdict::New,
"32 behind is the last bit"
);
assert_eq!(w.accept(1000 - 32), Verdict::Duplicate, "and now it is set");
assert_eq!(w.accept(1000 - 33), Verdict::Duplicate, "33 behind is out");
assert_eq!(
w.accept(1000 - 1),
Verdict::New,
"1 behind is the first bit"
);
}
#[test]
fn a_big_jump_forward_clears_the_history() {
let mut w = CounterWindow::new(CounterKind::SecureUnicast);
assert_eq!(w.accept(100), Verdict::New);
assert_eq!(w.accept(99), Verdict::New);
assert_eq!(w.accept(10_000), Verdict::New);
assert_eq!(w.accept(99), Verdict::Duplicate);
}
#[test]
fn a_secure_unicast_counter_does_not_roll_over() {
let mut w = CounterWindow::new(CounterKind::SecureUnicast);
assert_eq!(w.accept(u32::MAX - 1), Verdict::New);
assert_eq!(w.accept(u32::MAX), Verdict::New);
assert_eq!(w.accept(0), Verdict::Duplicate, "0 is behind, not ahead");
assert_eq!(w.accept(5), Verdict::Duplicate);
}
#[test]
fn a_group_counter_does_roll_over() {
let mut w = CounterWindow::new(CounterKind::Rollover);
assert_eq!(w.accept(u32::MAX), Verdict::New);
assert_eq!(w.accept(0), Verdict::New, "0 is one past u32::MAX");
assert_eq!(w.accept(1), Verdict::New);
assert_eq!(w.accept(u32::MAX), Verdict::Duplicate, "and back is behind");
}
#[test]
fn the_group_space_is_cut_in_half() {
let mut w = CounterWindow::new(CounterKind::Rollover);
assert_eq!(w.accept(1000), Verdict::New);
assert_eq!(w.accept(1000u32.wrapping_add(0x7FFF_FFFF)), Verdict::New);
let mut w = CounterWindow::new(CounterKind::Rollover);
assert_eq!(w.accept(1000), Verdict::New);
assert_eq!(
w.accept(1000u32.wrapping_add(0x8000_0000)),
Verdict::Duplicate
);
}
#[test]
fn a_window_restored_from_storage_rejects_everything_behind_it() {
let mut w = CounterWindow::primed_at(CounterKind::SecureUnicast, 5000);
for c in [4999, 4990, 4969, 1] {
assert_eq!(w.accept(c), Verdict::Duplicate, "counter {c}");
}
assert_eq!(w.accept(5001), Verdict::New);
}
#[test]
fn would_accept_does_not_record() {
let mut w = CounterWindow::new(CounterKind::SecureUnicast);
assert_eq!(w.accept(100), Verdict::New);
assert_eq!(w.would_accept(101), Verdict::New);
assert_eq!(w.would_accept(101), Verdict::New, "still new");
assert_eq!(w.accept(101), Verdict::New);
assert_eq!(w.would_accept(101), Verdict::Duplicate, "now it is not");
}
#[test]
fn a_replay_of_an_entire_window_is_caught() {
let mut w = CounterWindow::new(CounterKind::SecureUnicast);
for c in 1..=64u32 {
assert_eq!(w.accept(c), Verdict::New);
}
for c in 1..=64u32 {
assert_eq!(w.accept(c), Verdict::Duplicate, "replayed counter {c}");
}
}
#[test]
fn the_sender_counter_refuses_to_reuse_a_nonce() {
let mut c = MessageCounter::at(u32::MAX - 1);
assert_eq!(c.take().expect("one left"), u32::MAX - 1);
assert_eq!(
c.take().expect("the last counter is usable"),
u32::MAX,
"giving up at u32::MAX - 1 throws away a legal counter"
);
assert_eq!(
c.take().unwrap_err().code(),
ErrorCode::InvalidState,
"a unicast counter must not wrap: that reuses a nonce"
);
}
#[test]
fn the_group_sender_counter_does_roll_over() {
let mut c = MessageCounter::at(u32::MAX);
assert_eq!(c.take_with_rollover(), u32::MAX);
assert_eq!(c.take_with_rollover(), 0);
assert_eq!(c.peek(), 1);
}
#[test]
fn an_initial_counter_is_inside_the_twenty_eight_bit_range() {
const CEILING: u32 = 1 << 28;
let mut seen_top = false;
for high in 0..=u8::MAX {
for low in [0x00u32, 0x01, 0x7F, 0x80, 0xFE, 0xFF] {
let randomness = (u32::from(high) << 24) | (low << 16) | (low << 8) | low;
let start = MessageCounter::new(randomness).peek();
assert!(
(1..=CEILING).contains(&start),
"{randomness:#010x} started at {start:#010x}"
);
seen_top |= start == CEILING;
}
}
assert!(seen_top, "the top of the range is never reached");
assert_eq!(MessageCounter::new(0).peek(), 1);
assert_eq!(MessageCounter::new(u32::MAX).peek(), CEILING);
}
#[test]
fn an_initial_counter_leaves_the_session_its_supply() {
const RESERVED: u32 = u32::MAX - (1 << 28);
for randomness in [0, 1, u32::MAX, u32::MAX - 1, 0xFFFF_0000, 0x8000_0000] {
let remaining = u32::MAX - MessageCounter::new(randomness).peek();
assert!(
remaining >= RESERVED,
"{randomness:#010x} left only {remaining} counters"
);
}
}
#[test]
fn at_takes_the_value_it_is_given() {
assert_eq!(MessageCounter::at(u32::MAX).peek(), u32::MAX);
assert_eq!(MessageCounter::at(0).peek(), 0);
}
}