fastrand/
lib.rs

Help
1//! A simple and fast random number generator.
2//!
3//! The implementation uses [PCG XSH RR 64/32][paper], a simple and fast generator but **not**
4//! cryptographically secure.
5//!
6//! [paper]: https://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf
7//!
8//! # Examples
9//!
10//! Flip a coin:
11//!
12//! ```
13//! if fastrand::bool() {
14//!     println!("heads");
15//! } else {
16//!     println!("tails");
17//! }
18//! ```
19//!
20//! Generate a random `i32`:
21//!
22//! ```
23//! let num = fastrand::i32(..);
24//! ```
25//!
26//! Choose a random element in an array:
27//!
28//! ```
29//! let v = vec![1, 2, 3, 4, 5];
30//! let i = fastrand::usize(..v.len());
31//! let elem = v[i];
32//! ```
33//!
34//! Shuffle an array:
35//!
36//! ```
37//! let mut v = vec![1, 2, 3, 4, 5];
38//! fastrand::shuffle(&mut v);
39//! ```
40//!
41//! Generate a random [`Vec`] or [`String`]:
42//!
43//! ```
44//! use std::iter::repeat_with;
45//!
46//! let v: Vec<i32> = repeat_with(|| fastrand::i32(..)).take(10).collect();
47//! let s: String = repeat_with(fastrand::alphanumeric).take(10).collect();
48//! ```
49//!
50//! To get reproducible results on every run, initialize the generator with a seed:
51//!
52//! ```
53//! // Pick an arbitrary number as seed.
54//! fastrand::seed(7);
55//!
56//! // Now this prints the same number on every run:
57//! println!("{}", fastrand::u32(..));
58//! ```
59//!
60//! To be more efficient, create a new [`Rng`] instance instead of using the thread-local
61//! generator:
62//!
63//! ```
64//! use std::iter::repeat_with;
65//!
66//! let rng = fastrand::Rng::new();
67//! let mut bytes: Vec<u8> = repeat_with(|| rng.u8(..)).take(10_000).collect();
68//! ```
69
70#![forbid(unsafe_code)]
71#![warn(missing_docs, missing_debug_implementations, rust_2018_idioms)]
72
73use std::cell::Cell;
74use std::collections::hash_map::DefaultHasher;
75use std::hash::{Hash, Hasher};
76use std::ops::{Bound, RangeBounds};
77use std::thread;
78
79#[cfg(not(target_arch = "wasm32"))]
80use std::time::Instant;
81#[cfg(target_arch = "wasm32")]
82use instant::Instant;
83
84/// A random number generator.
85#[derive(Debug)]
86pub struct Rng(Cell<u64>);
87
88impl Default for Rng {
89    #[inline]
90    fn default() -> Rng {
91        Rng::new()
92    }
93}
94
95impl Clone for Rng {
96    /// Clones the generator by deterministically deriving a new generator based on the initial
97    /// seed.
98    ///
99    /// # Example
100    ///
101    /// ```
102    /// // Seed two generators equally, and clone both of them.
103    /// let base1 = fastrand::Rng::new();
104    /// base1.seed(0x4d595df4d0f33173);
105    /// base1.bool(); // Use the generator once.
106    ///
107    /// let base2 = fastrand::Rng::new();
108    /// base2.seed(0x4d595df4d0f33173);
109    /// base2.bool(); // Use the generator once.
110    ///
111    /// let rng1 = base1.clone();
112    /// let rng2 = base2.clone();
113    ///
114    /// assert_eq!(rng1.u64(..), rng2.u64(..), "the cloned generators are identical");
115    /// ```
116    fn clone(&self) -> Rng {
117        Rng::with_seed(self.gen_u64())
118    }
119}
120
121impl Rng {
122    /// Generates a random `u32`.
123    #[inline]
124    fn gen_u32(&self) -> u32 {
125        // Adapted from: https://en.wikipedia.org/wiki/Permuted_congruential_generator
126        let s = self.0.get();
127        self.0.set(
128            s.wrapping_mul(6364136223846793005)
129                .wrapping_add(1442695040888963407),
130        );
131        (((s ^ (s >> 18)) >> 27) as u32).rotate_right((s >> 59) as u32)
132    }
133
134    /// Generates a random `u64`.
135    #[inline]
136    fn gen_u64(&self) -> u64 {
137        ((self.gen_u32() as u64) << 32) | (self.gen_u32() as u64)
138    }
139
140    /// Generates a random `u128`.
141    #[inline]
142    fn gen_u128(&self) -> u128 {
143        ((self.gen_u64() as u128) << 64) | (self.gen_u64() as u128)
144    }
145
146    /// Generates a random `u32` in `0..n`.
147    #[inline]
148    fn gen_mod_u32(&self, n: u32) -> u32 {
149        // Adapted from: https://lemire.me/blog/2016/06/30/fast-random-shuffling/
150        let mut r = self.gen_u32();
151        let mut hi = mul_high_u32(r, n);
152        let mut lo = r.wrapping_mul(n);
153        if lo < n {
154            let t = n.wrapping_neg() % n;
155            while lo < t {
156                r = self.gen_u32();
157                hi = mul_high_u32(r, n);
158                lo = r.wrapping_mul(n);
159            }
160        }
161        hi
162    }
163
164    /// Generates a random `u64` in `0..n`.
165    #[inline]
166    fn gen_mod_u64(&self, n: u64) -> u64 {
167        // Adapted from: https://lemire.me/blog/2016/06/30/fast-random-shuffling/
168        let mut r = self.gen_u64();
169        let mut hi = mul_high_u64(r, n);
170        let mut lo = r.wrapping_mul(n);
171        if lo < n {
172            let t = n.wrapping_neg() % n;
173            while lo < t {
174                r = self.gen_u64();
175                hi = mul_high_u64(r, n);
176                lo = r.wrapping_mul(n);
177            }
178        }
179        hi
180    }
181
182    /// Generates a random `u128` in `0..n`.
183    #[inline]
184    fn gen_mod_u128(&self, n: u128) -> u128 {
185        // Adapted from: https://lemire.me/blog/2016/06/30/fast-random-shuffling/
186        let mut r = self.gen_u128();
187        let mut hi = mul_high_u128(r, n);
188        let mut lo = r.wrapping_mul(n);
189        if lo < n {
190            let t = n.wrapping_neg() % n;
191            while lo < t {
192                r = self.gen_u128();
193                hi = mul_high_u128(r, n);
194                lo = r.wrapping_mul(n);
195            }
196        }
197        hi
198    }
199}
200
201thread_local! {
202    static RNG: Rng = Rng(Cell::new({
203        let mut hasher = DefaultHasher::new();
204        Instant::now().hash(&mut hasher);
205        thread::current().id().hash(&mut hasher);
206        let hash = hasher.finish();
207        (hash << 1) | 1
208    }));
209}
210
211/// Computes `(a * b) >> 32`.
212#[inline]
213fn mul_high_u32(a: u32, b: u32) -> u32 {
214    (((a as u64) * (b as u64)) >> 32) as u32
215}
216
217/// Computes `(a * b) >> 64`.
218#[inline]
219fn mul_high_u64(a: u64, b: u64) -> u64 {
220    (((a as u128) * (b as u128)) >> 64) as u64
221}
222
223/// Computes `(a * b) >> 128`.
224#[inline]
225fn mul_high_u128(a: u128, b: u128) -> u128 {
226    // Adapted from: https://stackoverflow.com/a/28904636
227    let a_lo = a as u64 as u128;
228    let a_hi = (a >> 64) as u64 as u128;
229    let b_lo = b as u64 as u128;
230    let b_hi = (b >> 64) as u64 as u128;
231    let carry = (a_lo * b_lo) >> 64;
232    let carry = ((a_hi * b_lo) as u64 as u128 + (a_lo * b_hi) as u64 as u128 + carry) >> 64;
233    a_hi * b_hi + ((a_hi * b_lo) >> 64) + ((a_lo * b_hi) >> 64) + carry
234}
235
236macro_rules! rng_integer {
237    ($t:tt, $gen:tt, $mod:tt, $doc:tt) => {
238        #[doc = $doc]
239        ///
240        /// Panics if the range is empty.
241        #[inline]
242        pub fn $t(&self, range: impl RangeBounds<$t>) -> $t {
243            let panic_empty_range = || {
244                panic!(
245                    "empty range: {:?}..{:?}",
246                    range.start_bound(),
247                    range.end_bound()
248                )
249            };
250
251            let low = match range.start_bound() {
252                Bound::Unbounded => std::$t::MIN,
253                Bound::Included(&x) => x,
254                Bound::Excluded(&x) => x.checked_add(1).unwrap_or_else(panic_empty_range),
255            };
256
257            let high = match range.end_bound() {
258                Bound::Unbounded => std::$t::MAX,
259                Bound::Included(&x) => x,
260                Bound::Excluded(&x) => x.checked_sub(1).unwrap_or_else(panic_empty_range),
261            };
262
263            if low > high {
264                panic_empty_range();
265            }
266
267            if low == std::$t::MIN && high == std::$t::MAX {
268                self.$gen() as $t
269            } else {
270                let len = high.wrapping_sub(low).wrapping_add(1);
271                low.wrapping_add(self.$mod(len as _) as $t)
272            }
273        }
274    };
275}
276
277impl Rng {
278    /// Creates a new random number generator.
279    #[inline]
280    pub fn new() -> Rng {
281        Rng::with_seed(
282            RNG.try_with(|rng| rng.u64(..))
283                .unwrap_or(0x4d595df4d0f33173),
284        )
285    }
286
287    /// Creates a new random number generator with the initial seed.
288    #[inline]
289    pub fn with_seed(seed: u64) -> Self {
290        let rng = Rng(Cell::new(0));
291
292        rng.seed(seed);
293        rng
294    }
295
296    /// Generates a random `char` in ranges a-z and A-Z.
297    #[inline]
298    pub fn alphabetic(&self) -> char {
299        const CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
300        let len = CHARS.len() as u8;
301        let i = self.u8(..len);
302        CHARS[i as usize] as char
303    }
304
305    /// Generates a random `char` in ranges a-z, A-Z and 0-9.
306    #[inline]
307    pub fn alphanumeric(&self) -> char {
308        const CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
309        let len = CHARS.len() as u8;
310        let i = self.u8(..len);
311        CHARS[i as usize] as char
312    }
313
314    /// Generates a random `bool`.
315    #[inline]
316    pub fn bool(&self) -> bool {
317        self.u8(..) % 2 == 0
318    }
319
320    /// Generates a random digit in the given `base`.
321    ///
322    /// Digits are represented by `char`s in ranges 0-9 and a-z.
323    ///
324    /// Panics if the base is zero or greater than 36.
325    #[inline]
326    pub fn digit(&self, base: u32) -> char {
327        if base == 0 {
328            panic!("base cannot be zero");
329        }
330        if base > 36 {
331            panic!("base cannot be larger than 36");
332        }
333        let num = self.u8(..base as u8);
334        if num < 10 {
335            (b'0' + num) as char
336        } else {
337            (b'a' + num - 10) as char
338        }
339    }
340
341    /// Generates a random `f32` in range `0..1`.
342    pub fn f32(&self) -> f32 {
343        let b = 32;
344        let f = std::f32::MANTISSA_DIGITS - 1;
345        f32::from_bits((1 << (b - 2)) - (1 << f) + (self.u32(..) >> (b - f))) - 1.0
346    }
347
348    /// Generates a random `f64` in range `0..1`.
349    pub fn f64(&self) -> f64 {
350        let b = 64;
351        let f = std::f64::MANTISSA_DIGITS - 1;
352        f64::from_bits((1 << (b - 2)) - (1 << f) + (self.u64(..) >> (b - f))) - 1.0
353    }
354
355    rng_integer!(
356        i8,
357        gen_u32,
358        gen_mod_u32,
359        "Generates a random `i8` in the given range."
360    );
361
362    rng_integer!(
363        i16,
364        gen_u32,
365        gen_mod_u32,
366        "Generates a random `i16` in the given range."
367    );
368
369    rng_integer!(
370        i32,
371        gen_u32,
372        gen_mod_u32,
373        "Generates a random `i32` in the given range."
374    );
375
376    rng_integer!(
377        i64,
378        gen_u64,
379        gen_mod_u64,
380        "Generates a random `i64` in the given range."
381    );
382
383    rng_integer!(
384        i128,
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        gen_u32,
394        gen_mod_u32,
395        "Generates a random `isize` in the given range."
396    );
397    #[cfg(target_pointer_width = "32")]
398    rng_integer!(
399        isize,
400        gen_u32,
401        gen_mod_u32,
402        "Generates a random `isize` in the given range."
403    );
404    #[cfg(target_pointer_width = "64")]
405    rng_integer!(
406        isize,
407        gen_u64,
408        gen_mod_u64,
409        "Generates a random `isize` in the given range."
410    );
411
412    /// Generates a random `char` in range a-z.
413    #[inline]
414    pub fn lowercase(&self) -> char {
415        const CHARS: &[u8] = b"abcdefghijklmnopqrstuvwxyz";
416        let len = CHARS.len() as u8;
417        let i = self.u8(..len);
418        CHARS[i as usize] as char
419    }
420
421    /// Initializes this generator with the given seed.
422    #[inline]
423    pub fn seed(&self, seed: u64) {
424        self.0.set(seed.wrapping_add(1442695040888963407));
425        self.gen_u32();
426    }
427
428    /// Shuffles a slice randomly.
429    #[inline]
430    pub fn shuffle<T>(&self, slice: &mut [T]) {
431        for i in 1..slice.len() {
432            slice.swap(i, self.usize(..=i));
433        }
434    }
435
436    rng_integer!(
437        u8,
438        gen_u32,
439        gen_mod_u32,
440        "Generates a random `u8` in the given range."
441    );
442
443    rng_integer!(
444        u16,
445        gen_u32,
446        gen_mod_u32,
447        "Generates a random `u16` in the given range."
448    );
449
450    rng_integer!(
451        u32,
452        gen_u32,
453        gen_mod_u32,
454        "Generates a random `u32` in the given range."
455    );
456
457    rng_integer!(
458        u64,
459        gen_u64,
460        gen_mod_u64,
461        "Generates a random `u64` in the given range."
462    );
463
464    rng_integer!(
465        u128,
466        gen_u128,
467        gen_mod_u128,
468        "Generates a random `u128` in the given range."
469    );
470
471    #[cfg(target_pointer_width = "16")]
472    rng_integer!(
473        usize,
474        gen_u32,
475        gen_mod_u32,
476        "Generates a random `usize` in the given range."
477    );
478    #[cfg(target_pointer_width = "32")]
479    rng_integer!(
480        usize,
481        gen_u32,
482        gen_mod_u32,
483        "Generates a random `usize` in the given range."
484    );
485    #[cfg(target_pointer_width = "64")]
486    rng_integer!(
487        usize,
488        gen_u64,
489        gen_mod_u64,
490        "Generates a random `usize` in the given range."
491    );
492    #[cfg(target_pointer_width = "128")]
493    rng_integer!(
494        usize,
495        gen_u128,
496        gen_mod_u128,
497        "Generates a random `usize` in the given range."
498    );
499
500    /// Generates a random `char` in range A-Z.
501    #[inline]
502    pub fn uppercase(&self) -> char {
503        const CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZ";
504        let len = CHARS.len() as u8;
505        let i = self.u8(..len);
506        CHARS[i as usize] as char
507    }
508}
509
510/// Initializes the thread-local generator with the given seed.
511#[inline]
512pub fn seed(seed: u64) {
513    RNG.with(|rng| rng.seed(seed))
514}
515
516/// Generates a random `bool`.
517#[inline]
518pub fn bool() -> bool {
519    RNG.with(|rng| rng.bool())
520}
521
522/// Generates a random `char` in ranges a-z and A-Z.
523#[inline]
524pub fn alphabetic() -> char {
525    RNG.with(|rng| rng.alphabetic())
526}
527
528/// Generates a random `char` in ranges a-z, A-Z and 0-9.
529#[inline]
530pub fn alphanumeric() -> char {
531    RNG.with(|rng| rng.alphanumeric())
532}
533
534/// Generates a random `char` in range a-z.
535#[inline]
536pub fn lowercase() -> char {
537    RNG.with(|rng| rng.lowercase())
538}
539
540/// Generates a random `char` in range A-Z.
541#[inline]
542pub fn uppercase() -> char {
543    RNG.with(|rng| rng.uppercase())
544}
545
546/// Generates a random digit in the given `base`.
547///
548/// Digits are represented by `char`s in ranges 0-9 and a-z.
549///
550/// Panics if the base is zero or greater than 36.
551#[inline]
552pub fn digit(base: u32) -> char {
553    RNG.with(|rng| rng.digit(base))
554}
555
556/// Shuffles a slice randomly.
557#[inline]
558pub fn shuffle<T>(slice: &mut [T]) {
559    RNG.with(|rng| rng.shuffle(slice))
560}
561
562macro_rules! integer {
563    ($t:tt, $doc:tt) => {
564        #[doc = $doc]
565        ///
566        /// Panics if the range is empty.
567        #[inline]
568        pub fn $t(range: impl RangeBounds<$t>) -> $t {
569            RNG.with(|rng| rng.$t(range))
570        }
571    };
572}
573
574integer!(u8, "Generates a random `u8` in the given range.");
575integer!(i8, "Generates a random `i8` in the given range.");
576integer!(u16, "Generates a random `u16` in the given range.");
577integer!(i16, "Generates a random `i16` in the given range.");
578integer!(u32, "Generates a random `u32` in the given range.");
579integer!(i32, "Generates a random `i32` in the given range.");
580integer!(u64, "Generates a random `u64` in the given range.");
581integer!(i64, "Generates a random `i64` in the given range.");
582integer!(u128, "Generates a random `u128` in the given range.");
583integer!(i128, "Generates a random `i128` in the given range.");
584integer!(usize, "Generates a random `usize` in the given range.");
585integer!(isize, "Generates a random `isize` in the given range.");
586
587/// Generates a random `f32` in range `0..1`.
588pub fn f32() -> f32 {
589    RNG.with(|rng| rng.f32())
590}
591
592/// Generates a random `f64` in range `0..1`.
593pub fn f64() -> f64 {
594    RNG.with(|rng| rng.f64())
595}
fastrand/lib.rs

fastrand/
lib.rs
