diff options
Diffstat (limited to 'vendor/fastrand/src/lib.rs')
| -rw-r--r-- | vendor/fastrand/src/lib.rs | 692 |
1 files changed, 0 insertions, 692 deletions
diff --git a/vendor/fastrand/src/lib.rs b/vendor/fastrand/src/lib.rs deleted file mode 100644 index 24de8dd..0000000 --- a/vendor/fastrand/src/lib.rs +++ /dev/null @@ -1,692 +0,0 @@ -//! A simple and fast random number generator. -//! -//! The implementation uses [Wyrand](https://github.com/wangyi-fudan/wyhash), a simple and fast -//! generator but **not** cryptographically secure. -//! -//! # Examples -//! -//! Flip a coin: -//! -//! ``` -//! if fastrand::bool() { -//! println!("heads"); -//! } else { -//! println!("tails"); -//! } -//! ``` -//! -//! Generate a random `i32`: -//! -//! ``` -//! let num = fastrand::i32(..); -//! ``` -//! -//! Choose a random element in an array: -//! -//! ``` -//! let v = vec![1, 2, 3, 4, 5]; -//! let i = fastrand::usize(..v.len()); -//! let elem = v[i]; -//! ``` -//! -//! Sample values from an array with `O(n)` complexity (`n` is the length of array): -//! -//! ``` -//! fastrand::choose_multiple(vec![1, 4, 5].iter(), 2); -//! fastrand::choose_multiple(0..20, 12); -//! ``` -//! -//! -//! Shuffle an array: -//! -//! ``` -//! let mut v = vec![1, 2, 3, 4, 5]; -//! fastrand::shuffle(&mut v); -//! ``` -//! -//! Generate a random [`Vec`] or [`String`]: -//! -//! ``` -//! use std::iter::repeat_with; -//! -//! let v: Vec<i32> = repeat_with(|| fastrand::i32(..)).take(10).collect(); -//! let s: String = repeat_with(fastrand::alphanumeric).take(10).collect(); -//! ``` -//! -//! To get reproducible results on every run, initialize the generator with a seed: -//! -//! ``` -//! // Pick an arbitrary number as seed. -//! fastrand::seed(7); -//! -//! // Now this prints the same number on every run: -//! println!("{}", fastrand::u32(..)); -//! ``` -//! -//! To be more efficient, create a new [`Rng`] instance instead of using the thread-local -//! generator: -//! -//! ``` -//! use std::iter::repeat_with; -//! -//! let mut rng = fastrand::Rng::new(); -//! let mut bytes: Vec<u8> = repeat_with(|| rng.u8(..)).take(10_000).collect(); -//! ``` -//! -//! This crate aims to expose a core set of useful randomness primitives. For more niche algorithms, -//! consider using the [`fastrand-contrib`] crate alongside this one. -//! -//! # Features -//! -//! - `std` (enabled by default): Enables the `std` library. This is required for the global -//! generator and global entropy. Without this feature, [`Rng`] can only be instantiated using -//! the [`with_seed`](Rng::with_seed) method. -//! - `js`: Assumes that WebAssembly targets are being run in a JavaScript environment. See the -//! [WebAssembly Notes](#webassembly-notes) section for more information. -//! -//! # WebAssembly Notes -//! -//! For non-WASI WASM targets, there is additional sublety to consider when utilizing the global RNG. -//! By default, `std` targets will use entropy sources in the standard library to seed the global RNG. -//! However, these sources are not available by default on WASM targets outside of WASI. -//! -//! If the `js` feature is enabled, this crate will assume that it is running in a JavaScript -//! environment. At this point, the [`getrandom`] crate will be used in order to access the available -//! entropy sources and seed the global RNG. If the `js` feature is not enabled, the global RNG will -//! use a predefined seed. -//! -//! [`fastrand-contrib`]: https://crates.io/crates/fastrand-contrib -//! [`getrandom`]: https://crates.io/crates/getrandom - -#![cfg_attr(not(feature = "std"), no_std)] -#![cfg_attr(docsrs, feature(doc_cfg))] -#![forbid(unsafe_code)] -#![warn(missing_docs, missing_debug_implementations, rust_2018_idioms)] -#![doc( - html_favicon_url = "https://raw.githubusercontent.com/smol-rs/smol/master/assets/images/logo_fullsize_transparent.png" -)] -#![doc( - html_logo_url = "https://raw.githubusercontent.com/smol-rs/smol/master/assets/images/logo_fullsize_transparent.png" -)] - -#[cfg(feature = "alloc")] -extern crate alloc; - -use core::convert::{TryFrom, TryInto}; -use core::ops::{Bound, RangeBounds}; - -#[cfg(feature = "alloc")] -use alloc::vec::Vec; - -#[cfg(feature = "std")] -#[cfg_attr(docsrs, doc(cfg(feature = "std")))] -mod global_rng; - -#[cfg(feature = "std")] -pub use global_rng::*; - -/// A random number generator. -#[derive(Debug, PartialEq, Eq)] -pub struct Rng(u64); - -impl Clone for Rng { - /// Clones the generator by creating a new generator with the same seed. - fn clone(&self) -> Rng { - Rng::with_seed(self.0) - } -} - -impl Rng { - /// Generates a random `u32`. - #[inline] - fn gen_u32(&mut self) -> u32 { - self.gen_u64() as u32 - } - - /// Generates a random `u64`. - #[inline] - fn gen_u64(&mut self) -> u64 { - let s = self.0.wrapping_add(0xA0761D6478BD642F); - self.0 = s; - let t = u128::from(s) * u128::from(s ^ 0xE7037ED1A0B428DB); - (t as u64) ^ (t >> 64) as u64 - } - - /// Generates a random `u128`. - #[inline] - fn gen_u128(&mut self) -> u128 { - (u128::from(self.gen_u64()) << 64) | u128::from(self.gen_u64()) - } - - /// Generates a random `u32` in `0..n`. - #[inline] - fn gen_mod_u32(&mut self, n: u32) -> u32 { - // Adapted from: https://lemire.me/blog/2016/06/30/fast-random-shuffling/ - let mut r = self.gen_u32(); - let mut hi = mul_high_u32(r, n); - let mut lo = r.wrapping_mul(n); - if lo < n { - let t = n.wrapping_neg() % n; - while lo < t { - r = self.gen_u32(); - hi = mul_high_u32(r, n); - lo = r.wrapping_mul(n); - } - } - hi - } - - /// Generates a random `u64` in `0..n`. - #[inline] - fn gen_mod_u64(&mut self, n: u64) -> u64 { - // Adapted from: https://lemire.me/blog/2016/06/30/fast-random-shuffling/ - let mut r = self.gen_u64(); - let mut hi = mul_high_u64(r, n); - let mut lo = r.wrapping_mul(n); - if lo < n { - let t = n.wrapping_neg() % n; - while lo < t { - r = self.gen_u64(); - hi = mul_high_u64(r, n); - lo = r.wrapping_mul(n); - } - } - hi - } - - /// Generates a random `u128` in `0..n`. - #[inline] - fn gen_mod_u128(&mut self, n: u128) -> u128 { - // Adapted from: https://lemire.me/blog/2016/06/30/fast-random-shuffling/ - let mut r = self.gen_u128(); - let mut hi = mul_high_u128(r, n); - let mut lo = r.wrapping_mul(n); - if lo < n { - let t = n.wrapping_neg() % n; - while lo < t { - r = self.gen_u128(); - hi = mul_high_u128(r, n); - lo = r.wrapping_mul(n); - } - } - hi - } -} - -/// Computes `(a * b) >> 32`. -#[inline] -fn mul_high_u32(a: u32, b: u32) -> u32 { - (((a as u64) * (b as u64)) >> 32) as u32 -} - -/// Computes `(a * b) >> 64`. -#[inline] -fn mul_high_u64(a: u64, b: u64) -> u64 { - (((a as u128) * (b as u128)) >> 64) as u64 -} - -/// Computes `(a * b) >> 128`. -#[inline] -fn mul_high_u128(a: u128, b: u128) -> u128 { - // Adapted from: https://stackoverflow.com/a/28904636 - let a_lo = a as u64 as u128; - let a_hi = (a >> 64) as u64 as u128; - let b_lo = b as u64 as u128; - let b_hi = (b >> 64) as u64 as u128; - let carry = (a_lo * b_lo) >> 64; - let carry = ((a_hi * b_lo) as u64 as u128 + (a_lo * b_hi) as u64 as u128 + carry) >> 64; - a_hi * b_hi + ((a_hi * b_lo) >> 64) + ((a_lo * b_hi) >> 64) + carry -} - -macro_rules! rng_integer { - ($t:tt, $unsigned_t:tt, $gen:tt, $mod:tt, $doc:tt) => { - #[doc = $doc] - /// - /// Panics if the range is empty. - #[inline] - pub fn $t(&mut self, range: impl RangeBounds<$t>) -> $t { - let panic_empty_range = || { - panic!( - "empty range: {:?}..{:?}", - range.start_bound(), - range.end_bound() - ) - }; - - let low = match range.start_bound() { - Bound::Unbounded => core::$t::MIN, - Bound::Included(&x) => x, - Bound::Excluded(&x) => x.checked_add(1).unwrap_or_else(panic_empty_range), - }; - - let high = match range.end_bound() { - Bound::Unbounded => core::$t::MAX, - Bound::Included(&x) => x, - Bound::Excluded(&x) => x.checked_sub(1).unwrap_or_else(panic_empty_range), - }; - - if low > high { - panic_empty_range(); - } - - if low == core::$t::MIN && high == core::$t::MAX { - self.$gen() as $t - } else { - let len = high.wrapping_sub(low).wrapping_add(1); - low.wrapping_add(self.$mod(len as $unsigned_t as _) as $t) - } - } - }; -} - -impl Rng { - /// Creates a new random number generator with the initial seed. - #[inline] - #[must_use = "this creates a new instance of `Rng`; if you want to initialize the thread-local generator, use `fastrand::seed()` instead"] - pub fn with_seed(seed: u64) -> Self { - let mut rng = Rng(0); - - rng.seed(seed); - rng - } - - /// Clones the generator by deterministically deriving a new generator based on the initial - /// seed. - /// - /// This function can be used to create a new generator that is a "spinoff" of the old - /// generator. The new generator will not produce the same sequence of values as the - /// old generator. - /// - /// # Example - /// - /// ``` - /// // Seed two generators equally, and clone both of them. - /// let mut base1 = fastrand::Rng::with_seed(0x4d595df4d0f33173); - /// base1.bool(); // Use the generator once. - /// - /// let mut base2 = fastrand::Rng::with_seed(0x4d595df4d0f33173); - /// base2.bool(); // Use the generator once. - /// - /// let mut rng1 = base1.fork(); - /// let mut rng2 = base2.fork(); - /// - /// println!("rng1 returns {}", rng1.u32(..)); - /// println!("rng2 returns {}", rng2.u32(..)); - /// ``` - #[inline] - #[must_use = "this creates a new instance of `Rng`"] - pub fn fork(&mut self) -> Self { - Rng::with_seed(self.gen_u64()) - } - - /// Generates a random `char` in ranges a-z and A-Z. - #[inline] - pub fn alphabetic(&mut self) -> char { - const CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; - *self.choice(CHARS).unwrap() as char - } - - /// Generates a random `char` in ranges a-z, A-Z and 0-9. - #[inline] - pub fn alphanumeric(&mut self) -> char { - const CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"; - *self.choice(CHARS).unwrap() as char - } - - /// Generates a random `bool`. - #[inline] - pub fn bool(&mut self) -> bool { - self.u8(..) % 2 == 0 - } - - /// Generates a random digit in the given `base`. - /// - /// Digits are represented by `char`s in ranges 0-9 and a-z. - /// - /// Panics if the base is zero or greater than 36. - #[inline] - pub fn digit(&mut self, base: u32) -> char { - if base == 0 { - panic!("base cannot be zero"); - } - if base > 36 { - panic!("base cannot be larger than 36"); - } - let num = self.u8(..base as u8); - if num < 10 { - (b'0' + num) as char - } else { - (b'a' + num - 10) as char - } - } - - /// Generates a random `f32` in range `0..1`. - pub fn f32(&mut self) -> f32 { - let b = 32; - let f = core::f32::MANTISSA_DIGITS - 1; - f32::from_bits((1 << (b - 2)) - (1 << f) + (self.u32(..) >> (b - f))) - 1.0 - } - - /// Generates a random `f64` in range `0..1`. - pub fn f64(&mut self) -> f64 { - let b = 64; - let f = core::f64::MANTISSA_DIGITS - 1; - f64::from_bits((1 << (b - 2)) - (1 << f) + (self.u64(..) >> (b - f))) - 1.0 - } - - /// Collects `amount` values at random from the iterator into a vector. - /// - /// The length of the returned vector equals `amount` unless the iterator - /// contains insufficient elements, in which case it equals the number of - /// elements available. - /// - /// Complexity is `O(n)` where `n` is the length of the iterator. - #[cfg(feature = "alloc")] - #[cfg_attr(docsrs, doc(cfg(feature = "alloc")))] - pub fn choose_multiple<T: Iterator>(&mut self, mut source: T, amount: usize) -> Vec<T::Item> { - // Adapted from: https://docs.rs/rand/latest/rand/seq/trait.IteratorRandom.html#method.choose_multiple - let mut reservoir = Vec::with_capacity(amount); - - reservoir.extend(source.by_ref().take(amount)); - - // Continue unless the iterator was exhausted - // - // note: this prevents iterators that "restart" from causing problems. - // If the iterator stops once, then so do we. - if reservoir.len() == amount { - for (i, elem) in source.enumerate() { - let end = i + 1 + amount; - let k = self.usize(0..end); - if let Some(slot) = reservoir.get_mut(k) { - *slot = elem; - } - } - } else { - // If less than one third of the `Vec` was used, reallocate - // so that the unused space is not wasted. There is a corner - // case where `amount` was much less than `self.len()`. - if reservoir.capacity() > 3 * reservoir.len() { - reservoir.shrink_to_fit(); - } - } - reservoir - } - - rng_integer!( - i8, - u8, - gen_u32, - gen_mod_u32, - "Generates a random `i8` in the given range." - ); - - rng_integer!( - i16, - u16, - gen_u32, - gen_mod_u32, - "Generates a random `i16` in the given range." - ); - - rng_integer!( - i32, - u32, - gen_u32, - gen_mod_u32, - "Generates a random `i32` in the given range." - ); - - rng_integer!( - i64, - u64, - gen_u64, - gen_mod_u64, - "Generates a random `i64` in the given range." - ); - - rng_integer!( - i128, - u128, - gen_u128, - gen_mod_u128, - "Generates a random `i128` in the given range." - ); - - #[cfg(target_pointer_width = "16")] - rng_integer!( - isize, - usize, - gen_u32, - gen_mod_u32, - "Generates a random `isize` in the given range." - ); - #[cfg(target_pointer_width = "32")] - rng_integer!( - isize, - usize, - gen_u32, - gen_mod_u32, - "Generates a random `isize` in the given range." - ); - #[cfg(target_pointer_width = "64")] - rng_integer!( - isize, - usize, - gen_u64, - gen_mod_u64, - "Generates a random `isize` in the given range." - ); - - /// Generates a random `char` in range a-z. - #[inline] - pub fn lowercase(&mut self) -> char { - const CHARS: &[u8] = b"abcdefghijklmnopqrstuvwxyz"; - *self.choice(CHARS).unwrap() as char - } - - /// Initializes this generator with the given seed. - #[inline] - pub fn seed(&mut self, seed: u64) { - self.0 = seed; - } - - /// Gives back **current** seed that is being held by this generator. - #[inline] - pub fn get_seed(&self) -> u64 { - self.0 - } - - /// Choose an item from an iterator at random. - /// - /// This function may have an unexpected result if the `len()` property of the - /// iterator does not match the actual number of items in the iterator. If - /// the iterator is empty, this returns `None`. - #[inline] - pub fn choice<I>(&mut self, iter: I) -> Option<I::Item> - where - I: IntoIterator, - I::IntoIter: ExactSizeIterator, - { - let mut iter = iter.into_iter(); - - // Get the item at a random index. - let len = iter.len(); - if len == 0 { - return None; - } - let index = self.usize(0..len); - - iter.nth(index) - } - - /// Shuffles a slice randomly. - #[inline] - pub fn shuffle<T>(&mut self, slice: &mut [T]) { - for i in 1..slice.len() { - slice.swap(i, self.usize(..=i)); - } - } - - /// Fill a byte slice with random data. - #[inline] - pub fn fill(&mut self, slice: &mut [u8]) { - // We fill the slice by chunks of 8 bytes, or one block of - // WyRand output per new state. - let mut chunks = slice.chunks_exact_mut(core::mem::size_of::<u64>()); - for chunk in chunks.by_ref() { - let n = self.gen_u64().to_ne_bytes(); - // Safe because the chunks are always 8 bytes exactly. - chunk.copy_from_slice(&n); - } - - let remainder = chunks.into_remainder(); - - // Any remainder will always be less than 8 bytes. - if !remainder.is_empty() { - // Generate one last block of 8 bytes of entropy - let n = self.gen_u64().to_ne_bytes(); - - // Use the remaining length to copy from block - remainder.copy_from_slice(&n[..remainder.len()]); - } - } - - rng_integer!( - u8, - u8, - gen_u32, - gen_mod_u32, - "Generates a random `u8` in the given range." - ); - - rng_integer!( - u16, - u16, - gen_u32, - gen_mod_u32, - "Generates a random `u16` in the given range." - ); - - rng_integer!( - u32, - u32, - gen_u32, - gen_mod_u32, - "Generates a random `u32` in the given range." - ); - - rng_integer!( - u64, - u64, - gen_u64, - gen_mod_u64, - "Generates a random `u64` in the given range." - ); - - rng_integer!( - u128, - u128, - gen_u128, - gen_mod_u128, - "Generates a random `u128` in the given range." - ); - - #[cfg(target_pointer_width = "16")] - rng_integer!( - usize, - usize, - gen_u32, - gen_mod_u32, - "Generates a random `usize` in the given range." - ); - #[cfg(target_pointer_width = "32")] - rng_integer!( - usize, - usize, - gen_u32, - gen_mod_u32, - "Generates a random `usize` in the given range." - ); - #[cfg(target_pointer_width = "64")] - rng_integer!( - usize, - usize, - gen_u64, - gen_mod_u64, - "Generates a random `usize` in the given range." - ); - #[cfg(target_pointer_width = "128")] - rng_integer!( - usize, - usize, - gen_u128, - gen_mod_u128, - "Generates a random `usize` in the given range." - ); - - /// Generates a random `char` in range A-Z. - #[inline] - pub fn uppercase(&mut self) -> char { - const CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZ"; - *self.choice(CHARS).unwrap() as char - } - - /// Generates a random `char` in the given range. - /// - /// Panics if the range is empty. - #[inline] - pub fn char(&mut self, range: impl RangeBounds<char>) -> char { - let panic_empty_range = || { - panic!( - "empty range: {:?}..{:?}", - range.start_bound(), - range.end_bound() - ) - }; - - let surrogate_start = 0xd800u32; - let surrogate_len = 0x800u32; - - let low = match range.start_bound() { - Bound::Unbounded => 0u8 as char, - Bound::Included(&x) => x, - Bound::Excluded(&x) => { - let scalar = if x as u32 == surrogate_start - 1 { - surrogate_start + surrogate_len - } else { - x as u32 + 1 - }; - char::try_from(scalar).unwrap_or_else(|_| panic_empty_range()) - } - }; - - let high = match range.end_bound() { - Bound::Unbounded => core::char::MAX, - Bound::Included(&x) => x, - Bound::Excluded(&x) => { - let scalar = if x as u32 == surrogate_start + surrogate_len { - surrogate_start - 1 - } else { - (x as u32).wrapping_sub(1) - }; - char::try_from(scalar).unwrap_or_else(|_| panic_empty_range()) - } - }; - - if low > high { - panic_empty_range(); - } - - let gap = if (low as u32) < surrogate_start && (high as u32) >= surrogate_start { - surrogate_len - } else { - 0 - }; - let range = high as u32 - low as u32 - gap; - let mut val = self.u32(0..=range) + low as u32; - if val >= surrogate_start { - val += gap; - } - val.try_into().unwrap() - } -} |