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::convert::TryInto;
74use std::hash::{Hash, Hasher};
75use std::ops::{Bound, RangeBounds};
76use std::thread;
77
78#[cfg(all(target_arch = "wasm32", not(target_os = "wasi")))]
79use instant::Instant;
80#[cfg(not(all(target_arch = "wasm32", not(target_os = "wasi"))))]
81use std::time::Instant;
82
83/// A random number generator.
84#[derive(Debug, PartialEq, Eq)]
85pub struct Rng(Cell<u64>);
86
87impl Default for Rng {
88    #[inline]
89    fn default() -> Rng {
90        Rng::new()
91    }
92}
93
94impl Clone for Rng {
95    /// Clones the generator by deterministically deriving a new generator based on the initial
96    /// seed.
97    ///
98    /// # Example
99    ///
100    /// ```
101    /// // Seed two generators equally, and clone both of them.
102    /// let base1 = fastrand::Rng::new();
103    /// base1.seed(0x4d595df4d0f33173);
104    /// base1.bool(); // Use the generator once.
105    ///
106    /// let base2 = fastrand::Rng::new();
107    /// base2.seed(0x4d595df4d0f33173);
108    /// base2.bool(); // Use the generator once.
109    ///
110    /// let rng1 = base1.clone();
111    /// let rng2 = base2.clone();
112    ///
113    /// assert_eq!(rng1.u64(..), rng2.u64(..), "the cloned generators are identical");
114    /// ```
115    fn clone(&self) -> Rng {
116        Rng::with_seed(self.gen_u64())
117    }
118}
119
120impl Rng {
121    /// Generates a random `u32`.
122    #[inline]
123    fn gen_u32(&self) -> u32 {
124        self.gen_u64() as u32
125    }
126
127    /// Generates a random `u64`.
128    #[inline]
129    fn gen_u64(&self) -> u64 {
130        let s = self.0.get().wrapping_add(0xA0761D6478BD642F);
131        self.0.set(s);
132        let t = u128::from(s) * u128::from(s ^ 0xE7037ED1A0B428DB);
133        (t as u64) ^ (t >> 64) as u64
134    }
135
136    /// Generates a random `u128`.
137    #[inline]
138    fn gen_u128(&self) -> u128 {
139        (u128::from(self.gen_u64()) << 64) | u128::from(self.gen_u64())
140    }
141
142    /// Generates a random `u32` in `0..n`.
143    #[inline]
144    fn gen_mod_u32(&self, n: u32) -> u32 {
145        // Adapted from: https://lemire.me/blog/2016/06/30/fast-random-shuffling/
146        let mut r = self.gen_u32();
147        let mut hi = mul_high_u32(r, n);
148        let mut lo = r.wrapping_mul(n);
149        if lo < n {
150            let t = n.wrapping_neg() % n;
151            while lo < t {
152                r = self.gen_u32();
153                hi = mul_high_u32(r, n);
154                lo = r.wrapping_mul(n);
155            }
156        }
157        hi
158    }
159
160    /// Generates a random `u64` in `0..n`.
161    #[inline]
162    fn gen_mod_u64(&self, n: u64) -> u64 {
163        // Adapted from: https://lemire.me/blog/2016/06/30/fast-random-shuffling/
164        let mut r = self.gen_u64();
165        let mut hi = mul_high_u64(r, n);
166        let mut lo = r.wrapping_mul(n);
167        if lo < n {
168            let t = n.wrapping_neg() % n;
169            while lo < t {
170                r = self.gen_u64();
171                hi = mul_high_u64(r, n);
172                lo = r.wrapping_mul(n);
173            }
174        }
175        hi
176    }
177
178    /// Generates a random `u128` in `0..n`.
179    #[inline]
180    fn gen_mod_u128(&self, n: u128) -> u128 {
181        // Adapted from: https://lemire.me/blog/2016/06/30/fast-random-shuffling/
182        let mut r = self.gen_u128();
183        let mut hi = mul_high_u128(r, n);
184        let mut lo = r.wrapping_mul(n);
185        if lo < n {
186            let t = n.wrapping_neg() % n;
187            while lo < t {
188                r = self.gen_u128();
189                hi = mul_high_u128(r, n);
190                lo = r.wrapping_mul(n);
191            }
192        }
193        hi
194    }
195}
196
197thread_local! {
198    static RNG: Rng = Rng(Cell::new({
199        let mut hasher = DefaultHasher::new();
200        Instant::now().hash(&mut hasher);
201        thread::current().id().hash(&mut hasher);
202        let hash = hasher.finish();
203        (hash << 1) | 1
204    }));
205}
206
207/// Computes `(a * b) >> 32`.
208#[inline]
209fn mul_high_u32(a: u32, b: u32) -> u32 {
210    (((a as u64) * (b as u64)) >> 32) as u32
211}
212
213/// Computes `(a * b) >> 64`.
214#[inline]
215fn mul_high_u64(a: u64, b: u64) -> u64 {
216    (((a as u128) * (b as u128)) >> 64) as u64
217}
218
219/// Computes `(a * b) >> 128`.
220#[inline]
221fn mul_high_u128(a: u128, b: u128) -> u128 {
222    // Adapted from: https://stackoverflow.com/a/28904636
223    let a_lo = a as u64 as u128;
224    let a_hi = (a >> 64) as u64 as u128;
225    let b_lo = b as u64 as u128;
226    let b_hi = (b >> 64) as u64 as u128;
227    let carry = (a_lo * b_lo) >> 64;
228    let carry = ((a_hi * b_lo) as u64 as u128 + (a_lo * b_hi) as u64 as u128 + carry) >> 64;
229    a_hi * b_hi + ((a_hi * b_lo) >> 64) + ((a_lo * b_hi) >> 64) + carry
230}
231
232macro_rules! rng_integer {
233    ($t:tt, $unsigned_t:tt, $gen:tt, $mod:tt, $doc:tt) => {
234        #[doc = $doc]
235        ///
236        /// Panics if the range is empty.
237        #[inline]
238        pub fn $t(&self, range: impl RangeBounds<$t>) -> $t {
239            let panic_empty_range = || {
240                panic!(
241                    "empty range: {:?}..{:?}",
242                    range.start_bound(),
243                    range.end_bound()
244                )
245            };
246
247            let low = match range.start_bound() {
248                Bound::Unbounded => std::$t::MIN,
249                Bound::Included(&x) => x,
250                Bound::Excluded(&x) => x.checked_add(1).unwrap_or_else(panic_empty_range),
251            };
252
253            let high = match range.end_bound() {
254                Bound::Unbounded => std::$t::MAX,
255                Bound::Included(&x) => x,
256                Bound::Excluded(&x) => x.checked_sub(1).unwrap_or_else(panic_empty_range),
257            };
258
259            if low > high {
260                panic_empty_range();
261            }
262
263            if low == std::$t::MIN && high == std::$t::MAX {
264                self.$gen() as $t
265            } else {
266                let len = high.wrapping_sub(low).wrapping_add(1);
267                low.wrapping_add(self.$mod(len as $unsigned_t as _) as $t)
268            }
269        }
270    };
271}
272
273impl Rng {
274    /// Creates a new random number generator.
275    #[inline]
276    pub fn new() -> Rng {
277        Rng::with_seed(
278            RNG.try_with(|rng| rng.u64(..))
279                .unwrap_or(0x4d595df4d0f33173),
280        )
281    }
282
283    /// Creates a new random number generator with the initial seed.
284    #[inline]
285    #[must_use = "this creates a new instance of `Rng`; if you want to initialize the thread-local generator, use `fastrand::seed()` instead"]
286    pub fn with_seed(seed: u64) -> Self {
287        let rng = Rng(Cell::new(0));
288
289        rng.seed(seed);
290        rng
291    }
292
293    /// Generates a random `char` in ranges a-z and A-Z.
294    #[inline]
295    pub fn alphabetic(&self) -> char {
296        const CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
297        let len = CHARS.len() as u8;
298        let i = self.u8(..len);
299        CHARS[i as usize] as char
300    }
301
302    /// Generates a random `char` in ranges a-z, A-Z and 0-9.
303    #[inline]
304    pub fn alphanumeric(&self) -> char {
305        const CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
306        let len = CHARS.len() as u8;
307        let i = self.u8(..len);
308        CHARS[i as usize] as char
309    }
310
311    /// Generates a random `bool`.
312    #[inline]
313    pub fn bool(&self) -> bool {
314        self.u8(..) % 2 == 0
315    }
316
317    /// Generates a random digit in the given `base`.
318    ///
319    /// Digits are represented by `char`s in ranges 0-9 and a-z.
320    ///
321    /// Panics if the base is zero or greater than 36.
322    #[inline]
323    pub fn digit(&self, base: u32) -> char {
324        if base == 0 {
325            panic!("base cannot be zero");
326        }
327        if base > 36 {
328            panic!("base cannot be larger than 36");
329        }
330        let num = self.u8(..base as u8);
331        if num < 10 {
332            (b'0' + num) as char
333        } else {
334            (b'a' + num - 10) as char
335        }
336    }
337
338    /// Generates a random `f32` in range `0..1`.
339    pub fn f32(&self) -> f32 {
340        let b = 32;
341        let f = std::f32::MANTISSA_DIGITS - 1;
342        f32::from_bits((1 << (b - 2)) - (1 << f) + (self.u32(..) >> (b - f))) - 1.0
343    }
344
345    /// Generates a random `f64` in range `0..1`.
346    pub fn f64(&self) -> f64 {
347        let b = 64;
348        let f = std::f64::MANTISSA_DIGITS - 1;
349        f64::from_bits((1 << (b - 2)) - (1 << f) + (self.u64(..) >> (b - f))) - 1.0
350    }
351
352    rng_integer!(
353        i8,
354        u8,
355        gen_u32,
356        gen_mod_u32,
357        "Generates a random `i8` in the given range."
358    );
359
360    rng_integer!(
361        i16,
362        u16,
363        gen_u32,
364        gen_mod_u32,
365        "Generates a random `i16` in the given range."
366    );
367
368    rng_integer!(
369        i32,
370        u32,
371        gen_u32,
372        gen_mod_u32,
373        "Generates a random `i32` in the given range."
374    );
375
376    rng_integer!(
377        i64,
378        u64,
379        gen_u64,
380        gen_mod_u64,
381        "Generates a random `i64` in the given range."
382    );
383
384    rng_integer!(
385        i128,
386        u128,
387        gen_u128,
388        gen_mod_u128,
389        "Generates a random `i128` in the given range."
390    );
391
392    #[cfg(target_pointer_width = "16")]
393    rng_integer!(
394        isize,
395        usize,
396        gen_u32,
397        gen_mod_u32,
398        "Generates a random `isize` in the given range."
399    );
400    #[cfg(target_pointer_width = "32")]
401    rng_integer!(
402        isize,
403        usize,
404        gen_u32,
405        gen_mod_u32,
406        "Generates a random `isize` in the given range."
407    );
408    #[cfg(target_pointer_width = "64")]
409    rng_integer!(
410        isize,
411        usize,
412        gen_u64,
413        gen_mod_u64,
414        "Generates a random `isize` in the given range."
415    );
416
417    /// Generates a random `char` in range a-z.
418    #[inline]
419    pub fn lowercase(&self) -> char {
420        const CHARS: &[u8] = b"abcdefghijklmnopqrstuvwxyz";
421        let len = CHARS.len() as u8;
422        let i = self.u8(..len);
423        CHARS[i as usize] as char
424    }
425
426    /// Initializes this generator with the given seed.
427    #[inline]
428    pub fn seed(&self, seed: u64) {
429        self.0.set(seed);
430    }
431
432    /// Gives back **current** seed that is being held by this generator.
433    #[inline]
434    pub fn get_seed(&self) -> u64 {
435        self.0.get()
436    }
437
438    /// Shuffles a slice randomly.
439    #[inline]
440    pub fn shuffle<T>(&self, slice: &mut [T]) {
441        for i in 1..slice.len() {
442            slice.swap(i, self.usize(..=i));
443        }
444    }
445
446    /// Fill a byte slice with random data.
447    #[inline]
448    pub fn fill(&self, slice: &mut [u8]) {
449        // We fill the slice by chunks of 8 bytes, or one block of
450        // WyRand output per new state.
451        let mut chunks = slice.chunks_exact_mut(core::mem::size_of::<u64>());
452        for chunk in chunks.by_ref() {
453            let n = self.gen_u64().to_ne_bytes();
454            // Safe because the chunks are always 8 bytes exactly.
455            chunk.copy_from_slice(&n);
456        }
457
458        let remainder = chunks.into_remainder();
459
460        // Any remainder will always be less than 8 bytes.
461        if !remainder.is_empty() {
462            // Generate one last block of 8 bytes of entropy
463            let n = self.gen_u64().to_ne_bytes();
464
465            // Use the remaining length to copy from block
466            remainder.copy_from_slice(&n[..remainder.len()]);
467        }
468    }
469
470    rng_integer!(
471        u8,
472        u8,
473        gen_u32,
474        gen_mod_u32,
475        "Generates a random `u8` in the given range."
476    );
477
478    rng_integer!(
479        u16,
480        u16,
481        gen_u32,
482        gen_mod_u32,
483        "Generates a random `u16` in the given range."
484    );
485
486    rng_integer!(
487        u32,
488        u32,
489        gen_u32,
490        gen_mod_u32,
491        "Generates a random `u32` in the given range."
492    );
493
494    rng_integer!(
495        u64,
496        u64,
497        gen_u64,
498        gen_mod_u64,
499        "Generates a random `u64` in the given range."
500    );
501
502    rng_integer!(
503        u128,
504        u128,
505        gen_u128,
506        gen_mod_u128,
507        "Generates a random `u128` in the given range."
508    );
509
510    #[cfg(target_pointer_width = "16")]
511    rng_integer!(
512        usize,
513        usize,
514        gen_u32,
515        gen_mod_u32,
516        "Generates a random `usize` in the given range."
517    );
518    #[cfg(target_pointer_width = "32")]
519    rng_integer!(
520        usize,
521        usize,
522        gen_u32,
523        gen_mod_u32,
524        "Generates a random `usize` in the given range."
525    );
526    #[cfg(target_pointer_width = "64")]
527    rng_integer!(
528        usize,
529        usize,
530        gen_u64,
531        gen_mod_u64,
532        "Generates a random `usize` in the given range."
533    );
534    #[cfg(target_pointer_width = "128")]
535    rng_integer!(
536        usize,
537        usize,
538        gen_u128,
539        gen_mod_u128,
540        "Generates a random `usize` in the given range."
541    );
542
543    /// Generates a random `char` in range A-Z.
544    #[inline]
545    pub fn uppercase(&self) -> char {
546        const CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZ";
547        let len = CHARS.len() as u8;
548        let i = self.u8(..len);
549        CHARS[i as usize] as char
550    }
551
552    /// Generates a random `char` in the given range.
553    ///
554    /// Panics if the range is empty.
555    #[inline]
556    pub fn char(&self, range: impl RangeBounds<char>) -> char {
557        use std::convert::TryFrom;
558
559        let panic_empty_range = || {
560            panic!(
561                "empty range: {:?}..{:?}",
562                range.start_bound(),
563                range.end_bound()
564            )
565        };
566
567        let surrogate_start = 0xd800u32;
568        let surrogate_len = 0x800u32;
569
570        let low = match range.start_bound() {
571            Bound::Unbounded => 0u8 as char,
572            Bound::Included(&x) => x,
573            Bound::Excluded(&x) => {
574                let scalar = if x as u32 == surrogate_start - 1 {
575                    surrogate_start + surrogate_len
576                } else {
577                    x as u32 + 1
578                };
579                char::try_from(scalar).unwrap_or_else(|_| panic_empty_range())
580            }
581        };
582
583        let high = match range.end_bound() {
584            Bound::Unbounded => std::char::MAX,
585            Bound::Included(&x) => x,
586            Bound::Excluded(&x) => {
587                let scalar = if x as u32 == surrogate_start + surrogate_len {
588                    surrogate_start - 1
589                } else {
590                    (x as u32).wrapping_sub(1)
591                };
592                char::try_from(scalar).unwrap_or_else(|_| panic_empty_range())
593            }
594        };
595
596        if low > high {
597            panic_empty_range();
598        }
599
600        let gap = if (low as u32) < surrogate_start && (high as u32) >= surrogate_start {
601            surrogate_len
602        } else {
603            0
604        };
605        let range = high as u32 - low as u32 - gap;
606        let mut val = self.u32(0..=range) + low as u32;
607        if val >= surrogate_start {
608            val += gap;
609        }
610        val.try_into().unwrap()
611    }
612}
613
614/// Initializes the thread-local generator with the given seed.
615#[inline]
616pub fn seed(seed: u64) {
617    RNG.with(|rng| rng.seed(seed))
618}
619
620/// Gives back **current** seed that is being held by the thread-local generator.
621#[inline]
622pub fn get_seed() -> u64 {
623    RNG.with(|rng| rng.get_seed())
624}
625
626/// Generates a random `bool`.
627#[inline]
628pub fn bool() -> bool {
629    RNG.with(|rng| rng.bool())
630}
631
632/// Generates a random `char` in ranges a-z and A-Z.
633#[inline]
634pub fn alphabetic() -> char {
635    RNG.with(|rng| rng.alphabetic())
636}
637
638/// Generates a random `char` in ranges a-z, A-Z and 0-9.
639#[inline]
640pub fn alphanumeric() -> char {
641    RNG.with(|rng| rng.alphanumeric())
642}
643
644/// Generates a random `char` in range a-z.
645#[inline]
646pub fn lowercase() -> char {
647    RNG.with(|rng| rng.lowercase())
648}
649
650/// Generates a random `char` in range A-Z.
651#[inline]
652pub fn uppercase() -> char {
653    RNG.with(|rng| rng.uppercase())
654}
655
656/// Generates a random digit in the given `base`.
657///
658/// Digits are represented by `char`s in ranges 0-9 and a-z.
659///
660/// Panics if the base is zero or greater than 36.
661#[inline]
662pub fn digit(base: u32) -> char {
663    RNG.with(|rng| rng.digit(base))
664}
665
666/// Shuffles a slice randomly.
667#[inline]
668pub fn shuffle<T>(slice: &mut [T]) {
669    RNG.with(|rng| rng.shuffle(slice))
670}
671
672macro_rules! integer {
673    ($t:tt, $doc:tt) => {
674        #[doc = $doc]
675        ///
676        /// Panics if the range is empty.
677        #[inline]
678        pub fn $t(range: impl RangeBounds<$t>) -> $t {
679            RNG.with(|rng| rng.$t(range))
680        }
681    };
682}
683
684integer!(u8, "Generates a random `u8` in the given range.");
685integer!(i8, "Generates a random `i8` in the given range.");
686integer!(u16, "Generates a random `u16` in the given range.");
687integer!(i16, "Generates a random `i16` in the given range.");
688integer!(u32, "Generates a random `u32` in the given range.");
689integer!(i32, "Generates a random `i32` in the given range.");
690integer!(u64, "Generates a random `u64` in the given range.");
691integer!(i64, "Generates a random `i64` in the given range.");
692integer!(u128, "Generates a random `u128` in the given range.");
693integer!(i128, "Generates a random `i128` in the given range.");
694integer!(usize, "Generates a random `usize` in the given range.");
695integer!(isize, "Generates a random `isize` in the given range.");
696integer!(char, "Generates a random `char` in the given range.");
697
698/// Generates a random `f32` in range `0..1`.
699pub fn f32() -> f32 {
700    RNG.with(|rng| rng.f32())
701}
702
703/// Generates a random `f64` in range `0..1`.
704pub fn f64() -> f64 {
705    RNG.with(|rng| rng.f64())
706}
fastrand/lib.rs

fastrand/
lib.rs
