2 * *****************************************************************************
4 * Parts of this code are adapted from the following:
6 * PCG, A Family of Better Random Number Generators.
8 * You can find the original source code at:
9 * https://github.com/imneme/pcg-c
11 * -----------------------------------------------------------------------------
13 * This code is under the following license:
15 * Copyright (c) 2014-2017 Melissa O'Neill and PCG Project contributors
16 * Copyright (c) 2018-2023 Gavin D. Howard and contributors.
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:
25 * The above copyright notice and this permission notice shall be included in
26 * all copies or substantial portions of the Software.
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
36 * *****************************************************************************
59 #if BC_ENABLE_EXTRA_MATH
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.
70 bc_rand_addition(uint_fast64_t a, uint_fast64_t b)
75 res.hi = (res.lo < a);
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.
87 bc_rand_addition2(BcRandState a, BcRandState b)
89 BcRandState temp, res;
91 res = bc_rand_addition(a.lo, b.lo);
92 temp = bc_rand_addition(a.hi, b.hi);
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.
105 bc_rand_multiply(uint_fast64_t a, uint_fast64_t b)
107 uint_fast64_t al, ah, bl, bh, c0, c1, c2, c3;
108 BcRandState carry, res;
110 al = BC_RAND_TRUNC32(a);
111 ah = BC_RAND_CHOP32(a);
112 bl = BC_RAND_TRUNC32(b);
113 bh = BC_RAND_CHOP32(b);
120 carry = bc_rand_addition(c1, c2);
122 res = bc_rand_addition(c0, (BC_RAND_TRUNC32(carry.lo)) << 32);
123 res.hi += BC_RAND_CHOP32(carry.lo) + c3 + (carry.hi << 32);
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.
135 bc_rand_multiply2(BcRandState a, BcRandState b)
137 BcRandState c0, c1, c2, carry;
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);
143 carry = bc_rand_addition2(c1, c2);
147 return bc_rand_addition2(c0, carry);
150 #endif // BC_RAND_BUILTIN
153 * Marks a PRNG as modified. This is important for properly maintaining the
155 * @param r The PRNG to mark as modified.
158 bc_rand_setModified(BcRNGData* r)
161 r->inc |= (BcRandState) 1UL;
162 #else // BC_RAND_BUILTIN
163 r->inc.lo |= (uint_fast64_t) 1UL;
164 #endif // BC_RAND_BUILTIN
168 * Marks a PRNG as not modified. This is important for properly maintaining the
170 * @param r The PRNG to mark as not modified.
173 bc_rand_clearModified(BcRNGData* r)
176 r->inc &= ~((BcRandState) 1UL);
177 #else // BC_RAND_BUILTIN
179 #endif // BC_RAND_BUILTIN
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.
189 bc_rand_copy(BcRNGData* d, BcRNGData* s)
191 bool unmod = BC_RAND_NOTMODIFIED(d);
194 memcpy(d, s, sizeof(BcRNGData));
196 if (!unmod) bc_rand_setModified(d);
197 else if (!BC_RAND_NOTMODIFIED(s)) bc_rand_clearModified(d);
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.
208 bc_rand_frand(void* ptr)
218 nread = read(fd, buf, sizeof(ulong));
220 if (BC_ERR(nread != sizeof(ulong))) bc_vm_fatalError(BC_ERR_FATAL_IO_ERR);
222 return *((ulong*) buf);
227 * Reads random data from BCryptGenRandom().
228 * @param ptr An unused parameter.
229 * @return The random data as an unsigned long.
232 bc_rand_winrand(void* ptr)
241 s = BCryptGenRandom(NULL, (char*) buf, sizeof(ulong),
242 BCRYPT_USE_SYSTEM_PREFERRED_RNG);
244 if (BC_ERR(!BCRYPT_SUCCESS(s))) buf[0] = 0;
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
255 * @param ptr An unused parameter.
256 * @return The random data as an unsigned long.
259 bc_rand_rand(void* ptr)
266 // Fill up the unsigned long byte-by-byte.
267 for (i = 0; i < sizeof(ulong); ++i)
269 res |= ((ulong) (rand() & BC_RAND_SRAND_BITS)) << (i * CHAR_BIT);
276 * Returns the actual increment of the PRNG, including the required last odd
279 * @return The increment of the PRNG, including the last odd bit.
282 bc_rand_inc(BcRNGData* r)
288 #else // BC_RAND_BUILTIN
289 inc.lo = r->inc.lo | 1;
291 #endif // BC_RAND_BUILTIN
297 * Sets up the increment for the PRNG.
298 * @param r The PRNG whose increment will be set up.
301 bc_rand_setupInc(BcRNGData* r)
305 #else // BC_RAND_BUILTIN
307 r->inc.hi |= (r->inc.lo & (1UL << (BC_LONG_BIT - 1))) >> (BC_LONG_BIT - 1);
309 #endif // BC_RAND_BUILTIN
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.
319 bc_rand_seedState(BcRandState* state, ulong val1, ulong val2)
322 *state = ((BcRandState) val1) | ((BcRandState) val2) << (BC_LONG_BIT);
323 #else // BC_RAND_BUILTIN
326 #endif // BC_RAND_BUILTIN
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.
338 bc_rand_seedRNG(BcRNGData* r, ulong state1, ulong state2, ulong inc1,
341 bc_rand_seedState(&r->state, state1, state2);
342 bc_rand_seedState(&r->inc, inc1, inc2);
347 * Fills a PRNG with random data to seed it.
349 * @param fulong The function to fill an unsigned long.
350 * @param ptr The parameter to pass to @a fulong.
353 bc_rand_fill(BcRNGData* r, BcRandUlong fulong, void* ptr)
355 ulong state1, state2, inc1, inc2;
357 state1 = fulong(ptr);
358 state2 = fulong(ptr);
363 bc_rand_seedRNG(r, state1, state2, inc1, inc2);
367 * Executes the "step" portion of a PCG udpate.
371 bc_rand_step(BcRNGData* r)
373 BcRandState temp = bc_rand_mul2(r->state, bc_rand_multiplier);
374 r->state = bc_rand_add2(temp, bc_rand_inc(r));
378 * Returns the new output of PCG.
380 * @return The new output from the PRNG.
383 bc_rand_output(BcRNGData* r)
385 return BC_RAND_ROT(BC_RAND_FOLD(r->state), BC_RAND_ROTAMT(r->state));
389 * Seeds every PRNG on the PRNG stack between the top and @a idx that has not
391 * @param r The PRNG stack.
392 * @param rng The PRNG on the top of the stack. Must have been seeded.
395 bc_rand_seedZeroes(BcRNG* r, BcRNGData* rng, size_t idx)
399 // Just return if there are none to do.
400 if (r->v.len <= idx) return;
402 // Get the first PRNG that might need to be seeded.
403 rng2 = bc_vec_item_rev(&r->v, idx);
405 // Does it need seeding? Then it, and maybe more, do.
406 if (BC_RAND_ZERO(rng2))
410 // Seed the ones that need seeding.
411 for (i = 1; i < r->v.len; ++i)
413 bc_rand_copy(bc_vec_item_rev(&r->v, i), rng);
419 bc_rand_srand(BcRNGData* rng)
427 // Try /dev/urandom first.
428 fd = open("/dev/urandom", O_RDONLY);
430 if (BC_NO_ERR(fd >= 0))
432 bc_rand_fill(rng, bc_rand_frand, &fd);
437 // Try /dev/random second.
438 fd = open("/dev/random", O_RDONLY);
440 if (BC_NO_ERR(fd >= 0))
442 bc_rand_fill(rng, bc_rand_frand, &fd);
447 // Try BCryptGenRandom first.
448 bc_rand_fill(rng, bc_rand_winrand, NULL);
451 // Fallback to rand() until the thing is seeded.
452 while (BC_ERR(BC_RAND_ZERO(rng)))
454 bc_rand_fill(rng, bc_rand_rand, NULL);
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.
467 bc_rand_propagate(BcRNG* r, BcRNGData* rng)
469 // Just return if there are none to do.
470 if (r->v.len <= 1) return;
472 // If the PRNG has not been modified...
473 if (BC_RAND_NOTMODIFIED(rng))
478 // Find the first PRNG that is modified and seed the others.
479 for (i = 1; go && i < r->v.len; ++i)
481 BcRNGData* rng2 = bc_vec_item_rev(&r->v, i);
483 go = BC_RAND_NOTMODIFIED(rng2);
485 bc_rand_copy(rng2, rng);
488 // Seed everything else.
489 bc_rand_seedZeroes(r, rng, i);
492 else bc_rand_seedZeroes(r, rng, 1);
496 bc_rand_int(BcRNG* r)
498 // Get the actual PRNG.
499 BcRNGData* rng = bc_vec_top(&r->v);
502 // Make sure the PRNG is seeded.
503 if (BC_ERR(BC_RAND_ZERO(rng))) bc_rand_srand(rng);
507 // This is the important part of the PRNG. This is the stuff from PCG.
509 bc_rand_propagate(r, rng);
510 res = bc_rand_output(rng);
518 bc_rand_bounded(BcRNG* r, BcRand bound)
520 // Calculate the threshold below which we have to try again.
521 BcRand rand, threshold = (0 - bound) % bound;
525 rand = bc_rand_int(r);
527 while (rand < threshold);
533 bc_rand_seed(BcRNG* r, ulong state1, ulong state2, ulong inc1, ulong inc2)
535 // Get the actual PRNG.
536 BcRNGData* rng = bc_vec_top(&r->v);
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);
543 // If the state is 0, use the increment as the state. Otherwise, seed it
545 if (!state1 && !state2)
548 memcpy(&rng->state, &rng->inc, sizeof(BcRandState));
551 else bc_rand_seedState(&rng->state, state1, state2);
553 // Propagate the change to PRNG's that need it.
554 bc_rand_propagate(r, rng);
558 * Returns the increment in the PRNG *without* the odd bit and also with being
559 * shifted one bit down.
561 * @return The increment without the odd bit and with being shifted one bit
565 bc_rand_getInc(BcRNGData* r)
571 #else // BC_RAND_BUILTIN
574 res.lo |= (res.hi & 1) << (BC_LONG_BIT - 1);
576 #endif // BC_RAND_BUILTIN
582 bc_rand_getRands(BcRNG* r, BcRand* s1, BcRand* s2, BcRand* i1, BcRand* i2)
585 BcRNGData* rng = bc_vec_top(&r->v);
587 if (BC_ERR(BC_RAND_ZERO(rng))) bc_rand_srand(rng);
589 // Get the increment.
590 inc = bc_rand_getInc(rng);
593 *s1 = BC_RAND_TRUNC(rng->state);
594 *s2 = BC_RAND_CHOP(rng->state);
596 // Chop the increment.
597 *i1 = BC_RAND_TRUNC(inc);
598 *i2 = BC_RAND_CHOP(inc);
602 bc_rand_push(BcRNG* r)
604 BcRNGData* rng = bc_vec_pushEmpty(&r->v);
606 // Make sure the PRNG is properly zeroed because that marks it as needing to
609 memset(rng, 0, sizeof(BcRNGData));
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));
616 bc_rand_pop(BcRNG* r, bool reset)
618 bc_vec_npop(&r->v, reset ? r->v.len - 1 : 1);
622 bc_rand_init(BcRNG* r)
624 BC_SIG_ASSERT_LOCKED;
625 bc_vec_init(&r->v, sizeof(BcRNGData), BC_DTOR_NONE);
631 bc_rand_free(BcRNG* r)
633 BC_SIG_ASSERT_LOCKED;
636 #endif // BC_RAND_USE_FREE
638 #endif // BC_ENABLE_EXTRA_MATH