fast_clock/
wrapping_u64.rs

1#[cfg(feature = "std")]
2use crate::std_clocks::InstantTime;
3use crate::{CalibratedClock, Clock, ClockSynchronization, DurationCalibration, Time};
4use core::cmp::{self};
5
6/// [`Time`] implementation for clocks that produce raw `u64` tick values and wrap around at `2^BITS`.
7///
8/// All arithmetic uses wrapping semantics so measurements across a counter rollover
9/// remain accurate, provided the involved timestamps are less than `2^(BITS-1)` ticks apart.
10#[derive(Copy, Clone, Debug)]
11pub struct WrappingU64Time<const BITS: u32 = 64>;
12
13/// An instant in a [`WrappingU64Time`] domain.
14#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
15pub struct WrappingU64Instant<const BITS: u32 = 64>(u64);
16
17/// A non-negative duration in a [`WrappingU64Time`] domain.
18#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, PartialOrd, Ord)]
19pub struct WrappingU64Duration<const BITS: u32 = 64>(u64);
20
21const fn assert_bits(x: u32) {
22    assert!(x > 0 && x <= 64);
23}
24#[inline]
25#[track_caller]
26fn debug_assert_in_range(x: u64, unused_bits: u32) {
27    let mask = u64::MAX >> unused_bits;
28    debug_assert!(x & mask == x);
29}
30impl<const BITS: u32> WrappingU64Instant<BITS> {
31    /// Construct an instant from a clock reading in the range `0..2^BITS`.
32    #[inline]
33    pub fn new(x: u64) -> Self {
34        debug_assert_in_range(x, Self::UNUSED_BITS);
35        Self::wrapping_new(x)
36    }
37    /// Construct an instant from an arbitrary `u64` value.
38    ///
39    /// The provided value may be greater than `2^BITS`.
40    /// The instant will behave as if the top bits had been masked off.
41    /// When and how this masking is performed is unspecified.
42    #[inline]
43    pub fn wrapping_new(x: u64) -> Self {
44        const { assert_bits(BITS) };
45        Self(x << Self::UNUSED_BITS)
46    }
47
48    /// Convert to a tick count in the range `0..2^BITS`.
49    ///
50    /// If `BITS<64`, this type may use additional bits for extra precision.
51    /// The rounding behaviour of `to_ticks` is unspecified.
52    #[inline]
53    pub fn to_ticks(self) -> u64 {
54        self.0 >> Self::UNUSED_BITS
55    }
56
57    /// Return the internal representation of this type.
58    ///
59    /// It is unspecified how this maps to clock ticks.
60    #[inline]
61    pub fn to_bits(self) -> u64 {
62        self.0
63    }
64
65    /// Reconstruct an instant from its internal representation.
66    ///
67    /// This should only be called with values obtained from [`to_bits`](Self::to_bits).
68    #[inline]
69    pub fn from_bits(x: u64) -> Self {
70        const { assert_bits(BITS) };
71        Self(x)
72    }
73
74    const UNUSED_BITS: u32 = 64 - BITS;
75}
76
77impl<const BITS: u32> WrappingU64Duration<BITS> {
78    /// Construct a duration from a tick count in the range `0..2^BITS`.
79    #[inline]
80    pub fn new(x: u64) -> Self {
81        debug_assert_in_range(x, Self::UNUSED_BITS);
82        Self::wrapping_new(x)
83    }
84    /// Construct a duration from an arbitrary `u64` value.
85    ///
86    /// The provided value may be greater than `2^BITS`.
87    /// The duration will behave as if the top bits had been masked off.
88    /// When and how this masking is performed is unspecified.
89    #[inline]
90    pub fn wrapping_new(x: u64) -> Self {
91        const { assert_bits(BITS) };
92        Self(x << Self::UNUSED_BITS)
93    }
94
95    /// Convert to a tick count in the range `0..2^BITS`.
96    ///
97    /// If `BITS<64`, this type may use additional bits for extra precision.
98    /// The rounding behaviour of `to_ticks` is unspecified.
99    #[inline]
100    pub fn to_ticks(self) -> u64 {
101        self.0 >> Self::UNUSED_BITS
102    }
103
104    /// Return the internal representation of this type.
105    ///
106    /// It is unspecified how this maps to clock ticks.
107    #[inline]
108    pub fn to_bits(self) -> u64 {
109        self.0
110    }
111
112    /// Reconstruct a duration from its internal representation.
113    ///
114    /// This should only be called with values obtained from [`to_bits`](Self::to_bits).
115    #[inline]
116    pub fn from_bits(x: u64) -> Self {
117        const { assert_bits(BITS) };
118        Self(x)
119    }
120
121    const UNUSED_BITS: u32 = 64 - BITS;
122}
123
124impl<const BITS: u32> Time for WrappingU64Time<BITS> {
125    type Instant = WrappingU64Instant<BITS>;
126
127    type Duration = WrappingU64Duration<BITS>;
128
129    #[inline]
130    fn instant_sub(a: Self::Instant, b: Self::Instant) -> Self::Duration {
131        debug_assert!(Self::instant_cmp(a, b).is_ge());
132        WrappingU64Duration(a.0.wrapping_sub(b.0))
133    }
134
135    #[inline]
136    fn duration_sub(a: Self::Duration, b: Self::Duration) -> Self::Duration {
137        WrappingU64Duration(a.0 - b.0)
138    }
139
140    #[inline]
141    fn duration_add(a: Self::Duration, b: Self::Duration) -> Self::Duration {
142        WrappingU64Duration(a.0 + b.0)
143    }
144
145    #[inline]
146    fn mixed_sub(a: Self::Instant, b: Self::Duration) -> Self::Instant {
147        WrappingU64Instant(a.0.wrapping_sub(b.0))
148    }
149
150    #[inline]
151    fn mixed_add(a: Self::Instant, b: Self::Duration) -> Self::Instant {
152        WrappingU64Instant(a.0.wrapping_add(b.0))
153    }
154
155    #[inline]
156    fn instant_cmp(a: Self::Instant, b: Self::Instant) -> cmp::Ordering {
157        (a.0 as i64).wrapping_sub(b.0 as i64).cmp(&0)
158    }
159}
160
161/// Integer multiply-shift calibration for [`WrappingU64Duration`].
162///
163/// Converts between ticks and nanoseconds using precomputed multiply-shift factors.
164/// All involved durations must be less than half the maximum representable value:
165/// Less than 2^63 nanoseconds and less than 2^(BITS-1) ticks.
166///
167/// The conversion precision is best effort.
168/// No particular precision guarantee is made.
169/// The current implementation produces results with an error of at most 1 result unit (nanosecond or tick).
170#[derive(Clone, Copy, Debug)]
171pub struct U64Calibration<const BITS: u32 = 64> {
172    to_ns: u64,
173    to_ns_shift: u32,
174    from_ns: u64,
175    from_ns_shift: u32,
176}
177
178impl<const BITS: u32> U64Calibration<BITS> {
179    /// Creates a calibration from a measured duration and its nanosecond equivalent.
180    pub fn new(duration: WrappingU64Duration<BITS>, duration_ns: u64) -> Self {
181        assert!(duration.0 > 0);
182        assert!(duration_ns > 0);
183        let (to_ns, to_ns_shift) = make_mul_shift(duration.0, duration_ns);
184        let (from_ns, from_ns_shift) = make_mul_shift(duration_ns, duration.0);
185        U64Calibration {
186            to_ns,
187            to_ns_shift,
188            from_ns,
189            from_ns_shift,
190        }
191    }
192
193    /// Calibrates `clock` against `reference_clock`, calling `wait` until `min_duration` elapses.
194    ///
195    /// Returns the calibration and a [`ClockSynchronization`] relating the two clocks to each other
196    /// `wait` is invoked with the instant until which it should wait.
197    pub fn new_with_reference_clock<C: Clock<Time = WrappingU64Time<BITS>>, R: Clock>(
198        clock: &C,
199        reference_clock: &CalibratedClock<R>,
200        min_duration: <R::Time as Time>::Duration,
201        mut wait: impl FnMut(<R::Time as Time>::Instant),
202    ) -> (Self, ClockSynchronization<R::Time, C::Time>) {
203        let s1 = ClockSynchronization::new_aba_calibrated(reference_clock, clock);
204        let wait_until = R::Time::mixed_add(s1.epoch_a(), min_duration);
205        while R::Time::instant_cmp(reference_clock.clock.now(), wait_until).is_lt() {
206            wait(wait_until);
207        }
208        let s2 = ClockSynchronization::new_aba_calibrated(reference_clock, clock);
209        (
210            Self::new(
211                C::Time::instant_sub(s2.epoch_b(), s1.epoch_b()),
212                reference_clock
213                    .calibration
214                    .convert_to_ns(R::Time::instant_sub(s2.epoch_a(), s1.epoch_a())),
215            ),
216            s2,
217        )
218    }
219
220    /// Calibrates `clock` against `std::time::Instant`, sleeping for at least `min_duration`.
221    ///
222    /// This is a convenience wrapper around [`U64Calibration::new_with_reference_clock`] based on [`std::time::Instant`] and [`std::thread::sleep`].
223    #[cfg(feature = "std")]
224    pub fn new_with_std_instant<C: Clock<Time = WrappingU64Time<BITS>>>(
225        clock: &C,
226        min_duration: std::time::Duration,
227    ) -> (Self, ClockSynchronization<InstantTime, C::Time>) {
228        use crate::{InherentlyCalibrated, std_clocks::InstantClock};
229
230        Self::new_with_reference_clock(
231            clock,
232            &CalibratedClock {
233                clock: InstantClock,
234                calibration: InherentlyCalibrated,
235            },
236            min_duration,
237            |until| {
238                let now = std::time::Instant::now();
239                if let Some(remaining) = until.checked_duration_since(now) {
240                    std::thread::sleep(remaining);
241                }
242            },
243        )
244    }
245}
246
247impl<const BITS: u32> DurationCalibration<WrappingU64Duration<BITS>> for U64Calibration<BITS> {
248    #[inline]
249    fn convert_to_ns(&self, d: WrappingU64Duration<BITS>) -> u64 {
250        apply_mul_shift(d.0, self.to_ns, self.to_ns_shift)
251    }
252
253    #[inline]
254    fn convert_from_ns(&self, ns: u64) -> WrappingU64Duration<BITS> {
255        WrappingU64Duration(apply_mul_shift(ns, self.from_ns, self.from_ns_shift))
256    }
257}
258
259/// Computes `(mul, shift)` such that `apply_mul_shift(x, mul, shift) == round(x * to / from)`.
260fn make_mul_shift(from: u64, to: u64) -> (u64, u32) {
261    debug_assert!(from > 0 && from < (1 << 63));
262    debug_assert!(to > 0 && to < (1 << 63));
263
264    let l_to = 64 - to.leading_zeros();
265    let l_from = 64 - from.leading_zeros();
266    let s0 = l_from + 64 - l_to;
267
268    // `shift` is chosen such that mul lands in 2^63..2^64
269    let shift = if (to as u128) << s0 < (from as u128) << 64 {
270        s0
271    } else {
272        s0 - 1
273    };
274
275    let mul = (((to as u128) << shift) / from as u128) as u64;
276    debug_assert!(mul >= 1 << 63);
277    (mul, shift)
278}
279
280#[inline]
281fn apply_mul_shift(x: u64, mul: u64, shift: u32) -> u64 {
282    ((mul as u128 * x as u128 + (1u128 << (shift - 1))) >> shift) as u64
283}
284
285#[test]
286fn test_make_mul_shift() {
287    use std::vec::Vec;
288    let mut values: Vec<u64> = (1..61)
289        .flat_map(|s| (1..4).map(move |i| i << s))
290        .flat_map(|x| [x - 1, x, x + 1])
291        .filter(|&x| x > 0 && x < (1 << 63))
292        .collect();
293    values.sort_unstable();
294    values.dedup();
295    for &from in &values {
296        for &to in &values {
297            let (mul, shift) = make_mul_shift(from, to);
298            assert!(mul >= (1 << 63));
299            assert_eq!(apply_mul_shift(from, mul, shift), to);
300        }
301    }
302}
303
304/// Checks that conversions stay accurate right up to the documented half-period bound,
305/// independent of `BITS`.
306#[test]
307fn test_calibration() {
308    fn exact(x: u64, from: u64, to: u64) -> u128 {
309        (x as u128 * to as u128 + from as u128 / 2) / from as u128
310    }
311
312    fn check<const BITS: u32>(cal_ticks: u64, cal_ns: u64) {
313        if cal_ticks >= 1 << (BITS - 1) || cal_ns >= (1 << 63) {
314            return;
315        }
316        let cal_d = WrappingU64Duration::<BITS>::new(cal_ticks);
317        let c = U64Calibration::<BITS>::new(cal_d, cal_ns);
318        for i in 0..128u64 {
319            let d = WrappingU64Duration::<BITS>::new(cal_ticks / 64 * i);
320            let want = exact(d.to_bits(), cal_d.to_bits(), cal_ns);
321            let got = c.convert_to_ns(d) as u128;
322            assert!(got.abs_diff(want) <= 1, "BITS={BITS} to_ns {got} != {want}");
323        }
324        for i in 0..128u64 {
325            let ns = cal_ns / 64 * i;
326            let want = exact(ns, cal_ns, cal_d.to_bits());
327            if want < 1u128 << 63 {
328                let got = c.convert_from_ns(ns).to_bits() as u128;
329                assert!(
330                    got.abs_diff(want) <= 1,
331                    "BITS={BITS} from_ns {got} != {want}"
332                );
333            }
334        }
335    }
336
337    macro_rules! check_bits {
338        ($($bits:literal),*) => {$({
339            let max = (1u64 << ($bits - 1)) - 1;
340            for ns in [1u64, 112,180,999_999_999, 1 << 62, (1u64 << 63) - 1,max] {
341                for ticks in [1,112,180,max,max/3+1]{
342                    check::<$bits>(ticks, ns);
343                }
344            }
345        })*};
346    }
347    check_bits!(2, 3, 7, 8, 15, 16, 23, 24, 31, 32, 40, 48, 56, 63, 64);
348}
fast_clock/wrapping_u64.rs

fast_clock/
wrapping_u64.rs
