scru64/generator/
counter_mode.rs

1//! Types to customize the counter behavior of [`Scru64Generator`].
2
3use crate::NODE_CTR_SIZE;
4
5#[cfg(doc)]
6use super::Scru64Generator;
7
8/// A trait to customize the initial counter value for each new `timestamp`.
9///
10/// [`Scru64Generator`] calls `renew()` to obtain the initial counter value when the `timestamp`
11/// field has changed since the immediately preceding ID. Types implementing this trait may apply
12/// their respective logic to calculate the initial counter value.
13pub trait CounterMode {
14    /// Returns the next initial counter value of `counter_size` bits.
15    ///
16    /// [`Scru64Generator`] passes the `counter_size` (from 1 to 23) and other context information
17    /// that may be useful for counter renewal. The returned value must be within the range of
18    /// `counter_size`-bit unsigned integer.
19    fn renew(&mut self, counter_size: u8, context: &RenewContext) -> u32;
20}
21
22/// Represents the context information provided by [`Scru64Generator`] to [`CounterMode::renew()`].
23#[derive(Debug)]
24#[non_exhaustive]
25pub struct RenewContext {
26    /// The `timestamp` value for the new counter.
27    pub timestamp: u64,
28
29    /// The `node_id` of the generator.
30    pub node_id: u32,
31}
32
33/// The default "initialize a portion counter" strategy.
34///
35/// With this strategy, the counter is reset to a random number for each new `timestamp` tick, but
36/// some specified leading bits are set to zero to reserve space as the counter overflow guard.
37///
38/// Note that the random number generator employed is not cryptographically strong nor is securely
39/// seeded. This mode does not pay for security because a small random number is insecure anyway.
40#[derive(Clone, Debug, Eq, PartialEq, Default)]
41pub struct DefaultCounterMode {
42    overflow_guard_size: u8,
43    rng: u64,
44}
45
46impl DefaultCounterMode {
47    /// Creates a new instance with the size (in bits) of overflow guard bits.
48    pub const fn new(overflow_guard_size: u8) -> Self {
49        Self {
50            overflow_guard_size,
51            rng: 0, // zero indicates uninitialized state
52        }
53    }
54
55    /// Initializes the random number generator.
56    #[cold]
57    fn new_rng(&self, counter_size: u8, context: &RenewContext) -> u64 {
58        // use context and variable addresses as seed
59        #[cfg(feature = "std")]
60        let addr = (&*Box::new(42) as *const i32) as u64;
61        #[cfg(not(feature = "std"))]
62        let addr = (self as *const Self) as u64;
63
64        addr ^ ((context.timestamp << NODE_CTR_SIZE) | (u64::from(context.node_id) << counter_size))
65    }
66}
67
68impl CounterMode for DefaultCounterMode {
69    fn renew(&mut self, counter_size: u8, context: &RenewContext) -> u32 {
70        debug_assert!(counter_size < NODE_CTR_SIZE);
71        if self.rng == 0 {
72            self.rng = self.new_rng(counter_size, context);
73        }
74
75        if self.overflow_guard_size < counter_size {
76            let shift = 64 + self.overflow_guard_size - counter_size;
77
78            // xorshift64* (Vigna 2016)
79            self.rng ^= self.rng >> 12;
80            self.rng ^= self.rng << 25;
81            self.rng ^= self.rng >> 27;
82            (self.rng.wrapping_mul(2685821657736338717) >> shift) as u32
83        } else {
84            0
85        }
86    }
87}
88
89/// `DefaultCounterMode` returns random numbers, setting the leading guard bits to zero.
90///
91/// This case includes statistical tests for the random number generator and thus may fail at a
92/// certain low probability.
93#[cfg(test)]
94#[test]
95fn test_default_counter_mode() {
96    const N_LOOPS: usize = 4096;
97
98    // set margin based on binom dist 99.999999% confidence interval
99    let margin = 5.730729 * (0.5 * 0.5 / N_LOOPS as f64).sqrt();
100
101    let context = RenewContext {
102        timestamp: 0x0123_4567_89ab,
103        node_id: 0,
104    };
105    for counter_size in 1..NODE_CTR_SIZE {
106        for overflow_guard_size in 0..NODE_CTR_SIZE {
107            // count number of set bits by bit position (from LSB to MSB)
108            let mut counts_by_pos = [0u32; NODE_CTR_SIZE as usize];
109
110            let mut c = DefaultCounterMode::new(overflow_guard_size);
111            for _ in 0..N_LOOPS {
112                let mut n = c.renew(counter_size, &context);
113                for e in counts_by_pos.iter_mut() {
114                    *e += n & 1;
115                    n >>= 1;
116                }
117                assert_eq!(n, 0);
118            }
119
120            let filled = counter_size.saturating_sub(overflow_guard_size) as usize;
121            for &e in counts_by_pos[..filled].iter() {
122                assert!((e as f64 / N_LOOPS as f64 - 0.5).abs() < margin);
123            }
124            for &e in counts_by_pos[filled..].iter() {
125                assert_eq!(e, 0);
126            }
127        }
128    }
129}
scru64/generator/counter_mode.rs

scru64/generator/
counter_mode.rs
