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-2021 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 */ 69 static BcRandState 70 bc_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 */ 86 static BcRandState 87 bc_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 */ 104 static BcRandState 105 bc_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 */ 134 static BcRandState 135 bc_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 */ 157 static void 158 bc_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 */ 172 static void 173 bc_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 */ 188 static void 189 bc_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 */ 207 static ulong 208 bc_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 */ 231 static ulong 232 bc_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 */ 258 static ulong 259 bc_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 */ 281 static BcRandState 282 bc_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 */ 300 static void 301 bc_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 */ 318 static void 319 bc_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 */ 337 static void 338 bc_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 */ 352 static void 353 bc_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 */ 370 static void 371 bc_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 */ 382 static BcRand 383 bc_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 */ 394 static void 395 bc_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 418 void 419 bc_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 */ 466 static void 467 bc_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 495 BcRand 496 bc_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 517 BcRand 518 bc_rand_bounded(BcRNG* r, BcRand bound) 519 { 520 // Calculate the threshold below which we have to try again. 521 BcRand rand, threshold = (0 - bound) % bound; 522 523 do 524 { 525 rand = bc_rand_int(r); 526 } 527 while (rand < threshold); 528 529 return rand % bound; 530 } 531 532 void 533 bc_rand_seed(BcRNG* r, ulong state1, ulong state2, ulong inc1, ulong inc2) 534 { 535 // Get the actual PRNG. 536 BcRNGData* rng = bc_vec_top(&r->v); 537 538 // Seed and set up the PRNG's increment. 539 bc_rand_seedState(&rng->inc, inc1, inc2); 540 bc_rand_setupInc(rng); 541 bc_rand_setModified(rng); 542 543 // If the state is 0, use the increment as the state. Otherwise, seed it 544 // with the state. 545 if (!state1 && !state2) 546 { 547 // NOLINTNEXTLINE 548 memcpy(&rng->state, &rng->inc, sizeof(BcRandState)); 549 bc_rand_step(rng); 550 } 551 else bc_rand_seedState(&rng->state, state1, state2); 552 553 // Propagate the change to PRNG's that need it. 554 bc_rand_propagate(r, rng); 555 } 556 557 /** 558 * Returns the increment in the PRNG *without* the odd bit and also with being 559 * shifted one bit down. 560 * @param r The PRNG. 561 * @return The increment without the odd bit and with being shifted one bit 562 * down. 563 */ 564 static BcRandState 565 bc_rand_getInc(BcRNGData* r) 566 { 567 BcRandState res; 568 569 #if BC_RAND_BUILTIN 570 res = r->inc >> 1; 571 #else // BC_RAND_BUILTIN 572 res = r->inc; 573 res.lo >>= 1; 574 res.lo |= (res.hi & 1) << (BC_LONG_BIT - 1); 575 res.hi >>= 1; 576 #endif // BC_RAND_BUILTIN 577 578 return res; 579 } 580 581 void 582 bc_rand_getRands(BcRNG* r, BcRand* s1, BcRand* s2, BcRand* i1, BcRand* i2) 583 { 584 BcRandState inc; 585 BcRNGData* rng = bc_vec_top(&r->v); 586 587 if (BC_ERR(BC_RAND_ZERO(rng))) bc_rand_srand(rng); 588 589 // Get the increment. 590 inc = bc_rand_getInc(rng); 591 592 // Chop the state. 593 *s1 = BC_RAND_TRUNC(rng->state); 594 *s2 = BC_RAND_CHOP(rng->state); 595 596 // Chop the increment. 597 *i1 = BC_RAND_TRUNC(inc); 598 *i2 = BC_RAND_CHOP(inc); 599 } 600 601 void 602 bc_rand_push(BcRNG* r) 603 { 604 BcRNGData* rng = bc_vec_pushEmpty(&r->v); 605 606 // Make sure the PRNG is properly zeroed because that marks it as needing to 607 // be seeded. 608 // NOLINTNEXTLINE 609 memset(rng, 0, sizeof(BcRNGData)); 610 611 // If there is another item, copy it too. 612 if (r->v.len > 1) bc_rand_copy(rng, bc_vec_item_rev(&r->v, 1)); 613 } 614 615 void 616 bc_rand_pop(BcRNG* r, bool reset) 617 { 618 bc_vec_npop(&r->v, reset ? r->v.len - 1 : 1); 619 } 620 621 void 622 bc_rand_init(BcRNG* r) 623 { 624 BC_SIG_ASSERT_LOCKED; 625 bc_vec_init(&r->v, sizeof(BcRNGData), BC_DTOR_NONE); 626 bc_rand_push(r); 627 } 628 629 #if BC_RAND_USE_FREE 630 void 631 bc_rand_free(BcRNG* r) 632 { 633 BC_SIG_ASSERT_LOCKED; 634 bc_vec_free(&r->v); 635 } 636 #endif // BC_RAND_USE_FREE 637 638 #endif // BC_ENABLE_EXTRA_MATH 639