1 //! A tiny, robust PRNG implementation. 2 //! 3 //! More specifically, it implements a single GOOD PRNG algorithm, 4 //! which is currently a permuted congruential generator. It has two 5 //! implementations, one that returns `u32` and one that returns 6 //! `u64`. It also has functions that return floats or integer 7 //! ranges. And that's it. What more do you need? 8 //! 9 //! For more info on PCG generators, see http://www.pcg-random.org/ 10 //! 11 //! This was designed as a minimalist utility for video games. No 12 //! promises are made about its quality, and if you use it for 13 //! cryptography you will get what you deserve. 14 //! 15 //! Works with `#![no_std]`, has no global state, no dependencies 16 //! apart from some in the unit tests, and is generally neato. 17 18 #![forbid(unsafe_code)] 19 #![forbid(missing_docs)] 20 #![forbid(missing_debug_implementations)] 21 #![forbid(unused_results)] 22 #![no_std] 23 use core::ops::Range; 24 25 /// A PRNG producing a 32-bit output. 26 /// 27 /// The current implementation is `PCG-XSH-RR`. 28 #[derive(Copy, Clone, Debug, PartialEq)] 29 pub struct Rand32 { 30 state: u64, 31 inc: u64, 32 } 33 34 impl Rand32 { 35 /// The default value for `increment`. 36 /// This is basically arbitrary, it comes from the 37 /// PCG reference C implementation: 38 /// https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L284 39 pub const DEFAULT_INC: u64 = 1442695040888963407; 40 41 /// This is the number that you have to Really Get Right. 42 /// 43 /// The value used here is from the PCG C implementation: 44 /// https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L278 45 pub(crate) const MULTIPLIER: u64 = 6364136223846793005; 46 47 /// Creates a new PRNG with the given seed and a default increment. new(seed: u64) -> Self48 pub fn new(seed: u64) -> Self { 49 Self::new_inc(seed, Self::DEFAULT_INC) 50 } 51 52 /// Creates a new PRNG. The two inputs, `seed` and `increment`, 53 /// determine what you get; `increment` basically selects which 54 /// sequence of all those possible the PRNG will produce, and the 55 /// `seed` selects where in that sequence you start. 56 /// 57 /// Both are arbitrary; increment must be an odd number but this 58 /// handles that for you new_inc(seed: u64, increment: u64) -> Self59 pub fn new_inc(seed: u64, increment: u64) -> Self { 60 let mut rng = Self { 61 state: 0, 62 inc: increment.wrapping_shl(1) | 1, 63 }; 64 // This initialization song-and-dance is a little odd, 65 // but seems to be just how things go. 66 let _ = rng.rand_u32(); 67 rng.state = rng.state.wrapping_add(seed); 68 let _ = rng.rand_u32(); 69 rng 70 } 71 72 /// Returns the internal state of the PRNG. This allows 73 /// you to save a PRNG and create a new one that will resume 74 /// from the same spot in the sequence. state(&self) -> (u64, u64)75 pub fn state(&self) -> (u64, u64) { 76 (self.state, self.inc) 77 } 78 79 /// Creates a new PRNG from a saved state from `Rand32::state()`. 80 /// This is NOT quite the same as `new_inc()` because `new_inc()` does 81 /// a little extra setup work to initialize the state. from_state(state: (u64, u64)) -> Self82 pub fn from_state(state: (u64, u64)) -> Self { 83 let (state, inc) = state; 84 Self { state, inc } 85 } 86 87 /// Produces a random `u32` in the range `[0, u32::MAX]`. rand_u32(&mut self) -> u3288 pub fn rand_u32(&mut self) -> u32 { 89 let oldstate: u64 = self.state; 90 self.state = oldstate 91 .wrapping_mul(Self::MULTIPLIER) 92 .wrapping_add(self.inc); 93 let xorshifted: u32 = (((oldstate >> 18) ^ oldstate) >> 27) as u32; 94 let rot: u32 = (oldstate >> 59) as u32; 95 xorshifted.rotate_right(rot) 96 } 97 98 /// Produces a random `i32` in the range `[i32::MIN, i32::MAX]`. rand_i32(&mut self) -> i3299 pub fn rand_i32(&mut self) -> i32 { 100 self.rand_u32() as i32 101 } 102 103 /// Produces a random `f32` in the range `[0.0, 1.0)`. rand_float(&mut self) -> f32104 pub fn rand_float(&mut self) -> f32 { 105 // This impl was taken more or less from `rand`, see 106 // <https://docs.rs/rand/0.7.0/src/rand/distributions/float.rs.html#104-117> 107 // There MAY be better ways to do this, see: 108 // https://mumble.net/~campbell/2014/04/28/uniform-random-float 109 // https://mumble.net/~campbell/2014/04/28/random_real.c 110 // https://github.com/Lokathor/randomize/issues/34 111 const TOTAL_BITS: u32 = 32; 112 const PRECISION: u32 = core::f32::MANTISSA_DIGITS + 1; 113 const MANTISSA_SCALE: f32 = 1.0 / ((1u32 << PRECISION) as f32); 114 let mut u = self.rand_u32(); 115 u >>= TOTAL_BITS - PRECISION; 116 u as f32 * MANTISSA_SCALE 117 } 118 119 /// Produces a random within the given bounds. Like any `Range`, 120 /// it includes the lower bound and excludes the upper one. 121 /// 122 /// This should be faster than `Self::rand() % end + start`, but the 123 /// real advantage is it's more convenient. Requires that 124 /// `range.end <= range.start`. rand_range(&mut self, range: Range<u32>) -> u32125 pub fn rand_range(&mut self, range: Range<u32>) -> u32 { 126 // This is harder to do well than it looks, it seems. I don't 127 // trust Lokathor's implementation 'cause I don't understand 128 // it, so I went to numpy's, which points me to "Lemire's 129 // rejection algorithm": http://arxiv.org/abs/1805.10941 130 // 131 // Algorithms 3, 4 and 5 in that paper all seem fine modulo 132 // minor performance differences, so this is algorithm 5. 133 // It uses numpy's implementation, `buffered_bounded_lemire_uint32()` 134 135 debug_assert!(range.start < range.end); 136 let range_starting_from_zero = 0..(range.end - range.start); 137 138 let s: u32 = range_starting_from_zero.end; 139 let mut m: u64 = u64::from(self.rand_u32()) * u64::from(s); 140 let mut leftover: u32 = (m & 0xFFFF_FFFF) as u32; 141 142 if leftover < s { 143 // TODO: verify the wrapping_neg() here 144 let threshold: u32 = s.wrapping_neg() % s; 145 while leftover < threshold { 146 m = u64::from(self.rand_u32()).wrapping_mul(u64::from(s)); 147 leftover = (m & 0xFFFF_FFFF) as u32; 148 } 149 } 150 (m >> 32) as u32 + range.start 151 } 152 } 153 154 /// A PRNG producing a 64-bit output. 155 /// 156 /// The current implementation is `PCG-XSH-RR`. 157 // BUGGO: The recommended algorithm is PCG-XSL-RR? 158 // See https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L2405 159 // Not sure if it matters? 160 #[derive(Copy, Clone, Debug, PartialEq)] 161 pub struct Rand64 { 162 state: u128, 163 inc: u128, 164 } 165 166 impl Rand64 { 167 /// The default value for `increment`. 168 /// 169 /// The value used here is from the PCG default C implementation: http://www.pcg-random.org/download.html 170 pub const DEFAULT_INC: u128 = 0x2FE0E169_FFBD06E3_5BC307BD_4D2F814F; 171 172 /// This is the number that you have to Really Get Right. 173 /// 174 /// The value used here is from the PCG C implementation: 175 /// https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L288 176 pub(crate) const MULTIPLIER: u128 = 47026247687942121848144207491837523525; 177 178 /// Creates a new PRNG with the given seed and a default increment. new(seed: u128) -> Self179 pub fn new(seed: u128) -> Self { 180 Self::new_inc(seed, Self::DEFAULT_INC) 181 } 182 183 /// Same as `Rand32::new_inc()` new_inc(seed: u128, increment: u128) -> Self184 pub fn new_inc(seed: u128, increment: u128) -> Self { 185 let mut rng = Self { 186 state: 0, 187 inc: increment.wrapping_shl(1) | 1, 188 }; 189 let _ = rng.rand_u64(); 190 rng.state = rng.state.wrapping_add(seed); 191 let _ = rng.rand_u64(); 192 rng 193 } 194 195 /// Returns the internal state of the PRNG. This allows 196 /// you to save a PRNG and create a new one that will resume 197 /// from the same spot in the sequence. state(&self) -> (u128, u128)198 pub fn state(&self) -> (u128, u128) { 199 (self.state, self.inc) 200 } 201 202 /// Creates a new PRNG from a saved state from `Rand32::state()`. 203 /// This is NOT quite the same as `new_inc()` because `new_inc()` does 204 /// a little extra setup work to initialize the state. from_state(state: (u128, u128)) -> Self205 pub fn from_state(state: (u128, u128)) -> Self { 206 let (state, inc) = state; 207 Self { state, inc } 208 } 209 210 /// Produces a random `u64` in the range`[0, u64::MAX]`. rand_u64(&mut self) -> u64211 pub fn rand_u64(&mut self) -> u64 { 212 let oldstate: u128 = self.state; 213 self.state = oldstate 214 .wrapping_mul(Self::MULTIPLIER) 215 .wrapping_add(self.inc); 216 let xorshifted: u64 = (((oldstate >> 29) ^ oldstate) >> 58) as u64; 217 let rot: u32 = (oldstate >> 122) as u32; 218 xorshifted.rotate_right(rot) 219 } 220 221 /// Produces a random `i64` in the range `[i64::MIN, i64::MAX]`. rand_i64(&mut self) -> i64222 pub fn rand_i64(&mut self) -> i64 { 223 self.rand_u64() as i64 224 } 225 226 /// Produces a random `f64` in the range `[0.0, 1.0)`. rand_float(&mut self) -> f64227 pub fn rand_float(&mut self) -> f64 { 228 const TOTAL_BITS: u32 = 64; 229 const PRECISION: u32 = core::f64::MANTISSA_DIGITS + 1; 230 const MANTISSA_SCALE: f64 = 1.0 / ((1u64 << PRECISION) as f64); 231 let mut u = self.rand_u64(); 232 u >>= TOTAL_BITS - PRECISION; 233 u as f64 * MANTISSA_SCALE 234 } 235 236 /// Produces a random within the given bounds. Like any `Range`, 237 /// it includes the lower bound and excludes the upper one. 238 /// 239 /// This should be faster than `Self::rand() % end + start`, but the 240 /// real advantage is it's more convenient. Requires that 241 /// `range.end <= range.start`. rand_range(&mut self, range: Range<u64>) -> u64242 pub fn rand_range(&mut self, range: Range<u64>) -> u64 { 243 // Same as `Rand32::rand_range()` 244 debug_assert!(range.start < range.end); 245 let range_starting_from_zero = 0..(range.end - range.start); 246 247 let s: u64 = range_starting_from_zero.end; 248 let mut m: u128 = u128::from(self.rand_u64()) * u128::from(s); 249 let mut leftover: u64 = (m & 0xFFFFFFFF_FFFFFFFF) as u64; 250 251 if leftover < s { 252 // TODO: Verify the wrapping_negate() here 253 let threshold: u64 = s.wrapping_neg() % s; 254 while leftover < threshold { 255 m = u128::from(self.rand_u64()) * u128::from(s); 256 leftover = (m & 0xFFFFFFFF_FFFFFFFF) as u64; 257 } 258 } 259 (m.wrapping_shr(64)) as u64 + range.start 260 } 261 } 262 263 #[cfg(test)] 264 mod tests { 265 use super::*; 266 use randomize::{self, PCG32, PCG64}; 267 268 #[test] test_rand32_vs_randomize()269 fn test_rand32_vs_randomize() { 270 // Generate some random numbers and validate them against 271 // a known-good generator. 272 { 273 let seed = 54321; 274 let mut r1 = Rand32::new(seed); 275 let mut r2 = PCG32::seed(seed, Rand32::DEFAULT_INC); 276 for _ in 0..1000 { 277 assert_eq!(r1.rand_u32(), r2.next_u32()); 278 assert_eq!(r1.rand_i32(), r2.next_u32() as i32); 279 } 280 } 281 282 { 283 let seed = 3141592653; 284 let inc = 0xDEADBEEF; 285 let mut r1 = Rand32::new_inc(seed, inc); 286 let mut r2 = PCG32::seed(seed, inc); 287 for _ in 0..1000 { 288 assert_eq!(r1.rand_u32(), r2.next_u32()); 289 assert_eq!(r1.rand_i32(), r2.next_u32() as i32); 290 } 291 } 292 } 293 294 #[test] test_rand64_vs_randomize()295 fn test_rand64_vs_randomize() { 296 // Generate some random numbers and validate them against 297 // a known-good generator. 298 { 299 let seed = 54321; 300 let mut r1 = Rand64::new(seed); 301 let mut r2 = PCG64::seed(seed, Rand64::DEFAULT_INC); 302 for _ in 0..1000 { 303 assert_eq!(r1.rand_u64(), r2.next_u64()); 304 assert_eq!(r1.rand_i64(), r2.next_u64() as i64); 305 } 306 } 307 308 { 309 let seed = 3141592653; 310 let inc = 0xDEADBEEF; 311 let mut r1 = Rand64::new_inc(seed, inc); 312 let mut r2 = PCG64::seed(seed, inc); 313 for _ in 0..1000 { 314 assert_eq!(r1.rand_u64(), r2.next_u64()); 315 assert_eq!(r1.rand_i64(), r2.next_u64() as i64); 316 } 317 } 318 } 319 320 #[test] test_float32()321 fn test_float32() { 322 { 323 let seed = 2718281828; 324 let mut r1 = Rand32::new(seed); 325 let mut r2 = PCG32::seed(seed, Rand32::DEFAULT_INC); 326 for _ in 0..1000 { 327 // First just make sure they both work with randomize's 328 // f32 conversion function -- sanity checks. 329 let i1 = r1.rand_u32(); 330 let i2 = r2.next_u32(); 331 assert_eq!(i1, i2); 332 let f1 = randomize::f32_half_open_right(i1); 333 let f2 = randomize::f32_half_open_right(i2); 334 // We can directly compare floats 'cause we do no math, it's 335 // literally the same bitwise algorithm with the same inputs. 336 assert_eq!(f1, f2); 337 338 // Make sure result is in [0.0, 1.0) 339 assert!(f1 >= 0.0); 340 assert!(f1 < 1.0); 341 } 342 343 // At least make sure our float's from rand_float() are in the valid range. 344 for _ in 0..1000 { 345 let f1 = r1.rand_float(); 346 assert!(f1 >= 0.0); 347 assert!(f1 < 1.0); 348 } 349 350 /* 351 TODO: Randomize changed its int-to-float conversion functions and now they don't 352 match ours. 353 for _ in 0..1000 { 354 // Now make sure our own float conversion function works. 355 let f1 = r1.rand_float(); 356 //let f2 = randomize::f32_half_open_right(r2.next_u32()); 357 let f2 = randomize::f32_open(r2.next_u32()); 358 assert_eq!(f1, f2); 359 assert!(f1 >= 0.0); 360 assert!(f1 < 1.0); 361 } 362 */ 363 } 364 } 365 366 #[test] test_float64()367 fn test_float64() { 368 { 369 let seed = 2718281828; 370 let mut r1 = Rand64::new(seed); 371 let mut r2 = PCG64::seed(seed, Rand64::DEFAULT_INC); 372 for _ in 0..1000 { 373 // First just make sure they both work with randomize's 374 // f64 conversion function -- sanity checks. 375 let i1 = r1.rand_u64(); 376 let i2 = r2.next_u64(); 377 assert_eq!(i1, i2); 378 let f1 = randomize::f64_half_open_right(i1); 379 let f2 = randomize::f64_half_open_right(i2); 380 // We can directly compare floats 'cause we do no math, it's 381 // literally the same bitwise algorithm with the same inputs. 382 assert_eq!(f1, f2); 383 384 // Make sure result is in [0.0, 1.0) 385 assert!(f1 >= 0.0); 386 assert!(f1 < 1.0); 387 } 388 389 // At least make sure our float's from rand_float() are in the valid range. 390 for _ in 0..1000 { 391 let f1 = r1.rand_float(); 392 assert!(f1 >= 0.0); 393 assert!(f1 < 1.0); 394 } 395 396 /* 397 TODO: Randomize changed its int-to-float conversion functions and now they don't 398 match ours. 399 for _ in 0..1000 { 400 // Now make sure our own float conversion function works. 401 let f1 = r1.rand_float(); 402 //let f2 = randomize::f32_half_open_right(r2.next_u32()); 403 let f2 = randomize::f32_open(r2.next_u32()); 404 assert_eq!(f1, f2); 405 assert!(f1 >= 0.0); 406 assert!(f1 < 1.0); 407 } 408 */ 409 } 410 } 411 412 #[test] test_randrange32()413 fn test_randrange32() { 414 // Make sure ranges are valid and in the given range 415 let seed = 2342_3141; 416 let mut r1 = Rand32::new(seed); 417 for _ in 0..1000 { 418 // Generate our bounds at random 419 let a = r1.rand_u32(); 420 let b = r1.rand_u32(); 421 if a == b { 422 continue; 423 } 424 let (low, high) = if a < b { (a, b) } else { (b, a) }; 425 426 // Get a number in that range 427 let in_range = r1.rand_range(low..high); 428 assert!(in_range >= low); 429 assert!(in_range < high); 430 } 431 } 432 433 #[test] test_randrange64()434 fn test_randrange64() { 435 // Make sure ranges are valid and in the given range 436 let seed = 2342_2718; 437 let mut r1 = Rand64::new(seed); 438 for _ in 0..1000 { 439 // Generate our bounds at random 440 let a = r1.rand_u64(); 441 let b = r1.rand_u64(); 442 if a == b { 443 continue; 444 } 445 let (low, high) = if a < b { (a, b) } else { (b, a) }; 446 447 // Get a number in that range 448 let in_range = r1.rand_range(low..high); 449 assert!(in_range >= low); 450 assert!(in_range < high); 451 } 452 } 453 454 #[test] test_rand32_vs_rand()455 fn test_rand32_vs_rand() { 456 use rand_core::RngCore; 457 use rand_pcg; 458 { 459 let seed = 54321; 460 let mut r1 = Rand32::new(seed); 461 let mut r2 = rand_pcg::Pcg32::new(seed, Rand32::DEFAULT_INC); 462 for _ in 0..1000 { 463 assert_eq!(r1.rand_u32(), r2.next_u32()); 464 } 465 } 466 467 { 468 let seed = 3141592653; 469 let inc = 0xDEADBEEF; 470 let mut r1 = Rand32::new_inc(seed, inc); 471 let mut r2 = rand_pcg::Pcg32::new(seed, inc); 472 for _ in 0..1000 { 473 assert_eq!(r1.rand_u32(), r2.next_u32()); 474 } 475 } 476 } 477 478 // This doesn't work 'cause for 64-bit output `rand` uses 479 // PCG-XSL-RR 480 // and we use 481 // PCG-XSH-RR 482 /* 483 #[test] 484 fn test_rand64_vs_rand() { 485 use rand_pcg; 486 use rand_core::RngCore; 487 { 488 let seed = 54321; 489 let mut r1 = Rand64::new(seed); 490 let mut r2 = rand_pcg::Pcg64::new(seed, Rand64::DEFAULT_INC); 491 for _ in 0..1000 { 492 assert_eq!(r1.rand(), r2.next_u64()); 493 } 494 } 495 496 { 497 let seed = 3141592653; 498 let inc = 0xDEADBEEF; 499 let mut r1 = Rand64::new_inc(seed, inc); 500 let mut r2 = rand_pcg::Pcg64::new(seed, inc); 501 for _ in 0..1000 { 502 assert_eq!(r1.rand(), r2.next_u64()); 503 } 504 } 505 } 506 */ 507 508 // Test vs. random-fast-rng, which I will call rfr 509 // rfr's float conversion uses yet a different algorithm 510 // than ours, so we can't really check that. 511 #[test] test_rand32_vs_rfr()512 fn test_rand32_vs_rfr() { 513 use random_fast_rng as rfr; 514 use rfr::Random; 515 { 516 let seed = 54321; 517 let mut r1 = Rand32::new(seed); 518 let mut r2 = rfr::FastRng::seed(seed, Rand32::DEFAULT_INC); 519 for _ in 0..1000 { 520 assert_eq!(r1.rand_u32(), r2.get_u32()); 521 } 522 } 523 524 { 525 let seed = 3141592653; 526 let inc = 0xDEADBEEF; 527 let mut r1 = Rand32::new_inc(seed, inc); 528 let mut r2 = rfr::FastRng::seed(seed, inc); 529 for _ in 0..1000 { 530 assert_eq!(r1.rand_u32(), r2.get_u32()); 531 } 532 } 533 } 534 535 /// Make sure that saving a RNG state and restoring 536 /// it works. 537 /// See https://todo.sr.ht/~icefox/oorandom/1 538 #[test] test_save_restore()539 fn test_save_restore() { 540 { 541 let seed = 54321; 542 let mut r1 = Rand32::new(seed); 543 let s1 = r1.state(); 544 let mut r2 = Rand32::from_state(s1); 545 assert_eq!(r1, r2); 546 for _ in 0..1000 { 547 assert_eq!(r1.rand_u32(), r2.rand_u32()); 548 } 549 } 550 551 { 552 let seed = 3141592653; 553 let inc = 0xDEADBEEF; 554 let mut r1 = Rand32::new_inc(seed, inc); 555 let s1 = r1.state(); 556 let mut r2 = Rand32::from_state(s1); 557 assert_eq!(r1, r2); 558 for _ in 0..1000 { 559 assert_eq!(r1.rand_u32(), r2.rand_u32()); 560 } 561 } 562 563 { 564 let seed = 54321; 565 let mut r1 = Rand64::new(seed); 566 let s1 = r1.state(); 567 let mut r2 = Rand64::from_state(s1); 568 assert_eq!(r1, r2); 569 for _ in 0..1000 { 570 assert_eq!(r1.rand_u64(), r2.rand_u64()); 571 } 572 } 573 574 { 575 let seed = 3141592653; 576 let inc = 0xDEADBEEF; 577 let mut r1 = Rand64::new_inc(seed, inc); 578 let s1 = r1.state(); 579 let mut r2 = Rand64::from_state(s1); 580 assert_eq!(r1, r2); 581 for _ in 0..1000 { 582 assert_eq!(r1.rand_u64(), r2.rand_u64()); 583 } 584 } 585 } 586 } 587