rand/distributions/
other.rs

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

rand/distributions/
other.rs
