Debian Codegraph @

.cargo/vendor/fastrand/src/lib.rs

raw
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 #![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")]
113 extern crate alloc;
114 #[cfg(feature = "std")]
115 extern crate std;
116
117 use core::convert::{TryFrom, TryInto};
118 use core::ops::{Bound, RangeBounds};
119
120 #[cfg(feature = "alloc")]
121 use alloc::vec::Vec;
122
123 #[cfg(feature = "std")]
124 #[cfg_attr(docsrs, doc(cfg(feature = "std")))]
125 mod global_rng;
126
127 #[cfg(feature = "std")]
128 pub use global_rng::*;
129
130 /// A random number generator.
131 #[derive(Debug, PartialEq, Eq)]
132 pub struct Rng(u64);
133
134 impl 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
141 impl 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]
225 fn 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]
231 fn 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]
237 fn 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
248 macro_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
289 impl 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 iterator into a vector.
382 ///
383 /// The length of the returned vector equals `amount` unless the iterator
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 iterator.
388 #[cfg(feature = "alloc")]
389 #[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
390 pub fn choose_multiple<T: Iterator>(&mut self, mut source: T, amount: usize) -> Vec<T::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
394 reservoir.extend(source.by_ref().take(amount));
395
396 // Continue unless the iterator was exhausted
397 //
398 // note: this prevents iterators that "restart" from causing problems.
399 // If the iterator stops once, then so do we.
400 if reservoir.len() == amount {
401 for (i, elem) in source.enumerate() {
402 let end = i + 1 + amount;
403 let k = self.usize(0..end);
404 if let Some(slot) = reservoir.get_mut(k) {
405 *slot = elem;
406 }
407 }
408 } else {
409 // If less than one third of the `Vec` was used, reallocate
410 // so that the unused space is not wasted. There is a corner
411 // case where `amount` was much less than `self.len()`.
412 if reservoir.capacity() > 3 * reservoir.len() {
413 reservoir.shrink_to_fit();
414 }
415 }
416 reservoir
417 }
418
419 rng_integer!(
420 i8,
421 u8,
422 gen_u32,
423 gen_mod_u32,
424 "Generates a random `i8` in the given range."
425 );
426
427 rng_integer!(
428 i16,
429 u16,
430 gen_u32,
431 gen_mod_u32,
432 "Generates a random `i16` in the given range."
433 );
434
435 rng_integer!(
436 i32,
437 u32,
438 gen_u32,
439 gen_mod_u32,
440 "Generates a random `i32` in the given range."
441 );
442
443 rng_integer!(
444 i64,
445 u64,
446 gen_u64,
447 gen_mod_u64,
448 "Generates a random `i64` in the given range."
449 );
450
451 rng_integer!(
452 i128,
453 u128,
454 gen_u128,
455 gen_mod_u128,
456 "Generates a random `i128` in the given range."
457 );
458
459 #[cfg(target_pointer_width = "16")]
460 rng_integer!(
461 isize,
462 usize,
463 gen_u32,
464 gen_mod_u32,
465 "Generates a random `isize` in the given range."
466 );
467 #[cfg(target_pointer_width = "32")]
468 rng_integer!(
469 isize,
470 usize,
471 gen_u32,
472 gen_mod_u32,
473 "Generates a random `isize` in the given range."
474 );
475 #[cfg(target_pointer_width = "64")]
476 rng_integer!(
477 isize,
478 usize,
479 gen_u64,
480 gen_mod_u64,
481 "Generates a random `isize` in the given range."
482 );
483
484 /// Generates a random `char` in range a-z.
485 #[inline]
486 pub fn lowercase(&mut self) -> char {
487 const CHARS: &[u8] = b"abcdefghijklmnopqrstuvwxyz";
488 *self.choice(CHARS).unwrap() as char
489 }
490
491 /// Initializes this generator with the given seed.
492 #[inline]
493 pub fn seed(&mut self, seed: u64) {
494 self.0 = seed;
495 }
496
497 /// Gives back **current** seed that is being held by this generator.
498 #[inline]
499 pub fn get_seed(&self) -> u64 {
500 self.0
501 }
502
503 /// Choose an item from an iterator at random.
504 ///
505 /// This function may have an unexpected result if the `len()` property of the
506 /// iterator does not match the actual number of items in the iterator. If
507 /// the iterator is empty, this returns `None`.
508 #[inline]
509 pub fn choice<I>(&mut self, iter: I) -> Option<I::Item>
510 where
511 I: IntoIterator,
512 I::IntoIter: ExactSizeIterator,
513 {
514 let mut iter = iter.into_iter();
515
516 // Get the item at a random index.
517 let len = iter.len();
518 if len == 0 {
519 return None;
520 }
521 let index = self.usize(0..len);
522
523 iter.nth(index)
524 }
525
526 /// Shuffles a slice randomly.
527 #[inline]
528 pub fn shuffle<T>(&mut self, slice: &mut [T]) {
529 for i in 1..slice.len() {
530 slice.swap(i, self.usize(..=i));
531 }
532 }
533
534 /// Fill a byte slice with random data.
535 #[inline]
536 pub fn fill(&mut self, slice: &mut [u8]) {
537 // We fill the slice by chunks of 8 bytes, or one block of
538 // WyRand output per new state.
539 let mut chunks = slice.chunks_exact_mut(core::mem::size_of::<u64>());
540 for chunk in chunks.by_ref() {
541 let n = self.gen_u64().to_ne_bytes();
542 // Safe because the chunks are always 8 bytes exactly.
543 chunk.copy_from_slice(&n);
544 }
545
546 let remainder = chunks.into_remainder();
547
548 // Any remainder will always be less than 8 bytes.
549 if !remainder.is_empty() {
550 // Generate one last block of 8 bytes of entropy
551 let n = self.gen_u64().to_ne_bytes();
552
553 // Use the remaining length to copy from block
554 remainder.copy_from_slice(&n[..remainder.len()]);
555 }
556 }
557
558 rng_integer!(
559 u8,
560 u8,
561 gen_u32,
562 gen_mod_u32,
563 "Generates a random `u8` in the given range."
564 );
565
566 rng_integer!(
567 u16,
568 u16,
569 gen_u32,
570 gen_mod_u32,
571 "Generates a random `u16` in the given range."
572 );
573
574 rng_integer!(
575 u32,
576 u32,
577 gen_u32,
578 gen_mod_u32,
579 "Generates a random `u32` in the given range."
580 );
581
582 rng_integer!(
583 u64,
584 u64,
585 gen_u64,
586 gen_mod_u64,
587 "Generates a random `u64` in the given range."
588 );
589
590 rng_integer!(
591 u128,
592 u128,
593 gen_u128,
594 gen_mod_u128,
595 "Generates a random `u128` in the given range."
596 );
597
598 #[cfg(target_pointer_width = "16")]
599 rng_integer!(
600 usize,
601 usize,
602 gen_u32,
603 gen_mod_u32,
604 "Generates a random `usize` in the given range."
605 );
606 #[cfg(target_pointer_width = "32")]
607 rng_integer!(
608 usize,
609 usize,
610 gen_u32,
611 gen_mod_u32,
612 "Generates a random `usize` in the given range."
613 );
614 #[cfg(target_pointer_width = "64")]
615 rng_integer!(
616 usize,
617 usize,
618 gen_u64,
619 gen_mod_u64,
620 "Generates a random `usize` in the given range."
621 );
622 #[cfg(target_pointer_width = "128")]
623 rng_integer!(
624 usize,
625 usize,
626 gen_u128,
627 gen_mod_u128,
628 "Generates a random `usize` in the given range."
629 );
630
631 /// Generates a random `char` in range A-Z.
632 #[inline]
633 pub fn uppercase(&mut self) -> char {
634 const CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZ";
635 *self.choice(CHARS).unwrap() as char
636 }
637
638 /// Generates a random `char` in the given range.
639 ///
640 /// Panics if the range is empty.
641 #[inline]
642 pub fn char(&mut self, range: impl RangeBounds<char>) -> char {
643 let panic_empty_range = || {
644 panic!(
645 "empty range: {:?}..{:?}",
646 range.start_bound(),
647 range.end_bound()
648 )
649 };
650
651 let surrogate_start = 0xd800u32;
652 let surrogate_len = 0x800u32;
653
654 let low = match range.start_bound() {
655 Bound::Unbounded => 0u8 as char,
656 Bound::Included(&x) => x,
657 Bound::Excluded(&x) => {
658 let scalar = if x as u32 == surrogate_start - 1 {
659 surrogate_start + surrogate_len
660 } else {
661 x as u32 + 1
662 };
663 char::try_from(scalar).unwrap_or_else(|_| panic_empty_range())
664 }
665 };
666
667 let high = match range.end_bound() {
668 Bound::Unbounded => core::char::MAX,
669 Bound::Included(&x) => x,
670 Bound::Excluded(&x) => {
671 let scalar = if x as u32 == surrogate_start + surrogate_len {
672 surrogate_start - 1
673 } else {
674 (x as u32).wrapping_sub(1)
675 };
676 char::try_from(scalar).unwrap_or_else(|_| panic_empty_range())
677 }
678 };
679
680 if low > high {
681 panic_empty_range();
682 }
683
684 let gap = if (low as u32) < surrogate_start && (high as u32) >= surrogate_start {
685 surrogate_len
686 } else {
687 0
688 };
689 let range = high as u32 - low as u32 - gap;
690 let mut val = self.u32(0..=range) + low as u32;
691 if val >= surrogate_start {
692 val += gap;
693 }
694 val.try_into().unwrap()
695 }
696 }