fastrand/
lib.rs

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
71use std::cell::Cell;
72use std::collections::hash_map::DefaultHasher;
73use std::hash::{Hash, Hasher};
74use std::ops::{Bound, RangeBounds};
75use std::thread;
76
77#[cfg(target_arch = "wasm32")]
78use instant::Instant;
79#[cfg(not(target_arch = "wasm32"))]
80use std::time::Instant;
81
82/// A random number generator.
83#[derive(Debug, PartialEq, Eq)]
84pub struct Rng(Cell<u64>);
85
86impl Default for Rng {
87    #[inline]
88    fn default() -> Rng {
89        Rng::new()
90    }
91}
92
93impl 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    /// ```
114    fn clone(&self) -> Rng {
115        Rng::with_seed(self.gen_u64())
116    }
117}
118
119impl Rng {
120    /// Generates a random `u32`.
121    #[inline]
122    fn gen_u32(&self) -> u32 {
123        self.gen_u64() as u32
124    }
125
126    /// Generates a random `u64`.
127    #[inline]
128    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]
137    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]
143    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]
161    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]
179    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
196thread_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]
208fn 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]
214fn 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]
220fn 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
231macro_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
272impl Rng {
273    /// Creates a new random number generator.
274    #[inline]
275    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]
284    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]
293    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]
302    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]
311    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]
321    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`.
337    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`.
344    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]
417    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]
426    pub fn seed(&self, seed: u64) {
427        self.0.set(seed);
428    }
429
430    /// Gives back **current** seed that is being held by this generator.
431    #[inline]
432    pub fn get_seed(&self) -> u64 {
433        self.0.get()
434    }
435
436    /// Shuffles a slice randomly.
437    #[inline]
438    pub fn shuffle<T>(&self, slice: &mut [T]) {
439        for i in 1..slice.len() {
440            slice.swap(i, self.usize(..=i));
441        }
442    }
443
444    rng_integer!(
445        u8,
446        u8,
447        gen_u32,
448        gen_mod_u32,
449        "Generates a random `u8` in the given range."
450    );
451
452    rng_integer!(
453        u16,
454        u16,
455        gen_u32,
456        gen_mod_u32,
457        "Generates a random `u16` in the given range."
458    );
459
460    rng_integer!(
461        u32,
462        u32,
463        gen_u32,
464        gen_mod_u32,
465        "Generates a random `u32` in the given range."
466    );
467
468    rng_integer!(
469        u64,
470        u64,
471        gen_u64,
472        gen_mod_u64,
473        "Generates a random `u64` in the given range."
474    );
475
476    rng_integer!(
477        u128,
478        u128,
479        gen_u128,
480        gen_mod_u128,
481        "Generates a random `u128` in the given range."
482    );
483
484    #[cfg(target_pointer_width = "16")]
485    rng_integer!(
486        usize,
487        usize,
488        gen_u32,
489        gen_mod_u32,
490        "Generates a random `usize` in the given range."
491    );
492    #[cfg(target_pointer_width = "32")]
493    rng_integer!(
494        usize,
495        usize,
496        gen_u32,
497        gen_mod_u32,
498        "Generates a random `usize` in the given range."
499    );
500    #[cfg(target_pointer_width = "64")]
501    rng_integer!(
502        usize,
503        usize,
504        gen_u64,
505        gen_mod_u64,
506        "Generates a random `usize` in the given range."
507    );
508    #[cfg(target_pointer_width = "128")]
509    rng_integer!(
510        usize,
511        usize,
512        gen_u128,
513        gen_mod_u128,
514        "Generates a random `usize` in the given range."
515    );
516
517    /// Generates a random `char` in range A-Z.
518    #[inline]
519    pub fn uppercase(&self) -> char {
520        const CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZ";
521        let len = CHARS.len() as u8;
522        let i = self.u8(..len);
523        CHARS[i as usize] as char
524    }
525
526    /// Generates a random `char` in the given range.
527    ///
528    /// Panics if the range is empty.
529    #[inline]
530    pub fn char(&self, range: impl RangeBounds<char>) -> char {
531        use std::convert::{TryFrom, TryInto};
532
533        let panic_empty_range = || {
534            panic!(
535                "empty range: {:?}..{:?}",
536                range.start_bound(),
537                range.end_bound()
538            )
539        };
540
541        let surrogate_start = 0xd800u32;
542        let surrogate_len = 0x800u32;
543
544        let low = match range.start_bound() {
545            Bound::Unbounded => 0u8 as char,
546            Bound::Included(&x) => x,
547            Bound::Excluded(&x) => {
548                let scalar = if x as u32 == surrogate_start - 1 {
549                    surrogate_start + surrogate_len
550                } else {
551                    x as u32 + 1
552                };
553                char::try_from(scalar).unwrap_or_else(|_| panic_empty_range())
554            }
555        };
556
557        let high = match range.end_bound() {
558            Bound::Unbounded => std::char::MAX,
559            Bound::Included(&x) => x,
560            Bound::Excluded(&x) => {
561                let scalar = if x as u32 == surrogate_start + surrogate_len {
562                    surrogate_start - 1
563                } else {
564                    (x as u32).wrapping_sub(1)
565                };
566                char::try_from(scalar).unwrap_or_else(|_| panic_empty_range())
567            }
568        };
569
570        if low > high {
571            panic_empty_range();
572        }
573
574        let gap = if (low as u32) < surrogate_start && (high as u32) >= surrogate_start {
575            surrogate_len
576        } else {
577            0
578        };
579        let range = high as u32 - low as u32 - gap;
580        let mut val = self.u32(0..=range) + low as u32;
581        if val >= surrogate_start {
582            val += gap;
583        }
584        val.try_into().unwrap()
585    }
586}
587
588/// Initializes the thread-local generator with the given seed.
589#[inline]
590pub fn seed(seed: u64) {
591    RNG.with(|rng| rng.seed(seed))
592}
593
594/// Gives back **current** seed that is being held by the thread-local generator.
595#[inline]
596pub fn get_seed() -> u64 {
597    RNG.with(|rng| rng.get_seed())
598}
599
600/// Generates a random `bool`.
601#[inline]
602pub fn bool() -> bool {
603    RNG.with(|rng| rng.bool())
604}
605
606/// Generates a random `char` in ranges a-z and A-Z.
607#[inline]
608pub fn alphabetic() -> char {
609    RNG.with(|rng| rng.alphabetic())
610}
611
612/// Generates a random `char` in ranges a-z, A-Z and 0-9.
613#[inline]
614pub fn alphanumeric() -> char {
615    RNG.with(|rng| rng.alphanumeric())
616}
617
618/// Generates a random `char` in range a-z.
619#[inline]
620pub fn lowercase() -> char {
621    RNG.with(|rng| rng.lowercase())
622}
623
624/// Generates a random `char` in range A-Z.
625#[inline]
626pub fn uppercase() -> char {
627    RNG.with(|rng| rng.uppercase())
628}
629
630/// Generates a random digit in the given `base`.
631///
632/// Digits are represented by `char`s in ranges 0-9 and a-z.
633///
634/// Panics if the base is zero or greater than 36.
635#[inline]
636pub fn digit(base: u32) -> char {
637    RNG.with(|rng| rng.digit(base))
638}
639
640/// Shuffles a slice randomly.
641#[inline]
642pub fn shuffle<T>(slice: &mut [T]) {
643    RNG.with(|rng| rng.shuffle(slice))
644}
645
646macro_rules! integer {
647    ($t:tt, $doc:tt) => {
648        #[doc = $doc]
649        ///
650        /// Panics if the range is empty.
651        #[inline]
652        pub fn $t(range: impl RangeBounds<$t>) -> $t {
653            RNG.with(|rng| rng.$t(range))
654        }
655    };
656}
657
658integer!(u8, "Generates a random `u8` in the given range.");
659integer!(i8, "Generates a random `i8` in the given range.");
660integer!(u16, "Generates a random `u16` in the given range.");
661integer!(i16, "Generates a random `i16` in the given range.");
662integer!(u32, "Generates a random `u32` in the given range.");
663integer!(i32, "Generates a random `i32` in the given range.");
664integer!(u64, "Generates a random `u64` in the given range.");
665integer!(i64, "Generates a random `i64` in the given range.");
666integer!(u128, "Generates a random `u128` in the given range.");
667integer!(i128, "Generates a random `i128` in the given range.");
668integer!(usize, "Generates a random `usize` in the given range.");
669integer!(isize, "Generates a random `isize` in the given range.");
670integer!(char, "Generates a random `char` in the given range.");
671
672/// Generates a random `f32` in range `0..1`.
673pub fn f32() -> f32 {
674    RNG.with(|rng| rng.f32())
675}
676
677/// Generates a random `f64` in range `0..1`.
678pub fn f64() -> f64 {
679    RNG.with(|rng| rng.f64())
680}
fastrand/lib.rs

fastrand/
lib.rs
