2 * *****************************************************************************
4 * SPDX-License-Identifier: BSD-2-Clause
6 * Copyright (c) 2018-2019 Gavin D. Howard and contributors.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions are met:
11 * * Redistributions of source code must retain the above copyright notice, this
12 * list of conditions and the following disclaimer.
14 * * Redistributions in binary form must reproduce the above copyright notice,
15 * this list of conditions and the following disclaimer in the documentation
16 * and/or other materials provided with the distribution.
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
22 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
23 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
26 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
27 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
28 * POSSIBILITY OF SUCH DAMAGE.
30 * *****************************************************************************
32 * Parts of this code are adapted from the following:
34 * PCG, A Family of Better Random Number Generators.
36 * You can find the original source code at:
37 * https://github.com/imneme/pcg-c
39 * -----------------------------------------------------------------------------
41 * Parts of this code are also under the following license:
43 * Copyright (c) 2014-2017 Melissa O'Neill and PCG Project contributors
45 * Permission is hereby granted, free of charge, to any person obtaining a copy
46 * of this software and associated documentation files (the "Software"), to deal
47 * in the Software without restriction, including without limitation the rights
48 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
49 * copies of the Software, and to permit persons to whom the Software is
50 * furnished to do so, subject to the following conditions:
52 * The above copyright notice and this permission notice shall be included in
53 * all copies or substantial portions of the Software.
55 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
56 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
57 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
58 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
59 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
60 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
63 * *****************************************************************************
80 #if BC_ENABLE_EXTRA_MATH && BC_ENABLE_RAND
84 static BcRandState bc_rand_addition(uint_fast64_t a, uint_fast64_t b) {
89 res.hi = (res.lo < a);
94 static BcRandState bc_rand_addition2(BcRandState a, BcRandState b) {
96 BcRandState temp, res;
98 res = bc_rand_addition(a.lo, b.lo);
99 temp = bc_rand_addition(a.hi, b.hi);
105 static BcRandState 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);
128 static BcRandState bc_rand_multiply2(BcRandState a, BcRandState b) {
130 BcRandState c0, c1, c2, carry;
132 c0 = bc_rand_multiply(a.lo, b.lo);
133 c1 = bc_rand_multiply(a.lo, b.hi);
134 c2 = bc_rand_multiply(a.hi, b.lo);
136 carry = bc_rand_addition2(c1, c2);
140 return bc_rand_addition2(c0, carry);
143 #endif // BC_RAND_BUILTIN
145 static void bc_rand_setModified(BcRNGData *r) {
148 r->inc |= (BcRandState) 1UL;
149 #else // BC_RAND_BUILTIN
150 r->inc.lo |= (uint_fast64_t) 1UL;
151 #endif // BC_RAND_BUILTIN
154 static void bc_rand_clearModified(BcRNGData *r) {
157 r->inc &= ~((BcRandState) 1UL);
158 #else // BC_RAND_BUILTIN
160 #endif // BC_RAND_BUILTIN
163 static void bc_rand_copy(BcRNGData *d, BcRNGData *s) {
164 bool unmod = BC_RAND_NOTMODIFIED(d);
165 memcpy(d, s, sizeof(BcRNGData));
166 if (!unmod) bc_rand_setModified(d);
167 else if (!BC_RAND_NOTMODIFIED(s)) bc_rand_clearModified(d);
170 static ulong bc_rand_frand(void *ptr) {
180 nread = read(fd, buf, sizeof(ulong));
182 if (BC_ERR(nread != sizeof(ulong))) bc_vm_err(BC_ERR_FATAL_IO_ERR);
184 return *((ulong*) buf);
187 static ulong bc_rand_rand(void *ptr) {
194 for (i = 0; i < sizeof(ulong); ++i)
195 res |= ((ulong) (rand() & BC_RAND_SRAND_BITS)) << (i * CHAR_BIT);
200 static BcRandState bc_rand_inc(BcRNGData *r) {
206 #else // BC_RAND_BUILTIN
207 inc.lo = r->inc.lo | 1;
209 #endif // BC_RAND_BUILTIN
214 static void bc_rand_setInc(BcRNGData *r) {
218 #else // BC_RAND_BUILTIN
220 r->inc.hi |= (r->inc.lo & (1UL << (BC_LONG_BIT - 1))) >> (BC_LONG_BIT - 1);
222 #endif // BC_RAND_BUILTIN
225 static void bc_rand_seedState(BcRandState *state, ulong val1, ulong val2) {
228 *state = ((BcRandState) val1) | ((BcRandState) val2) << (BC_LONG_BIT);
229 #else // BC_RAND_BUILTIN
232 #endif // BC_RAND_BUILTIN
235 static void bc_rand_seedRNG(BcRNGData *r, ulong state1, ulong state2,
236 ulong inc1, ulong inc2)
238 bc_rand_seedState(&r->state, state1, state2);
239 bc_rand_seedState(&r->inc, inc1, inc2);
243 static void bc_rand_fill(BcRNGData *r, BcRandUlong fulong, void *ptr) {
245 ulong state1, state2, inc1, inc2;
247 state1 = fulong(ptr);
248 state2 = fulong(ptr);
253 bc_rand_seedRNG(r, state1, state2, inc1, inc2);
256 static void bc_rand_step(BcRNGData *r) {
257 BcRandState temp = bc_rand_mul2(r->state, bc_rand_multiplier);
258 r->state = bc_rand_add2(temp, bc_rand_inc(r));
261 static BcRand bc_rand_output(BcRNGData *r) {
262 return BC_RAND_ROT(BC_RAND_FOLD(r->state), BC_RAND_ROTAMT(r->state));
265 static void bc_rand_seedZeroes(BcRNG *r, BcRNGData *rng, size_t idx) {
269 if (r->v.len <= idx) return;
271 rng2 = bc_vec_item_rev(&r->v, idx);
273 if (BC_RAND_ZERO(rng2)) {
275 for (i = 1; i < r->v.len; ++i)
276 bc_rand_copy(bc_vec_item_rev(&r->v, i), rng);
280 void bc_rand_srand(BcRNGData *rng) {
286 fd = open("/dev/urandom", O_RDONLY);
288 if (BC_NO_ERR(fd >= 0)) {
289 bc_rand_fill(rng, bc_rand_frand, &fd);
293 while (BC_ERR(BC_RAND_ZERO(rng))) bc_rand_fill(rng, bc_rand_rand, NULL);
298 static void bc_rand_propagate(BcRNG *r, BcRNGData *rng) {
300 if (r->v.len <= 1) return;
302 if (BC_RAND_NOTMODIFIED(rng)) {
307 for (i = 1; go && i < r->v.len; ++i) {
308 BcRNGData *rng2 = bc_vec_item_rev(&r->v, i);
309 go = BC_RAND_NOTMODIFIED(rng2);
310 bc_rand_copy(rng2, rng);
313 bc_rand_seedZeroes(r, rng, i);
315 else bc_rand_seedZeroes(r, rng, 1);
318 BcRand bc_rand_int(BcRNG *r) {
320 BcRNGData *rng = bc_vec_top(&r->v);
322 if (BC_ERR(BC_RAND_ZERO(rng))) bc_rand_srand(rng);
325 bc_rand_propagate(r, rng);
327 return bc_rand_output(rng);
330 BcRand bc_rand_bounded(BcRNG *r, BcRand bound) {
332 BcRand rand, threshold = (0 - bound) % bound;
335 rand = bc_rand_int(r);
336 } while (rand < threshold);
341 void bc_rand_seed(BcRNG *r, ulong state1, ulong state2, ulong inc1, ulong inc2)
343 BcRNGData *rng = bc_vec_top(&r->v);
345 bc_rand_seedState(&rng->inc, inc1, inc2);
347 bc_rand_setModified(rng);
349 if (!state1 && !state2) {
350 memcpy(&rng->state, &rng->inc, sizeof(BcRandState));
353 else bc_rand_seedState(&rng->state, state1, state2);
355 bc_rand_propagate(r, rng);
358 static BcRandState bc_rand_getInc(BcRNGData *r) {
364 #else // BC_RAND_BUILTIN
367 res.lo |= (res.hi & 1) << (BC_LONG_BIT - 1);
369 #endif // BC_RAND_BUILTIN
374 void bc_rand_getRands(BcRNG *r, BcRand *s1, BcRand *s2, BcRand *i1, BcRand *i2)
377 BcRNGData *rng = bc_vec_top(&r->v);
379 if (BC_ERR(BC_RAND_ZERO(rng))) bc_rand_srand(rng);
381 inc = bc_rand_getInc(rng);
383 *s1 = BC_RAND_TRUNC(rng->state);
384 *s2 = BC_RAND_CHOP(rng->state);
386 *i1 = BC_RAND_TRUNC(inc);
387 *i2 = BC_RAND_CHOP(inc);
390 void bc_rand_push(BcRNG *r) {
392 memset(&rng, 0, sizeof(BcRNGData));
393 if (r->v.len > 0) bc_rand_copy(&rng, bc_vec_top(&r->v));
394 bc_vec_push(&r->v, &rng);
397 void bc_rand_pop(BcRNG *r, bool reset) {
398 bc_vec_npop(&r->v, reset ? r->v.len - 1 : 1);
401 void bc_rand_init(BcRNG *r) {
402 BC_SIG_ASSERT_LOCKED;
403 bc_vec_init(&r->v, sizeof(BcRNGData), NULL);
408 void bc_rand_free(BcRNG *r) {
409 BC_SIG_ASSERT_LOCKED;
414 #endif // BC_ENABLE_EXTRA_MATH && BC_ENABLE_RAND