1 use std::{ 2 cell::Cell, 3 collections::hash_map::DefaultHasher, 4 hash::Hasher, 5 num::Wrapping, 6 sync::atomic::{AtomicUsize, Ordering}, 7 }; 8 9 // Based on [Fisher–Yates shuffle]. 10 // 11 // [Fisher–Yates shuffle]: https://en.wikipedia.org/wiki/Fisher–Yates_shuffle 12 #[doc(hidden)] shuffle<T>(slice: &mut [T])13pub fn shuffle<T>(slice: &mut [T]) { 14 for i in (1..slice.len()).rev() { 15 slice.swap(i, gen_index(i + 1)); 16 } 17 } 18 19 /// Return a value from `0..n`. gen_index(n: usize) -> usize20fn gen_index(n: usize) -> usize { 21 (random() % n as u64) as usize 22 } 23 24 /// Pseudorandom number generator based on [xorshift*]. 25 /// 26 /// [xorshift*]: https://en.wikipedia.org/wiki/Xorshift#xorshift* random() -> u6427fn random() -> u64 { 28 thread_local! { 29 static RNG: Cell<Wrapping<u64>> = Cell::new(Wrapping(prng_seed())); 30 } 31 32 fn prng_seed() -> u64 { 33 static COUNTER: AtomicUsize = AtomicUsize::new(0); 34 35 // Any non-zero seed will do 36 let mut seed = 0; 37 while seed == 0 { 38 let mut hasher = DefaultHasher::new(); 39 hasher.write_usize(COUNTER.fetch_add(1, Ordering::Relaxed)); 40 seed = hasher.finish(); 41 } 42 seed 43 } 44 45 RNG.with(|rng| { 46 let mut x = rng.get(); 47 debug_assert_ne!(x.0, 0); 48 x ^= x >> 12; 49 x ^= x << 25; 50 x ^= x >> 27; 51 rng.set(x); 52 x.0.wrapping_mul(0x2545_f491_4f6c_dd1d) 53 }) 54 } 55