fastrand/
lib.rs

Help
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//! Sample values from an array with `O(n)` complexity (`n` is the length of array):
33//!
34//! ```
35//! fastrand::choose_multiple(vec![1, 4, 5].iter(), 2);
36//! fastrand::choose_multiple(0..20, 12);
37//! ```
38//!
39//!
40//! Shuffle an array:
41//!
42//! ```
43//! let mut v = vec![1, 2, 3, 4, 5];
44//! fastrand::shuffle(&mut v);
45//! ```
46//!
47//! Generate a random [`Vec`] or [`String`]:
48//!
49//! ```
50//! use std::iter::repeat_with;
51//!
52//! let v: Vec<i32> = repeat_with(|| fastrand::i32(..)).take(10).collect();
53//! let s: String = repeat_with(fastrand::alphanumeric).take(10).collect();
54//! ```
55//!
56//! To get reproducible results on every run, initialize the generator with a seed:
57//!
58//! ```
59//! // Pick an arbitrary number as seed.
60//! fastrand::seed(7);
61//!
62//! // Now this prints the same number on every run:
63//! println!("{}", fastrand::u32(..));
64//! ```
65//!
66//! To be more efficient, create a new [`Rng`] instance instead of using the thread-local
67//! generator:
68//!
69//! ```
70//! use std::iter::repeat_with;
71//!
72//! let mut rng = fastrand::Rng::new();
73//! let mut bytes: Vec<u8> = repeat_with(|| rng.u8(..)).take(10_000).collect();
74//! ```
75//!
76//! This crate aims to expose a core set of useful randomness primitives. For more niche algorithms,
77//! consider using the [`fastrand-contrib`] crate alongside this one.
78//!
79//! # Features
80//!
81//! - `std` (enabled by default): Enables the `std` library. This is required for the global
82//!   generator and global entropy. Without this feature, [`Rng`] can only be instantiated using
83//!   the [`with_seed`](Rng::with_seed) method.
84//! - `js`: Assumes that WebAssembly targets are being run in a JavaScript environment. See the
85//!   [WebAssembly Notes](#webassembly-notes) section for more information.
86//!
87//! # WebAssembly Notes
88//!
89//! For non-WASI WASM targets, there is additional sublety to consider when utilizing the global RNG.
90//! By default, `std` targets will use entropy sources in the standard library to seed the global RNG.
91//! However, these sources are not available by default on WASM targets outside of WASI.
92//!
93//! If the `js` feature is enabled, this crate will assume that it is running in a JavaScript
94//! environment. At this point, the [`getrandom`] crate will be used in order to access the available
95//! entropy sources and seed the global RNG. If the `js` feature is not enabled, the global RNG will
96//! use a predefined seed.
97//!
98//! [`fastrand-contrib`]: https://crates.io/crates/fastrand-contrib
99//! [`getrandom`]: https://crates.io/crates/getrandom
100
101#![cfg_attr(not(feature = "std"), no_std)]
102#![cfg_attr(docsrs, feature(doc_cfg))]
103#![forbid(unsafe_code)]
104#![warn(missing_docs, missing_debug_implementations, rust_2018_idioms)]
105#![doc(
106    html_favicon_url = "https://raw.githubusercontent.com/smol-rs/smol/master/assets/images/logo_fullsize_transparent.png"
107)]
108#![doc(
109    html_logo_url = "https://raw.githubusercontent.com/smol-rs/smol/master/assets/images/logo_fullsize_transparent.png"
110)]
111
112#[cfg(feature = "alloc")]
113extern crate alloc;
114
115use core::convert::{TryFrom, TryInto};
116use core::ops::{Bound, RangeBounds};
117
118#[cfg(feature = "alloc")]
119use alloc::vec::Vec;
120
121#[cfg(feature = "std")]
122#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
123mod global_rng;
124
125#[cfg(feature = "std")]
126pub use global_rng::*;
127
128/// A random number generator.
129#[derive(Debug, PartialEq, Eq)]
130pub struct Rng(u64);
131
132impl Clone for Rng {
133    /// Clones the generator by creating a new generator with the same seed.
134    fn clone(&self) -> Rng {
135        Rng::with_seed(self.0)
136    }
137}
138
139impl Rng {
140    /// Generates a random `u32`.
141    #[inline]
142    fn gen_u32(&mut self) -> u32 {
143        self.gen_u64() as u32
144    }
145
146    /// Generates a random `u64`.
147    #[inline]
148    fn gen_u64(&mut self) -> u64 {
149        let s = self.0.wrapping_add(0xA0761D6478BD642F);
150        self.0 = s;
151        let t = u128::from(s) * u128::from(s ^ 0xE7037ED1A0B428DB);
152        (t as u64) ^ (t >> 64) as u64
153    }
154
155    /// Generates a random `u128`.
156    #[inline]
157    fn gen_u128(&mut self) -> u128 {
158        (u128::from(self.gen_u64()) << 64) | u128::from(self.gen_u64())
159    }
160
161    /// Generates a random `u32` in `0..n`.
162    #[inline]
163    fn gen_mod_u32(&mut self, n: u32) -> u32 {
164        // Adapted from: https://lemire.me/blog/2016/06/30/fast-random-shuffling/
165        let mut r = self.gen_u32();
166        let mut hi = mul_high_u32(r, n);
167        let mut lo = r.wrapping_mul(n);
168        if lo < n {
169            let t = n.wrapping_neg() % n;
170            while lo < t {
171                r = self.gen_u32();
172                hi = mul_high_u32(r, n);
173                lo = r.wrapping_mul(n);
174            }
175        }
176        hi
177    }
178
179    /// Generates a random `u64` in `0..n`.
180    #[inline]
181    fn gen_mod_u64(&mut self, n: u64) -> u64 {
182        // Adapted from: https://lemire.me/blog/2016/06/30/fast-random-shuffling/
183        let mut r = self.gen_u64();
184        let mut hi = mul_high_u64(r, n);
185        let mut lo = r.wrapping_mul(n);
186        if lo < n {
187            let t = n.wrapping_neg() % n;
188            while lo < t {
189                r = self.gen_u64();
190                hi = mul_high_u64(r, n);
191                lo = r.wrapping_mul(n);
192            }
193        }
194        hi
195    }
196
197    /// Generates a random `u128` in `0..n`.
198    #[inline]
199    fn gen_mod_u128(&mut self, n: u128) -> u128 {
200        // Adapted from: https://lemire.me/blog/2016/06/30/fast-random-shuffling/
201        let mut r = self.gen_u128();
202        let mut hi = mul_high_u128(r, n);
203        let mut lo = r.wrapping_mul(n);
204        if lo < n {
205            let t = n.wrapping_neg() % n;
206            while lo < t {
207                r = self.gen_u128();
208                hi = mul_high_u128(r, n);
209                lo = r.wrapping_mul(n);
210            }
211        }
212        hi
213    }
214}
215
216/// Computes `(a * b) >> 32`.
217#[inline]
218fn mul_high_u32(a: u32, b: u32) -> u32 {
219    (((a as u64) * (b as u64)) >> 32) as u32
220}
221
222/// Computes `(a * b) >> 64`.
223#[inline]
224fn mul_high_u64(a: u64, b: u64) -> u64 {
225    (((a as u128) * (b as u128)) >> 64) as u64
226}
227
228/// Computes `(a * b) >> 128`.
229#[inline]
230fn mul_high_u128(a: u128, b: u128) -> u128 {
231    // Adapted from: https://stackoverflow.com/a/28904636
232    let a_lo = a as u64 as u128;
233    let a_hi = (a >> 64) as u64 as u128;
234    let b_lo = b as u64 as u128;
235    let b_hi = (b >> 64) as u64 as u128;
236    let carry = (a_lo * b_lo) >> 64;
237    let carry = ((a_hi * b_lo) as u64 as u128 + (a_lo * b_hi) as u64 as u128 + carry) >> 64;
238    a_hi * b_hi + ((a_hi * b_lo) >> 64) + ((a_lo * b_hi) >> 64) + carry
239}
240
241macro_rules! rng_integer {
242    ($t:tt, $unsigned_t:tt, $gen:tt, $mod:tt, $doc:tt) => {
243        #[doc = $doc]
244        ///
245        /// Panics if the range is empty.
246        #[inline]
247        pub fn $t(&mut self, range: impl RangeBounds<$t>) -> $t {
248            let panic_empty_range = || {
249                panic!(
250                    "empty range: {:?}..{:?}",
251                    range.start_bound(),
252                    range.end_bound()
253                )
254            };
255
256            let low = match range.start_bound() {
257                Bound::Unbounded => core::$t::MIN,
258                Bound::Included(&x) => x,
259                Bound::Excluded(&x) => x.checked_add(1).unwrap_or_else(panic_empty_range),
260            };
261
262            let high = match range.end_bound() {
263                Bound::Unbounded => core::$t::MAX,
264                Bound::Included(&x) => x,
265                Bound::Excluded(&x) => x.checked_sub(1).unwrap_or_else(panic_empty_range),
266            };
267
268            if low > high {
269                panic_empty_range();
270            }
271
272            if low == core::$t::MIN && high == core::$t::MAX {
273                self.$gen() as $t
274            } else {
275                let len = high.wrapping_sub(low).wrapping_add(1);
276                low.wrapping_add(self.$mod(len as $unsigned_t as _) as $t)
277            }
278        }
279    };
280}
281
282impl Rng {
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 mut rng = Rng(0);
288
289        rng.seed(seed);
290        rng
291    }
292
293    /// Clones the generator by deterministically deriving a new generator based on the initial
294    /// seed.
295    ///
296    /// This function can be used to create a new generator that is a "spinoff" of the old
297    /// generator. The new generator will not produce the same sequence of values as the
298    /// old generator.
299    ///
300    /// # Example
301    ///
302    /// ```
303    /// // Seed two generators equally, and clone both of them.
304    /// let mut base1 = fastrand::Rng::with_seed(0x4d595df4d0f33173);
305    /// base1.bool(); // Use the generator once.
306    ///
307    /// let mut base2 = fastrand::Rng::with_seed(0x4d595df4d0f33173);
308    /// base2.bool(); // Use the generator once.
309    ///
310    /// let mut rng1 = base1.fork();
311    /// let mut rng2 = base2.fork();
312    ///
313    /// println!("rng1 returns {}", rng1.u32(..));
314    /// println!("rng2 returns {}", rng2.u32(..));
315    /// ```
316    #[inline]
317    #[must_use = "this creates a new instance of `Rng`"]
318    pub fn fork(&mut self) -> Self {
319        Rng::with_seed(self.gen_u64())
320    }
321
322    /// Generates a random `char` in ranges a-z and A-Z.
323    #[inline]
324    pub fn alphabetic(&mut self) -> char {
325        const CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
326        *self.choice(CHARS).unwrap() as char
327    }
328
329    /// Generates a random `char` in ranges a-z, A-Z and 0-9.
330    #[inline]
331    pub fn alphanumeric(&mut self) -> char {
332        const CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
333        *self.choice(CHARS).unwrap() as char
334    }
335
336    /// Generates a random `bool`.
337    #[inline]
338    pub fn bool(&mut self) -> bool {
339        self.u8(..) % 2 == 0
340    }
341
342    /// Generates a random digit in the given `base`.
343    ///
344    /// Digits are represented by `char`s in ranges 0-9 and a-z.
345    ///
346    /// Panics if the base is zero or greater than 36.
347    #[inline]
348    pub fn digit(&mut self, base: u32) -> char {
349        if base == 0 {
350            panic!("base cannot be zero");
351        }
352        if base > 36 {
353            panic!("base cannot be larger than 36");
354        }
355        let num = self.u8(..base as u8);
356        if num < 10 {
357            (b'0' + num) as char
358        } else {
359            (b'a' + num - 10) as char
360        }
361    }
362
363    /// Generates a random `f32` in range `0..1`.
364    pub fn f32(&mut self) -> f32 {
365        let b = 32;
366        let f = core::f32::MANTISSA_DIGITS - 1;
367        f32::from_bits((1 << (b - 2)) - (1 << f) + (self.u32(..) >> (b - f))) - 1.0
368    }
369
370    /// Generates a random `f64` in range `0..1`.
371    pub fn f64(&mut self) -> f64 {
372        let b = 64;
373        let f = core::f64::MANTISSA_DIGITS - 1;
374        f64::from_bits((1 << (b - 2)) - (1 << f) + (self.u64(..) >> (b - f))) - 1.0
375    }
376
377    /// Collects `amount` values at random from the iterator into a vector.
378    ///
379    /// The length of the returned vector equals `amount` unless the iterator
380    /// contains insufficient elements, in which case it equals the number of
381    /// elements available.
382    ///
383    /// Complexity is `O(n)` where `n` is the length of the iterator.
384    #[cfg(feature = "alloc")]
385    #[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
386    pub fn choose_multiple<T: Iterator>(&mut self, mut source: T, amount: usize) -> Vec<T::Item> {
387        // Adapted from: https://docs.rs/rand/latest/rand/seq/trait.IteratorRandom.html#method.choose_multiple
388        let mut reservoir = Vec::with_capacity(amount);
389
390        reservoir.extend(source.by_ref().take(amount));
391
392        // Continue unless the iterator was exhausted
393        //
394        // note: this prevents iterators that "restart" from causing problems.
395        // If the iterator stops once, then so do we.
396        if reservoir.len() == amount {
397            for (i, elem) in source.enumerate() {
398                let end = i + 1 + amount;
399                let k = self.usize(0..end);
400                if let Some(slot) = reservoir.get_mut(k) {
401                    *slot = elem;
402                }
403            }
404        } else {
405            // If less than one third of the `Vec` was used, reallocate
406            // so that the unused space is not wasted. There is a corner
407            // case where `amount` was much less than `self.len()`.
408            if reservoir.capacity() > 3 * reservoir.len() {
409                reservoir.shrink_to_fit();
410            }
411        }
412        reservoir
413    }
414
415    rng_integer!(
416        i8,
417        u8,
418        gen_u32,
419        gen_mod_u32,
420        "Generates a random `i8` in the given range."
421    );
422
423    rng_integer!(
424        i16,
425        u16,
426        gen_u32,
427        gen_mod_u32,
428        "Generates a random `i16` in the given range."
429    );
430
431    rng_integer!(
432        i32,
433        u32,
434        gen_u32,
435        gen_mod_u32,
436        "Generates a random `i32` in the given range."
437    );
438
439    rng_integer!(
440        i64,
441        u64,
442        gen_u64,
443        gen_mod_u64,
444        "Generates a random `i64` in the given range."
445    );
446
447    rng_integer!(
448        i128,
449        u128,
450        gen_u128,
451        gen_mod_u128,
452        "Generates a random `i128` in the given range."
453    );
454
455    #[cfg(target_pointer_width = "16")]
456    rng_integer!(
457        isize,
458        usize,
459        gen_u32,
460        gen_mod_u32,
461        "Generates a random `isize` in the given range."
462    );
463    #[cfg(target_pointer_width = "32")]
464    rng_integer!(
465        isize,
466        usize,
467        gen_u32,
468        gen_mod_u32,
469        "Generates a random `isize` in the given range."
470    );
471    #[cfg(target_pointer_width = "64")]
472    rng_integer!(
473        isize,
474        usize,
475        gen_u64,
476        gen_mod_u64,
477        "Generates a random `isize` in the given range."
478    );
479
480    /// Generates a random `char` in range a-z.
481    #[inline]
482    pub fn lowercase(&mut self) -> char {
483        const CHARS: &[u8] = b"abcdefghijklmnopqrstuvwxyz";
484        *self.choice(CHARS).unwrap() as char
485    }
486
487    /// Initializes this generator with the given seed.
488    #[inline]
489    pub fn seed(&mut self, seed: u64) {
490        self.0 = seed;
491    }
492
493    /// Gives back **current** seed that is being held by this generator.
494    #[inline]
495    pub fn get_seed(&self) -> u64 {
496        self.0
497    }
498
499    /// Choose an item from an iterator at random.
500    ///
501    /// This function may have an unexpected result if the `len()` property of the
502    /// iterator does not match the actual number of items in the iterator. If
503    /// the iterator is empty, this returns `None`.
504    #[inline]
505    pub fn choice<I>(&mut self, iter: I) -> Option<I::Item>
506    where
507        I: IntoIterator,
508        I::IntoIter: ExactSizeIterator,
509    {
510        let mut iter = iter.into_iter();
511
512        // Get the item at a random index.
513        let len = iter.len();
514        if len == 0 {
515            return None;
516        }
517        let index = self.usize(0..len);
518
519        iter.nth(index)
520    }
521
522    /// Shuffles a slice randomly.
523    #[inline]
524    pub fn shuffle<T>(&mut self, slice: &mut [T]) {
525        for i in 1..slice.len() {
526            slice.swap(i, self.usize(..=i));
527        }
528    }
529
530    /// Fill a byte slice with random data.
531    #[inline]
532    pub fn fill(&mut self, slice: &mut [u8]) {
533        // We fill the slice by chunks of 8 bytes, or one block of
534        // WyRand output per new state.
535        let mut chunks = slice.chunks_exact_mut(core::mem::size_of::<u64>());
536        for chunk in chunks.by_ref() {
537            let n = self.gen_u64().to_ne_bytes();
538            // Safe because the chunks are always 8 bytes exactly.
539            chunk.copy_from_slice(&n);
540        }
541
542        let remainder = chunks.into_remainder();
543
544        // Any remainder will always be less than 8 bytes.
545        if !remainder.is_empty() {
546            // Generate one last block of 8 bytes of entropy
547            let n = self.gen_u64().to_ne_bytes();
548
549            // Use the remaining length to copy from block
550            remainder.copy_from_slice(&n[..remainder.len()]);
551        }
552    }
553
554    rng_integer!(
555        u8,
556        u8,
557        gen_u32,
558        gen_mod_u32,
559        "Generates a random `u8` in the given range."
560    );
561
562    rng_integer!(
563        u16,
564        u16,
565        gen_u32,
566        gen_mod_u32,
567        "Generates a random `u16` in the given range."
568    );
569
570    rng_integer!(
571        u32,
572        u32,
573        gen_u32,
574        gen_mod_u32,
575        "Generates a random `u32` in the given range."
576    );
577
578    rng_integer!(
579        u64,
580        u64,
581        gen_u64,
582        gen_mod_u64,
583        "Generates a random `u64` in the given range."
584    );
585
586    rng_integer!(
587        u128,
588        u128,
589        gen_u128,
590        gen_mod_u128,
591        "Generates a random `u128` in the given range."
592    );
593
594    #[cfg(target_pointer_width = "16")]
595    rng_integer!(
596        usize,
597        usize,
598        gen_u32,
599        gen_mod_u32,
600        "Generates a random `usize` in the given range."
601    );
602    #[cfg(target_pointer_width = "32")]
603    rng_integer!(
604        usize,
605        usize,
606        gen_u32,
607        gen_mod_u32,
608        "Generates a random `usize` in the given range."
609    );
610    #[cfg(target_pointer_width = "64")]
611    rng_integer!(
612        usize,
613        usize,
614        gen_u64,
615        gen_mod_u64,
616        "Generates a random `usize` in the given range."
617    );
618    #[cfg(target_pointer_width = "128")]
619    rng_integer!(
620        usize,
621        usize,
622        gen_u128,
623        gen_mod_u128,
624        "Generates a random `usize` in the given range."
625    );
626
627    /// Generates a random `char` in range A-Z.
628    #[inline]
629    pub fn uppercase(&mut self) -> char {
630        const CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZ";
631        *self.choice(CHARS).unwrap() as char
632    }
633
634    /// Generates a random `char` in the given range.
635    ///
636    /// Panics if the range is empty.
637    #[inline]
638    pub fn char(&mut self, range: impl RangeBounds<char>) -> char {
639        let panic_empty_range = || {
640            panic!(
641                "empty range: {:?}..{:?}",
642                range.start_bound(),
643                range.end_bound()
644            )
645        };
646
647        let surrogate_start = 0xd800u32;
648        let surrogate_len = 0x800u32;
649
650        let low = match range.start_bound() {
651            Bound::Unbounded => 0u8 as char,
652            Bound::Included(&x) => x,
653            Bound::Excluded(&x) => {
654                let scalar = if x as u32 == surrogate_start - 1 {
655                    surrogate_start + surrogate_len
656                } else {
657                    x as u32 + 1
658                };
659                char::try_from(scalar).unwrap_or_else(|_| panic_empty_range())
660            }
661        };
662
663        let high = match range.end_bound() {
664            Bound::Unbounded => core::char::MAX,
665            Bound::Included(&x) => x,
666            Bound::Excluded(&x) => {
667                let scalar = if x as u32 == surrogate_start + surrogate_len {
668                    surrogate_start - 1
669                } else {
670                    (x as u32).wrapping_sub(1)
671                };
672                char::try_from(scalar).unwrap_or_else(|_| panic_empty_range())
673            }
674        };
675
676        if low > high {
677            panic_empty_range();
678        }
679
680        let gap = if (low as u32) < surrogate_start && (high as u32) >= surrogate_start {
681            surrogate_len
682        } else {
683            0
684        };
685        let range = high as u32 - low as u32 - gap;
686        let mut val = self.u32(0..=range) + low as u32;
687        if val >= surrogate_start {
688            val += gap;
689        }
690        val.try_into().unwrap()
691    }
692}
fastrand/lib.rs

fastrand/
lib.rs
