uuid/
timestamp.rs

1//! Generating UUIDs from timestamps.
2//!
3//! Timestamps are used in a few UUID versions as a source of decentralized
4//! uniqueness (as in versions 1 and 6), and as a way to enable sorting (as
5//! in versions 6 and 7). Timestamps aren't encoded the same way by all UUID
6//! versions so this module provides a single [`Timestamp`] type that can
7//! convert between them.
8//!
9//! # Timestamp representations in UUIDs
10//!
11//! Versions 1 and 6 UUIDs use a bespoke timestamp that consists of the
12//! number of 100ns ticks since `1582-10-15 00:00:00`, along with
13//! a counter value to avoid duplicates.
14//!
15//! Version 7 UUIDs use a more standard timestamp that consists of the
16//! number of millisecond ticks since the Unix epoch (`1970-01-01 00:00:00`).
17//!
18//! # References
19//!
20//! * [UUID Version 1 in RFC 9562](https://www.ietf.org/rfc/rfc9562.html#section-5.1)
21//! * [UUID Version 7 in RFC 9562](https://www.ietf.org/rfc/rfc9562.html#section-5.7)
22//! * [Timestamp Considerations in RFC 9562](https://www.ietf.org/rfc/rfc9562.html#section-6.1)
23
24use core::cmp;
25
26use crate::Uuid;
27
28/// The number of 100 nanosecond ticks between the RFC 9562 epoch
29/// (`1582-10-15 00:00:00`) and the Unix epoch (`1970-01-01 00:00:00`).
30pub const UUID_TICKS_BETWEEN_EPOCHS: u64 = 0x01B2_1DD2_1381_4000;
31
32/// A timestamp that can be encoded into a UUID.
33///
34/// This type abstracts the specific encoding, so versions 1, 6, and 7
35/// UUIDs can both be supported through the same type, even
36/// though they have a different representation of a timestamp.
37///
38/// # References
39///
40/// * [Timestamp Considerations in RFC 9562](https://www.ietf.org/rfc/rfc9562.html#section-6.1)
41/// * [UUID Generator States in RFC 9562](https://www.ietf.org/rfc/rfc9562.html#section-6.3)
42#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
43pub struct Timestamp {
44    seconds: u64,
45    subsec_nanos: u32,
46    counter: u128,
47    usable_counter_bits: u8,
48}
49
50impl Timestamp {
51    /// Get a timestamp representing the current system time and up to a 128-bit counter.
52    ///
53    /// This method defers to the standard library's `SystemTime` type.
54    #[cfg(feature = "std")]
55    pub fn now(context: impl ClockSequence<Output = impl Into<u128>>) -> Self {
56        let (seconds, subsec_nanos) = now();
57
58        let (counter, seconds, subsec_nanos) =
59            context.generate_timestamp_sequence(seconds, subsec_nanos);
60        let counter = counter.into();
61        let usable_counter_bits = context.usable_bits() as u8;
62
63        Timestamp {
64            seconds,
65            subsec_nanos,
66            counter,
67            usable_counter_bits,
68        }
69    }
70
71    /// Construct a `Timestamp` from the number of 100 nanosecond ticks since 00:00:00.00,
72    /// 15 October 1582 (the date of Gregorian reform to the Christian calendar) and a 14-bit
73    /// counter, as used in versions 1 and 6 UUIDs.
74    ///
75    /// # Overflow
76    ///
77    /// If conversion from RFC 9562 ticks to the internal timestamp format would overflow
78    /// it will wrap.
79    pub const fn from_gregorian(ticks: u64, counter: u16) -> Self {
80        let (seconds, subsec_nanos) = Self::gregorian_to_unix(ticks);
81
82        Timestamp {
83            seconds,
84            subsec_nanos,
85            counter: counter as u128,
86            usable_counter_bits: 14,
87        }
88    }
89
90    /// Construct a `Timestamp` from a Unix timestamp and up to a 128-bit counter, as used in version 7 UUIDs.
91    pub const fn from_unix_time(
92        seconds: u64,
93        subsec_nanos: u32,
94        counter: u128,
95        usable_counter_bits: u8,
96    ) -> Self {
97        Timestamp {
98            seconds,
99            subsec_nanos,
100            counter,
101            usable_counter_bits,
102        }
103    }
104
105    /// Construct a `Timestamp` from a Unix timestamp and up to a 128-bit counter, as used in version 7 UUIDs.
106    pub fn from_unix(
107        context: impl ClockSequence<Output = impl Into<u128>>,
108        seconds: u64,
109        subsec_nanos: u32,
110    ) -> Self {
111        let (counter, seconds, subsec_nanos) =
112            context.generate_timestamp_sequence(seconds, subsec_nanos);
113        let counter = counter.into();
114        let usable_counter_bits = context.usable_bits() as u8;
115
116        Timestamp {
117            seconds,
118            subsec_nanos,
119            counter,
120            usable_counter_bits,
121        }
122    }
123
124    /// Get the value of the timestamp as the number of 100 nanosecond ticks since 00:00:00.00,
125    /// 15 October 1582 and a 14-bit counter, as used in versions 1 and 6 UUIDs.
126    ///
127    /// # Overflow
128    ///
129    /// If conversion from the internal timestamp format to ticks would overflow
130    /// then it will wrap.
131    ///
132    /// If the internal counter is wider than 14 bits then it will be truncated to 14 bits.
133    pub const fn to_gregorian(&self) -> (u64, u16) {
134        (
135            Self::unix_to_gregorian_ticks(self.seconds, self.subsec_nanos),
136            (self.counter as u16) & 0x3FFF,
137        )
138    }
139
140    // NOTE: This method is not public; the usable counter bits are lost in a version 7 UUID
141    // so can't be reliably recovered.
142    #[cfg(feature = "v7")]
143    pub(crate) const fn counter(&self) -> (u128, u8) {
144        (self.counter, self.usable_counter_bits)
145    }
146
147    /// Get the value of the timestamp as a Unix timestamp, as used in version 7 UUIDs.
148    pub const fn to_unix(&self) -> (u64, u32) {
149        (self.seconds, self.subsec_nanos)
150    }
151
152    const fn unix_to_gregorian_ticks(seconds: u64, nanos: u32) -> u64 {
153        UUID_TICKS_BETWEEN_EPOCHS
154            .wrapping_add(seconds.wrapping_mul(10_000_000))
155            .wrapping_add(nanos as u64 / 100)
156    }
157
158    const fn gregorian_to_unix(ticks: u64) -> (u64, u32) {
159        (
160            ticks.wrapping_sub(UUID_TICKS_BETWEEN_EPOCHS) / 10_000_000,
161            (ticks.wrapping_sub(UUID_TICKS_BETWEEN_EPOCHS) % 10_000_000) as u32 * 100,
162        )
163    }
164}
165
166#[doc(hidden)]
167impl Timestamp {
168    #[deprecated(
169        since = "1.10.0",
170        note = "use `Timestamp::from_gregorian(ticks, counter)`"
171    )]
172    pub const fn from_rfc4122(ticks: u64, counter: u16) -> Self {
173        Timestamp::from_gregorian(ticks, counter)
174    }
175
176    #[deprecated(since = "1.10.0", note = "use `Timestamp::to_gregorian()`")]
177    pub const fn to_rfc4122(&self) -> (u64, u16) {
178        self.to_gregorian()
179    }
180
181    #[deprecated(
182        since = "1.2.0",
183        note = "`Timestamp::to_unix_nanos()` is deprecated and will be removed: use `Timestamp::to_unix()`"
184    )]
185    pub const fn to_unix_nanos(&self) -> u32 {
186        panic!("`Timestamp::to_unix_nanos()` is deprecated and will be removed: use `Timestamp::to_unix()`")
187    }
188}
189
190pub(crate) const fn encode_gregorian_timestamp(
191    ticks: u64,
192    counter: u16,
193    node_id: &[u8; 6],
194) -> Uuid {
195    let time_low = (ticks & 0xFFFF_FFFF) as u32;
196    let time_mid = ((ticks >> 32) & 0xFFFF) as u16;
197    let time_high_and_version = (((ticks >> 48) & 0x0FFF) as u16) | (1 << 12);
198
199    let mut d4 = [0; 8];
200
201    d4[0] = (((counter & 0x3F00) >> 8) as u8) | 0x80;
202    d4[1] = (counter & 0xFF) as u8;
203    d4[2] = node_id[0];
204    d4[3] = node_id[1];
205    d4[4] = node_id[2];
206    d4[5] = node_id[3];
207    d4[6] = node_id[4];
208    d4[7] = node_id[5];
209
210    Uuid::from_fields(time_low, time_mid, time_high_and_version, &d4)
211}
212
213pub(crate) const fn decode_gregorian_timestamp(uuid: &Uuid) -> (u64, u16) {
214    let bytes = uuid.as_bytes();
215
216    let ticks: u64 = ((bytes[6] & 0x0F) as u64) << 56
217        | (bytes[7] as u64) << 48
218        | (bytes[4] as u64) << 40
219        | (bytes[5] as u64) << 32
220        | (bytes[0] as u64) << 24
221        | (bytes[1] as u64) << 16
222        | (bytes[2] as u64) << 8
223        | (bytes[3] as u64);
224
225    let counter: u16 = ((bytes[8] & 0x3F) as u16) << 8 | (bytes[9] as u16);
226
227    (ticks, counter)
228}
229
230pub(crate) const fn encode_sorted_gregorian_timestamp(
231    ticks: u64,
232    counter: u16,
233    node_id: &[u8; 6],
234) -> Uuid {
235    let time_high = ((ticks >> 28) & 0xFFFF_FFFF) as u32;
236    let time_mid = ((ticks >> 12) & 0xFFFF) as u16;
237    let time_low_and_version = ((ticks & 0x0FFF) as u16) | (0x6 << 12);
238
239    let mut d4 = [0; 8];
240
241    d4[0] = (((counter & 0x3F00) >> 8) as u8) | 0x80;
242    d4[1] = (counter & 0xFF) as u8;
243    d4[2] = node_id[0];
244    d4[3] = node_id[1];
245    d4[4] = node_id[2];
246    d4[5] = node_id[3];
247    d4[6] = node_id[4];
248    d4[7] = node_id[5];
249
250    Uuid::from_fields(time_high, time_mid, time_low_and_version, &d4)
251}
252
253pub(crate) const fn decode_sorted_gregorian_timestamp(uuid: &Uuid) -> (u64, u16) {
254    let bytes = uuid.as_bytes();
255
256    let ticks: u64 = ((bytes[0]) as u64) << 52
257        | (bytes[1] as u64) << 44
258        | (bytes[2] as u64) << 36
259        | (bytes[3] as u64) << 28
260        | (bytes[4] as u64) << 20
261        | (bytes[5] as u64) << 12
262        | ((bytes[6] & 0xF) as u64) << 8
263        | (bytes[7] as u64);
264
265    let counter: u16 = ((bytes[8] & 0x3F) as u16) << 8 | (bytes[9] as u16);
266
267    (ticks, counter)
268}
269
270pub(crate) const fn encode_unix_timestamp_millis(
271    millis: u64,
272    counter_random_bytes: &[u8; 10],
273) -> Uuid {
274    let millis_high = ((millis >> 16) & 0xFFFF_FFFF) as u32;
275    let millis_low = (millis & 0xFFFF) as u16;
276
277    let counter_random_version = (counter_random_bytes[1] as u16
278        | ((counter_random_bytes[0] as u16) << 8) & 0x0FFF)
279        | (0x7 << 12);
280
281    let mut d4 = [0; 8];
282
283    d4[0] = (counter_random_bytes[2] & 0x3F) | 0x80;
284    d4[1] = counter_random_bytes[3];
285    d4[2] = counter_random_bytes[4];
286    d4[3] = counter_random_bytes[5];
287    d4[4] = counter_random_bytes[6];
288    d4[5] = counter_random_bytes[7];
289    d4[6] = counter_random_bytes[8];
290    d4[7] = counter_random_bytes[9];
291
292    Uuid::from_fields(millis_high, millis_low, counter_random_version, &d4)
293}
294
295pub(crate) const fn decode_unix_timestamp_millis(uuid: &Uuid) -> u64 {
296    let bytes = uuid.as_bytes();
297
298    let millis: u64 = (bytes[0] as u64) << 40
299        | (bytes[1] as u64) << 32
300        | (bytes[2] as u64) << 24
301        | (bytes[3] as u64) << 16
302        | (bytes[4] as u64) << 8
303        | (bytes[5] as u64);
304
305    millis
306}
307
308#[cfg(all(
309    feature = "std",
310    feature = "js",
311    all(
312        target_arch = "wasm32",
313        target_vendor = "unknown",
314        target_os = "unknown"
315    )
316))]
317fn now() -> (u64, u32) {
318    use wasm_bindgen::prelude::*;
319
320    #[wasm_bindgen]
321    extern "C" {
322        // NOTE: This signature works around https://bugzilla.mozilla.org/show_bug.cgi?id=1787770
323        #[wasm_bindgen(js_namespace = Date, catch)]
324        fn now() -> Result<f64, JsValue>;
325    }
326
327    let now = now().unwrap_throw();
328
329    let secs = (now / 1_000.0) as u64;
330    let nanos = ((now % 1_000.0) * 1_000_000.0) as u32;
331
332    (secs, nanos)
333}
334
335#[cfg(all(
336    feature = "std",
337    not(miri),
338    any(
339        not(feature = "js"),
340        not(all(
341            target_arch = "wasm32",
342            target_vendor = "unknown",
343            target_os = "unknown"
344        ))
345    )
346))]
347fn now() -> (u64, u32) {
348    let dur = std::time::SystemTime::UNIX_EPOCH.elapsed().expect(
349        "Getting elapsed time since UNIX_EPOCH. If this fails, we've somehow violated causality",
350    );
351
352    (dur.as_secs(), dur.subsec_nanos())
353}
354
355#[cfg(all(feature = "std", miri))]
356fn now() -> (u64, u32) {
357    use std::{sync::Mutex, time::Duration};
358
359    static TS: Mutex<u64> = Mutex::new(0);
360
361    let ts = Duration::from_nanos({
362        let mut ts = TS.lock().unwrap();
363        *ts += 1;
364        *ts
365    });
366
367    (ts.as_secs(), ts.subsec_nanos())
368}
369
370/// A counter that can be used by versions 1 and 6 UUIDs to support
371/// the uniqueness of timestamps.
372///
373/// # References
374///
375/// * [UUID Version 1 in RFC 9562](https://www.ietf.org/rfc/rfc9562.html#section-5.1)
376/// * [UUID Version 6 in RFC 9562](https://www.ietf.org/rfc/rfc9562.html#section-5.6)
377/// * [UUID Generator States in RFC 9562](https://www.ietf.org/rfc/rfc9562.html#section-6.3)
378pub trait ClockSequence {
379    /// The type of sequence returned by this counter.
380    type Output;
381
382    /// Get the next value in the sequence to feed into a timestamp.
383    ///
384    /// This method will be called each time a [`Timestamp`] is constructed.
385    ///
386    /// Any bits beyond [`ClockSequence::usable_bits`] in the output must be unset.
387    fn generate_sequence(&self, seconds: u64, subsec_nanos: u32) -> Self::Output;
388
389    /// Get the next value in the sequence, potentially also adjusting the timestamp.
390    ///
391    /// This method should be preferred over `generate_sequence`.
392    ///
393    /// Any bits beyond [`ClockSequence::usable_bits`] in the output must be unset.
394    fn generate_timestamp_sequence(
395        &self,
396        seconds: u64,
397        subsec_nanos: u32,
398    ) -> (Self::Output, u64, u32) {
399        (
400            self.generate_sequence(seconds, subsec_nanos),
401            seconds,
402            subsec_nanos,
403        )
404    }
405
406    /// The number of usable bits from the least significant bit in the result of [`ClockSequence::generate_sequence`]
407    /// or [`ClockSequence::generate_timestamp_sequence`].
408    ///
409    /// The number of usable bits must not exceed 128.
410    ///
411    /// The number of usable bits is not expected to change between calls. An implementation of `ClockSequence` should
412    /// always return the same value from this method.
413    fn usable_bits(&self) -> usize
414    where
415        Self::Output: Sized,
416    {
417        cmp::min(128, core::mem::size_of::<Self::Output>())
418    }
419}
420
421impl<'a, T: ClockSequence + ?Sized> ClockSequence for &'a T {
422    type Output = T::Output;
423
424    fn generate_sequence(&self, seconds: u64, subsec_nanos: u32) -> Self::Output {
425        (**self).generate_sequence(seconds, subsec_nanos)
426    }
427
428    fn generate_timestamp_sequence(
429        &self,
430        seconds: u64,
431        subsec_nanos: u32,
432    ) -> (Self::Output, u64, u32) {
433        (**self).generate_timestamp_sequence(seconds, subsec_nanos)
434    }
435
436    fn usable_bits(&self) -> usize
437    where
438        Self::Output: Sized,
439    {
440        (**self).usable_bits()
441    }
442}
443
444/// Default implementations for the [`ClockSequence`] trait.
445pub mod context {
446    use super::ClockSequence;
447
448    #[cfg(any(feature = "v1", feature = "v6"))]
449    mod v1_support {
450        use super::*;
451
452        use atomic::{Atomic, Ordering};
453
454        #[cfg(all(feature = "std", feature = "rng"))]
455        static CONTEXT: Context = Context {
456            count: Atomic::new(0),
457        };
458
459        #[cfg(all(feature = "std", feature = "rng"))]
460        static CONTEXT_INITIALIZED: Atomic<bool> = Atomic::new(false);
461
462        #[cfg(all(feature = "std", feature = "rng"))]
463        pub(crate) fn shared_context() -> &'static Context {
464            // If the context is in its initial state then assign it to a random value
465            // It doesn't matter if multiple threads observe `false` here and initialize the context
466            if CONTEXT_INITIALIZED
467                .compare_exchange(false, true, Ordering::Relaxed, Ordering::Relaxed)
468                .is_ok()
469            {
470                CONTEXT.count.store(crate::rng::u16(), Ordering::Release);
471            }
472
473            &CONTEXT
474        }
475
476        /// A thread-safe, wrapping counter that produces 14-bit values.
477        ///
478        /// This type works by:
479        ///
480        /// 1. Atomically incrementing the counter value for each timestamp.
481        /// 2. Wrapping the counter back to zero if it overflows its 14-bit storage.
482        ///
483        /// This type should be used when constructing versions 1 and 6 UUIDs.
484        ///
485        /// This type should not be used when constructing version 7 UUIDs. When used to
486        /// construct a version 7 UUID, the 14-bit counter will be padded with random data.
487        /// Counter overflows are more likely with a 14-bit counter than they are with a
488        /// 42-bit counter when working at millisecond precision. This type doesn't attempt
489        /// to adjust the timestamp on overflow.
490        #[derive(Debug)]
491        pub struct Context {
492            count: Atomic<u16>,
493        }
494
495        impl Context {
496            /// Construct a new context that's initialized with the given value.
497            ///
498            /// The starting value should be a random number, so that UUIDs from
499            /// different systems with the same timestamps are less likely to collide.
500            /// When the `rng` feature is enabled, prefer the [`Context::new_random`] method.
501            pub const fn new(count: u16) -> Self {
502                Self {
503                    count: Atomic::<u16>::new(count),
504                }
505            }
506
507            /// Construct a new context that's initialized with a random value.
508            #[cfg(feature = "rng")]
509            pub fn new_random() -> Self {
510                Self {
511                    count: Atomic::<u16>::new(crate::rng::u16()),
512                }
513            }
514        }
515
516        impl ClockSequence for Context {
517            type Output = u16;
518
519            fn generate_sequence(&self, _seconds: u64, _nanos: u32) -> Self::Output {
520                // RFC 9562 reserves 2 bits of the clock sequence so the actual
521                // maximum value is smaller than `u16::MAX`. Since we unconditionally
522                // increment the clock sequence we want to wrap once it becomes larger
523                // than what we can represent in a "u14". Otherwise there'd be patches
524                // where the clock sequence doesn't change regardless of the timestamp
525                self.count.fetch_add(1, Ordering::AcqRel) & (u16::MAX >> 2)
526            }
527
528            fn usable_bits(&self) -> usize {
529                14
530            }
531        }
532
533        #[cfg(test)]
534        mod tests {
535            use crate::Timestamp;
536
537            use super::*;
538
539            #[test]
540            fn context() {
541                let seconds = 1_496_854_535;
542                let subsec_nanos = 812_946_000;
543
544                let context = Context::new(u16::MAX >> 2);
545
546                let ts = Timestamp::from_unix(&context, seconds, subsec_nanos);
547                assert_eq!(16383, ts.counter);
548                assert_eq!(14, ts.usable_counter_bits);
549
550                let seconds = 1_496_854_536;
551
552                let ts = Timestamp::from_unix(&context, seconds, subsec_nanos);
553                assert_eq!(0, ts.counter);
554
555                let seconds = 1_496_854_535;
556
557                let ts = Timestamp::from_unix(&context, seconds, subsec_nanos);
558                assert_eq!(1, ts.counter);
559            }
560        }
561    }
562
563    #[cfg(any(feature = "v1", feature = "v6"))]
564    pub use v1_support::*;
565
566    #[cfg(feature = "std")]
567    mod std_support {
568        use super::*;
569
570        use core::panic::{AssertUnwindSafe, RefUnwindSafe};
571        use std::{sync::Mutex, thread::LocalKey};
572
573        /// A wrapper for a context that uses thread-local storage.
574        pub struct ThreadLocalContext<C: 'static>(&'static LocalKey<C>);
575
576        impl<C> std::fmt::Debug for ThreadLocalContext<C> {
577            fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
578                f.debug_struct("ThreadLocalContext").finish_non_exhaustive()
579            }
580        }
581
582        impl<C: 'static> ThreadLocalContext<C> {
583            /// Wrap a thread-local container with a context.
584            pub const fn new(local_key: &'static LocalKey<C>) -> Self {
585                ThreadLocalContext(local_key)
586            }
587        }
588
589        impl<C: ClockSequence + 'static> ClockSequence for ThreadLocalContext<C> {
590            type Output = C::Output;
591
592            fn generate_sequence(&self, seconds: u64, subsec_nanos: u32) -> Self::Output {
593                self.0
594                    .with(|ctxt| ctxt.generate_sequence(seconds, subsec_nanos))
595            }
596
597            fn generate_timestamp_sequence(
598                &self,
599                seconds: u64,
600                subsec_nanos: u32,
601            ) -> (Self::Output, u64, u32) {
602                self.0
603                    .with(|ctxt| ctxt.generate_timestamp_sequence(seconds, subsec_nanos))
604            }
605
606            fn usable_bits(&self) -> usize {
607                self.0.with(|ctxt| ctxt.usable_bits())
608            }
609        }
610
611        impl<C: ClockSequence> ClockSequence for AssertUnwindSafe<C> {
612            type Output = C::Output;
613
614            fn generate_sequence(&self, seconds: u64, subsec_nanos: u32) -> Self::Output {
615                self.0.generate_sequence(seconds, subsec_nanos)
616            }
617
618            fn generate_timestamp_sequence(
619                &self,
620                seconds: u64,
621                subsec_nanos: u32,
622            ) -> (Self::Output, u64, u32) {
623                self.0.generate_timestamp_sequence(seconds, subsec_nanos)
624            }
625
626            fn usable_bits(&self) -> usize
627            where
628                Self::Output: Sized,
629            {
630                self.0.usable_bits()
631            }
632        }
633
634        impl<C: ClockSequence + RefUnwindSafe> ClockSequence for Mutex<C> {
635            type Output = C::Output;
636
637            fn generate_sequence(&self, seconds: u64, subsec_nanos: u32) -> Self::Output {
638                self.lock()
639                    .unwrap_or_else(|err| err.into_inner())
640                    .generate_sequence(seconds, subsec_nanos)
641            }
642
643            fn generate_timestamp_sequence(
644                &self,
645                seconds: u64,
646                subsec_nanos: u32,
647            ) -> (Self::Output, u64, u32) {
648                self.lock()
649                    .unwrap_or_else(|err| err.into_inner())
650                    .generate_timestamp_sequence(seconds, subsec_nanos)
651            }
652
653            fn usable_bits(&self) -> usize
654            where
655                Self::Output: Sized,
656            {
657                self.lock()
658                    .unwrap_or_else(|err| err.into_inner())
659                    .usable_bits()
660            }
661        }
662    }
663
664    #[cfg(feature = "std")]
665    pub use std_support::*;
666
667    #[cfg(feature = "v7")]
668    mod v7_support {
669        use super::*;
670
671        use core::{cell::Cell, panic::RefUnwindSafe};
672
673        #[cfg(feature = "std")]
674        static CONTEXT_V7: SharedContextV7 =
675            SharedContextV7(std::sync::Mutex::new(ContextV7::new()));
676
677        #[cfg(feature = "std")]
678        pub(crate) fn shared_context_v7() -> &'static SharedContextV7 {
679            &CONTEXT_V7
680        }
681
682        const USABLE_BITS: usize = 42;
683
684        // Leave the most significant bit unset
685        // This guarantees the counter has at least 2,199,023,255,552
686        // values before it will overflow, which is exceptionally unlikely
687        // even in the worst case
688        const RESEED_MASK: u64 = u64::MAX >> 23;
689        const MAX_COUNTER: u64 = u64::MAX >> 22;
690
691        /// An unsynchronized, reseeding counter that produces 42-bit values.
692        ///
693        /// This type works by:
694        ///
695        /// 1. Reseeding the counter each millisecond with a random 41-bit value. The 42nd bit
696        ///    is left unset so the counter can safely increment over the millisecond.
697        /// 2. Wrapping the counter back to zero if it overflows its 42-bit storage and adding a
698        ///    millisecond to the timestamp.
699        ///
700        /// This type can be used when constructing version 7 UUIDs. When used to construct a
701        /// version 7 UUID, the 42-bit counter will be padded with random data. This type can
702        /// be used to maintain ordering of UUIDs within the same millisecond.
703        ///
704        /// This type should not be used when constructing version 1 or version 6 UUIDs.
705        /// When used to construct a version 1 or version 6 UUID, only the 14 least significant
706        /// bits of the counter will be used.
707        #[derive(Debug)]
708        pub struct ContextV7 {
709            last_reseed: Cell<LastReseed>,
710            counter: Cell<u64>,
711        }
712
713        #[derive(Debug, Default, Clone, Copy)]
714        struct LastReseed {
715            millis: u64,
716            ts_seconds: u64,
717            ts_subsec_nanos: u32,
718        }
719
720        impl LastReseed {
721            fn from_millis(millis: u64) -> Self {
722                LastReseed {
723                    millis,
724                    ts_seconds: millis / 1_000,
725                    ts_subsec_nanos: (millis % 1_000) as u32 * 1_000_000,
726                }
727            }
728        }
729
730        impl RefUnwindSafe for ContextV7 {}
731
732        impl ContextV7 {
733            /// Construct a new context that will reseed its counter on the first
734            /// non-zero timestamp it receives.
735            pub const fn new() -> Self {
736                ContextV7 {
737                    last_reseed: Cell::new(LastReseed {
738                        millis: 0,
739                        ts_seconds: 0,
740                        ts_subsec_nanos: 0,
741                    }),
742                    counter: Cell::new(0),
743                }
744            }
745        }
746
747        impl ClockSequence for ContextV7 {
748            type Output = u64;
749
750            fn generate_sequence(&self, seconds: u64, subsec_nanos: u32) -> Self::Output {
751                self.generate_timestamp_sequence(seconds, subsec_nanos).0
752            }
753
754            fn generate_timestamp_sequence(
755                &self,
756                seconds: u64,
757                subsec_nanos: u32,
758            ) -> (Self::Output, u64, u32) {
759                let millis = (seconds * 1_000).saturating_add(subsec_nanos as u64 / 1_000_000);
760
761                let last_reseed = self.last_reseed.get();
762
763                // If the observed system time has shifted forwards then regenerate the counter
764                if millis > last_reseed.millis {
765                    let last_reseed = LastReseed::from_millis(millis);
766                    self.last_reseed.set(last_reseed);
767
768                    let counter = crate::rng::u64() & RESEED_MASK;
769                    self.counter.set(counter);
770
771                    (counter, last_reseed.ts_seconds, last_reseed.ts_subsec_nanos)
772                }
773                // If the observed system time has not shifted forwards then increment the counter
774                else {
775                    // If the incoming timestamp is earlier than the last observed one then
776                    // use it instead. This may happen if the system clock jitters, or if the counter
777                    // has wrapped and the timestamp is artificially incremented
778                    let millis = ();
779                    let _ = millis;
780
781                    // Guaranteed to never overflow u64
782                    let counter = self.counter.get() + 1;
783
784                    // If the counter has not overflowed its 42-bit storage then return it
785                    if counter <= MAX_COUNTER {
786                        self.counter.set(counter);
787
788                        (counter, last_reseed.ts_seconds, last_reseed.ts_subsec_nanos)
789                    }
790                    // Unlikely: If the counter has overflowed its 42-bit storage then wrap it
791                    // and increment the timestamp. Until the observed system time shifts past
792                    // this incremented value, all timestamps will use it to maintain monotonicity
793                    else {
794                        // Increment the timestamp by 1 milli
795                        let last_reseed = LastReseed::from_millis(last_reseed.millis + 1);
796                        self.last_reseed.set(last_reseed);
797
798                        // Reseed the counter
799                        let counter = crate::rng::u64() & RESEED_MASK;
800                        self.counter.set(counter);
801
802                        (counter, last_reseed.ts_seconds, last_reseed.ts_subsec_nanos)
803                    }
804                }
805            }
806
807            fn usable_bits(&self) -> usize {
808                USABLE_BITS
809            }
810        }
811
812        #[cfg(feature = "std")]
813        pub(crate) struct SharedContextV7(std::sync::Mutex<ContextV7>);
814
815        #[cfg(feature = "std")]
816        impl ClockSequence for SharedContextV7 {
817            type Output = u64;
818
819            fn generate_sequence(&self, seconds: u64, subsec_nanos: u32) -> Self::Output {
820                self.0.generate_sequence(seconds, subsec_nanos)
821            }
822
823            fn generate_timestamp_sequence(
824                &self,
825                seconds: u64,
826                subsec_nanos: u32,
827            ) -> (Self::Output, u64, u32) {
828                self.0.generate_timestamp_sequence(seconds, subsec_nanos)
829            }
830
831            fn usable_bits(&self) -> usize
832            where
833                Self::Output: Sized,
834            {
835                USABLE_BITS
836            }
837        }
838
839        #[cfg(test)]
840        mod tests {
841            use core::time::Duration;
842
843            use super::*;
844
845            use crate::Timestamp;
846
847            #[test]
848            fn context() {
849                let seconds = 1_496_854_535;
850                let subsec_nanos = 812_946_000;
851
852                let context = ContextV7::new();
853
854                let ts1 = Timestamp::from_unix(&context, seconds, subsec_nanos);
855                assert_eq!(42, ts1.usable_counter_bits);
856
857                // Backwards second
858                let seconds = 1_496_854_534;
859
860                let ts2 = Timestamp::from_unix(&context, seconds, subsec_nanos);
861
862                // The backwards time should be ignored
863                // The counter should still increment
864                assert_eq!(ts1.seconds, ts2.seconds);
865                assert_eq!(ts1.subsec_nanos, ts2.subsec_nanos);
866                assert_eq!(ts1.counter + 1, ts2.counter);
867
868                // Forwards second
869                let seconds = 1_496_854_536;
870
871                let ts3 = Timestamp::from_unix(&context, seconds, subsec_nanos);
872
873                // The counter should have reseeded
874                assert_ne!(ts2.counter + 1, ts3.counter);
875                assert_ne!(0, ts3.counter);
876            }
877
878            #[test]
879            fn context_wrap() {
880                let seconds = 1_496_854_535u64;
881                let subsec_nanos = 812_946_000u32;
882
883                let millis = (seconds * 1000).saturating_add(subsec_nanos as u64 / 1_000_000);
884
885                // This context will wrap
886                let context = ContextV7 {
887                    last_reseed: Cell::new(LastReseed::from_millis(millis)),
888                    counter: Cell::new(u64::MAX >> 22),
889                };
890
891                let ts = Timestamp::from_unix(&context, seconds, subsec_nanos);
892
893                // The timestamp should be incremented by 1ms
894                let expected_ts = Duration::new(seconds, subsec_nanos / 1_000_000 * 1_000_000)
895                    + Duration::from_millis(1);
896                assert_eq!(expected_ts.as_secs(), ts.seconds);
897                assert_eq!(expected_ts.subsec_nanos(), ts.subsec_nanos);
898
899                // The counter should have reseeded
900                assert!(ts.counter < (u64::MAX >> 22) as u128);
901                assert_ne!(0, ts.counter);
902            }
903        }
904    }
905
906    #[cfg(feature = "v7")]
907    pub use v7_support::*;
908
909    /// An empty counter that will always return the value `0`.
910    ///
911    /// This type can be used when constructing version 7 UUIDs. When used to
912    /// construct a version 7 UUID, the entire counter segment of the UUID will be
913    /// filled with a random value. This type does not maintain ordering of UUIDs
914    /// within a millisecond but is efficient.
915    ///
916    /// This type should not be used when constructing version 1 or version 6 UUIDs.
917    /// When used to construct a version 1 or version 6 UUID, the counter
918    /// segment will remain zero.
919    #[derive(Debug, Clone, Copy, Default)]
920    pub struct NoContext;
921
922    impl ClockSequence for NoContext {
923        type Output = u16;
924
925        fn generate_sequence(&self, _seconds: u64, _nanos: u32) -> Self::Output {
926            0
927        }
928
929        fn usable_bits(&self) -> usize {
930            0
931        }
932    }
933}
934
935#[cfg(all(test, any(feature = "v1", feature = "v6")))]
936mod tests {
937    use super::*;
938
939    #[cfg(all(
940        target_arch = "wasm32",
941        target_vendor = "unknown",
942        target_os = "unknown"
943    ))]
944    use wasm_bindgen_test::*;
945
946    #[test]
947    #[cfg_attr(
948        all(
949            target_arch = "wasm32",
950            target_vendor = "unknown",
951            target_os = "unknown"
952        ),
953        wasm_bindgen_test
954    )]
955    fn gregorian_unix_does_not_panic() {
956        // Ensure timestamp conversions never panic
957        Timestamp::unix_to_gregorian_ticks(u64::MAX, 0);
958        Timestamp::unix_to_gregorian_ticks(0, u32::MAX);
959        Timestamp::unix_to_gregorian_ticks(u64::MAX, u32::MAX);
960
961        Timestamp::gregorian_to_unix(u64::MAX);
962    }
963
964    #[test]
965    #[cfg_attr(
966        all(
967            target_arch = "wasm32",
968            target_vendor = "unknown",
969            target_os = "unknown"
970        ),
971        wasm_bindgen_test
972    )]
973    fn to_gregorian_truncates_to_usable_bits() {
974        let ts = Timestamp::from_gregorian(123, u16::MAX);
975
976        assert_eq!((123, u16::MAX >> 2), ts.to_gregorian());
977    }
978}