1 //! A simple and fast random number generator.
2 //!
3 //! The implementation uses [Wyrand](https://github.com/wangyi-fudan/wyhash), a simple and fast
4 //! generator but **not** cryptographically secure.
5 //!
6 //! # Examples
7 //!
8 //! Flip a coin:
9 //!
10 //! ```
11 //! if fastrand::bool() {
12 //!     println!("heads");
13 //! } else {
14 //!     println!("tails");
15 //! }
16 //! ```
17 //!
18 //! Generate a random `i32`:
19 //!
20 //! ```
21 //! let num = fastrand::i32(..);
22 //! ```
23 //!
24 //! Choose a random element in an array:
25 //!
26 //! ```
27 //! let v = vec![1, 2, 3, 4, 5];
28 //! let i = fastrand::usize(..v.len());
29 //! let elem = v[i];
30 //! ```
31 //!
32 //! Shuffle an array:
33 //!
34 //! ```
35 //! let mut v = vec![1, 2, 3, 4, 5];
36 //! fastrand::shuffle(&mut v);
37 //! ```
38 //!
39 //! Generate a random [`Vec`] or [`String`]:
40 //!
41 //! ```
42 //! use std::iter::repeat_with;
43 //!
44 //! let v: Vec<i32> = repeat_with(|| fastrand::i32(..)).take(10).collect();
45 //! let s: String = repeat_with(fastrand::alphanumeric).take(10).collect();
46 //! ```
47 //!
48 //! To get reproducible results on every run, initialize the generator with a seed:
49 //!
50 //! ```
51 //! // Pick an arbitrary number as seed.
52 //! fastrand::seed(7);
53 //!
54 //! // Now this prints the same number on every run:
55 //! println!("{}", fastrand::u32(..));
56 //! ```
57 //!
58 //! To be more efficient, create a new [`Rng`] instance instead of using the thread-local
59 //! generator:
60 //!
61 //! ```
62 //! use std::iter::repeat_with;
63 //!
64 //! let rng = fastrand::Rng::new();
65 //! let mut bytes: Vec<u8> = repeat_with(|| rng.u8(..)).take(10_000).collect();
66 //! ```
67 
68 #![forbid(unsafe_code)]
69 #![warn(missing_docs, missing_debug_implementations, rust_2018_idioms)]
70 
71 use std::cell::Cell;
72 use std::collections::hash_map::DefaultHasher;
73 use std::hash::{Hash, Hasher};
74 use std::ops::{Bound, RangeBounds};
75 use std::thread;
76 
77 #[cfg(target_arch = "wasm32")]
78 use instant::Instant;
79 #[cfg(not(target_arch = "wasm32"))]
80 use std::time::Instant;
81 
82 /// A random number generator.
83 #[derive(Debug, PartialEq, Eq)]
84 pub struct Rng(Cell<u64>);
85 
86 impl Default for Rng {
87     #[inline]
default() -> Rng88     fn default() -> Rng {
89         Rng::new()
90     }
91 }
92 
93 impl Clone for Rng {
94     /// Clones the generator by deterministically deriving a new generator based on the initial
95     /// seed.
96     ///
97     /// # Example
98     ///
99     /// ```
100     /// // Seed two generators equally, and clone both of them.
101     /// let base1 = fastrand::Rng::new();
102     /// base1.seed(0x4d595df4d0f33173);
103     /// base1.bool(); // Use the generator once.
104     ///
105     /// let base2 = fastrand::Rng::new();
106     /// base2.seed(0x4d595df4d0f33173);
107     /// base2.bool(); // Use the generator once.
108     ///
109     /// let rng1 = base1.clone();
110     /// let rng2 = base2.clone();
111     ///
112     /// assert_eq!(rng1.u64(..), rng2.u64(..), "the cloned generators are identical");
113     /// ```
clone(&self) -> Rng114     fn clone(&self) -> Rng {
115         Rng::with_seed(self.gen_u64())
116     }
117 }
118 
119 impl Rng {
120     /// Generates a random `u32`.
121     #[inline]
gen_u32(&self) -> u32122     fn gen_u32(&self) -> u32 {
123         self.gen_u64() as u32
124     }
125 
126     /// Generates a random `u64`.
127     #[inline]
gen_u64(&self) -> u64128     fn gen_u64(&self) -> u64 {
129         let s = self.0.get().wrapping_add(0xA0761D6478BD642F);
130         self.0.set(s);
131         let t = u128::from(s) * u128::from(s ^ 0xE7037ED1A0B428DB);
132         (t as u64) ^ (t >> 64) as u64
133     }
134 
135     /// Generates a random `u128`.
136     #[inline]
gen_u128(&self) -> u128137     fn gen_u128(&self) -> u128 {
138         (u128::from(self.gen_u64()) << 64) | u128::from(self.gen_u64())
139     }
140 
141     /// Generates a random `u32` in `0..n`.
142     #[inline]
gen_mod_u32(&self, n: u32) -> u32143     fn gen_mod_u32(&self, n: u32) -> u32 {
144         // Adapted from: https://lemire.me/blog/2016/06/30/fast-random-shuffling/
145         let mut r = self.gen_u32();
146         let mut hi = mul_high_u32(r, n);
147         let mut lo = r.wrapping_mul(n);
148         if lo < n {
149             let t = n.wrapping_neg() % n;
150             while lo < t {
151                 r = self.gen_u32();
152                 hi = mul_high_u32(r, n);
153                 lo = r.wrapping_mul(n);
154             }
155         }
156         hi
157     }
158 
159     /// Generates a random `u64` in `0..n`.
160     #[inline]
gen_mod_u64(&self, n: u64) -> u64161     fn gen_mod_u64(&self, n: u64) -> u64 {
162         // Adapted from: https://lemire.me/blog/2016/06/30/fast-random-shuffling/
163         let mut r = self.gen_u64();
164         let mut hi = mul_high_u64(r, n);
165         let mut lo = r.wrapping_mul(n);
166         if lo < n {
167             let t = n.wrapping_neg() % n;
168             while lo < t {
169                 r = self.gen_u64();
170                 hi = mul_high_u64(r, n);
171                 lo = r.wrapping_mul(n);
172             }
173         }
174         hi
175     }
176 
177     /// Generates a random `u128` in `0..n`.
178     #[inline]
gen_mod_u128(&self, n: u128) -> u128179     fn gen_mod_u128(&self, n: u128) -> u128 {
180         // Adapted from: https://lemire.me/blog/2016/06/30/fast-random-shuffling/
181         let mut r = self.gen_u128();
182         let mut hi = mul_high_u128(r, n);
183         let mut lo = r.wrapping_mul(n);
184         if lo < n {
185             let t = n.wrapping_neg() % n;
186             while lo < t {
187                 r = self.gen_u128();
188                 hi = mul_high_u128(r, n);
189                 lo = r.wrapping_mul(n);
190             }
191         }
192         hi
193     }
194 }
195 
196 thread_local! {
197     static RNG: Rng = Rng(Cell::new({
198         let mut hasher = DefaultHasher::new();
199         Instant::now().hash(&mut hasher);
200         thread::current().id().hash(&mut hasher);
201         let hash = hasher.finish();
202         (hash << 1) | 1
203     }));
204 }
205 
206 /// Computes `(a * b) >> 32`.
207 #[inline]
mul_high_u32(a: u32, b: u32) -> u32208 fn mul_high_u32(a: u32, b: u32) -> u32 {
209     (((a as u64) * (b as u64)) >> 32) as u32
210 }
211 
212 /// Computes `(a * b) >> 64`.
213 #[inline]
mul_high_u64(a: u64, b: u64) -> u64214 fn mul_high_u64(a: u64, b: u64) -> u64 {
215     (((a as u128) * (b as u128)) >> 64) as u64
216 }
217 
218 /// Computes `(a * b) >> 128`.
219 #[inline]
mul_high_u128(a: u128, b: u128) -> u128220 fn mul_high_u128(a: u128, b: u128) -> u128 {
221     // Adapted from: https://stackoverflow.com/a/28904636
222     let a_lo = a as u64 as u128;
223     let a_hi = (a >> 64) as u64 as u128;
224     let b_lo = b as u64 as u128;
225     let b_hi = (b >> 64) as u64 as u128;
226     let carry = (a_lo * b_lo) >> 64;
227     let carry = ((a_hi * b_lo) as u64 as u128 + (a_lo * b_hi) as u64 as u128 + carry) >> 64;
228     a_hi * b_hi + ((a_hi * b_lo) >> 64) + ((a_lo * b_hi) >> 64) + carry
229 }
230 
231 macro_rules! rng_integer {
232     ($t:tt, $unsigned_t:tt, $gen:tt, $mod:tt, $doc:tt) => {
233         #[doc = $doc]
234         ///
235         /// Panics if the range is empty.
236         #[inline]
237         pub fn $t(&self, range: impl RangeBounds<$t>) -> $t {
238             let panic_empty_range = || {
239                 panic!(
240                     "empty range: {:?}..{:?}",
241                     range.start_bound(),
242                     range.end_bound()
243                 )
244             };
245 
246             let low = match range.start_bound() {
247                 Bound::Unbounded => std::$t::MIN,
248                 Bound::Included(&x) => x,
249                 Bound::Excluded(&x) => x.checked_add(1).unwrap_or_else(panic_empty_range),
250             };
251 
252             let high = match range.end_bound() {
253                 Bound::Unbounded => std::$t::MAX,
254                 Bound::Included(&x) => x,
255                 Bound::Excluded(&x) => x.checked_sub(1).unwrap_or_else(panic_empty_range),
256             };
257 
258             if low > high {
259                 panic_empty_range();
260             }
261 
262             if low == std::$t::MIN && high == std::$t::MAX {
263                 self.$gen() as $t
264             } else {
265                 let len = high.wrapping_sub(low).wrapping_add(1);
266                 low.wrapping_add(self.$mod(len as $unsigned_t as _) as $t)
267             }
268         }
269     };
270 }
271 
272 impl Rng {
273     /// Creates a new random number generator.
274     #[inline]
new() -> Rng275     pub fn new() -> Rng {
276         Rng::with_seed(
277             RNG.try_with(|rng| rng.u64(..))
278                 .unwrap_or(0x4d595df4d0f33173),
279         )
280     }
281 
282     /// Creates a new random number generator with the initial seed.
283     #[inline]
with_seed(seed: u64) -> Self284     pub fn with_seed(seed: u64) -> Self {
285         let rng = Rng(Cell::new(0));
286 
287         rng.seed(seed);
288         rng
289     }
290 
291     /// Generates a random `char` in ranges a-z and A-Z.
292     #[inline]
alphabetic(&self) -> char293     pub fn alphabetic(&self) -> char {
294         const CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
295         let len = CHARS.len() as u8;
296         let i = self.u8(..len);
297         CHARS[i as usize] as char
298     }
299 
300     /// Generates a random `char` in ranges a-z, A-Z and 0-9.
301     #[inline]
alphanumeric(&self) -> char302     pub fn alphanumeric(&self) -> char {
303         const CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
304         let len = CHARS.len() as u8;
305         let i = self.u8(..len);
306         CHARS[i as usize] as char
307     }
308 
309     /// Generates a random `bool`.
310     #[inline]
bool(&self) -> bool311     pub fn bool(&self) -> bool {
312         self.u8(..) % 2 == 0
313     }
314 
315     /// Generates a random digit in the given `base`.
316     ///
317     /// Digits are represented by `char`s in ranges 0-9 and a-z.
318     ///
319     /// Panics if the base is zero or greater than 36.
320     #[inline]
digit(&self, base: u32) -> char321     pub fn digit(&self, base: u32) -> char {
322         if base == 0 {
323             panic!("base cannot be zero");
324         }
325         if base > 36 {
326             panic!("base cannot be larger than 36");
327         }
328         let num = self.u8(..base as u8);
329         if num < 10 {
330             (b'0' + num) as char
331         } else {
332             (b'a' + num - 10) as char
333         }
334     }
335 
336     /// Generates a random `f32` in range `0..1`.
f32(&self) -> f32337     pub fn f32(&self) -> f32 {
338         let b = 32;
339         let f = std::f32::MANTISSA_DIGITS - 1;
340         f32::from_bits((1 << (b - 2)) - (1 << f) + (self.u32(..) >> (b - f))) - 1.0
341     }
342 
343     /// Generates a random `f64` in range `0..1`.
f64(&self) -> f64344     pub fn f64(&self) -> f64 {
345         let b = 64;
346         let f = std::f64::MANTISSA_DIGITS - 1;
347         f64::from_bits((1 << (b - 2)) - (1 << f) + (self.u64(..) >> (b - f))) - 1.0
348     }
349 
350     rng_integer!(
351         i8,
352         u8,
353         gen_u32,
354         gen_mod_u32,
355         "Generates a random `i8` in the given range."
356     );
357 
358     rng_integer!(
359         i16,
360         u16,
361         gen_u32,
362         gen_mod_u32,
363         "Generates a random `i16` in the given range."
364     );
365 
366     rng_integer!(
367         i32,
368         u32,
369         gen_u32,
370         gen_mod_u32,
371         "Generates a random `i32` in the given range."
372     );
373 
374     rng_integer!(
375         i64,
376         u64,
377         gen_u64,
378         gen_mod_u64,
379         "Generates a random `i64` in the given range."
380     );
381 
382     rng_integer!(
383         i128,
384         u128,
385         gen_u128,
386         gen_mod_u128,
387         "Generates a random `i128` in the given range."
388     );
389 
390     #[cfg(target_pointer_width = "16")]
391     rng_integer!(
392         isize,
393         usize,
394         gen_u32,
395         gen_mod_u32,
396         "Generates a random `isize` in the given range."
397     );
398     #[cfg(target_pointer_width = "32")]
399     rng_integer!(
400         isize,
401         usize,
402         gen_u32,
403         gen_mod_u32,
404         "Generates a random `isize` in the given range."
405     );
406     #[cfg(target_pointer_width = "64")]
407     rng_integer!(
408         isize,
409         usize,
410         gen_u64,
411         gen_mod_u64,
412         "Generates a random `isize` in the given range."
413     );
414 
415     /// Generates a random `char` in range a-z.
416     #[inline]
lowercase(&self) -> char417     pub fn lowercase(&self) -> char {
418         const CHARS: &[u8] = b"abcdefghijklmnopqrstuvwxyz";
419         let len = CHARS.len() as u8;
420         let i = self.u8(..len);
421         CHARS[i as usize] as char
422     }
423 
424     /// Initializes this generator with the given seed.
425     #[inline]
seed(&self, seed: u64)426     pub fn seed(&self, seed: u64) {
427         self.0.set(seed);
428     }
429 
430     /// Shuffles a slice randomly.
431     #[inline]
shuffle<T>(&self, slice: &mut [T])432     pub fn shuffle<T>(&self, slice: &mut [T]) {
433         for i in 1..slice.len() {
434             slice.swap(i, self.usize(..=i));
435         }
436     }
437 
438     rng_integer!(
439         u8,
440         u8,
441         gen_u32,
442         gen_mod_u32,
443         "Generates a random `u8` in the given range."
444     );
445 
446     rng_integer!(
447         u16,
448         u16,
449         gen_u32,
450         gen_mod_u32,
451         "Generates a random `u16` in the given range."
452     );
453 
454     rng_integer!(
455         u32,
456         u32,
457         gen_u32,
458         gen_mod_u32,
459         "Generates a random `u32` in the given range."
460     );
461 
462     rng_integer!(
463         u64,
464         u64,
465         gen_u64,
466         gen_mod_u64,
467         "Generates a random `u64` in the given range."
468     );
469 
470     rng_integer!(
471         u128,
472         u128,
473         gen_u128,
474         gen_mod_u128,
475         "Generates a random `u128` in the given range."
476     );
477 
478     #[cfg(target_pointer_width = "16")]
479     rng_integer!(
480         usize,
481         usize,
482         gen_u32,
483         gen_mod_u32,
484         "Generates a random `usize` in the given range."
485     );
486     #[cfg(target_pointer_width = "32")]
487     rng_integer!(
488         usize,
489         usize,
490         gen_u32,
491         gen_mod_u32,
492         "Generates a random `usize` in the given range."
493     );
494     #[cfg(target_pointer_width = "64")]
495     rng_integer!(
496         usize,
497         usize,
498         gen_u64,
499         gen_mod_u64,
500         "Generates a random `usize` in the given range."
501     );
502     #[cfg(target_pointer_width = "128")]
503     rng_integer!(
504         usize,
505         usize,
506         gen_u128,
507         gen_mod_u128,
508         "Generates a random `usize` in the given range."
509     );
510 
511     /// Generates a random `char` in range A-Z.
512     #[inline]
uppercase(&self) -> char513     pub fn uppercase(&self) -> char {
514         const CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZ";
515         let len = CHARS.len() as u8;
516         let i = self.u8(..len);
517         CHARS[i as usize] as char
518     }
519 
520     /// Generates a random `char` in the given range.
521     ///
522     /// Panics if the range is empty.
523     #[inline]
char(&self, range: impl RangeBounds<char>) -> char524     pub fn char(&self, range: impl RangeBounds<char>) -> char {
525         use std::convert::{TryFrom, TryInto};
526 
527         let panic_empty_range = || {
528             panic!(
529                 "empty range: {:?}..{:?}",
530                 range.start_bound(),
531                 range.end_bound()
532             )
533         };
534 
535         let surrogate_start = 0xd800u32;
536         let surrogate_len = 0x800u32;
537 
538         let low = match range.start_bound() {
539             Bound::Unbounded => 0u8 as char,
540             Bound::Included(&x) => x,
541             Bound::Excluded(&x) => {
542                 let scalar = if x as u32 == surrogate_start - 1 {
543                     surrogate_start + surrogate_len
544                 } else {
545                     x as u32 + 1
546                 };
547                 char::try_from(scalar).unwrap_or_else(|_| panic_empty_range())
548             }
549         };
550 
551         let high = match range.end_bound() {
552             Bound::Unbounded => std::char::MAX,
553             Bound::Included(&x) => x,
554             Bound::Excluded(&x) => {
555                 let scalar = if x as u32 == surrogate_start + surrogate_len {
556                     surrogate_start - 1
557                 } else {
558                     (x as u32).wrapping_sub(1)
559                 };
560                 char::try_from(scalar).unwrap_or_else(|_| panic_empty_range())
561             }
562         };
563 
564         if low > high {
565             panic_empty_range();
566         }
567 
568         let gap = if (low as u32) < surrogate_start && (high as u32) >= surrogate_start {
569             surrogate_len
570         } else {
571             0
572         };
573         let range = high as u32 - low as u32 - gap;
574         let mut val = self.u32(0..=range) + low as u32;
575         if val >= surrogate_start {
576             val += gap;
577         }
578         val.try_into().unwrap()
579     }
580 }
581 
582 /// Initializes the thread-local generator with the given seed.
583 #[inline]
seed(seed: u64)584 pub fn seed(seed: u64) {
585     RNG.with(|rng| rng.seed(seed))
586 }
587 
588 /// Generates a random `bool`.
589 #[inline]
bool() -> bool590 pub fn bool() -> bool {
591     RNG.with(|rng| rng.bool())
592 }
593 
594 /// Generates a random `char` in ranges a-z and A-Z.
595 #[inline]
alphabetic() -> char596 pub fn alphabetic() -> char {
597     RNG.with(|rng| rng.alphabetic())
598 }
599 
600 /// Generates a random `char` in ranges a-z, A-Z and 0-9.
601 #[inline]
alphanumeric() -> char602 pub fn alphanumeric() -> char {
603     RNG.with(|rng| rng.alphanumeric())
604 }
605 
606 /// Generates a random `char` in range a-z.
607 #[inline]
lowercase() -> char608 pub fn lowercase() -> char {
609     RNG.with(|rng| rng.lowercase())
610 }
611 
612 /// Generates a random `char` in range A-Z.
613 #[inline]
uppercase() -> char614 pub fn uppercase() -> char {
615     RNG.with(|rng| rng.uppercase())
616 }
617 
618 /// Generates a random digit in the given `base`.
619 ///
620 /// Digits are represented by `char`s in ranges 0-9 and a-z.
621 ///
622 /// Panics if the base is zero or greater than 36.
623 #[inline]
digit(base: u32) -> char624 pub fn digit(base: u32) -> char {
625     RNG.with(|rng| rng.digit(base))
626 }
627 
628 /// Shuffles a slice randomly.
629 #[inline]
shuffle<T>(slice: &mut [T])630 pub fn shuffle<T>(slice: &mut [T]) {
631     RNG.with(|rng| rng.shuffle(slice))
632 }
633 
634 macro_rules! integer {
635     ($t:tt, $doc:tt) => {
636         #[doc = $doc]
637         ///
638         /// Panics if the range is empty.
639         #[inline]
640         pub fn $t(range: impl RangeBounds<$t>) -> $t {
641             RNG.with(|rng| rng.$t(range))
642         }
643     };
644 }
645 
646 integer!(u8, "Generates a random `u8` in the given range.");
647 integer!(i8, "Generates a random `i8` in the given range.");
648 integer!(u16, "Generates a random `u16` in the given range.");
649 integer!(i16, "Generates a random `i16` in the given range.");
650 integer!(u32, "Generates a random `u32` in the given range.");
651 integer!(i32, "Generates a random `i32` in the given range.");
652 integer!(u64, "Generates a random `u64` in the given range.");
653 integer!(i64, "Generates a random `i64` in the given range.");
654 integer!(u128, "Generates a random `u128` in the given range.");
655 integer!(i128, "Generates a random `i128` in the given range.");
656 integer!(usize, "Generates a random `usize` in the given range.");
657 integer!(isize, "Generates a random `isize` in the given range.");
658 integer!(char, "Generates a random `char` in the given range.");
659 
660 /// Generates a random `f32` in range `0..1`.
f32() -> f32661 pub fn f32() -> f32 {
662     RNG.with(|rng| rng.f32())
663 }
664 
665 /// Generates a random `f64` in range `0..1`.
f64() -> f64666 pub fn f64() -> f64 {
667     RNG.with(|rng| rng.f64())
668 }
669