random.rs - source
Skip to main content core/ random.rs 1 //! Random value generation. 2 3 use crate ::range::{ RangeFull , RangeInclusive }; 4 5 /// A source of randomness. 6 #[unstable(feature = "random" , issue = "130703" )] 7 pub 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" )] 20 impl < '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" )] 28 pub 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 33 impl <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 39 impl 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 46 macro_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 61 impl_full! ( u8 ); 62 impl_full! ( i8 ); 63 impl_full! ( u16 ); 64 impl_full! ( i16 ); 65 impl_full! ( u32 ); 66 impl_full! ( i32 ); 67 impl_full! ( u64 ); 68 impl_full! ( i64 ); 69 impl_full! ( u128 ); 70 impl_full! ( i128 ); 71 impl_full! ( usize ); 72 impl_full! ( isize ); 73 74 #[cold] 75 fn empty_range() -> ! { 76 panic! ( "cannot sample from an empty distribution" ) 77 } 78 79 macro_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 112 lemire_sample! (bounded32( u32 )); 113 lemire_sample! (bounded64( u64 )); 114 lemire_sample! (bounded128( u128 )); 115 116 macro_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.wra
The rest of this page is on the live site.