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