diff options
author | Jeff Vander Stoep <jeffv@google.com> | 2024-02-08 14:16:51 +0000 |
---|---|---|
committer | Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com> | 2024-02-08 14:16:51 +0000 |
commit | e614fb34c8c00b82be77f1d255a53851d8c4d013 (patch) | |
tree | be0a0b57e7d325816decfc234bb5ebbbd13965ca | |
parent | 6401b4a593ec1c8182ab00fc9f0ce7a2d15f8cc2 (diff) | |
parent | f00a459d95e87096a8366dc67f5fbfdf33a4e205 (diff) | |
download | fastrand-e614fb34c8c00b82be77f1d255a53851d8c4d013.tar.gz |
Upgrade fastrand to 2.0.1 am: f00a459d95
Original change: https://android-review.googlesource.com/c/platform/external/rust/crates/fastrand/+/2953856
Change-Id: Ifbd87bc93feedac2e3de1fcf5b3b2c14c13fa934
Signed-off-by: Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com>
-rw-r--r-- | .cargo_vcs_info.json | 6 | ||||
-rw-r--r-- | Android.bp | 7 | ||||
-rw-r--r-- | CHANGELOG.md | 14 | ||||
-rw-r--r-- | Cargo.toml | 32 | ||||
-rw-r--r-- | Cargo.toml.orig | 23 | ||||
-rw-r--r-- | METADATA | 24 | ||||
-rw-r--r-- | README.md | 18 | ||||
-rw-r--r-- | benches/bench.rs | 10 | ||||
-rw-r--r-- | src/global_rng.rs | 218 | ||||
-rw-r--r-- | src/lib.rs | 380 | ||||
-rw-r--r-- | tests/smoke.rs | 35 |
11 files changed, 530 insertions, 237 deletions
diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json new file mode 100644 index 0000000..9bdc3d0 --- /dev/null +++ b/.cargo_vcs_info.json @@ -0,0 +1,6 @@ +{ + "git": { + "sha1": "387e3baead884a504d98e89bb4316db98f5c15ce" + }, + "path_in_vcs": "" +}
\ No newline at end of file @@ -42,9 +42,14 @@ rust_library { host_supported: true, crate_name: "fastrand", cargo_env_compat: true, - cargo_pkg_version: "1.9.0", + cargo_pkg_version: "2.0.1", srcs: ["src/lib.rs"], edition: "2018", + features: [ + "alloc", + "default", + "std", + ], apex_available: [ "//apex_available:platform", "com.android.virt", diff --git a/CHANGELOG.md b/CHANGELOG.md index 869f314..b744e31 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -1,3 +1,17 @@ +# Version 2.0.1 + +- Clarify documentation for the `fork()` method. (#62) +- Mention `fastrand-contrib` in documentation. (#70) + +# Version 2.0.0 + +- **Breaking:** Remove interior mutability from `Rng`. (#47) +- Add a `fork()` method. (#49) +- Add a `no_std` mode. (#50) +- Add an iterator selection function. (#51) +- Add a `choose_multiple()` function for sampling several elements from an iterator. (#55) +- Use the `getrandom` crate for seeding on WebAssembly targets if the `js` feature is enabled. (#60) + # Version 1.9.0 - Add `Rng::fill()` (#35, #43) @@ -11,9 +11,9 @@ [package] edition = "2018" -rust-version = "1.34" +rust-version = "1.36" name = "fastrand" -version = "1.9.0" +version = "2.0.1" authors = ["Stjepan Glavina <stjepang@gmail.com>"] exclude = ["/.*"] description = "A simple and fast random number generator" @@ -29,6 +29,13 @@ categories = ["algorithms"] license = "Apache-2.0 OR MIT" repository = "https://github.com/smol-rs/fastrand" +[package.metadata.docs.rs] +all-features = true +rustdoc-args = [ + "--cfg", + "docsrs", +] + [dev-dependencies.getrandom] version = "0.2" @@ -38,16 +45,23 @@ version = "0.8" [dev-dependencies.wyhash] version = "0.5" -[target."cfg(all(target_arch = \"wasm32\", not(target_os = \"wasi\")))".dependencies.instant] -version = "0.1" +[features] +alloc = [] +default = ["std"] +js = [ + "std", + "getrandom", +] +std = ["alloc"] -[target."cfg(all(target_arch = \"wasm32\", not(target_os = \"wasi\")))".dev-dependencies.getrandom] +[target."cfg(all(any(target_arch = \"wasm32\", target_arch = \"wasm64\"), target_os = \"unknown\"))".dependencies.getrandom] version = "0.2" features = ["js"] +optional = true -[target."cfg(all(target_arch = \"wasm32\", not(target_os = \"wasi\")))".dev-dependencies.instant] -version = "0.1" -features = ["wasm-bindgen"] +[target."cfg(all(any(target_arch = \"wasm32\", target_arch = \"wasm64\"), target_os = \"unknown\"))".dev-dependencies.getrandom] +version = "0.2" +features = ["js"] -[target."cfg(all(target_arch = \"wasm32\", not(target_os = \"wasi\")))".dev-dependencies.wasm-bindgen-test] +[target."cfg(all(any(target_arch = \"wasm32\", target_arch = \"wasm64\"), target_os = \"unknown\"))".dev-dependencies.wasm-bindgen-test] version = "0.3" diff --git a/Cargo.toml.orig b/Cargo.toml.orig index 8c80502..c5e85ad 100644 --- a/Cargo.toml.orig +++ b/Cargo.toml.orig @@ -2,11 +2,11 @@ name = "fastrand" # When publishing a new version: # - Update CHANGELOG.md -# - Create "v1.x.y" git tag -version = "1.9.0" +# - Create "v2.x.y" git tag +version = "2.0.1" authors = ["Stjepan Glavina <stjepang@gmail.com>"] edition = "2018" -rust-version = "1.34" +rust-version = "1.36" description = "A simple and fast random number generator" license = "Apache-2.0 OR MIT" repository = "https://github.com/smol-rs/fastrand" @@ -14,11 +14,16 @@ keywords = ["simple", "fast", "rand", "random", "wyrand"] categories = ["algorithms"] exclude = ["/.*"] -[target.'cfg(all(target_arch = "wasm32", not(target_os = "wasi")))'.dependencies] -instant = "0.1" +[features] +default = ["std"] +alloc = [] +std = ["alloc"] +js = ["std", "getrandom"] -[target.'cfg(all(target_arch = "wasm32", not(target_os = "wasi")))'.dev-dependencies] -instant = { version = "0.1", features = ["wasm-bindgen"] } +[target.'cfg(all(any(target_arch = "wasm32", target_arch = "wasm64"), target_os = "unknown"))'.dependencies] +getrandom = { version = "0.2", features = ["js"], optional = true } + +[target.'cfg(all(any(target_arch = "wasm32", target_arch = "wasm64"), target_os = "unknown"))'.dev-dependencies] wasm-bindgen-test = "0.3" getrandom = { version = "0.2", features = ["js"] } @@ -26,3 +31,7 @@ getrandom = { version = "0.2", features = ["js"] } rand = "0.8" wyhash = "0.5" getrandom = "0.2" + +[package.metadata.docs.rs] +all-features = true +rustdoc-args = ["--cfg", "docsrs"] @@ -1,20 +1,20 @@ +# This project was upgraded with external_updater. +# Usage: tools/external_updater/updater.sh update external/rust/crates/fastrand +# For more info, check https://cs.android.com/android/platform/superproject/+/main:tools/external_updater/README.md + name: "fastrand" description: "A simple and fast random number generator" third_party { - url { - type: HOMEPAGE - value: "https://crates.io/crates/fastrand" - } - url { - type: ARCHIVE - value: "https://static.crates.io/crates/fastrand/fastrand-1.9.0.crate" - } - version: "1.9.0" - # Dual-licensed, using the least restrictive per go/thirdpartylicenses#same. license_type: NOTICE last_upgrade_date { - year: 2023 + year: 2024 month: 2 - day: 17 + day: 8 + } + homepage: "https://crates.io/crates/fastrand" + identifier { + type: "Archive" + value: "https://static.crates.io/crates/fastrand/fastrand-2.0.1.crate" + version: "2.0.1" } } @@ -40,6 +40,13 @@ 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): + +```rust +fastrand::choose_multiple(vec![1, 4, 5].iter(), 2); +fastrand::choose_multiple(0..20, 12); +``` + Shuffle an array: ```rust @@ -76,6 +83,17 @@ let 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`](https://docs.rs/fastrand/latest/fastrand/struct.Rng.html#method.with_seed) method. +- `js`: Assumes that WebAssembly targets are being run in a JavaScript environment. + +[`fastrand-contrib`]: https://crates.io/crates/fastrand-contrib + ## License Licensed under either of diff --git a/benches/bench.rs b/benches/bench.rs index 4b882b7..a940aac 100644 --- a/benches/bench.rs +++ b/benches/bench.rs @@ -18,7 +18,7 @@ fn shuffle_wyhash(b: &mut Bencher) { #[bench] fn shuffle_fastrand(b: &mut Bencher) { - let rng = fastrand::Rng::new(); + let mut rng = fastrand::Rng::new(); let mut x = (0..100).collect::<Vec<usize>>(); b.iter(|| { rng.shuffle(&mut x); @@ -40,7 +40,7 @@ fn u8_wyhash(b: &mut Bencher) { #[bench] fn u8_fastrand(b: &mut Bencher) { - let rng = fastrand::Rng::new(); + let mut rng = fastrand::Rng::new(); b.iter(|| { let mut sum = 0u8; for _ in 0..10_000 { @@ -64,7 +64,7 @@ fn u32_wyhash(b: &mut Bencher) { #[bench] fn u32_fastrand(b: &mut Bencher) { - let rng = fastrand::Rng::new(); + let mut rng = fastrand::Rng::new(); b.iter(|| { let mut sum = 0u32; for _ in 0..10_000 { @@ -76,7 +76,7 @@ fn u32_fastrand(b: &mut Bencher) { #[bench] fn fill(b: &mut Bencher) { - let rng = fastrand::Rng::new(); + let mut rng = fastrand::Rng::new(); b.iter(|| { // Pick a size that isn't divisble by 8. let mut bytes = [0u8; 367]; @@ -87,7 +87,7 @@ fn fill(b: &mut Bencher) { #[bench] fn fill_naive(b: &mut Bencher) { - let rng = fastrand::Rng::new(); + let mut rng = fastrand::Rng::new(); b.iter(|| { let mut bytes = [0u8; 367]; for item in &mut bytes { diff --git a/src/global_rng.rs b/src/global_rng.rs new file mode 100644 index 0000000..f994902 --- /dev/null +++ b/src/global_rng.rs @@ -0,0 +1,218 @@ +//! A global, thread-local random number generator. + +use crate::Rng; + +use std::cell::Cell; +use std::ops::RangeBounds; + +// Chosen by fair roll of the dice. +const DEFAULT_RNG_SEED: u64 = 0xef6f79ed30ba75a; + +impl Default for Rng { + /// Initialize the `Rng` from the system's random number generator. + /// + /// This is equivalent to [`Rng::new()`]. + #[inline] + fn default() -> Rng { + Rng::new() + } +} + +impl Rng { + /// Creates a new random number generator. + #[inline] + pub fn new() -> Rng { + try_with_rng(Rng::fork).unwrap_or_else(|_| Rng::with_seed(0x4d595df4d0f33173)) + } +} + +thread_local! { + static RNG: Cell<Rng> = Cell::new(Rng(random_seed().unwrap_or(DEFAULT_RNG_SEED))); +} + +/// Run an operation with the current thread-local generator. +#[inline] +fn with_rng<R>(f: impl FnOnce(&mut Rng) -> R) -> R { + RNG.with(|rng| { + let current = rng.replace(Rng(0)); + + let mut restore = RestoreOnDrop { rng, current }; + + f(&mut restore.current) + }) +} + +/// Try to run an operation with the current thread-local generator. +#[inline] +fn try_with_rng<R>(f: impl FnOnce(&mut Rng) -> R) -> Result<R, std::thread::AccessError> { + RNG.try_with(|rng| { + let current = rng.replace(Rng(0)); + + let mut restore = RestoreOnDrop { rng, current }; + + f(&mut restore.current) + }) +} + +/// Make sure the original RNG is restored even on panic. +struct RestoreOnDrop<'a> { + rng: &'a Cell<Rng>, + current: Rng, +} + +impl Drop for RestoreOnDrop<'_> { + fn drop(&mut self) { + self.rng.set(Rng(self.current.0)); + } +} + +/// Initializes the thread-local generator with the given seed. +#[inline] +pub fn seed(seed: u64) { + with_rng(|r| r.seed(seed)); +} + +/// Gives back **current** seed that is being held by the thread-local generator. +#[inline] +pub fn get_seed() -> u64 { + with_rng(|r| r.get_seed()) +} + +/// Generates a random `bool`. +#[inline] +pub fn bool() -> bool { + with_rng(|r| r.bool()) +} + +/// Generates a random `char` in ranges a-z and A-Z. +#[inline] +pub fn alphabetic() -> char { + with_rng(|r| r.alphabetic()) +} + +/// Generates a random `char` in ranges a-z, A-Z and 0-9. +#[inline] +pub fn alphanumeric() -> char { + with_rng(|r| r.alphanumeric()) +} + +/// Generates a random `char` in range a-z. +#[inline] +pub fn lowercase() -> char { + with_rng(|r| r.lowercase()) +} + +/// Generates a random `char` in range A-Z. +#[inline] +pub fn uppercase() -> char { + with_rng(|r| r.uppercase()) +} + +/// 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>(iter: I) -> Option<I::Item> +where + I: IntoIterator, + I::IntoIter: ExactSizeIterator, +{ + with_rng(|r| r.choice(iter)) +} + +/// 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(base: u32) -> char { + with_rng(|r| r.digit(base)) +} + +/// Shuffles a slice randomly. +#[inline] +pub fn shuffle<T>(slice: &mut [T]) { + with_rng(|r| r.shuffle(slice)) +} + +macro_rules! integer { + ($t:tt, $doc:tt) => { + #[doc = $doc] + /// + /// Panics if the range is empty. + #[inline] + pub fn $t(range: impl RangeBounds<$t>) -> $t { + with_rng(|r| r.$t(range)) + } + }; +} + +integer!(u8, "Generates a random `u8` in the given range."); +integer!(i8, "Generates a random `i8` in the given range."); +integer!(u16, "Generates a random `u16` in the given range."); +integer!(i16, "Generates a random `i16` in the given range."); +integer!(u32, "Generates a random `u32` in the given range."); +integer!(i32, "Generates a random `i32` in the given range."); +integer!(u64, "Generates a random `u64` in the given range."); +integer!(i64, "Generates a random `i64` in the given range."); +integer!(u128, "Generates a random `u128` in the given range."); +integer!(i128, "Generates a random `i128` in the given range."); +integer!(usize, "Generates a random `usize` in the given range."); +integer!(isize, "Generates a random `isize` in the given range."); +integer!(char, "Generates a random `char` in the given range."); + +/// Generates a random `f32` in range `0..1`. +pub fn f32() -> f32 { + with_rng(|r| r.f32()) +} + +/// Generates a random `f64` in range `0..1`. +pub fn f64() -> f64 { + with_rng(|r| r.f64()) +} + +/// Collects `amount` values at random from the iterator into a vector. +pub fn choose_multiple<T: Iterator>(source: T, amount: usize) -> Vec<T::Item> { + with_rng(|rng| rng.choose_multiple(source, amount)) +} + +#[cfg(not(all( + any(target_arch = "wasm32", target_arch = "wasm64"), + target_os = "unknown" +)))] +fn random_seed() -> Option<u64> { + use std::collections::hash_map::DefaultHasher; + use std::hash::{Hash, Hasher}; + use std::thread; + use std::time::Instant; + + let mut hasher = DefaultHasher::new(); + Instant::now().hash(&mut hasher); + thread::current().id().hash(&mut hasher); + let hash = hasher.finish(); + Some((hash << 1) | 1) +} + +#[cfg(all( + any(target_arch = "wasm32", target_arch = "wasm64"), + target_os = "unknown", + feature = "js" +))] +fn random_seed() -> Option<u64> { + // TODO(notgull): Failures should be logged somewhere. + let mut seed = [0u8; 8]; + getrandom::getrandom(&mut seed).ok()?; + Some(u64::from_ne_bytes(seed)) +} + +#[cfg(all( + any(target_arch = "wasm32", target_arch = "wasm64"), + target_os = "unknown", + not(feature = "js") +))] +fn random_seed() -> Option<u64> { + None +} @@ -29,6 +29,14 @@ //! 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: //! //! ``` @@ -61,87 +69,98 @@ //! ``` //! use std::iter::repeat_with; //! -//! let rng = fastrand::Rng::new(); +//! 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}; -use std::cell::Cell; -use std::collections::hash_map::DefaultHasher; -use std::convert::TryInto; -use std::hash::{Hash, Hasher}; -use std::ops::{Bound, RangeBounds}; -use std::thread; +#[cfg(feature = "alloc")] +use alloc::vec::Vec; -#[cfg(all(target_arch = "wasm32", not(target_os = "wasi")))] -use instant::Instant; -#[cfg(not(all(target_arch = "wasm32", not(target_os = "wasi"))))] -use std::time::Instant; +#[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(Cell<u64>); - -impl Default for Rng { - #[inline] - fn default() -> Rng { - Rng::new() - } -} +pub struct Rng(u64); impl Clone for Rng { - /// Clones the generator by deterministically deriving a new generator based on the initial - /// seed. - /// - /// # Example - /// - /// ``` - /// // Seed two generators equally, and clone both of them. - /// let base1 = fastrand::Rng::new(); - /// base1.seed(0x4d595df4d0f33173); - /// base1.bool(); // Use the generator once. - /// - /// let base2 = fastrand::Rng::new(); - /// base2.seed(0x4d595df4d0f33173); - /// base2.bool(); // Use the generator once. - /// - /// let rng1 = base1.clone(); - /// let rng2 = base2.clone(); - /// - /// assert_eq!(rng1.u64(..), rng2.u64(..), "the cloned generators are identical"); - /// ``` + /// Clones the generator by creating a new generator with the same seed. fn clone(&self) -> Rng { - Rng::with_seed(self.gen_u64()) + Rng::with_seed(self.0) } } impl Rng { /// Generates a random `u32`. #[inline] - fn gen_u32(&self) -> u32 { + fn gen_u32(&mut self) -> u32 { self.gen_u64() as u32 } /// Generates a random `u64`. #[inline] - fn gen_u64(&self) -> u64 { - let s = self.0.get().wrapping_add(0xA0761D6478BD642F); - self.0.set(s); + 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(&self) -> u128 { + 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(&self, n: u32) -> u32 { + 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); @@ -159,7 +178,7 @@ impl Rng { /// Generates a random `u64` in `0..n`. #[inline] - fn gen_mod_u64(&self, n: u64) -> u64 { + 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); @@ -177,7 +196,7 @@ impl Rng { /// Generates a random `u128` in `0..n`. #[inline] - fn gen_mod_u128(&self, n: u128) -> u128 { + 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); @@ -194,16 +213,6 @@ impl Rng { } } -thread_local! { - static RNG: Rng = Rng(Cell::new({ - let mut hasher = DefaultHasher::new(); - Instant::now().hash(&mut hasher); - thread::current().id().hash(&mut hasher); - let hash = hasher.finish(); - (hash << 1) | 1 - })); -} - /// Computes `(a * b) >> 32`. #[inline] fn mul_high_u32(a: u32, b: u32) -> u32 { @@ -235,7 +244,7 @@ macro_rules! rng_integer { /// /// Panics if the range is empty. #[inline] - pub fn $t(&self, range: impl RangeBounds<$t>) -> $t { + pub fn $t(&mut self, range: impl RangeBounds<$t>) -> $t { let panic_empty_range = || { panic!( "empty range: {:?}..{:?}", @@ -245,13 +254,13 @@ macro_rules! rng_integer { }; let low = match range.start_bound() { - Bound::Unbounded => std::$t::MIN, + 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 => std::$t::MAX, + Bound::Unbounded => core::$t::MAX, Bound::Included(&x) => x, Bound::Excluded(&x) => x.checked_sub(1).unwrap_or_else(panic_empty_range), }; @@ -260,7 +269,7 @@ macro_rules! rng_integer { panic_empty_range(); } - if low == std::$t::MIN && high == std::$t::MAX { + if low == core::$t::MIN && high == core::$t::MAX { self.$gen() as $t } else { let len = high.wrapping_sub(low).wrapping_add(1); @@ -271,46 +280,62 @@ macro_rules! rng_integer { } impl Rng { - /// Creates a new random number generator. - #[inline] - pub fn new() -> Rng { - Rng::with_seed( - RNG.try_with(|rng| rng.u64(..)) - .unwrap_or(0x4d595df4d0f33173), - ) - } - /// 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 rng = Rng(Cell::new(0)); + 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(&self) -> char { + pub fn alphabetic(&mut self) -> char { const CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; - let len = CHARS.len() as u8; - let i = self.u8(..len); - CHARS[i as usize] as char + *self.choice(CHARS).unwrap() as char } /// Generates a random `char` in ranges a-z, A-Z and 0-9. #[inline] - pub fn alphanumeric(&self) -> char { + pub fn alphanumeric(&mut self) -> char { const CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"; - let len = CHARS.len() as u8; - let i = self.u8(..len); - CHARS[i as usize] as char + *self.choice(CHARS).unwrap() as char } /// Generates a random `bool`. #[inline] - pub fn bool(&self) -> bool { + pub fn bool(&mut self) -> bool { self.u8(..) % 2 == 0 } @@ -320,7 +345,7 @@ impl Rng { /// /// Panics if the base is zero or greater than 36. #[inline] - pub fn digit(&self, base: u32) -> char { + pub fn digit(&mut self, base: u32) -> char { if base == 0 { panic!("base cannot be zero"); } @@ -336,19 +361,57 @@ impl Rng { } /// Generates a random `f32` in range `0..1`. - pub fn f32(&self) -> f32 { + pub fn f32(&mut self) -> f32 { let b = 32; - let f = std::f32::MANTISSA_DIGITS - 1; + 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(&self) -> f64 { + pub fn f64(&mut self) -> f64 { let b = 64; - let f = std::f64::MANTISSA_DIGITS - 1; + 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, @@ -416,28 +479,49 @@ impl Rng { /// Generates a random `char` in range a-z. #[inline] - pub fn lowercase(&self) -> char { + pub fn lowercase(&mut self) -> char { const CHARS: &[u8] = b"abcdefghijklmnopqrstuvwxyz"; - let len = CHARS.len() as u8; - let i = self.u8(..len); - CHARS[i as usize] as char + *self.choice(CHARS).unwrap() as char } /// Initializes this generator with the given seed. #[inline] - pub fn seed(&self, seed: u64) { - self.0.set(seed); + 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.get() + 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>(&self, slice: &mut [T]) { + pub fn shuffle<T>(&mut self, slice: &mut [T]) { for i in 1..slice.len() { slice.swap(i, self.usize(..=i)); } @@ -445,7 +529,7 @@ impl Rng { /// Fill a byte slice with random data. #[inline] - pub fn fill(&self, slice: &mut [u8]) { + 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>()); @@ -542,20 +626,16 @@ impl Rng { /// Generates a random `char` in range A-Z. #[inline] - pub fn uppercase(&self) -> char { + pub fn uppercase(&mut self) -> char { const CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZ"; - let len = CHARS.len() as u8; - let i = self.u8(..len); - CHARS[i as usize] as char + *self.choice(CHARS).unwrap() as char } /// Generates a random `char` in the given range. /// /// Panics if the range is empty. #[inline] - pub fn char(&self, range: impl RangeBounds<char>) -> char { - use std::convert::TryFrom; - + pub fn char(&mut self, range: impl RangeBounds<char>) -> char { let panic_empty_range = || { panic!( "empty range: {:?}..{:?}", @@ -581,7 +661,7 @@ impl Rng { }; let high = match range.end_bound() { - Bound::Unbounded => std::char::MAX, + Bound::Unbounded => core::char::MAX, Bound::Included(&x) => x, Bound::Excluded(&x) => { let scalar = if x as u32 == surrogate_start + surrogate_len { @@ -610,97 +690,3 @@ impl Rng { val.try_into().unwrap() } } - -/// Initializes the thread-local generator with the given seed. -#[inline] -pub fn seed(seed: u64) { - RNG.with(|rng| rng.seed(seed)) -} - -/// Gives back **current** seed that is being held by the thread-local generator. -#[inline] -pub fn get_seed() -> u64 { - RNG.with(|rng| rng.get_seed()) -} - -/// Generates a random `bool`. -#[inline] -pub fn bool() -> bool { - RNG.with(|rng| rng.bool()) -} - -/// Generates a random `char` in ranges a-z and A-Z. -#[inline] -pub fn alphabetic() -> char { - RNG.with(|rng| rng.alphabetic()) -} - -/// Generates a random `char` in ranges a-z, A-Z and 0-9. -#[inline] -pub fn alphanumeric() -> char { - RNG.with(|rng| rng.alphanumeric()) -} - -/// Generates a random `char` in range a-z. -#[inline] -pub fn lowercase() -> char { - RNG.with(|rng| rng.lowercase()) -} - -/// Generates a random `char` in range A-Z. -#[inline] -pub fn uppercase() -> char { - RNG.with(|rng| rng.uppercase()) -} - -/// 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(base: u32) -> char { - RNG.with(|rng| rng.digit(base)) -} - -/// Shuffles a slice randomly. -#[inline] -pub fn shuffle<T>(slice: &mut [T]) { - RNG.with(|rng| rng.shuffle(slice)) -} - -macro_rules! integer { - ($t:tt, $doc:tt) => { - #[doc = $doc] - /// - /// Panics if the range is empty. - #[inline] - pub fn $t(range: impl RangeBounds<$t>) -> $t { - RNG.with(|rng| rng.$t(range)) - } - }; -} - -integer!(u8, "Generates a random `u8` in the given range."); -integer!(i8, "Generates a random `i8` in the given range."); -integer!(u16, "Generates a random `u16` in the given range."); -integer!(i16, "Generates a random `i16` in the given range."); -integer!(u32, "Generates a random `u32` in the given range."); -integer!(i32, "Generates a random `i32` in the given range."); -integer!(u64, "Generates a random `u64` in the given range."); -integer!(i64, "Generates a random `i64` in the given range."); -integer!(u128, "Generates a random `u128` in the given range."); -integer!(i128, "Generates a random `i128` in the given range."); -integer!(usize, "Generates a random `usize` in the given range."); -integer!(isize, "Generates a random `isize` in the given range."); -integer!(char, "Generates a random `char` in the given range."); - -/// Generates a random `f32` in range `0..1`. -pub fn f32() -> f32 { - RNG.with(|rng| rng.f32()) -} - -/// Generates a random `f64` in range `0..1`. -pub fn f64() -> f64 { - RNG.with(|rng| rng.f64()) -} diff --git a/tests/smoke.rs b/tests/smoke.rs index ff3cea6..7c92ee5 100644 --- a/tests/smoke.rs +++ b/tests/smoke.rs @@ -77,7 +77,7 @@ fn u128() { #[test] fn fill() { - let r = fastrand::Rng::new(); + let mut r = fastrand::Rng::new(); let mut a = [0u8; 64]; let mut b = [0u8; 64]; @@ -89,7 +89,7 @@ fn fill() { #[test] fn rng() { - let r = fastrand::Rng::new(); + let mut r = fastrand::Rng::new(); assert_ne!(r.u64(..), r.u64(..)); @@ -102,8 +102,8 @@ fn rng() { #[test] fn rng_init() { - let a = fastrand::Rng::new(); - let b = fastrand::Rng::new(); + let mut a = fastrand::Rng::new(); + let mut b = fastrand::Rng::new(); assert_ne!(a.u64(..), b.u64(..)); a.seed(7); @@ -113,8 +113,31 @@ fn rng_init() { #[test] fn with_seed() { - let a = fastrand::Rng::with_seed(7); - let b = fastrand::Rng::new(); + let mut a = fastrand::Rng::with_seed(7); + let mut b = fastrand::Rng::new(); b.seed(7); assert_eq!(a.u64(..), b.u64(..)); } + +#[test] +fn choose_multiple() { + let mut a = fastrand::Rng::new(); + let mut elements = (0..20).collect::<Vec<_>>(); + + while !elements.is_empty() { + let chosen = a.choose_multiple(0..20, 5); + for &x in &chosen { + elements.retain(|&y| y != x); + } + } +} + +#[test] +fn choice() { + let items = [1, 4, 9, 5, 2, 3, 6, 7, 8, 0]; + let mut r = fastrand::Rng::new(); + + for item in &items { + while r.choice(&items).unwrap() != item {} + } +} |