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