ratsio/
nuid.rs

1// Copyright 2018 Ivan Porto Carrero
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14//
15// Copied here due to lazy_static version collision.
16extern crate rand;
17
18use rand::thread_rng;
19use rand::rngs::{OsRng};
20use rand::distributions::Alphanumeric;
21use rand::Rng;
22use std::sync::Mutex;
23
24const BASE: usize = 62;
25const ALPHABET: [u8; BASE as usize] = [b'0', b'1', b'2', b'3', b'4', b'5', b'6', b'7', b'8', b'9',
26                                       b'A', b'B', b'C', b'D', b'E', b'F', b'G', b'H', b'I', b'J',
27                                       b'K', b'L', b'M', b'N', b'O', b'P', b'Q', b'R', b'S', b'T',
28                                       b'U', b'V', b'W', b'X', b'Y', b'Z', b'a', b'b', b'c', b'd',
29                                       b'e', b'f', b'g', b'h', b'i', b'j', b'k', b'l', b'm', b'n',
30                                       b'o', b'p', b'q', b'r', b's', b't', b'u', b'v', b'w', b'x',
31                                       b'y', b'z'];
32
33const PRE_LEN: usize = 12;
34const MAX_SEQ: u64 = 839_299_365_868_340_224; // (BASE ^ remaining bytes 22 - 12) == 62^10
35const MIN_INC: u64 = 33;
36const MAX_INC: u64 = 333;
37const TOTAL_LEN: usize = 22;
38
39lazy_static! {
40    static ref GLOBAL_NUID: Mutex<NUID> = Mutex::new(NUID::new());
41}
42
43/// Generate the next `NUID` string from the global locked `NUID` instance.
44pub fn next() -> String {
45    GLOBAL_NUID.lock().unwrap().next()
46}
47
48/// NUID needs to be very fast to generate and truly unique, all while being entropy pool friendly.
49/// We will use 12 bytes of crypto generated data (entropy draining), and 10 bytes of sequential data
50/// that is started at a pseudo random number and increments with a pseudo-random increment.
51/// Total is 22 bytes of base 62 ascii text :)
52pub struct NUID {
53    pre: [u8; PRE_LEN],
54    seq: u64,
55    inc: u64,
56}
57
58impl Default for NUID {
59
60   fn default() -> Self {
61        let mut rng = thread_rng();
62        let seq = Rng::gen_range::<u64, u64, _>(&mut rng, 0, MAX_SEQ);
63        let inc = MIN_INC + Rng::gen_range::<u64, u64, _>(&mut rng, 0, MAX_INC+MIN_INC);
64        let mut n = NUID {
65            pre: [0; PRE_LEN], seq, inc,
66        };
67        n.randomize_prefix();
68        n
69    }
70}
71
72
73impl NUID {
74    /// generate a new `NUID` and properly initialize the prefix, sequential start, and sequential increment.
75    pub fn new() -> Self {
76        Self::default()
77    }
78
79    pub fn randomize_prefix(&mut self) {
80        let mut rng = OsRng::new().expect("failed to get crypto random number generator");
81        for (i, n) in rng.sample_iter(&Alphanumeric).take(PRE_LEN).enumerate() {
82            self.pre[i] = ALPHABET[n as usize % BASE];
83        }
84    }
85
86    /// Generate the next `NUID` string.
87    #[allow(clippy::should_implement_trait)]
88    pub fn next(&mut self) -> String {
89        self.seq += self.inc;
90        if self.seq >= MAX_SEQ {
91            self.randomize_prefix();
92            self.reset_sequential();
93        }
94        let seq: usize = self.seq as usize;
95
96        let mut b: [u8; TOTAL_LEN] = [0; TOTAL_LEN];
97        for (i, n) in self.pre.iter().enumerate() {
98            b[i] = *n;
99        }
100
101        let mut l = seq;
102        for i in (PRE_LEN..TOTAL_LEN).rev() {
103            b[i] = ALPHABET[l%BASE];
104            l /= BASE;
105        }
106
107        // data is base62 encoded so this can't fail
108        String::from_utf8(b.to_vec()).unwrap()
109    }
110
111    fn reset_sequential(&mut self) {
112        let mut rng = thread_rng();
113        self.seq = Rng::gen_range::<u64, _, _>(&mut rng, 0, MAX_SEQ);
114        self.inc = MIN_INC + Rng::gen_range::<u64, _, _>(&mut rng, 0, MIN_INC+MAX_INC);
115    }
116}
117
118#[cfg(test)]
119mod tests {
120    use super::*;
121    use std::collections::HashSet;
122
123    #[test]
124    fn alphabet_size() {
125        assert_eq!(ALPHABET.len(), BASE);
126    }
127
128    #[test]
129    fn global_nuid_init() {
130        assert_eq!(GLOBAL_NUID.lock().unwrap().pre.len(), PRE_LEN);
131        assert_ne!(GLOBAL_NUID.lock().unwrap().seq, 0);
132    }
133
134    #[test]
135    fn nuid_rollover() {
136        let mut n = NUID::new();
137        n.seq = MAX_SEQ;
138        let old = n.pre.to_vec().clone();
139        n.next();
140        assert_ne!(n.pre.to_vec(), old);
141
142        let mut n = NUID::new();
143        n.seq = 1;
144        let old = n.pre.to_vec().clone();
145        n.next();
146        assert_eq!(n.pre.to_vec(), old);
147    }
148
149    #[test]
150    fn nuid_len() {
151        let id = next();
152        assert_eq!(id.len(), TOTAL_LEN);
153    }
154
155    #[test]
156    fn proper_prefix() {
157        let mut min: u8 = 255;
158        let mut max: u8 = 0;
159
160        for nn in ALPHABET.iter() {
161            let n = *nn;
162            if n < min {
163                min = n;
164            }
165            if n > max {
166                max = n;
167            }
168        }
169
170        for _ in 0..100_000 {
171            let nuid = NUID::new();
172            for j in 0..PRE_LEN {
173                assert!(nuid.pre[j] >= min || nuid.pre[j] <= max);
174            }
175        }
176    }
177
178    #[test]
179    fn unique() {
180        let mut set = HashSet::new();
181        for _ in 0..100_000 {
182            assert_eq!(set.insert(next()), true);
183        }
184
185    }
186}
ratsio/nuid.rs

ratsio/
nuid.rs
