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: u32 = (ticks & 0xFFFF_FFFF) as u32;
196 let time_mid: u16 = ((ticks >> 32) & 0xFFFF) as u16;
197 let time_high_and_version: u16 = (((ticks >> 48) & 0x0FFF) as u16) | (1 << 12);
198
199 let mut d4: [u8; 8] = [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(d1:time_low, d2:time_mid, d3:time_high_and_version, &d4)
211}
212
213pub(crate) const fn decode_gregorian_timestamp(uuid: &Uuid) -> (u64, u16) {
214 let bytes: &[u8; 16] = 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: u32 = ((ticks >> 28) & 0xFFFF_FFFF) as u32;
236 let time_mid: u16 = ((ticks >> 12) & 0xFFFF) as u16;
237 let time_low_and_version: u16 = ((ticks & 0x0FFF) as u16) | (0x6 << 12);
238
239 let mut d4: [u8; 8] = [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(d1:time_high, d2:time_mid, d3:time_low_and_version, &d4)
251}
252
253pub(crate) const fn decode_sorted_gregorian_timestamp(uuid: &Uuid) -> (u64, u16) {
254 let bytes: &[u8; 16] = 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: u32 = ((millis >> 16) & 0xFFFF_FFFF) as u32;
275 let millis_low: u16 = (millis & 0xFFFF) as u16;
276
277 let counter_random_version: u16 = (counter_random_bytes[1] as u16
278 | ((counter_random_bytes[0] as u16) << 8) & 0x0FFF)
279 | (0x7 << 12);
280
281 let mut d4: [u8; 8] = [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(d1:millis_high, d2:millis_low, d3:counter_random_version, &d4)
293}
294
295pub(crate) const fn decode_unix_timestamp_millis(uuid: &Uuid) -> u64 {
296 let bytes: &[u8; 16] = 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: Duration = std::time::SystemTime::UNIX_EPOCH.elapsed().expect(
349 msg:"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}
979