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-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  */
  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         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
 535 void
 536 bc_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  */
 567 static BcRandState
 568 bc_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
 584 void
 585 bc_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
 604 void
 605 bc_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
 618 void
 619 bc_rand_pop(BcRNG* r, bool reset)
 620 {
 621         bc_vec_npop(&r->v, reset ? r->v.len - 1 : 1);
 622 }
 623
 624 void
 625 bc_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
 633 void
 634 bc_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