core/random.rs
1//! Random value generation.
2
3use crate::range::{RangeFull, RangeInclusive};
4
5/// A source of randomness.
6#[unstable(feature = "random", issue = "130703")]
7pub trait Rng {
8 /// Fills `bytes` with random bytes.
9 ///
10 /// Note that calling `fill_bytes` multiple times is not equivalent to calling `fill_bytes` once
11 /// with a larger buffer. An `Rng` is allowed to return different bytes for those two cases. For
12 /// instance, this allows an `Rng` to generate a word at a time and throw part of it away if not
13 /// needed.
14 fn fill_bytes(&mut self, bytes: &mut [u8]);
15}
16
17/// Implements `Rng` for mutable references to random number generators by
18/// forwarding all methods to the referenced generator.
19#[unstable(feature = "random", issue = "130703")]
20impl<'a, R: Rng + ?Sized> Rng for &'a mut R {
21 fn fill_bytes(&mut self, bytes: &mut [u8]) {
22 R::fill_bytes(self, bytes);
23 }
24}
25
26/// A trait representing a distribution of random values for a type.
27#[unstable(feature = "random", issue = "130703")]
28pub trait Distribution<T> {
29 /// Samples a random value from the distribution, using the specified random source.
30 fn sample(&self, source: &mut (impl Rng + ?Sized)) -> T;
31}
32
33impl<T, DT: Distribution<T>> Distribution<T> for &DT {
34 fn sample(&self, source: &mut (impl Rng + ?Sized)) -> T {
35 (*self).sample(source)
36 }
37}
38
39impl Distribution<bool> for RangeFull {
40 fn sample(&self, source: &mut (impl Rng + ?Sized)) -> bool {
41 let byte: u8 = RangeFull.sample(source);
42 byte & 1 == 1
43 }
44}
45
46macro_rules! impl_full {
47 ($t:ty) => {
48 impl Distribution<$t> for RangeFull {
49 fn sample(&self, source: &mut (impl Rng + ?Sized)) -> $t {
50 let mut bytes = (0 as $t).to_ne_bytes();
51 source.fill_bytes(&mut bytes);
52 // Always use little-endian for reproducibility. Since the vast majority of code is
53 // mainly or exclusively tested on LE targets, giving different PRNG results for the
54 // same seed on BE targets is a serious portability hazard.
55 <$t>::from_le_bytes(bytes)
56 }
57 }
58 };
59}
60
61impl_full!(u8);
62impl_full!(i8);
63impl_full!(u16);
64impl_full!(i16);
65impl_full!(u32);
66impl_full!(i32);
67impl_full!(u64);
68impl_full!(i64);
69impl_full!(u128);
70impl_full!(i128);
71impl_full!(usize);
72impl_full!(isize);
73
74#[cold]
75fn empty_range() -> ! {
76 panic!("cannot sample from an empty distribution")
77}
78
79macro_rules! lemire_sample {
80 ($name:ident($ty:ty)) => {
81 // Unbiased uniform sampling of a number within the range [0, bound).
82 //
83 // By performing some clever modular arithmetic, this algorithm manages
84 // to both reduce divisions and minimize the chance of sample rejections.
85 //
86 // Algorithm from:
87 // spellchecker:off
88 // Daniel Lemire. 2019. Fast Random Integer Generation in an Interval.
89 // ACM Trans. Model. Comput. Simul. 29, 1, Article 3 (January 2019), 12 pages.
90 // https://doi.org/10.1145/3230636
91 // spellchecker:on
92 fn $name(bound: $ty, source: &mut (impl Rng + ?Sized)) -> $ty {
93 debug_assert_ne!(bound, 0);
94
95 let sample: $ty = (..).sample(source);
96
97 let (mut l, mut res) = sample.carrying_mul(bound, 0);
98 if l < bound {
99 let t = bound.wrapping_neg() % bound;
100 while l < t {
101 let sample: $ty = (..).sample(source);
102 (l, res) = sample.carrying_mul(bound, 0);
103 }
104 }
105
106 debug_assert!(res < bound);
107 res
108 }
109 };
110}
111
112lemire_sample!(bounded32(u32));
113lemire_sample!(bounded64(u64));
114lemire_sample!(bounded128(u128));
115
116macro_rules! impl_range {
117 ($unsigned:ty, $signed:ty as $base:ty => $bounded:ident) => {
118 impl Distribution<$unsigned> for RangeInclusive<$unsigned> {
119 /// Chooses a random number within the range.
120 ///
121 /// Every possible result value is equally likely. In other words,
122 /// this operation uses unbiased uniform sampling.
123 ///
124 /// # Panics
125 ///
126 /// Panics if the range is empty.
127 ///
128 /// # Side-channels
129 ///
130 /// This implementation does not claim to be resistant against side-
131 /// channel attacks. In particular, the execution time of this operation
132 /// may leak information about the returned value, and not just the
133 /// values of the range bounds. While this implementation tries to
134 /// avoid operations with particularly data-dependent timing (such
135 /// as divisions), Rust as a language has no facilities for ensuring
136 /// data-independent timing, voiding all promises about side-channel-
137 /// freedom.
138 ///
139 /// # Examples
140 ///
141 /// A D20 dice roll:
142 /// ```
143 /// #![feature(random)]
144 ///
145 /// use std::random::{Distribution, SystemRng};
146 /// use std::range::RangeInclusive;
147 ///
148 /// let roll = RangeInclusive::from(1..=20).sample(&mut SystemRng);
149 /// assert!(1 <= roll && roll <= 20);
150 /// if roll == 20 {
151 /// println!("Wow! You achieve writing a sound linked list.");
152 /// } else {
153 /// println!("Miri attacks!");
154 /// }
155 /// ```
156 #[inline]
157 fn sample(&self, source: &mut (impl Rng + ?Sized)) -> $unsigned {
158 if self.start > self.last {
159 empty_range();
160 }
161
162 if self.start == self.last {
163 return self.start;
164 }
165
166 let Some(bound) = (self.last - self.start).checked_add(1) else {
167 // Overflow can only occur for Self::MIN..=Self::MAX, meaning
168 // the range is effectively unbounded.
169 return RangeFull.sample(source);
170 };
171
172 let offset = if bound.is_power_of_two() {
173 let sample: $unsigned = RangeFull.sample(source);
174 sample & (bound - 1)
175 } else {
176 $bounded(bound as $base, source) as $unsigned
177 };
178
179 self.start + offset
180 }
181 }
182
183 impl Distribution<$signed> for RangeInclusive<$signed> {
184 /// Chooses a random number within the range.
185 ///
186 /// Every possible result value is equally likely. In other words,
187 /// this operation uses unbiased uniform sampling.
188 ///
189 /// # Panics
190 ///
191 /// Panics if the range is empty.
192 ///
193 /// # Side-channels
194 ///
195 /// This implementation does not claim to be resistant against side-
196 /// channel attacks. In particular, the execution time of this operation
197 /// may leak information about the returned value, and not just the
198 /// values of the range bounds. While this implementation tries to
199 /// avoid operations with particularly data-dependent timing (such
200 /// as divisions), Rust as a language has no facilities for ensuring
201 /// data-independent timing, voiding all promises about side-channel-
202 /// freedom.
203 ///
204 /// # Examples
205 ///
206 /// A D20 dice roll:
207 /// ```
208 /// #![feature(random)]
209 ///
210 /// use std::random::{Distribution, SystemRng};
211 /// use std::range::RangeInclusive;
212 ///
213 /// let roll = RangeInclusive::from(1..=20).sample(&mut SystemRng);
214 /// assert!(1 <= roll && roll <= 20);
215 /// if roll == 20 {
216 /// println!("Wow! You achieve writing a sound linked list.");
217 /// } else {
218 /// println!("Miri attacks!");
219 /// }
220 /// ```
221 #[inline]
222 fn sample(&self, source: &mut (impl Rng + ?Sized)) -> $signed {
223 if self.start > self.last {
224 empty_range();
225 }
226
227 if self.start == self.last {
228 return self.start;
229 }
230
231 let Some(bound) = self.last.wrapping_sub(self.start).cast_unsigned().checked_add(1)
232 else {
233 // Overflow can only occur for Self::MIN..=Self::MAX, meaning
234 // the range is effectively unbounded.
235 return RangeFull.sample(source);
236 };
237
238 let offset = if bound.is_power_of_two() {
239 let sample: $unsigned = RangeFull.sample(source);
240 sample & (bound - 1)
241 } else {
242 $bounded(bound as $base, source) as $unsigned
243 };
244
245 self.start.wrapping_add_unsigned(offset)
246 }
247 }
248 };
249}
250
251// Use 32-bit integers for small integers since it reduces the likelihood of
252// sample rejections.
253impl_range!(u8, i8 as u32 => bounded32);
254impl_range!(u16, i16 as u32 => bounded32);
255
256impl_range!(u32, i32 as u32 => bounded32);
257impl_range!(u64, i64 as u64 => bounded64);
258impl_range!(u128, i128 as u128 => bounded128);
259#[cfg(any(target_pointer_width = "16", target_pointer_width = "32",))]
260impl_range!(usize, isize as u32 => bounded32);
261#[cfg(target_pointer_width = "64")]
262impl_range!(usize, isize as u64 => bounded64);