1/* 2 * ***************************************************************************** 3 * 4 * Parts of this code are adapted from the following: 5 * 6 * PCG, A Family of Better Random Number Generators. 7 * 8 * You can find the original source code at: 9 * https://github.com/imneme/pcg-c 10 * 11 * ----------------------------------------------------------------------------- 12 * 13 * This code is under the following license: 14 * 15 * Copyright (c) 2014-2017 Melissa O'Neill and PCG Project contributors 16 * Copyright (c) 2018-2023 Gavin D. Howard and contributors. 17 * 18 * Permission is hereby granted, free of charge, to any person obtaining a copy 19 * of this software and associated documentation files (the "Software"), to deal 20 * in the Software without restriction, including without limitation the rights 21 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 22 * copies of the Software, and to permit persons to whom the Software is 23 * furnished to do so, subject to the following conditions: 24 * 25 * The above copyright notice and this permission notice shall be included in 26 * all copies or substantial portions of the Software. 27 * 28 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 29 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 30 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 31 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 32 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 33 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 34 * SOFTWARE. 35 * 36 * ***************************************************************************** 37 * 38 * Code for the RNG. 39 * 40 */ 41 42#include <assert.h> 43#include <stdlib.h> 44#include <string.h> 45#include <time.h> 46#include <fcntl.h> 47 48#ifndef _WIN32 49#include <unistd.h> 50#else // _WIN32 51#include <Windows.h> 52#include <bcrypt.h> 53#endif // _WIN32 54 55#include <status.h> 56#include <rand.h> 57#include <vm.h> 58 59#if BC_ENABLE_EXTRA_MATH 60 61#if !BC_RAND_BUILTIN 62 63/** 64 * Adds two 64-bit values and preserves the overflow. 65 * @param a The first operand. 66 * @param b The second operand. 67 * @return The sum, including overflow. 68 */ 69static BcRandState 70bc_rand_addition(uint_fast64_t a, uint_fast64_t b) 71{ 72 BcRandState res; 73 74 res.lo = a + b; 75 res.hi = (res.lo < a); 76 77 return res; 78} 79 80/** 81 * Adds two 128-bit values and discards the overflow. 82 * @param a The first operand. 83 * @param b The second operand. 84 * @return The sum, without overflow. 85 */ 86static BcRandState 87bc_rand_addition2(BcRandState a, BcRandState b) 88{ 89 BcRandState temp, res; 90 91 res = bc_rand_addition(a.lo, b.lo); 92 temp = bc_rand_addition(a.hi, b.hi); 93 res.hi += temp.lo; 94 95 return res; 96} 97 98/** 99 * Multiplies two 64-bit values and preserves the overflow. 100 * @param a The first operand. 101 * @param b The second operand. 102 * @return The product, including overflow. 103 */ 104static BcRandState 105bc_rand_multiply(uint_fast64_t a, uint_fast64_t b) 106{ 107 uint_fast64_t al, ah, bl, bh, c0, c1, c2, c3; 108 BcRandState carry, res; 109 110 al = BC_RAND_TRUNC32(a); 111 ah = BC_RAND_CHOP32(a); 112 bl = BC_RAND_TRUNC32(b); 113 bh = BC_RAND_CHOP32(b); 114 115 c0 = al * bl; 116 c1 = al * bh; 117 c2 = ah * bl; 118 c3 = ah * bh; 119 120 carry = bc_rand_addition(c1, c2); 121 122 res = bc_rand_addition(c0, (BC_RAND_TRUNC32(carry.lo)) << 32); 123 res.hi += BC_RAND_CHOP32(carry.lo) + c3 + (carry.hi << 32); 124 125 return res; 126} 127 128/** 129 * Multiplies two 128-bit values and discards the overflow. 130 * @param a The first operand. 131 * @param b The second operand. 132 * @return The product, without overflow. 133 */ 134static BcRandState 135bc_rand_multiply2(BcRandState a, BcRandState b) 136{ 137 BcRandState c0, c1, c2, carry; 138 139 c0 = bc_rand_multiply(a.lo, b.lo); 140 c1 = bc_rand_multiply(a.lo, b.hi); 141 c2 = bc_rand_multiply(a.hi, b.lo); 142 143 carry = bc_rand_addition2(c1, c2); 144 carry.hi = carry.lo; 145 carry.lo = 0; 146 147 return bc_rand_addition2(c0, carry); 148} 149 150#endif // BC_RAND_BUILTIN 151 152/** 153 * Marks a PRNG as modified. This is important for properly maintaining the 154 * stack of PRNG's. 155 * @param r The PRNG to mark as modified. 156 */ 157static void 158bc_rand_setModified(BcRNGData* r) 159{ 160#if BC_RAND_BUILTIN 161 r->inc |= (BcRandState) 1UL; 162#else // BC_RAND_BUILTIN 163 r->inc.lo |= (uint_fast64_t) 1UL; 164#endif // BC_RAND_BUILTIN 165} 166 167/** 168 * Marks a PRNG as not modified. This is important for properly maintaining the 169 * stack of PRNG's. 170 * @param r The PRNG to mark as not modified. 171 */ 172static void 173bc_rand_clearModified(BcRNGData* r) 174{ 175#if BC_RAND_BUILTIN 176 r->inc &= ~((BcRandState) 1UL); 177#else // BC_RAND_BUILTIN 178 r->inc.lo &= ~(1UL); 179#endif // BC_RAND_BUILTIN 180} 181 182/** 183 * Copies a PRNG to another and marks the copy as modified if it already was or 184 * marks it modified if it already was. 185 * @param d The destination PRNG. 186 * @param s The source PRNG. 187 */ 188static void 189bc_rand_copy(BcRNGData* d, BcRNGData* s) 190{ 191 bool unmod = BC_RAND_NOTMODIFIED(d); 192 193 // NOLINTNEXTLINE 194 memcpy(d, s, sizeof(BcRNGData)); 195 196 if (!unmod) bc_rand_setModified(d); 197 else if (!BC_RAND_NOTMODIFIED(s)) bc_rand_clearModified(d); 198} 199 200#ifndef _WIN32 201 202/** 203 * Reads random data from a file. 204 * @param ptr A pointer to the file, as a void pointer. 205 * @return The random data as an unsigned long. 206 */ 207static ulong 208bc_rand_frand(void* ptr) 209{ 210 ulong buf[1]; 211 int fd; 212 ssize_t nread; 213 214 assert(ptr != NULL); 215 216 fd = *((int*) ptr); 217 218 nread = read(fd, buf, sizeof(ulong)); 219 220 if (BC_ERR(nread != sizeof(ulong))) bc_vm_fatalError(BC_ERR_FATAL_IO_ERR); 221 222 return *((ulong*) buf); 223} 224#else // _WIN32 225 226/** 227 * Reads random data from BCryptGenRandom(). 228 * @param ptr An unused parameter. 229 * @return The random data as an unsigned long. 230 */ 231static ulong 232bc_rand_winrand(void* ptr) 233{ 234 ulong buf[1]; 235 NTSTATUS s; 236 237 BC_UNUSED(ptr); 238 239 buf[0] = 0; 240 241 s = BCryptGenRandom(NULL, (char*) buf, sizeof(ulong), 242 BCRYPT_USE_SYSTEM_PREFERRED_RNG); 243 244 if (BC_ERR(!BCRYPT_SUCCESS(s))) buf[0] = 0; 245 246 return buf[0]; 247} 248#endif // _WIN32 249 250/** 251 * Reads random data from rand(), byte-by-byte because rand() is only guaranteed 252 * to return 15 bits of random data. This is the final fallback and is not 253 * preferred as it is possible to access cryptographically-secure PRNG's on most 254 * systems. 255 * @param ptr An unused parameter. 256 * @return The random data as an unsigned long. 257 */ 258static ulong 259bc_rand_rand(void* ptr) 260{ 261 size_t i; 262 ulong res = 0; 263 264 BC_UNUSED(ptr); 265 266 // Fill up the unsigned long byte-by-byte. 267 for (i = 0; i < sizeof(ulong); ++i) 268 { 269 res |= ((ulong) (rand() & BC_RAND_SRAND_BITS)) << (i * CHAR_BIT); 270 } 271 272 return res; 273} 274 275/** 276 * Returns the actual increment of the PRNG, including the required last odd 277 * bit. 278 * @param r The PRNG. 279 * @return The increment of the PRNG, including the last odd bit. 280 */ 281static BcRandState 282bc_rand_inc(BcRNGData* r) 283{ 284 BcRandState inc; 285 286#if BC_RAND_BUILTIN 287 inc = r->inc | 1; 288#else // BC_RAND_BUILTIN 289 inc.lo = r->inc.lo | 1; 290 inc.hi = r->inc.hi; 291#endif // BC_RAND_BUILTIN 292 293 return inc; 294} 295 296/** 297 * Sets up the increment for the PRNG. 298 * @param r The PRNG whose increment will be set up. 299 */ 300static void 301bc_rand_setupInc(BcRNGData* r) 302{ 303#if BC_RAND_BUILTIN 304 r->inc <<= 1UL; 305#else // BC_RAND_BUILTIN 306 r->inc.hi <<= 1UL; 307 r->inc.hi |= (r->inc.lo & (1UL << (BC_LONG_BIT - 1))) >> (BC_LONG_BIT - 1); 308 r->inc.lo <<= 1UL; 309#endif // BC_RAND_BUILTIN 310} 311 312/** 313 * Seeds the state of a PRNG. 314 * @param state The return parameter; the state to seed. 315 * @param val1 The lower half of the state. 316 * @param val2 The upper half of the state. 317 */ 318static void 319bc_rand_seedState(BcRandState* state, ulong val1, ulong val2) 320{ 321#if BC_RAND_BUILTIN 322 *state = ((BcRandState) val1) | ((BcRandState) val2) << (BC_LONG_BIT); 323#else // BC_RAND_BUILTIN 324 state->lo = val1; 325 state->hi = val2; 326#endif // BC_RAND_BUILTIN 327} 328 329/** 330 * Seeds a PRNG. 331 * @param r The return parameter; the PRNG to seed. 332 * @param state1 The lower half of the state. 333 * @param state2 The upper half of the state. 334 * @param inc1 The lower half of the increment. 335 * @param inc2 The upper half of the increment. 336 */ 337static void 338bc_rand_seedRNG(BcRNGData* r, ulong state1, ulong state2, ulong inc1, 339 ulong inc2) 340{ 341 bc_rand_seedState(&r->state, state1, state2); 342 bc_rand_seedState(&r->inc, inc1, inc2); 343 bc_rand_setupInc(r); 344} 345 346/** 347 * Fills a PRNG with random data to seed it. 348 * @param r The PRNG. 349 * @param fulong The function to fill an unsigned long. 350 * @param ptr The parameter to pass to @a fulong. 351 */ 352static void 353bc_rand_fill(BcRNGData* r, BcRandUlong fulong, void* ptr) 354{ 355 ulong state1, state2, inc1, inc2; 356 357 state1 = fulong(ptr); 358 state2 = fulong(ptr); 359 360 inc1 = fulong(ptr); 361 inc2 = fulong(ptr); 362 363 bc_rand_seedRNG(r, state1, state2, inc1, inc2); 364} 365 366/** 367 * Executes the "step" portion of a PCG udpate. 368 * @param r The PRNG. 369 */ 370static void 371bc_rand_step(BcRNGData* r) 372{ 373 BcRandState temp = bc_rand_mul2(r->state, bc_rand_multiplier); 374 r->state = bc_rand_add2(temp, bc_rand_inc(r)); 375} 376 377/** 378 * Returns the new output of PCG. 379 * @param r The PRNG. 380 * @return The new output from the PRNG. 381 */ 382static BcRand 383bc_rand_output(BcRNGData* r) 384{ 385 return BC_RAND_ROT(BC_RAND_FOLD(r->state), BC_RAND_ROTAMT(r->state)); 386} 387 388/** 389 * Seeds every PRNG on the PRNG stack between the top and @a idx that has not 390 * been seeded. 391 * @param r The PRNG stack. 392 * @param rng The PRNG on the top of the stack. Must have been seeded. 393 */ 394static void 395bc_rand_seedZeroes(BcRNG* r, BcRNGData* rng, size_t idx) 396{ 397 BcRNGData* rng2; 398 399 // Just return if there are none to do. 400 if (r->v.len <= idx) return; 401 402 // Get the first PRNG that might need to be seeded. 403 rng2 = bc_vec_item_rev(&r->v, idx); 404 405 // Does it need seeding? Then it, and maybe more, do. 406 if (BC_RAND_ZERO(rng2)) 407 { 408 size_t i; 409 410 // Seed the ones that need seeding. 411 for (i = 1; i < r->v.len; ++i) 412 { 413 bc_rand_copy(bc_vec_item_rev(&r->v, i), rng); 414 } 415 } 416} 417 418void 419bc_rand_srand(BcRNGData* rng) 420{ 421 int fd = 0; 422 423 BC_SIG_LOCK; 424 425#ifndef _WIN32 426 427 // Try /dev/urandom first. 428 fd = open("/dev/urandom", O_RDONLY); 429 430 if (BC_NO_ERR(fd >= 0)) 431 { 432 bc_rand_fill(rng, bc_rand_frand, &fd); 433 close(fd); 434 } 435 else 436 { 437 // Try /dev/random second. 438 fd = open("/dev/random", O_RDONLY); 439 440 if (BC_NO_ERR(fd >= 0)) 441 { 442 bc_rand_fill(rng, bc_rand_frand, &fd); 443 close(fd); 444 } 445 } 446#else // _WIN32 447 // Try BCryptGenRandom first. 448 bc_rand_fill(rng, bc_rand_winrand, NULL); 449#endif // _WIN32 450 451 // Fallback to rand() until the thing is seeded. 452 while (BC_ERR(BC_RAND_ZERO(rng))) 453 { 454 bc_rand_fill(rng, bc_rand_rand, NULL); 455 } 456 457 BC_SIG_UNLOCK; 458} 459 460/** 461 * Propagates a change to the PRNG to all PRNG's in the stack that should have 462 * it. The ones that should have it are laid out in the manpages. 463 * @param r The PRNG stack. 464 * @param rng The PRNG that will be used to seed the others. 465 */ 466static void 467bc_rand_propagate(BcRNG* r, BcRNGData* rng) 468{ 469 // Just return if there are none to do. 470 if (r->v.len <= 1) return; 471 472 // If the PRNG has not been modified... 473 if (BC_RAND_NOTMODIFIED(rng)) 474 { 475 size_t i; 476 bool go = true; 477 478 // Find the first PRNG that is modified and seed the others. 479 for (i = 1; go && i < r->v.len; ++i) 480 { 481 BcRNGData* rng2 = bc_vec_item_rev(&r->v, i); 482 483 go = BC_RAND_NOTMODIFIED(rng2); 484 485 bc_rand_copy(rng2, rng); 486 } 487 488 // Seed everything else. 489 bc_rand_seedZeroes(r, rng, i); 490 } 491 // Seed everything. 492 else bc_rand_seedZeroes(r, rng, 1); 493} 494 495BcRand 496bc_rand_int(BcRNG* r) 497{ 498 // Get the actual PRNG. 499 BcRNGData* rng = bc_vec_top(&r->v); 500 BcRand res; 501 502 // Make sure the PRNG is seeded. 503 if (BC_ERR(BC_RAND_ZERO(rng))) bc_rand_srand(rng); 504 505 BC_SIG_LOCK; 506 507 // This is the important part of the PRNG. This is the stuff from PCG. 508 bc_rand_step(rng); 509 bc_rand_propagate(r, rng); 510 res = bc_rand_output(rng); 511 512 BC_SIG_UNLOCK; 513 514 return res; 515} 516 517BcRand 518bc_rand_bounded(BcRNG* r, BcRand bound) 519{ 520 BcRand rand; 521 BcRand threshold; 522 523 // Calculate the threshold below which we have to try again. 524 threshold = (0 - bound) % bound; 525 526 do 527 { 528 rand = bc_rand_int(r); 529 } 530 while (rand < threshold); 531 532 return rand % bound; 533} 534 535void 536bc_rand_seed(BcRNG* r, ulong state1, ulong state2, ulong inc1, ulong inc2) 537{ 538 // Get the actual PRNG. 539 BcRNGData* rng = bc_vec_top(&r->v); 540 541 // Seed and set up the PRNG's increment. 542 bc_rand_seedState(&rng->inc, inc1, inc2); 543 bc_rand_setupInc(rng); 544 bc_rand_setModified(rng); 545 546 // If the state is 0, use the increment as the state. Otherwise, seed it 547 // with the state. 548 if (!state1 && !state2) 549 { 550 // NOLINTNEXTLINE 551 memcpy(&rng->state, &rng->inc, sizeof(BcRandState)); 552 bc_rand_step(rng); 553 } 554 else bc_rand_seedState(&rng->state, state1, state2); 555 556 // Propagate the change to PRNG's that need it. 557 bc_rand_propagate(r, rng); 558} 559 560/** 561 * Returns the increment in the PRNG *without* the odd bit and also with being 562 * shifted one bit down. 563 * @param r The PRNG. 564 * @return The increment without the odd bit and with being shifted one bit 565 * down. 566 */ 567static BcRandState 568bc_rand_getInc(BcRNGData* r) 569{ 570 BcRandState res; 571 572#if BC_RAND_BUILTIN 573 res = r->inc >> 1; 574#else // BC_RAND_BUILTIN 575 res = r->inc; 576 res.lo >>= 1; 577 res.lo |= (res.hi & 1) << (BC_LONG_BIT - 1); 578 res.hi >>= 1; 579#endif // BC_RAND_BUILTIN 580 581 return res; 582} 583 584void 585bc_rand_getRands(BcRNG* r, BcRand* s1, BcRand* s2, BcRand* i1, BcRand* i2) 586{ 587 BcRandState inc; 588 BcRNGData* rng = bc_vec_top(&r->v); 589 590 if (BC_ERR(BC_RAND_ZERO(rng))) bc_rand_srand(rng); 591 592 // Get the increment. 593 inc = bc_rand_getInc(rng); 594 595 // Chop the state. 596 *s1 = BC_RAND_TRUNC(rng->state); 597 *s2 = BC_RAND_CHOP(rng->state); 598 599 // Chop the increment. 600 *i1 = BC_RAND_TRUNC(inc); 601 *i2 = BC_RAND_CHOP(inc); 602} 603 604void 605bc_rand_push(BcRNG* r) 606{ 607 BcRNGData* rng = bc_vec_pushEmpty(&r->v); 608 609 // Make sure the PRNG is properly zeroed because that marks it as needing to 610 // be seeded. 611 // NOLINTNEXTLINE 612 memset(rng, 0, sizeof(BcRNGData)); 613 614 // If there is another item, copy it too. 615 if (r->v.len > 1) bc_rand_copy(rng, bc_vec_item_rev(&r->v, 1)); 616} 617 618void 619bc_rand_pop(BcRNG* r, bool reset) 620{ 621 bc_vec_npop(&r->v, reset ? r->v.len - 1 : 1); 622} 623 624void 625bc_rand_init(BcRNG* r) 626{ 627 BC_SIG_ASSERT_LOCKED; 628 bc_vec_init(&r->v, sizeof(BcRNGData), BC_DTOR_NONE); 629 bc_rand_push(r); 630} 631 632#if BC_RAND_USE_FREE 633void 634bc_rand_free(BcRNG* r) 635{ 636 BC_SIG_ASSERT_LOCKED; 637 bc_vec_free(&r->v); 638} 639#endif // BC_RAND_USE_FREE 640 641#endif // BC_ENABLE_EXTRA_MATH 642