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

fastrand/
lib.rs
