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//! * [Timestamp in RFC4122](https://www.rfc-editor.org/rfc/rfc4122#section-4.1.4)
21//! * [Timestamp in Draft RFC: New UUID Formats, Version 4](https://datatracker.ietf.org/doc/html/draft-peabody-dispatch-new-uuid-format-04#section-6.1)
22
23use crate::Uuid;
24
25/// The number of 100 nanosecond ticks between the RFC4122 epoch
26/// (`1582-10-15 00:00:00`) and the Unix epoch (`1970-01-01 00:00:00`).
27pub const UUID_TICKS_BETWEEN_EPOCHS: u64 = 0x01B2_1DD2_1381_4000;
28
29/// A timestamp that can be encoded into a UUID.
30///
31/// This type abstracts the specific encoding, so versions 1, 6, and 7
32/// UUIDs can both be supported through the same type, even
33/// though they have a different representation of a timestamp.
34///
35/// # References
36///
37/// * [Timestamp in RFC4122](https://www.rfc-editor.org/rfc/rfc4122#section-4.1.4)
38/// * [Timestamp in Draft RFC: New UUID Formats, Version 4](https://datatracker.ietf.org/doc/html/draft-peabody-dispatch-new-uuid-format-04#section-6.1)
39/// * [Clock Sequence in RFC4122](https://datatracker.ietf.org/doc/html/rfc4122#section-4.1.5)
40#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
41pub struct Timestamp {
42 pub(crate) seconds: u64,
43 pub(crate) nanos: u32,
44 #[cfg(any(feature = "v1", feature = "v6"))]
45 pub(crate) counter: u16,
46}
47
48impl Timestamp {
49 /// Get a timestamp representing the current system time.
50 ///
51 /// This method defers to the standard library's `SystemTime` type.
52 ///
53 /// # Panics
54 ///
55 /// This method will panic if calculating the elapsed time since the Unix epoch fails.
56 #[cfg(feature = "std")]
57 pub fn now(context: impl ClockSequence<Output = u16>) -> Self {
58 #[cfg(not(any(feature = "v1", feature = "v6")))]
59 {
60 let _ = context;
61 }
62
63 let (seconds, nanos) = now();
64
65 Timestamp {
66 seconds,
67 nanos,
68 #[cfg(any(feature = "v1", feature = "v6"))]
69 counter: context.generate_sequence(seconds, nanos),
70 }
71 }
72
73 /// Construct a `Timestamp` from an RFC4122 timestamp and counter, as used
74 /// in versions 1 and 6 UUIDs.
75 ///
76 /// # Overflow
77 ///
78 /// If conversion from RFC4122 ticks to the internal timestamp format would overflow
79 /// it will wrap.
80 pub const fn from_rfc4122(ticks: u64, counter: u16) -> Self {
81 #[cfg(not(any(feature = "v1", feature = "v6")))]
82 {
83 let _ = counter;
84 }
85
86 let (seconds, nanos) = Self::rfc4122_to_unix(ticks);
87
88 Timestamp {
89 seconds,
90 nanos,
91 #[cfg(any(feature = "v1", feature = "v6"))]
92 counter,
93 }
94 }
95
96 /// Construct a `Timestamp` from a Unix timestamp, as used in version 7 UUIDs.
97 ///
98 /// # Overflow
99 ///
100 /// If conversion from RFC4122 ticks to the internal timestamp format would overflow
101 /// it will wrap.
102 pub fn from_unix(context: impl ClockSequence<Output = u16>, seconds: u64, nanos: u32) -> Self {
103 #[cfg(not(any(feature = "v1", feature = "v6")))]
104 {
105 let _ = context;
106
107 Timestamp { seconds, nanos }
108 }
109 #[cfg(any(feature = "v1", feature = "v6"))]
110 {
111 let counter = context.generate_sequence(seconds, nanos);
112
113 Timestamp {
114 seconds,
115 nanos,
116 counter,
117 }
118 }
119 }
120
121 /// Get the value of the timestamp as an RFC4122 timestamp and counter,
122 /// as used in versions 1 and 6 UUIDs.
123 ///
124 /// # Overflow
125 ///
126 /// If conversion from RFC4122 ticks to the internal timestamp format would overflow
127 /// it will wrap.
128 #[cfg(any(feature = "v1", feature = "v6"))]
129 pub const fn to_rfc4122(&self) -> (u64, u16) {
130 (
131 Self::unix_to_rfc4122_ticks(self.seconds, self.nanos),
132 self.counter,
133 )
134 }
135
136 /// Get the value of the timestamp as a Unix timestamp, as used in version 7 UUIDs.
137 ///
138 /// # Overflow
139 ///
140 /// If conversion from RFC4122 ticks to the internal timestamp format would overflow
141 /// it will wrap.
142 pub const fn to_unix(&self) -> (u64, u32) {
143 (self.seconds, self.nanos)
144 }
145
146 #[cfg(any(feature = "v1", feature = "v6"))]
147 const fn unix_to_rfc4122_ticks(seconds: u64, nanos: u32) -> u64 {
148 let ticks = UUID_TICKS_BETWEEN_EPOCHS
149 .wrapping_add(seconds.wrapping_mul(10_000_000))
150 .wrapping_add(nanos as u64 / 100);
151
152 ticks
153 }
154
155 const fn rfc4122_to_unix(ticks: u64) -> (u64, u32) {
156 (
157 ticks.wrapping_sub(UUID_TICKS_BETWEEN_EPOCHS) / 10_000_000,
158 (ticks.wrapping_sub(UUID_TICKS_BETWEEN_EPOCHS) % 10_000_000) as u32 * 100,
159 )
160 }
161
162 #[deprecated(note = "use `to_unix` instead; this method will be removed in a future release")]
163 /// Get the number of fractional nanoseconds in the Unix timestamp.
164 ///
165 /// This method is deprecated and probably doesn't do what you're expecting it to.
166 /// It doesn't return the timestamp as nanoseconds since the Unix epoch, it returns
167 /// the fractional seconds of the timestamp.
168 pub const fn to_unix_nanos(&self) -> u32 {
169 panic!("`Timestamp::to_unix_nanos` is deprecated and will be removed: use `Timestamp::to_unix` instead")
170 }
171}
172
173pub(crate) const fn encode_rfc4122_timestamp(ticks: u64, counter: u16, node_id: &[u8; 6]) -> Uuid {
174 let time_low: u32 = (ticks & 0xFFFF_FFFF) as u32;
175 let time_mid: u16 = ((ticks >> 32) & 0xFFFF) as u16;
176 let time_high_and_version: u16 = (((ticks >> 48) & 0x0FFF) as u16) | (1 << 12);
177
178 let mut d4: [u8; 8] = [0; 8];
179
180 d4[0] = (((counter & 0x3F00) >> 8) as u8) | 0x80;
181 d4[1] = (counter & 0xFF) as u8;
182 d4[2] = node_id[0];
183 d4[3] = node_id[1];
184 d4[4] = node_id[2];
185 d4[5] = node_id[3];
186 d4[6] = node_id[4];
187 d4[7] = node_id[5];
188
189 Uuid::from_fields(d1:time_low, d2:time_mid, d3:time_high_and_version, &d4)
190}
191
192pub(crate) const fn decode_rfc4122_timestamp(uuid: &Uuid) -> (u64, u16) {
193 let bytes: &[u8; 16] = uuid.as_bytes();
194
195 let ticks: u64 = ((bytes[6] & 0x0F) as u64) << 56
196 | (bytes[7] as u64) << 48
197 | (bytes[4] as u64) << 40
198 | (bytes[5] as u64) << 32
199 | (bytes[0] as u64) << 24
200 | (bytes[1] as u64) << 16
201 | (bytes[2] as u64) << 8
202 | (bytes[3] as u64);
203
204 let counter: u16 = ((bytes[8] & 0x3F) as u16) << 8 | (bytes[9] as u16);
205
206 (ticks, counter)
207}
208
209#[cfg(uuid_unstable)]
210pub(crate) const fn encode_sorted_rfc4122_timestamp(
211 ticks: u64,
212 counter: u16,
213 node_id: &[u8; 6],
214) -> Uuid {
215 let time_high = ((ticks >> 28) & 0xFFFF_FFFF) as u32;
216 let time_mid = ((ticks >> 12) & 0xFFFF) as u16;
217 let time_low_and_version = ((ticks & 0x0FFF) as u16) | (0x6 << 12);
218
219 let mut d4 = [0; 8];
220
221 d4[0] = (((counter & 0x3F00) >> 8) as u8) | 0x80;
222 d4[1] = (counter & 0xFF) as u8;
223 d4[2] = node_id[0];
224 d4[3] = node_id[1];
225 d4[4] = node_id[2];
226 d4[5] = node_id[3];
227 d4[6] = node_id[4];
228 d4[7] = node_id[5];
229
230 Uuid::from_fields(time_high, time_mid, time_low_and_version, &d4)
231}
232
233#[cfg(uuid_unstable)]
234pub(crate) const fn decode_sorted_rfc4122_timestamp(uuid: &Uuid) -> (u64, u16) {
235 let bytes = uuid.as_bytes();
236
237 let ticks: u64 = ((bytes[0]) as u64) << 52
238 | (bytes[1] as u64) << 44
239 | (bytes[2] as u64) << 36
240 | (bytes[3] as u64) << 28
241 | (bytes[4] as u64) << 20
242 | (bytes[5] as u64) << 12
243 | ((bytes[6] & 0xF) as u64) << 8
244 | (bytes[7] as u64);
245
246 let counter: u16 = ((bytes[8] & 0x3F) as u16) << 8 | (bytes[9] as u16);
247
248 (ticks, counter)
249}
250
251#[cfg(uuid_unstable)]
252pub(crate) const fn encode_unix_timestamp_millis(millis: u64, random_bytes: &[u8; 10]) -> Uuid {
253 let millis_high = ((millis >> 16) & 0xFFFF_FFFF) as u32;
254 let millis_low = (millis & 0xFFFF) as u16;
255
256 let random_and_version =
257 (random_bytes[1] as u16 | ((random_bytes[0] as u16) << 8) & 0x0FFF) | (0x7 << 12);
258
259 let mut d4 = [0; 8];
260
261 d4[0] = (random_bytes[2] & 0x3F) | 0x80;
262 d4[1] = random_bytes[3];
263 d4[2] = random_bytes[4];
264 d4[3] = random_bytes[5];
265 d4[4] = random_bytes[6];
266 d4[5] = random_bytes[7];
267 d4[6] = random_bytes[8];
268 d4[7] = random_bytes[9];
269
270 Uuid::from_fields(millis_high, millis_low, random_and_version, &d4)
271}
272
273#[cfg(uuid_unstable)]
274pub(crate) const fn decode_unix_timestamp_millis(uuid: &Uuid) -> u64 {
275 let bytes = uuid.as_bytes();
276
277 let millis: u64 = (bytes[0] as u64) << 40
278 | (bytes[1] as u64) << 32
279 | (bytes[2] as u64) << 24
280 | (bytes[3] as u64) << 16
281 | (bytes[4] as u64) << 8
282 | (bytes[5] as u64);
283
284 millis
285}
286
287#[cfg(all(
288 feature = "std",
289 feature = "js",
290 all(
291 target_arch = "wasm32",
292 target_vendor = "unknown",
293 target_os = "unknown"
294 )
295))]
296fn now() -> (u64, u32) {
297 use wasm_bindgen::prelude::*;
298
299 #[wasm_bindgen]
300 extern "C" {
301 // NOTE: This signature works around https://bugzilla.mozilla.org/show_bug.cgi?id=1787770
302 #[wasm_bindgen(js_namespace = Date, catch)]
303 fn now() -> Result<f64, JsValue>;
304 }
305
306 let now = now().unwrap_throw();
307
308 let secs = (now / 1_000.0) as u64;
309 let nanos = ((now % 1_000.0) * 1_000_000.0) as u32;
310
311 (secs, nanos)
312}
313
314#[cfg(all(
315 feature = "std",
316 any(
317 not(feature = "js"),
318 not(all(
319 target_arch = "wasm32",
320 target_vendor = "unknown",
321 target_os = "unknown"
322 ))
323 )
324))]
325fn now() -> (u64, u32) {
326 let dur: Duration = std::time::SystemTime::UNIX_EPOCH.elapsed().expect(
327 msg:"Getting elapsed time since UNIX_EPOCH. If this fails, we've somehow violated causality",
328 );
329
330 (dur.as_secs(), dur.subsec_nanos())
331}
332
333/// A counter that can be used by version 1 and version 6 UUIDs to support
334/// the uniqueness of timestamps.
335///
336/// # References
337///
338/// * [Clock Sequence in RFC4122](https://datatracker.ietf.org/doc/html/rfc4122#section-4.1.5)
339pub trait ClockSequence {
340 /// The type of sequence returned by this counter.
341 type Output;
342
343 /// Get the next value in the sequence to feed into a timestamp.
344 ///
345 /// This method will be called each time a [`Timestamp`] is constructed.
346 fn generate_sequence(&self, seconds: u64, subsec_nanos: u32) -> Self::Output;
347}
348
349impl<'a, T: ClockSequence + ?Sized> ClockSequence for &'a T {
350 type Output = T::Output;
351 fn generate_sequence(&self, seconds: u64, subsec_nanos: u32) -> Self::Output {
352 (**self).generate_sequence(seconds, subsec_nanos)
353 }
354}
355
356/// Default implementations for the [`ClockSequence`] trait.
357pub mod context {
358 use super::ClockSequence;
359
360 #[cfg(any(feature = "v1", feature = "v6"))]
361 use atomic::{Atomic, Ordering};
362
363 /// An empty counter that will always return the value `0`.
364 ///
365 /// This type should be used when constructing timestamps for version 7 UUIDs,
366 /// since they don't need a counter for uniqueness.
367 #[derive(Debug, Clone, Copy, Default)]
368 pub struct NoContext;
369
370 impl ClockSequence for NoContext {
371 type Output = u16;
372
373 fn generate_sequence(&self, _seconds: u64, _nanos: u32) -> Self::Output {
374 0
375 }
376 }
377
378 #[cfg(all(any(feature = "v1", feature = "v6"), feature = "std", feature = "rng"))]
379 static CONTEXT: Context = Context {
380 count: Atomic::new(0),
381 };
382
383 #[cfg(all(any(feature = "v1", feature = "v6"), feature = "std", feature = "rng"))]
384 static CONTEXT_INITIALIZED: Atomic<bool> = Atomic::new(false);
385
386 #[cfg(all(any(feature = "v1", feature = "v6"), feature = "std", feature = "rng"))]
387 pub(crate) fn shared_context() -> &'static Context {
388 // If the context is in its initial state then assign it to a random value
389 // It doesn't matter if multiple threads observe `false` here and initialize the context
390 if CONTEXT_INITIALIZED
391 .compare_exchange(false, true, Ordering::Relaxed, Ordering::Relaxed)
392 .is_ok()
393 {
394 CONTEXT.count.store(crate::rng::u16(), Ordering::Release);
395 }
396
397 &CONTEXT
398 }
399
400 /// A thread-safe, wrapping counter that produces 14-bit numbers.
401 ///
402 /// This type should be used when constructing version 1 and version 6 UUIDs.
403 #[derive(Debug)]
404 #[cfg(any(feature = "v1", feature = "v6"))]
405 pub struct Context {
406 count: Atomic<u16>,
407 }
408
409 #[cfg(any(feature = "v1", feature = "v6"))]
410 impl Context {
411 /// Construct a new context that's initialized with the given value.
412 ///
413 /// The starting value should be a random number, so that UUIDs from
414 /// different systems with the same timestamps are less likely to collide.
415 /// When the `rng` feature is enabled, prefer the [`Context::new_random`] method.
416 pub const fn new(count: u16) -> Self {
417 Self {
418 count: Atomic::<u16>::new(count),
419 }
420 }
421
422 /// Construct a new context that's initialized with a random value.
423 #[cfg(feature = "rng")]
424 pub fn new_random() -> Self {
425 Self {
426 count: Atomic::<u16>::new(crate::rng::u16()),
427 }
428 }
429 }
430
431 #[cfg(any(feature = "v1", feature = "v6"))]
432 impl ClockSequence for Context {
433 type Output = u16;
434
435 fn generate_sequence(&self, _seconds: u64, _nanos: u32) -> Self::Output {
436 // RFC4122 reserves 2 bits of the clock sequence so the actual
437 // maximum value is smaller than `u16::MAX`. Since we unconditionally
438 // increment the clock sequence we want to wrap once it becomes larger
439 // than what we can represent in a "u14". Otherwise there'd be patches
440 // where the clock sequence doesn't change regardless of the timestamp
441 self.count.fetch_add(1, Ordering::AcqRel) % (u16::MAX >> 2)
442 }
443 }
444}
445
446#[cfg(all(test, any(feature = "v1", feature = "v6")))]
447mod tests {
448 use super::*;
449
450 #[cfg(all(
451 target_arch = "wasm32",
452 target_vendor = "unknown",
453 target_os = "unknown"
454 ))]
455 use wasm_bindgen_test::*;
456
457 #[test]
458 #[cfg_attr(
459 all(
460 target_arch = "wasm32",
461 target_vendor = "unknown",
462 target_os = "unknown"
463 ),
464 wasm_bindgen_test
465 )]
466 fn rfc4122_unix_does_not_panic() {
467 // Ensure timestamp conversions never panic
468 Timestamp::unix_to_rfc4122_ticks(u64::MAX, 0);
469 Timestamp::unix_to_rfc4122_ticks(0, u32::MAX);
470 Timestamp::unix_to_rfc4122_ticks(u64::MAX, u32::MAX);
471
472 Timestamp::rfc4122_to_unix(u64::MAX);
473 }
474}
475