1 // Copyright 2018 Developers of the Rand project. 2 // 3 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or 4 // https://www.apache.org/licenses/LICENSE-2.0> or the MIT license 5 // <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your 6 // option. This file may not be copied, modified, or distributed 7 // except according to those terms. 8 9 //! The implementations of the `Standard` distribution for other built-in types. 10 11 use core::char; 12 use core::num::Wrapping; 13 14 use crate::distributions::{Distribution, Standard, Uniform}; 15 use crate::Rng; 16 17 #[cfg(feature = "serde1")] 18 use serde::{Serialize, Deserialize}; 19 20 // ----- Sampling distributions ----- 21 22 /// Sample a `u8`, uniformly distributed over ASCII letters and numbers: 23 /// a-z, A-Z and 0-9. 24 /// 25 /// # Example 26 /// 27 /// ``` 28 /// use std::iter; 29 /// use rand::{Rng, thread_rng}; 30 /// use rand::distributions::Alphanumeric; 31 /// 32 /// let mut rng = thread_rng(); 33 /// let chars: String = iter::repeat(()) 34 /// .map(|()| rng.sample(Alphanumeric)) 35 /// .map(char::from) 36 /// .take(7) 37 /// .collect(); 38 /// println!("Random chars: {}", chars); 39 /// ``` 40 /// 41 /// # Passwords 42 /// 43 /// Users sometimes ask whether it is safe to use a string of random characters 44 /// as a password. In principle, all RNGs in Rand implementing `CryptoRng` are 45 /// suitable as a source of randomness for generating passwords (if they are 46 /// properly seeded), but it is more conservative to only use randomness 47 /// directly from the operating system via the `getrandom` crate, or the 48 /// corresponding bindings of a crypto library. 49 /// 50 /// When generating passwords or keys, it is important to consider the threat 51 /// model and in some cases the memorability of the password. This is out of 52 /// scope of the Rand project, and therefore we defer to the following 53 /// references: 54 /// 55 /// - [Wikipedia article on Password Strength](https://en.wikipedia.org/wiki/Password_strength) 56 /// - [Diceware for generating memorable passwords](https://en.wikipedia.org/wiki/Diceware) 57 #[derive(Debug)] 58 #[cfg_attr(feature = "serde1", derive(Serialize, Deserialize))] 59 pub struct Alphanumeric; 60 61 62 // ----- Implementations of distributions ----- 63 64 impl Distribution<char> for Standard { 65 #[inline] sample<R: Rng + ?Sized>(&self, rng: &mut R) -> char66 fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> char { 67 // A valid `char` is either in the interval `[0, 0xD800)` or 68 // `(0xDFFF, 0x11_0000)`. All `char`s must therefore be in 69 // `[0, 0x11_0000)` but not in the "gap" `[0xD800, 0xDFFF]` which is 70 // reserved for surrogates. This is the size of that gap. 71 const GAP_SIZE: u32 = 0xDFFF - 0xD800 + 1; 72 73 // Uniform::new(0, 0x11_0000 - GAP_SIZE) can also be used but it 74 // seemed slower. 75 let range = Uniform::new(GAP_SIZE, 0x11_0000); 76 77 let mut n = range.sample(rng); 78 if n <= 0xDFFF { 79 n -= GAP_SIZE; 80 } 81 unsafe { char::from_u32_unchecked(n) } 82 } 83 } 84 85 impl Distribution<u8> for Alphanumeric { sample<R: Rng + ?Sized>(&self, rng: &mut R) -> u886 fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> u8 { 87 const RANGE: u32 = 26 + 26 + 10; 88 const GEN_ASCII_STR_CHARSET: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZ\ 89 abcdefghijklmnopqrstuvwxyz\ 90 0123456789"; 91 // We can pick from 62 characters. This is so close to a power of 2, 64, 92 // that we can do better than `Uniform`. Use a simple bitshift and 93 // rejection sampling. We do not use a bitmask, because for small RNGs 94 // the most significant bits are usually of higher quality. 95 loop { 96 let var = rng.next_u32() >> (32 - 6); 97 if var < RANGE { 98 return GEN_ASCII_STR_CHARSET[var as usize]; 99 } 100 } 101 } 102 } 103 104 impl Distribution<bool> for Standard { 105 #[inline] sample<R: Rng + ?Sized>(&self, rng: &mut R) -> bool106 fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> bool { 107 // We can compare against an arbitrary bit of an u32 to get a bool. 108 // Because the least significant bits of a lower quality RNG can have 109 // simple patterns, we compare against the most significant bit. This is 110 // easiest done using a sign test. 111 (rng.next_u32() as i32) < 0 112 } 113 } 114 115 macro_rules! tuple_impl { 116 // use variables to indicate the arity of the tuple 117 ($($tyvar:ident),* ) => { 118 // the trailing commas are for the 1 tuple 119 impl< $( $tyvar ),* > 120 Distribution<( $( $tyvar ),* , )> 121 for Standard 122 where $( Standard: Distribution<$tyvar> ),* 123 { 124 #[inline] 125 fn sample<R: Rng + ?Sized>(&self, _rng: &mut R) -> ( $( $tyvar ),* , ) { 126 ( 127 // use the $tyvar's to get the appropriate number of 128 // repeats (they're not actually needed) 129 $( 130 _rng.gen::<$tyvar>() 131 ),* 132 , 133 ) 134 } 135 } 136 } 137 } 138 139 impl Distribution<()> for Standard { 140 #[allow(clippy::unused_unit)] 141 #[inline] sample<R: Rng + ?Sized>(&self, _: &mut R) -> ()142 fn sample<R: Rng + ?Sized>(&self, _: &mut R) -> () { 143 () 144 } 145 } 146 tuple_impl! {A} 147 tuple_impl! {A, B} 148 tuple_impl! {A, B, C} 149 tuple_impl! {A, B, C, D} 150 tuple_impl! {A, B, C, D, E} 151 tuple_impl! {A, B, C, D, E, F} 152 tuple_impl! {A, B, C, D, E, F, G} 153 tuple_impl! {A, B, C, D, E, F, G, H} 154 tuple_impl! {A, B, C, D, E, F, G, H, I} 155 tuple_impl! {A, B, C, D, E, F, G, H, I, J} 156 tuple_impl! {A, B, C, D, E, F, G, H, I, J, K} 157 tuple_impl! {A, B, C, D, E, F, G, H, I, J, K, L} 158 159 macro_rules! array_impl { 160 // recursive, given at least one type parameter: 161 {$n:expr, $t:ident, $($ts:ident,)*} => { 162 array_impl!{($n - 1), $($ts,)*} 163 164 impl<T> Distribution<[T; $n]> for Standard where Standard: Distribution<T> { 165 #[inline] 166 fn sample<R: Rng + ?Sized>(&self, _rng: &mut R) -> [T; $n] { 167 [_rng.gen::<$t>(), $(_rng.gen::<$ts>()),*] 168 } 169 } 170 }; 171 // empty case: 172 {$n:expr,} => { 173 impl<T> Distribution<[T; $n]> for Standard { 174 fn sample<R: Rng + ?Sized>(&self, _rng: &mut R) -> [T; $n] { [] } 175 } 176 }; 177 } 178 179 array_impl! {32, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T,} 180 181 impl<T> Distribution<Option<T>> for Standard 182 where Standard: Distribution<T> 183 { 184 #[inline] sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Option<T>185 fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Option<T> { 186 // UFCS is needed here: https://github.com/rust-lang/rust/issues/24066 187 if rng.gen::<bool>() { 188 Some(rng.gen()) 189 } else { 190 None 191 } 192 } 193 } 194 195 impl<T> Distribution<Wrapping<T>> for Standard 196 where Standard: Distribution<T> 197 { 198 #[inline] sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Wrapping<T>199 fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Wrapping<T> { 200 Wrapping(rng.gen()) 201 } 202 } 203 204 205 #[cfg(test)] 206 mod tests { 207 use super::*; 208 use crate::RngCore; 209 #[cfg(feature = "alloc")] use alloc::string::String; 210 211 #[test] test_misc()212 fn test_misc() { 213 let rng: &mut dyn RngCore = &mut crate::test::rng(820); 214 215 rng.sample::<char, _>(Standard); 216 rng.sample::<bool, _>(Standard); 217 } 218 219 #[cfg(feature = "alloc")] 220 #[test] test_chars()221 fn test_chars() { 222 use core::iter; 223 let mut rng = crate::test::rng(805); 224 225 // Test by generating a relatively large number of chars, so we also 226 // take the rejection sampling path. 227 let word: String = iter::repeat(()) 228 .map(|()| rng.gen::<char>()) 229 .take(1000) 230 .collect(); 231 assert!(word.len() != 0); 232 } 233 234 #[test] test_alphanumeric()235 fn test_alphanumeric() { 236 let mut rng = crate::test::rng(806); 237 238 // Test by generating a relatively large number of chars, so we also 239 // take the rejection sampling path. 240 let mut incorrect = false; 241 for _ in 0..100 { 242 let c: char = rng.sample(Alphanumeric).into(); 243 incorrect |= !((c >= '0' && c <= '9') || 244 (c >= 'A' && c <= 'Z') || 245 (c >= 'a' && c <= 'z') ); 246 } 247 assert!(incorrect == false); 248 } 249 250 #[test] value_stability()251 fn value_stability() { 252 fn test_samples<T: Copy + core::fmt::Debug + PartialEq, D: Distribution<T>>( 253 distr: &D, zero: T, expected: &[T], 254 ) { 255 let mut rng = crate::test::rng(807); 256 let mut buf = [zero; 5]; 257 for x in &mut buf { 258 *x = rng.sample(&distr); 259 } 260 assert_eq!(&buf, expected); 261 } 262 263 test_samples(&Standard, 'a', &[ 264 '\u{8cdac}', 265 '\u{a346a}', 266 '\u{80120}', 267 '\u{ed692}', 268 '\u{35888}', 269 ]); 270 test_samples(&Alphanumeric, 0, &[104, 109, 101, 51, 77]); 271 test_samples(&Standard, false, &[true, true, false, true, false]); 272 test_samples(&Standard, None as Option<bool>, &[ 273 Some(true), 274 None, 275 Some(false), 276 None, 277 Some(false), 278 ]); 279 test_samples(&Standard, Wrapping(0i32), &[ 280 Wrapping(-2074640887), 281 Wrapping(-1719949321), 282 Wrapping(2018088303), 283 Wrapping(-547181756), 284 Wrapping(838957336), 285 ]); 286 287 // We test only sub-sets of tuple and array impls 288 test_samples(&Standard, (), &[(), (), (), (), ()]); 289 test_samples(&Standard, (false,), &[ 290 (true,), 291 (true,), 292 (false,), 293 (true,), 294 (false,), 295 ]); 296 test_samples(&Standard, (false, false), &[ 297 (true, true), 298 (false, true), 299 (false, false), 300 (true, false), 301 (false, false), 302 ]); 303 304 test_samples(&Standard, [0u8; 0], &[[], [], [], [], []]); 305 test_samples(&Standard, [0u8; 3], &[ 306 [9, 247, 111], 307 [68, 24, 13], 308 [174, 19, 194], 309 [172, 69, 213], 310 [149, 207, 29], 311 ]); 312 } 313 } 314