euid/
lib.rs

1// MIT License
2//
3// Copyright (c) 2023 Ardika Rommy Sanjaya
4//
5// Permission is hereby granted, free of charge, to any person obtaining a copy
6// of this software and associated documentation files (the "Software"), to deal
7// in the Software without restriction, including without limitation the rights
8// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9// copies of the Software, and to permit persons to whom the Software is
10// furnished to do so, subject to the following conditions:
11//
12// The above copyright notice and this permission notice shall be included in all
13// copies or substantial portions of the Software.
14//
15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
21// SOFTWARE.
22
23//! # EUID
24//! Reference implementation of EUID.
25//!
26
27mod base32;
28mod check;
29mod random;
30mod time;
31
32/// Error enum.
33#[derive(Debug, PartialEq, Eq)]
34pub enum Error {
35    /// EUID must have 27 character in size.
36    InvalidLength(usize, usize),
37    /// EUID use a set of 10 digits and 22 letters, excluding 4 of the 26 letters: I L O U.
38    InvalidCharacter(char),
39    /// Invalid entry (typo).
40    InvalidCheckmod(usize, usize),
41}
42
43/// Extendable Universally Unique Identifier or EUID contains two main components:
44/// header and random number.
45///
46/// Binary layout (Big Endian):
47/// ```text
48///        0               1               2               3
49/// 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
50/// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
51/// |                         Timestamp High                        |
52/// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
53/// |      Timestamp Low      | N Bit Random + Ops Ext Data |Ext Len|
54/// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
55/// |                             Random                            |
56/// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
57/// |                             Random                            |
58/// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
59/// ```
60#[derive(Default, Copy, Clone, Debug)]
61pub struct EUID(u64, u64);
62
63/// A Standard implementation of EUID.
64impl EUID {
65    const TIMESTAMP_BITMASK: u64 = 0x1fffffffffff;
66    const EXT_LEN_BITMASK: u64 = 0xf;
67    const EXT_DATA_BITMASK: u64 = 0x7fff;
68
69    /// Create random EUID.
70    /// None will returns if the EUID is created after Friday, December 12, 3084 12:41:28.831 PM (UTC).
71    ///
72    /// Example:
73    /// ```rust
74    /// use euid::EUID;
75    ///
76    /// let euid: EUID = EUID::create().unwrap_or_default();
77    /// println!("{}", euid); // with check-mod.
78    /// println!("{}", euid.encode(true)); // with check-mod.
79    /// println!("{}", euid.encode(false)); // without check-mod.
80    /// ```
81    pub fn create() -> Option<EUID> {
82        EUID::create_with_timestamp(time::current_timestamp())
83    }
84
85    /// Create random EUID with attachable data (max 15 bit).
86    /// None will returns if the EUID is created after Friday, December 12, 3084 12:41:28.831 PM (UTC)
87    /// or the extenstion (user attached data) is more then 15 bits.
88    ///
89    /// Example:
90    /// ```rust
91    /// use euid::EUID;
92    ///
93    /// let euid: EUID = EUID::create_with_extension(1).unwrap_or_default();
94    /// println!("{}", euid); // with check-mod.
95    /// println!("{}", euid.encode(true)); // with check-mod.
96    /// println!("{}", euid.encode(false)); // without check-mod.
97    ///
98    /// let overflowed_euid: Option<EUID> = EUID::create_with_extension(32768);
99    /// assert_eq!(None, overflowed_euid);
100    /// ```
101    pub fn create_with_extension(extension: u16) -> Option<EUID> {
102        if extension > ((EUID::EXT_DATA_BITMASK) as u16) {
103            None
104        } else {
105            EUID::create_with_timestamp_and_extension(time::current_timestamp(), extension)
106        }
107    }
108
109    /// Returns user attached data (extension), or None if no attached data.
110    pub fn extension(&self) -> Option<u16> {
111        let ext_len: u64 = self.0 & EUID::EXT_LEN_BITMASK;
112        if ext_len == 0 {
113            None
114        } else {
115            let bitmask: u64 = (1 << ext_len) - 1;
116            Some(((self.0 >> 4) & bitmask) as u16)
117        }
118    }
119
120    /// Returns timestamp in milliseconds.
121    pub fn timestamp(&self) -> u64 {
122        (self.0 >> 19) & EUID::TIMESTAMP_BITMASK
123    }
124
125    /// Derive monotonic EUID.
126    ///
127    /// This function generate sortable EUID, None returns if overflow happens when incrementing randomness.
128    pub fn next(&self) -> Option<EUID> {
129        let timestamp: u64 = time::current_timestamp();
130        if timestamp == self.timestamp() {
131            let r_hi = self.1 >> 32;
132            if r_hi == 0xffffffff {
133                None
134            } else {
135                Some(EUID(
136                    self.0,
137                    ((r_hi + 1) << 32) | random::random_u32() as u64,
138                ))
139            }
140        } else {
141            match self.extension() {
142                Some(ext) => EUID::create_with_timestamp_and_extension(timestamp, ext),
143                None => EUID::create_with_timestamp(timestamp),
144            }
145        }
146    }
147
148    /// Encode EUID to string Base-32 string.
149    ///
150    /// Example:
151    /// ```rust
152    /// use euid::EUID;
153    ///
154    /// let euid: EUID = EUID::create().unwrap_or_default();
155    /// println!("{}", euid.encode(true)); // with check-mod.
156    /// println!("{}", euid.encode(false)); // without check-mod.
157    /// ```
158    pub fn encode(&self, checkmod: bool) -> String {
159        base32::encode(self, checkmod)
160    }
161
162    #[inline(always)]
163    fn get_ext_bit_len(ext: u16) -> u64 {
164        let mut x: u16 = ext & 0x7fff;
165        let mut n: u64 = 0;
166        if x <= 0x00ff {
167            n += 8;
168            x <<= 8;
169        }
170        if x <= 0x0fff {
171            n += 4;
172            x <<= 4;
173        }
174        if x <= 0x3fff {
175            n += 2;
176            x <<= 2;
177        }
178        if x <= 0x7fff {
179            n += 1;
180        }
181        16 - n
182    }
183
184    #[inline(always)]
185    fn create_with_timestamp(timestamp: u64) -> Option<EUID> {
186        if timestamp > EUID::TIMESTAMP_BITMASK {
187            None
188        } else {
189            let (r0, r1) = random::random_u128();
190            Some(EUID((timestamp << 19) | ((r0 & 0x7fff) << 4), r1))
191        }
192    }
193
194    #[inline(always)]
195    fn create_with_timestamp_and_extension(timestamp: u64, extension: u16) -> Option<EUID> {
196        if timestamp > EUID::TIMESTAMP_BITMASK {
197            None
198        } else {
199            let ext_data: u64 = extension as u64;
200            if ext_data > EUID::EXT_DATA_BITMASK {
201                None
202            } else {
203                let ext_len: u64 = EUID::get_ext_bit_len(extension);
204                let (r0, r1) = random::random_u128();
205                let remain_rand: u64 = r0 & ((1 << (15 - ext_len)) - 1);
206                let hi: u64 =
207                    (timestamp << 19) | (remain_rand << (4 + ext_len)) | (ext_data << 4) | ext_len;
208                Some(EUID(hi, r1))
209            }
210        }
211    }
212}
213
214impl std::fmt::Display for EUID {
215    /// Encode to lexicographically sortable string.
216    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
217        write!(f, "{}", self.encode(true))
218    }
219}
220
221impl From<EUID> for u128 {
222    fn from(val: EUID) -> Self {
223        ((val.0 as u128) << 64) | (val.1 as u128)
224    }
225}
226
227impl From<u128> for EUID {
228    fn from(value: u128) -> EUID {
229        let hi: u64 = (value >> 64) as u64;
230        let lo: u64 = (value & 0xffffffffffffffff) as u64;
231        EUID(hi, lo)
232    }
233}
234
235impl std::str::FromStr for EUID {
236    type Err = Error;
237
238    /// Parse string representation of EUID.
239    fn from_str(encoded: &str) -> Result<EUID, Self::Err> {
240        match base32::decode(encoded) {
241            Ok(euid) => Ok(euid),
242            Err(e) => Err(e),
243        }
244    }
245}
246
247impl PartialEq for EUID {
248    fn eq(&self, other: &Self) -> bool {
249        self.0 == other.0 && self.1 == other.1
250    }
251}
252
253impl Eq for EUID {}
254
255impl std::hash::Hash for EUID {
256    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
257        self.0.hash(state);
258        self.1.hash(state);
259    }
260}
261
262impl Ord for EUID {
263    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
264        self.partial_cmp(other).unwrap()
265    }
266}
267
268impl From<[u8; 16]> for EUID {
269    fn from(value: [u8; 16]) -> Self {
270        let id: u128 = u128::from_be_bytes(value);
271        EUID((id >> 64) as u64, (id & 0xffffffffffffffff) as u64)
272    }
273}
274
275impl From<EUID> for [u8; 16] {
276    #[cfg(not(feature = "euid_64"))]
277    fn from(value: EUID) -> Self {
278        (((value.0 as u128) << 64) | (value.1 as u128)).to_be_bytes()
279    }
280
281    #[cfg(feature = "euid_64")]
282    fn from(value: EUID) -> Self {
283        let mut v: [u8; 16] = [0u8; 16];
284        v[0] = ((value.0 >> 56) & 0xff) as u8;
285        v[1] = ((value.0 >> 48) & 0xff) as u8;
286        v[2] = ((value.0 >> 40) & 0xff) as u8;
287        v[3] = ((value.0 >> 32) & 0xff) as u8;
288        v[4] = ((value.0 >> 24) & 0xff) as u8;
289        v[5] = ((value.0 >> 16) & 0xff) as u8;
290        v[6] = ((value.0 >> 8) & 0xff) as u8;
291        v[7] = (value.0 & 0xff) as u8;
292        v[8] = ((value.0 >> 56) & 0xff) as u8;
293        v[9] = ((value.0 >> 48) & 0xff) as u8;
294        v[10] = ((value.0 >> 40) & 0xff) as u8;
295        v[11] = ((value.0 >> 32) & 0xff) as u8;
296        v[12] = ((value.0 >> 24) & 0xff) as u8;
297        v[13] = ((value.0 >> 16) & 0xff) as u8;
298        v[14] = ((value.0 >> 8) & 0xff) as u8;
299        v[15] = (value.0 & 0xff) as u8;
300        v
301    }
302}
303
304impl PartialOrd for EUID {
305    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
306        if self.0 != other.0 {
307            return Some(if self.0 > other.0 {
308                std::cmp::Ordering::Greater
309            } else {
310                std::cmp::Ordering::Less
311            });
312        }
313        if self.1 != other.1 {
314            return Some(if self.1 > other.1 {
315                std::cmp::Ordering::Greater
316            } else {
317                std::cmp::Ordering::Less
318            });
319        }
320        Some(std::cmp::Ordering::Equal)
321    }
322}
323
324#[cfg(test)]
325mod tests {
326
327    use std::hash::Hasher;
328    use std::str::FromStr;
329
330    use rand::{seq::SliceRandom, thread_rng};
331
332    fn get_timestamp_diff(start: u64, timestamp: u64) -> u64 {
333        if start < timestamp {
334            timestamp - start
335        } else {
336            start - timestamp
337        }
338    }
339
340    fn get_ext_bit_len0(v: u16) -> u64 {
341        let mut i: i32 = 14;
342        while i > 0 {
343            if (v >> i) != 0 {
344                return (i as u64) + 1;
345            }
346            i -= 1;
347        }
348        1
349    }
350
351    #[test]
352    fn get_timestamp_diff_test() {
353        assert_eq!(1, get_timestamp_diff(1, 2));
354        assert_eq!(1, get_timestamp_diff(2, 1));
355    }
356
357    fn normalize_timestamp(now: u64, epoch: u64) -> u64 {
358        if epoch < now {
359            now - epoch
360        } else {
361            now
362        }
363    }
364
365    fn get_timestamp_from_epoch(epoch: u64) -> u64 {
366        let duration: Result<std::time::Duration, std::time::SystemTimeError> =
367            std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH);
368        match duration {
369            Ok(now) => {
370                let millis: u64 = now.as_millis() as u64;
371                let final_epoch: u64 = epoch & 0x3ffffffffff;
372                normalize_timestamp(millis, final_epoch)
373            }
374            Err(_) => 0,
375        }
376    }
377
378    #[test]
379    fn create_with_timestamp_and_extension_test() {
380        assert_eq!(
381            None,
382            crate::EUID::create_with_timestamp_and_extension(u64::MAX, 0)
383        );
384        assert_eq!(
385            None,
386            crate::EUID::create_with_timestamp_and_extension(
387                crate::time::current_timestamp(),
388                (crate::EUID::EXT_DATA_BITMASK + 1) as u16
389            )
390        );
391        for i in 0u32..65535 {
392            let epoch: u64 = crate::random::random_u32() as u64;
393            let ts: u64 = get_timestamp_from_epoch(epoch);
394            let now: u64 = std::time::SystemTime::now()
395                .duration_since(std::time::UNIX_EPOCH)
396                .unwrap()
397                .as_millis() as u64;
398            let euid = crate::EUID::create_with_timestamp_and_extension(
399                ts,
400                ((i as u64) & crate::EUID::EXT_DATA_BITMASK) as u16,
401            )
402            .unwrap();
403            let timestamp: u64 = euid.timestamp();
404            assert!(timestamp <= crate::EUID::TIMESTAMP_BITMASK);
405            let t: u64 = now - epoch;
406            let diff: u64 = get_timestamp_diff(t, timestamp);
407            assert!(diff < 50);
408            assert_eq!(
409                (i as u64 & crate::EUID::EXT_DATA_BITMASK) as u16,
410                euid.extension().unwrap()
411            );
412            assert!(euid.extension().unwrap() as u64 <= crate::EUID::EXT_DATA_BITMASK);
413            assert!(
414                crate::EUID::get_ext_bit_len(euid.extension().unwrap())
415                    <= crate::EUID::EXT_LEN_BITMASK
416            );
417        }
418    }
419
420    #[test]
421    fn get_ext_bit_len_test() {
422        let max: u16 = 1 << 15;
423        for i in 0..max {
424            assert_eq!(crate::EUID::get_ext_bit_len(i), get_ext_bit_len0(i));
425        }
426    }
427
428    #[test]
429    fn create_test() {
430        let now: u64 = std::time::SystemTime::now()
431            .duration_since(std::time::UNIX_EPOCH)
432            .unwrap()
433            .as_millis() as u64;
434        let euid: crate::EUID = crate::EUID::create().unwrap_or_default();
435        let timestamp: u64 = euid.timestamp();
436        let diff: u64 = get_timestamp_diff(now, timestamp);
437        assert!(diff < 50);
438        assert_eq!(None, euid.extension());
439    }
440
441    #[test]
442    fn create_with_extension_test() {
443        for i in 0u64..crate::EUID::EXT_DATA_BITMASK {
444            let now: u64 = std::time::SystemTime::now()
445                .duration_since(std::time::UNIX_EPOCH)
446                .unwrap()
447                .as_millis() as u64;
448            let euid: crate::EUID = crate::EUID::create_with_extension(i as u16).unwrap();
449            let timestamp: u64 = euid.timestamp();
450            let diff: u64 = get_timestamp_diff(now, timestamp);
451            assert!(diff < 50);
452            assert_eq!(i, euid.extension().unwrap() as u64);
453        }
454        assert_eq!(
455            None,
456            crate::EUID::create_with_extension(crate::EUID::EXT_DATA_BITMASK as u16 + 1)
457        );
458    }
459
460    #[test]
461    fn conversion_test() {
462        for i in 0..crate::EUID::EXT_DATA_BITMASK {
463            let euid: crate::EUID = crate::EUID::create_with_extension(i as u16).unwrap();
464            let encoded: String = euid.to_string();
465            assert_eq!(27, encoded.len());
466            let decoded: crate::EUID = crate::EUID::from_str(&encoded).unwrap();
467            assert_eq!(euid, decoded);
468            let e128: u128 = euid.into();
469            assert_eq!(crate::EUID::from(e128), euid);
470            assert_eq!(
471                std::cmp::Ordering::Equal,
472                crate::EUID::from(e128).cmp(&euid)
473            );
474            assert_eq!(euid, euid.clone());
475            let euid_copy: crate::EUID = euid;
476            assert_eq!(euid, euid_copy);
477            let euidx: crate::EUID = e128.into();
478            assert_eq!(euid, euidx);
479            let x: u128 = u128::from(euid);
480            assert_eq!(x, e128);
481        }
482        assert_eq!(None, crate::EUID::create_with_extension(0x7fff + 1));
483        assert_eq!(
484            Err(crate::Error::InvalidLength(25, 27)),
485            crate::EUID::from_str("C8754X9NN8H80X298KRKERG8K")
486        );
487        assert_eq!(
488            Err(crate::Error::InvalidLength(28, 27)),
489            crate::EUID::from_str("C8754X9NN8H80X298KRKERG8K888")
490        );
491        assert_eq!(
492            Err(crate::Error::InvalidCharacter('U')),
493            crate::EUID::from_str("C8754X9NN8H80X298KRKERG8KU8")
494        );
495    }
496
497    #[test]
498    fn monotonic_test() {
499        let hi: u64 = crate::EUID::create().unwrap().0;
500        let euid: crate::EUID = crate::EUID(hi, u64::MAX);
501        assert_eq!(None, euid.next());
502
503        let mut euids: Vec<crate::EUID> = Vec::<crate::EUID>::new();
504        for i in 0usize..0x7fff {
505            if i == 0 {
506                euids.push(crate::EUID::create_with_extension(i as u16).unwrap());
507            } else {
508                euids.push(euids[i - 1].next().unwrap())
509            }
510        }
511        assert_eq!(None, crate::EUID::create_with_extension(0x7fff + 1));
512        let mut unordered: Vec<crate::EUID> = euids.clone();
513        unordered.shuffle(&mut thread_rng());
514        let mut ordered: Vec<crate::EUID> = unordered.clone();
515        ordered.sort();
516        for i in 0..euids.len() {
517            assert_eq!(euids[i], ordered[i]);
518            assert_eq!(euids[i].to_string(), ordered[i].to_string());
519        }
520    }
521
522    #[test]
523    fn bytes_test() {
524        let euid: crate::EUID = crate::EUID::create().unwrap_or_default();
525        let bytes: [u8; 16] = From::from(euid);
526        let from_bytes: crate::EUID = From::from(bytes);
527        assert_eq!(16, bytes.len());
528        assert_eq!(euid, from_bytes);
529    }
530
531    #[test]
532    fn hash_test() {
533        let euid: crate::EUID = crate::EUID::create().unwrap_or_default();
534        let mut default_hasher0 = std::collections::hash_map::DefaultHasher::new();
535        let mut default_hasher1 = std::collections::hash_map::DefaultHasher::new();
536        std::hash::Hash::hash(&euid, &mut default_hasher0);
537        std::hash::Hash::hash_slice(&[euid], &mut default_hasher1);
538        assert_eq!(default_hasher0.finish(), default_hasher1.finish());
539    }
540
541    #[test]
542    fn print_test() {
543        let euid: crate::EUID = crate::EUID::create().unwrap_or_default();
544        println!("{:?}\n{}", euid, euid);
545    }
546}
euid/lib.rs

euid/
lib.rs
