contrib/bc/src/rand.c

   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 bc_rand_addition(uint_fast64_t a, uint_fast64_t b) {
  70
  71         BcRandState res;
  72
  73         res.lo = a + b;
  74         res.hi = (res.lo < a);
  75
  76         return res;
  77 }
  78
  79 /**
  80  * Adds two 128-bit values and discards the overflow.
  81  * @param a  The first operand.
  82  * @param b  The second operand.
  83  * @return   The sum, without overflow.
  84  */
  85 static BcRandState bc_rand_addition2(BcRandState a, BcRandState b) {
  86
  87         BcRandState temp, res;
  88
  89         res = bc_rand_addition(a.lo, b.lo);
  90         temp = bc_rand_addition(a.hi, b.hi);
  91         res.hi += temp.lo;
  92
  93         return res;
  94 }
  95
  96 /**
  97  * Multiplies two 64-bit values and preserves the overflow.
  98  * @param a  The first operand.
  99  * @param b  The second operand.
 100  * @return   The product, including overflow.
 101  */
 102 static BcRandState bc_rand_multiply(uint_fast64_t a, uint_fast64_t b) {
 103
 104         uint_fast64_t al, ah, bl, bh, c0, c1, c2, c3;
 105         BcRandState carry, res;
 106
 107         al = BC_RAND_TRUNC32(a);
 108         ah = BC_RAND_CHOP32(a);
 109         bl = BC_RAND_TRUNC32(b);
 110         bh = BC_RAND_CHOP32(b);
 111
 112         c0 = al * bl;
 113         c1 = al * bh;
 114         c2 = ah * bl;
 115         c3 = ah * bh;
 116
 117         carry = bc_rand_addition(c1, c2);
 118
 119         res = bc_rand_addition(c0, (BC_RAND_TRUNC32(carry.lo)) << 32);
 120         res.hi += BC_RAND_CHOP32(carry.lo) + c3 + (carry.hi << 32);
 121
 122         return res;
 123 }
 124
 125 /**
 126  * Multiplies two 128-bit values and discards the overflow.
 127  * @param a  The first operand.
 128  * @param b  The second operand.
 129  * @return   The product, without overflow.
 130  */
 131 static BcRandState bc_rand_multiply2(BcRandState a, BcRandState b) {
 132
 133         BcRandState c0, c1, c2, carry;
 134
 135         c0 = bc_rand_multiply(a.lo, b.lo);
 136         c1 = bc_rand_multiply(a.lo, b.hi);
 137         c2 = bc_rand_multiply(a.hi, b.lo);
 138
 139         carry = bc_rand_addition2(c1, c2);
 140         carry.hi = carry.lo;
 141         carry.lo = 0;
 142
 143         return bc_rand_addition2(c0, carry);
 144 }
 145
 146 #endif // BC_RAND_BUILTIN
 147
 148 /**
 149  * Marks a PRNG as modified. This is important for properly maintaining the
 150  * stack of PRNG's.
 151  * @param r  The PRNG to mark as modified.
 152  */
 153 static void bc_rand_setModified(BcRNGData *r) {
 154
 155 #if BC_RAND_BUILTIN
 156         r->inc |= (BcRandState) 1UL;
 157 #else // BC_RAND_BUILTIN
 158         r->inc.lo |= (uint_fast64_t) 1UL;
 159 #endif // BC_RAND_BUILTIN
 160 }
 161
 162 /**
 163  * Marks a PRNG as not modified. This is important for properly maintaining the
 164  * stack of PRNG's.
 165  * @param r  The PRNG to mark as not modified.
 166  */
 167 static void bc_rand_clearModified(BcRNGData *r) {
 168
 169 #if BC_RAND_BUILTIN
 170         r->inc &= ~((BcRandState) 1UL);
 171 #else // BC_RAND_BUILTIN
 172         r->inc.lo &= ~(1UL);
 173 #endif // BC_RAND_BUILTIN
 174 }
 175
 176 /**
 177  * Copies a PRNG to another and marks the copy as modified if it already was or
 178  * marks it modified if it already was.
 179  * @param d  The destination PRNG.
 180  * @param s  The source PRNG.
 181  */
 182 static void bc_rand_copy(BcRNGData *d, BcRNGData *s) {
 183         bool unmod = BC_RAND_NOTMODIFIED(d);
 184         memcpy(d, s, sizeof(BcRNGData));
 185         if (!unmod) bc_rand_setModified(d);
 186         else if (!BC_RAND_NOTMODIFIED(s)) bc_rand_clearModified(d);
 187 }
 188
 189 #ifndef _WIN32
 190
 191 /**
 192  * Reads random data from a file.
 193  * @param ptr  A pointer to the file, as a void pointer.
 194  * @return     The random data as an unsigned long.
 195  */
 196 static ulong bc_rand_frand(void* ptr) {
 197
 198         ulong buf[1];
 199         int fd;
 200         ssize_t nread;
 201
 202         assert(ptr != NULL);
 203
 204         fd = *((int*)ptr);
 205
 206         nread = read(fd, buf, sizeof(ulong));
 207
 208         if (BC_ERR(nread != sizeof(ulong))) bc_vm_fatalError(BC_ERR_FATAL_IO_ERR);
 209
 210         return *((ulong*)buf);
 211 }
 212 #else // _WIN32
 213
 214 /**
 215  * Reads random data from BCryptGenRandom().
 216  * @param ptr  An unused parameter.
 217  * @return     The random data as an unsigned long.
 218  */
 219 static ulong bc_rand_winrand(void *ptr) {
 220
 221         ulong buf[1];
 222         NTSTATUS s;
 223
 224         BC_UNUSED(ptr);
 225
 226         buf[0] = 0;
 227
 228         s = BCryptGenRandom(NULL, (char*) buf, sizeof(ulong),
 229                             BCRYPT_USE_SYSTEM_PREFERRED_RNG);
 230
 231         if (BC_ERR(!BCRYPT_SUCCESS(s))) buf[0] = 0;
 232
 233         return buf[0];
 234 }
 235 #endif // _WIN32
 236
 237 /**
 238  * Reads random data from rand(), byte-by-byte because rand() is only guaranteed
 239  * to return 15 bits of random data. This is the final fallback and is not
 240  * preferred as it is possible to access cryptographically-secure PRNG's on most
 241  * systems.
 242  * @param ptr  An unused parameter.
 243  * @return     The random data as an unsigned long.
 244  */
 245 static ulong bc_rand_rand(void *ptr) {
 246
 247         size_t i;
 248         ulong res = 0;
 249
 250         BC_UNUSED(ptr);
 251
 252         // Fill up the unsigned long byte-by-byte.
 253         for (i = 0; i < sizeof(ulong); ++i)
 254                 res |= ((ulong) (rand() & BC_RAND_SRAND_BITS)) << (i * CHAR_BIT);
 255
 256         return res;
 257 }
 258
 259 /**
 260  * Returns the actual increment of the PRNG, including the required last odd
 261  * bit.
 262  * @param r  The PRNG.
 263  * @return   The increment of the PRNG, including the last odd bit.
 264  */
 265 static BcRandState bc_rand_inc(BcRNGData *r) {
 266
 267         BcRandState inc;
 268
 269 #if BC_RAND_BUILTIN
 270         inc = r->inc | 1;
 271 #else // BC_RAND_BUILTIN
 272         inc.lo = r->inc.lo | 1;
 273         inc.hi = r->inc.hi;
 274 #endif // BC_RAND_BUILTIN
 275
 276         return inc;
 277 }
 278
 279 /**
 280  * Sets up the increment for the PRNG.
 281  * @param r  The PRNG whose increment will be set up.
 282  */
 283 static void bc_rand_setupInc(BcRNGData *r) {
 284
 285 #if BC_RAND_BUILTIN
 286         r->inc <<= 1UL;
 287 #else // BC_RAND_BUILTIN
 288         r->inc.hi <<= 1UL;
 289         r->inc.hi |= (r->inc.lo & (1UL << (BC_LONG_BIT - 1))) >> (BC_LONG_BIT - 1);
 290         r->inc.lo <<= 1UL;
 291 #endif // BC_RAND_BUILTIN
 292 }
 293
 294 /**
 295  * Seeds the state of a PRNG.
 296  * @param state  The return parameter; the state to seed.
 297  * @param val1   The lower half of the state.
 298  * @param val2   The upper half of the state.
 299  */
 300 static void bc_rand_seedState(BcRandState *state, ulong val1, ulong val2) {
 301
 302 #if BC_RAND_BUILTIN
 303         *state = ((BcRandState) val1) | ((BcRandState) val2) << (BC_LONG_BIT);
 304 #else // BC_RAND_BUILTIN
 305         state->lo = val1;
 306         state->hi = val2;
 307 #endif // BC_RAND_BUILTIN
 308 }
 309
 310 /**
 311  * Seeds a PRNG.
 312  * @param r       The return parameter; the PRNG to seed.
 313  * @param state1  The lower half of the state.
 314  * @param state2  The upper half of the state.
 315  * @param inc1    The lower half of the increment.
 316  * @param inc2    The upper half of the increment.
 317  */
 318 static void bc_rand_seedRNG(BcRNGData *r, ulong state1, ulong state2,
 319                             ulong inc1, ulong inc2)
 320 {
 321         bc_rand_seedState(&r->state, state1, state2);
 322         bc_rand_seedState(&r->inc, inc1, inc2);
 323         bc_rand_setupInc(r);
 324 }
 325
 326 /**
 327  * Fills a PRNG with random data to seed it.
 328  * @param r       The PRNG.
 329  * @param fulong  The function to fill an unsigned long.
 330  * @param ptr     The parameter to pass to @a fulong.
 331  */
 332 static void bc_rand_fill(BcRNGData *r, BcRandUlong fulong, void *ptr) {
 333
 334         ulong state1, state2, inc1, inc2;
 335
 336         state1 = fulong(ptr);
 337         state2 = fulong(ptr);
 338
 339         inc1 = fulong(ptr);
 340         inc2 = fulong(ptr);
 341
 342         bc_rand_seedRNG(r, state1, state2, inc1, inc2);
 343 }
 344
 345 /**
 346  * Executes the "step" portion of a PCG udpate.
 347  * @param r  The PRNG.
 348  */
 349 static void bc_rand_step(BcRNGData *r) {
 350         BcRandState temp = bc_rand_mul2(r->state, bc_rand_multiplier);
 351         r->state = bc_rand_add2(temp, bc_rand_inc(r));
 352 }
 353
 354 /**
 355  * Returns the new output of PCG.
 356  * @param r  The PRNG.
 357  * @return   The new output from the PRNG.
 358  */
 359 static BcRand bc_rand_output(BcRNGData *r) {
 360         return BC_RAND_ROT(BC_RAND_FOLD(r->state), BC_RAND_ROTAMT(r->state));
 361 }
 362
 363 /**
 364  * Seeds every PRNG on the PRNG stack between the top and @a idx that has not
 365  * been seeded.
 366  * @param r    The PRNG stack.
 367  * @param rng  The PRNG on the top of the stack. Must have been seeded.
 368  */
 369 static void bc_rand_seedZeroes(BcRNG *r, BcRNGData *rng, size_t idx) {
 370
 371         BcRNGData *rng2;
 372
 373         // Just return if there are none to do.
 374         if (r->v.len <= idx) return;
 375
 376         // Get the first PRNG that might need to be seeded.
 377         rng2 = bc_vec_item_rev(&r->v, idx);
 378
 379         // Does it need seeding? Then it, and maybe more, do.
 380         if (BC_RAND_ZERO(rng2)) {
 381
 382                 size_t i;
 383
 384                 // Seed the ones that need seeding.
 385                 for (i = 1; i < r->v.len; ++i)
 386                         bc_rand_copy(bc_vec_item_rev(&r->v, i), rng);
 387         }
 388 }
 389
 390 void bc_rand_srand(BcRNGData *rng) {
 391
 392         int fd = 0;
 393
 394         BC_SIG_LOCK;
 395
 396 #ifndef _WIN32
 397
 398         // Try /dev/urandom first.
 399         fd = open("/dev/urandom", O_RDONLY);
 400
 401         if (BC_NO_ERR(fd >= 0)) {
 402                 bc_rand_fill(rng, bc_rand_frand, &fd);
 403                 close(fd);
 404         }
 405         else {
 406
 407                 // Try /dev/random second.
 408                 fd = open("/dev/random", O_RDONLY);
 409
 410                 if (BC_NO_ERR(fd >= 0)) {
 411                         bc_rand_fill(rng, bc_rand_frand, &fd);
 412                         close(fd);
 413                 }
 414         }
 415 #else // _WIN32
 416         // Try BCryptGenRandom first.
 417         bc_rand_fill(rng, bc_rand_winrand, NULL);
 418 #endif // _WIN32
 419
 420         // Fallback to rand() until the thing is seeded.
 421         while (BC_ERR(BC_RAND_ZERO(rng))) bc_rand_fill(rng, bc_rand_rand, NULL);
 422
 423         BC_SIG_UNLOCK;
 424 }
 425
 426 /**
 427  * Propagates a change to the PRNG to all PRNG's in the stack that should have
 428  * it. The ones that should have it are laid out in the manpages.
 429  * @param r    The PRNG stack.
 430  * @param rng  The PRNG that will be used to seed the others.
 431  */
 432 static void bc_rand_propagate(BcRNG *r, BcRNGData *rng) {
 433
 434         // Just return if there are none to do.
 435         if (r->v.len <= 1) return;
 436
 437         // If the PRNG has not been modified...
 438         if (BC_RAND_NOTMODIFIED(rng)) {
 439
 440                 size_t i;
 441                 bool go = true;
 442
 443                 // Find the first PRNG that is modified and seed the others.
 444                 for (i = 1; go && i < r->v.len; ++i) {
 445
 446                         BcRNGData *rng2 = bc_vec_item_rev(&r->v, i);
 447
 448                         go = BC_RAND_NOTMODIFIED(rng2);
 449
 450                         bc_rand_copy(rng2, rng);
 451                 }
 452
 453                 // Seed everything else.
 454                 bc_rand_seedZeroes(r, rng, i);
 455         }
 456         // Seed everything.
 457         else bc_rand_seedZeroes(r, rng, 1);
 458 }
 459
 460 BcRand bc_rand_int(BcRNG *r) {
 461
 462         // Get the actual PRNG.
 463         BcRNGData *rng = bc_vec_top(&r->v);
 464
 465         // Make sure the PRNG is seeded.
 466         if (BC_ERR(BC_RAND_ZERO(rng))) bc_rand_srand(rng);
 467
 468         // This is the important part of the PRNG. This is the stuff from PCG,
 469         // including the return statement.
 470         bc_rand_step(rng);
 471         bc_rand_propagate(r, rng);
 472
 473         return bc_rand_output(rng);
 474 }
 475
 476 BcRand bc_rand_bounded(BcRNG *r, BcRand bound) {
 477
 478         // Calculate the threshold below which we have to try again.
 479         BcRand rand, threshold = (0 - bound) % bound;
 480
 481         do {
 482                 rand = bc_rand_int(r);
 483         } while (rand < threshold);
 484
 485         return rand % bound;
 486 }
 487
 488 void bc_rand_seed(BcRNG *r, ulong state1, ulong state2, ulong inc1, ulong inc2)
 489 {
 490         // Get the actual PRNG.
 491         BcRNGData *rng = bc_vec_top(&r->v);
 492
 493         // Seed and set up the PRNG's increment.
 494         bc_rand_seedState(&rng->inc, inc1, inc2);
 495         bc_rand_setupInc(rng);
 496         bc_rand_setModified(rng);
 497
 498         // If the state is 0, use the increment as the state. Otherwise, seed it
 499         // with the state.
 500         if (!state1 && !state2) {
 501                 memcpy(&rng->state, &rng->inc, sizeof(BcRandState));
 502                 bc_rand_step(rng);
 503         }
 504         else bc_rand_seedState(&rng->state, state1, state2);
 505
 506         // Propagate the change to PRNG's that need it.
 507         bc_rand_propagate(r, rng);
 508 }
 509
 510 /**
 511  * Returns the increment in the PRNG *without* the odd bit and also with being
 512  * shifted one bit down.
 513  * @param r  The PRNG.
 514  * @return   The increment without the odd bit and with being shifted one bit
 515  *           down.
 516  */
 517 static BcRandState bc_rand_getInc(BcRNGData *r) {
 518
 519         BcRandState res;
 520
 521 #if BC_RAND_BUILTIN
 522         res = r->inc >> 1;
 523 #else // BC_RAND_BUILTIN
 524         res = r->inc;
 525         res.lo >>= 1;
 526         res.lo |= (res.hi & 1) << (BC_LONG_BIT - 1);
 527         res.hi >>= 1;
 528 #endif // BC_RAND_BUILTIN
 529
 530         return res;
 531 }
 532
 533 void bc_rand_getRands(BcRNG *r, BcRand *s1, BcRand *s2, BcRand *i1, BcRand *i2)
 534 {
 535         BcRandState inc;
 536         BcRNGData *rng = bc_vec_top(&r->v);
 537
 538         if (BC_ERR(BC_RAND_ZERO(rng))) bc_rand_srand(rng);
 539
 540         // Get the increment.
 541         inc = bc_rand_getInc(rng);
 542
 543         // Chop the state.
 544         *s1 = BC_RAND_TRUNC(rng->state);
 545         *s2 = BC_RAND_CHOP(rng->state);
 546
 547         // Chop the increment.
 548         *i1 = BC_RAND_TRUNC(inc);
 549         *i2 = BC_RAND_CHOP(inc);
 550 }
 551
 552 void bc_rand_push(BcRNG *r) {
 553
 554         BcRNGData *rng = bc_vec_pushEmpty(&r->v);
 555
 556         // Make sure the PRNG is properly zeroed because that marks it as needing to
 557         // be seeded.
 558         memset(rng, 0, sizeof(BcRNGData));
 559
 560         // If there is another item, copy it too.
 561         if (r->v.len > 1) bc_rand_copy(rng, bc_vec_item_rev(&r->v, 1));
 562 }
 563
 564 void bc_rand_pop(BcRNG *r, bool reset) {
 565         bc_vec_npop(&r->v, reset ? r->v.len - 1 : 1);
 566 }
 567
 568 void bc_rand_init(BcRNG *r) {
 569         BC_SIG_ASSERT_LOCKED;
 570         bc_vec_init(&r->v, sizeof(BcRNGData), BC_DTOR_NONE);
 571         bc_rand_push(r);
 572 }
 573
 574 #if BC_RAND_USE_FREE
 575 void bc_rand_free(BcRNG *r) {
 576         BC_SIG_ASSERT_LOCKED;
 577         bc_vec_free(&r->v);
 578 }
 579 #endif // BC_RAND_USE_FREE
 580
 581 #endif // BC_ENABLE_EXTRA_MATH