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 <$t>::from_ne_bytes(bytes)
53 }
54 }
55 };
56}
57
58impl_full!(u8);
59impl_full!(i8);
60impl_full!(u16);
61impl_full!(i16);
62impl_full!(u32);
63impl_full!(i32);
64impl_full!(u64);
65impl_full!(i64);
66impl_full!(u128);
67impl_full!(i128);
68impl_full!(usize);
69impl_full!(isize);
70
71#[cold]
72fn empty_range() -> ! {
73 panic!("cannot sample from an empty distribution")
74}
75
76macro_rules! lemire_sample {
77 ($name:ident($ty:ty)) => {
78 // Unbiased uniform sampling of a number within the range [0, bound).
79 //
80 // By performing some clever modular arithmetic, this algorithm manages
81 // to both reduce divisions and minimize the chance of sample rejections.
82 //
83 // Algorithm from:
84 // spellchecker:off
85 // Daniel Lemire. 2019. Fast Random Integer Generation in an Interval.
86 // ACM Trans. Model. Comput. Simul. 29, 1, Article 3 (January 2019), 12 pages.
87 // https://doi.org/10.1145/3230636
88 // spellchecker:on
89 fn $name(bound: $ty, source: &mut (impl Rng + ?Sized)) -> $ty {
90 debug_assert_ne!(bound, 0);
91
92 let sample: $ty = (..).sample(source);
93
94 let (mut l, mut res) = sample.carrying_mul(bound, 0);
95 if l < bound {
96 let t = bound.wrapping_neg() % bound;
97 while l < t {
98 let sample: $ty = (..).sample(source);
99 (l, res) = sample.carrying_mul(bound, 0);
100 }
101 }
102
103 debug_assert!(res < bound);
104 res
105 }
106 };
107}
108
109lemire_sample!(bounded32(u32));
110lemire_sample!(bounded64(u64));
111lemire_sample!(bounded128(u128));
112
113macro_rules! impl_range {
114 ($unsigned:ty, $signed:ty as $base:ty => $bounded:ident) => {
115 impl Distribution<$unsigned> for RangeInclusive<$unsigned> {
116 /// Chooses a random number within the range.
117 ///
118 /// Every possible result value is equally likely. In other words,
119 /// this operation uses unbiased uniform sampling.
120 ///
121 /// # Panics
122 ///
123 /// Panics if the range is empty.
124 ///
125 /// # Side-channels
126 ///
127 /// This implementation does not claim to be resistant against side-
128 /// channel attacks. In particular, the execution time of this operation
129 /// may leak information about the returned value, and not just the
130 /// values of the range bounds. While this implementation tries to
131 /// avoid operations with particularly data-dependent timing (such
132 /// as divisions), Rust as a language has no facilities for ensuring
133 /// data-independent timing, voiding all promises about side-channel-
134 /// freedom.
135 ///
136 /// # Examples
137 ///
138 /// A D20 dice roll:
139 /// ```
140 /// #![feature(random)]
141 ///
142 /// use std::random::{Distribution, SystemRng};
143 /// use std::range::RangeInclusive;
144 ///
145 /// let roll = RangeInclusive::from(1..=20).sample(&mut SystemRng);
146 /// assert!(1 <= roll && roll <= 20);
147 /// if roll == 20 {
148 /// println!("Wow! You achieve writing a sound linked list.");
149 /// } else {
150 /// println!("Miri attacks!");
151 /// }
152 /// ```
153 #[inline]
154 fn sample(&self, source: &mut (impl Rng + ?Sized)) -> $unsigned {
155 if self.start > self.last {
156 empty_range();
157 }
158
159 if self.start == self.last {
160 return self.start;
161 }
162
163 let Some(bound) = (self.last - self.start).checked_add(1) else {
164 // Overflow can only occur for Self::MIN..=Self::MAX, meaning
165 // the range is effectively unbounded.
166 return RangeFull.sample(source);
167 };
168
169 let offset = if bound.is_power_of_two() {
170 let sample: $unsigned = RangeFull.sample(source);
171 sample & (bound - 1)
172 } else {
173 $bounded(bound as $base, source) as $unsigned
174 };
175
176 self.start + offset
177 }
178 }
179
180 impl Distribution<$signed> for RangeInclusive<$signed> {
181 /// Chooses a random number within the range.
182 ///
183 /// Every possible result value is equally likely. In other words,
184 /// this operation uses unbiased uniform sampling.
185 ///
186 /// # Panics
187 ///
188 /// Panics if the range is empty.
189 ///
190 /// # Side-channels
191 ///
192 /// This implementation does not claim to be resistant against side-
193 /// channel attacks. In particular, the execution time of this operation
194 /// may leak information about the returned value, and not just the
195 /// values of the range bounds. While this implementation tries to
196 /// avoid operations with particularly data-dependent timing (such
197 /// as divisions), Rust as a language has no facilities for ensuring
198 /// data-independent timing, voiding all promises about side-channel-
199 /// freedom.
200 ///
201 /// # Examples
202 ///
203 /// A D20 dice roll:
204 /// ```
205 /// #![feature(random)]
206 ///
207 /// use std::random::{Distribution, SystemRng};
208 /// use std::range::RangeInclusive;
209 ///
210 /// let roll = RangeInclusive::from(1..=20).sample(&mut SystemRng);
211 /// assert!(1 <= roll && roll <= 20);
212 /// if roll == 20 {
213 /// println!("Wow! You achieve writing a sound linked list.");
214 /// } else {
215 /// println!("Miri attacks!");
216 /// }
217 /// ```
218 #[inline]
219 fn sample(&self, source: &mut (impl Rng + ?Sized)) -> $signed {
220 if self.start > self.last {
221 empty_range();
222 }
223
224 if self.start == self.last {
225 return self.start;
226 }
227
228 let Some(bound) = self.last.wrapping_sub(self.start).cast_unsigned().checked_add(1)
229 else {
230 // Overflow can only occur for Self::MIN..=Self::MAX, meaning
231 // the range is effectively unbounded.
232 return RangeFull.sample(source);
233 };
234
235 let offset = if bound.is_power_of_two() {
236 let sample: $unsigned = RangeFull.sample(source);
237 sample & (bound - 1)
238 } else {
239 $bounded(bound as $base, source) as $unsigned
240 };
241
242 self.start.wrapping_add_unsigned(offset)
243 }
244 }
245 };
246}
247
248// Use 32-bit integers for small integers since it reduces the likelihood of
249// sample rejections.
250impl_range!(u8, i8 as u32 => bounded32);
251impl_range!(u16, i16 as u32 => bounded32);
252
253impl_range!(u32, i32 as u32 => bounded32);
254impl_range!(u64, i64 as u64 => bounded64);
255impl_range!(u128, i128 as u128 => bounded128);
256#[cfg(any(target_pointer_width = "16", target_pointer_width = "32",))]
257impl_range!(usize, isize as u32 => bounded32);
258#[cfg(target_pointer_width = "64")]
259impl_range!(usize, isize as u64 => bounded64);