rand/distr/
other.rs

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 `StandardUniform` distribution for other built-in types.
10
11#[cfg(feature = "alloc")]
12use alloc::string::String;
13use core::array;
14use core::char;
15use core::num::Wrapping;
16
17#[cfg(feature = "alloc")]
18use crate::distr::SampleString;
19use crate::distr::{Distribution, StandardUniform, Uniform};
20use crate::Rng;
21
22#[cfg(feature = "simd_support")]
23use core::simd::prelude::*;
24#[cfg(feature = "simd_support")]
25use core::simd::{LaneCount, MaskElement, SupportedLaneCount};
26#[cfg(feature = "serde")]
27use serde::{Deserialize, Serialize};
28
29// ----- Sampling distributions -----
30
31/// Sample a `u8`, uniformly distributed over ASCII letters and numbers:
32/// a-z, A-Z and 0-9.
33///
34/// # Example
35///
36/// ```
37/// use rand::Rng;
38/// use rand::distr::Alphanumeric;
39///
40/// let mut rng = rand::rng();
41/// let chars: String = (0..7).map(|_| rng.sample(Alphanumeric) as char).collect();
42/// println!("Random chars: {}", chars);
43/// ```
44///
45/// The [`SampleString`] trait provides an easier method of generating
46/// a random [`String`], and offers more efficient allocation:
47/// ```
48/// use rand::distr::{Alphanumeric, SampleString};
49/// let string = Alphanumeric.sample_string(&mut rand::rng(), 16);
50/// println!("Random string: {}", string);
51/// ```
52///
53/// # Passwords
54///
55/// Users sometimes ask whether it is safe to use a string of random characters
56/// as a password. In principle, all RNGs in Rand implementing `CryptoRng` are
57/// suitable as a source of randomness for generating passwords (if they are
58/// properly seeded), but it is more conservative to only use randomness
59/// directly from the operating system via the `getrandom` crate, or the
60/// corresponding bindings of a crypto library.
61///
62/// When generating passwords or keys, it is important to consider the threat
63/// model and in some cases the memorability of the password. This is out of
64/// scope of the Rand project, and therefore we defer to the following
65/// references:
66///
67/// - [Wikipedia article on Password Strength](https://en.wikipedia.org/wiki/Password_strength)
68/// - [Diceware for generating memorable passwords](https://en.wikipedia.org/wiki/Diceware)
69#[derive(Debug, Clone, Copy, Default)]
70#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
71pub struct Alphanumeric;
72
73/// Sample a [`u8`], uniformly distributed over letters:
74/// a-z and A-Z.
75///
76/// # Example
77///
78/// You're able to generate random Alphabetic characters via mapping or via the
79/// [`SampleString::sample_string`] method like so:
80///
81/// ```
82/// use rand::Rng;
83/// use rand::distr::{Alphabetic, SampleString};
84///
85/// // Manual mapping
86/// let mut rng = rand::rng();
87/// let chars: String = (0..7).map(|_| rng.sample(Alphabetic) as char).collect();
88/// println!("Random chars: {}", chars);
89///
90/// // Using [`SampleString::sample_string`]
91/// let string = Alphabetic.sample_string(&mut rand::rng(), 16);
92/// println!("Random string: {}", string);
93/// ```
94///
95/// # Passwords
96///
97/// Refer to [`Alphanumeric#Passwords`].
98#[derive(Debug, Clone, Copy, Default)]
99#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
100pub struct Alphabetic;
101
102// ----- Implementations of distributions -----
103
104impl Distribution<char> for StandardUniform {
105    #[inline]
106    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> char {
107        // A valid `char` is either in the interval `[0, 0xD800)` or
108        // `(0xDFFF, 0x11_0000)`. All `char`s must therefore be in
109        // `[0, 0x11_0000)` but not in the "gap" `[0xD800, 0xDFFF]` which is
110        // reserved for surrogates. This is the size of that gap.
111        const GAP_SIZE: u32 = 0xDFFF - 0xD800 + 1;
112
113        // Uniform::new(0, 0x11_0000 - GAP_SIZE) can also be used, but it
114        // seemed slower.
115        let range = Uniform::new(GAP_SIZE, 0x11_0000).unwrap();
116
117        let mut n = range.sample(rng);
118        if n <= 0xDFFF {
119            n -= GAP_SIZE;
120        }
121        // SAFETY: We ensure above that `n` represents a `char`.
122        unsafe { char::from_u32_unchecked(n) }
123    }
124}
125
126#[cfg(feature = "alloc")]
127impl SampleString for StandardUniform {
128    fn append_string<R: Rng + ?Sized>(&self, rng: &mut R, s: &mut String, len: usize) {
129        // A char is encoded with at most four bytes, thus this reservation is
130        // guaranteed to be sufficient. We do not shrink_to_fit afterwards so
131        // that repeated usage on the same `String` buffer does not reallocate.
132        s.reserve(4 * len);
133        s.extend(Distribution::<char>::sample_iter(self, rng).take(len));
134    }
135}
136
137impl Distribution<u8> for Alphanumeric {
138    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> u8 {
139        const RANGE: u32 = 26 + 26 + 10;
140        const GEN_ASCII_STR_CHARSET: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZ\
141                abcdefghijklmnopqrstuvwxyz\
142                0123456789";
143        // We can pick from 62 characters. This is so close to a power of 2, 64,
144        // that we can do better than `Uniform`. Use a simple bitshift and
145        // rejection sampling. We do not use a bitmask, because for small RNGs
146        // the most significant bits are usually of higher quality.
147        loop {
148            let var = rng.next_u32() >> (32 - 6);
149            if var < RANGE {
150                return GEN_ASCII_STR_CHARSET[var as usize];
151            }
152        }
153    }
154}
155
156impl Distribution<u8> for Alphabetic {
157    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> u8 {
158        const RANGE: u8 = 26 + 26;
159
160        let offset = rng.random_range(0..RANGE) + b'A';
161
162        // Account for upper-cases
163        offset + (offset > b'Z') as u8 * (b'a' - b'Z' - 1)
164    }
165}
166
167#[cfg(feature = "alloc")]
168impl SampleString for Alphanumeric {
169    fn append_string<R: Rng + ?Sized>(&self, rng: &mut R, string: &mut String, len: usize) {
170        // SAFETY: `self` only samples alphanumeric characters, which are valid UTF-8.
171        unsafe {
172            let v = string.as_mut_vec();
173            v.extend(
174                self.sample_iter(rng)
175                    .take(len)
176                    .inspect(|b| debug_assert!(b.is_ascii_alphanumeric())),
177            );
178        }
179    }
180}
181
182#[cfg(feature = "alloc")]
183impl SampleString for Alphabetic {
184    fn append_string<R: Rng + ?Sized>(&self, rng: &mut R, string: &mut String, len: usize) {
185        // SAFETY: With this distribution we guarantee that we're working with valid ASCII
186        // characters.
187        // See [#1590](https://github.com/rust-random/rand/issues/1590).
188        unsafe {
189            let v = string.as_mut_vec();
190            v.reserve_exact(len);
191            v.extend(self.sample_iter(rng).take(len));
192        }
193    }
194}
195
196impl Distribution<bool> for StandardUniform {
197    #[inline]
198    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> bool {
199        // We can compare against an arbitrary bit of an u32 to get a bool.
200        // Because the least significant bits of a lower quality RNG can have
201        // simple patterns, we compare against the most significant bit. This is
202        // easiest done using a sign test.
203        (rng.next_u32() as i32) < 0
204    }
205}
206
207/// Note that on some hardware like x86/64 mask operations like [`_mm_blendv_epi8`]
208/// only care about a single bit. This means that you could use uniform random bits
209/// directly:
210///
211/// ```ignore
212/// // this may be faster...
213/// let x = unsafe { _mm_blendv_epi8(a.into(), b.into(), rng.random::<__m128i>()) };
214///
215/// // ...than this
216/// let x = rng.random::<mask8x16>().select(b, a);
217/// ```
218///
219/// Since most bits are unused you could also generate only as many bits as you need, i.e.:
220/// ```
221/// #![feature(portable_simd)]
222/// use std::simd::prelude::*;
223/// use rand::prelude::*;
224/// let mut rng = rand::rng();
225///
226/// let x = u16x8::splat(rng.random::<u8>() as u16);
227/// let mask = u16x8::splat(1) << u16x8::from([0, 1, 2, 3, 4, 5, 6, 7]);
228/// let rand_mask = (x & mask).simd_eq(mask);
229/// ```
230///
231/// [`_mm_blendv_epi8`]: https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#text=_mm_blendv_epi8&ig_expand=514/
232/// [`simd_support`]: https://github.com/rust-random/rand#crate-features
233#[cfg(feature = "simd_support")]
234impl<T, const LANES: usize> Distribution<Mask<T, LANES>> for StandardUniform
235where
236    T: MaskElement + Default,
237    LaneCount<LANES>: SupportedLaneCount,
238    StandardUniform: Distribution<Simd<T, LANES>>,
239    Simd<T, LANES>: SimdPartialOrd<Mask = Mask<T, LANES>>,
240{
241    #[inline]
242    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Mask<T, LANES> {
243        // `MaskElement` must be a signed integer, so this is equivalent
244        // to the scalar `i32 < 0` method
245        let var = rng.random::<Simd<T, LANES>>();
246        var.simd_lt(Simd::default())
247    }
248}
249
250/// Implement `Distribution<(A, B, C, ...)> for StandardUniform`, using the list of
251/// identifiers
252macro_rules! tuple_impl {
253    ($($tyvar:ident)*) => {
254        impl< $($tyvar,)* > Distribution<($($tyvar,)*)> for StandardUniform
255        where $(
256            StandardUniform: Distribution< $tyvar >,
257        )*
258        {
259            #[inline]
260            fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> ( $($tyvar,)* ) {
261                let out = ($(
262                    // use the $tyvar's to get the appropriate number of
263                    // repeats (they're not actually needed)
264                    rng.random::<$tyvar>()
265                ,)*);
266
267                // Suppress the unused variable warning for empty tuple
268                let _rng = rng;
269
270                out
271            }
272        }
273    }
274}
275
276/// Looping wrapper for `tuple_impl`. Given (A, B, C), it also generates
277/// implementations for (A, B) and (A,)
278macro_rules! tuple_impls {
279    ($($tyvar:ident)*) => {tuple_impls!{[] $($tyvar)*}};
280
281    ([$($prefix:ident)*] $head:ident $($tail:ident)*) => {
282        tuple_impl!{$($prefix)*}
283        tuple_impls!{[$($prefix)* $head] $($tail)*}
284    };
285
286
287    ([$($prefix:ident)*]) => {
288        tuple_impl!{$($prefix)*}
289    };
290
291}
292
293tuple_impls! {A B C D E F G H I J K L}
294
295impl<T, const N: usize> Distribution<[T; N]> for StandardUniform
296where
297    StandardUniform: Distribution<T>,
298{
299    #[inline]
300    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> [T; N] {
301        array::from_fn(|_| rng.random())
302    }
303}
304
305impl<T> Distribution<Wrapping<T>> for StandardUniform
306where
307    StandardUniform: Distribution<T>,
308{
309    #[inline]
310    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Wrapping<T> {
311        Wrapping(rng.random())
312    }
313}
314
315#[cfg(test)]
316mod tests {
317    use super::*;
318    use crate::RngCore;
319
320    #[test]
321    fn test_misc() {
322        let rng: &mut dyn RngCore = &mut crate::test::rng(820);
323
324        rng.sample::<char, _>(StandardUniform);
325        rng.sample::<bool, _>(StandardUniform);
326    }
327
328    #[cfg(feature = "alloc")]
329    #[test]
330    fn test_chars() {
331        use core::iter;
332        let mut rng = crate::test::rng(805);
333
334        // Test by generating a relatively large number of chars, so we also
335        // take the rejection sampling path.
336        let word: String = iter::repeat(())
337            .map(|()| rng.random::<char>())
338            .take(1000)
339            .collect();
340        assert!(!word.is_empty());
341    }
342
343    #[test]
344    fn test_alphanumeric() {
345        let mut rng = crate::test::rng(806);
346
347        // Test by generating a relatively large number of chars, so we also
348        // take the rejection sampling path.
349        let mut incorrect = false;
350        for _ in 0..100 {
351            let c: char = rng.sample(Alphanumeric).into();
352            incorrect |= !c.is_ascii_alphanumeric();
353        }
354        assert!(!incorrect);
355    }
356
357    #[test]
358    fn test_alphabetic() {
359        let mut rng = crate::test::rng(806);
360
361        // Test by generating a relatively large number of chars, so we also
362        // take the rejection sampling path.
363        let mut incorrect = false;
364        for _ in 0..100 {
365            let c: char = rng.sample(Alphabetic).into();
366            incorrect |= !c.is_ascii_alphabetic();
367        }
368        assert!(!incorrect);
369    }
370
371    #[test]
372    fn value_stability() {
373        fn test_samples<T: Copy + core::fmt::Debug + PartialEq, D: Distribution<T>>(
374            distr: &D,
375            zero: T,
376            expected: &[T],
377        ) {
378            let mut rng = crate::test::rng(807);
379            let mut buf = [zero; 5];
380            for x in &mut buf {
381                *x = rng.sample(distr);
382            }
383            assert_eq!(&buf, expected);
384        }
385
386        test_samples(
387            &StandardUniform,
388            'a',
389            &[
390                '\u{8cdac}',
391                '\u{a346a}',
392                '\u{80120}',
393                '\u{ed692}',
394                '\u{35888}',
395            ],
396        );
397        test_samples(&Alphanumeric, 0, &[104, 109, 101, 51, 77]);
398        test_samples(&Alphabetic, 0, &[97, 102, 89, 116, 75]);
399        test_samples(&StandardUniform, false, &[true, true, false, true, false]);
400        test_samples(
401            &StandardUniform,
402            Wrapping(0i32),
403            &[
404                Wrapping(-2074640887),
405                Wrapping(-1719949321),
406                Wrapping(2018088303),
407                Wrapping(-547181756),
408                Wrapping(838957336),
409            ],
410        );
411
412        // We test only sub-sets of tuple and array impls
413        test_samples(&StandardUniform, (), &[(), (), (), (), ()]);
414        test_samples(
415            &StandardUniform,
416            (false,),
417            &[(true,), (true,), (false,), (true,), (false,)],
418        );
419        test_samples(
420            &StandardUniform,
421            (false, false),
422            &[
423                (true, true),
424                (false, true),
425                (false, false),
426                (true, false),
427                (false, false),
428            ],
429        );
430
431        test_samples(&StandardUniform, [0u8; 0], &[[], [], [], [], []]);
432        test_samples(
433            &StandardUniform,
434            [0u8; 3],
435            &[
436                [9, 247, 111],
437                [68, 24, 13],
438                [174, 19, 194],
439                [172, 69, 213],
440                [149, 207, 29],
441            ],
442        );
443    }
444}
rand/distr/other.rs

rand/distr/
other.rs
