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 #include <unistd.h> 48 49 #include <status.h> 50 #include <rand.h> 51 #include <vm.h> 52 53 #if BC_ENABLE_EXTRA_MATH && BC_ENABLE_RAND 54 55 #if !BC_RAND_BUILTIN 56 57 static BcRandState bc_rand_addition(uint_fast64_t a, uint_fast64_t b) { 58 59 BcRandState res; 60 61 res.lo = a + b; 62 res.hi = (res.lo < a); 63 64 return res; 65 } 66 67 static BcRandState bc_rand_addition2(BcRandState a, BcRandState b) { 68 69 BcRandState temp, res; 70 71 res = bc_rand_addition(a.lo, b.lo); 72 temp = bc_rand_addition(a.hi, b.hi); 73 res.hi += temp.lo; 74 75 return res; 76 } 77 78 static BcRandState bc_rand_multiply(uint_fast64_t a, uint_fast64_t b) { 79 80 uint_fast64_t al, ah, bl, bh, c0, c1, c2, c3; 81 BcRandState carry, res; 82 83 al = BC_RAND_TRUNC32(a); 84 ah = BC_RAND_CHOP32(a); 85 bl = BC_RAND_TRUNC32(b); 86 bh = BC_RAND_CHOP32(b); 87 88 c0 = al * bl; 89 c1 = al * bh; 90 c2 = ah * bl; 91 c3 = ah * bh; 92 93 carry = bc_rand_addition(c1, c2); 94 95 res = bc_rand_addition(c0, (BC_RAND_TRUNC32(carry.lo)) << 32); 96 res.hi += BC_RAND_CHOP32(carry.lo) + c3 + (carry.hi << 32); 97 98 return res; 99 } 100 101 static BcRandState bc_rand_multiply2(BcRandState a, BcRandState b) { 102 103 BcRandState c0, c1, c2, carry; 104 105 c0 = bc_rand_multiply(a.lo, b.lo); 106 c1 = bc_rand_multiply(a.lo, b.hi); 107 c2 = bc_rand_multiply(a.hi, b.lo); 108 109 carry = bc_rand_addition2(c1, c2); 110 carry.hi = carry.lo; 111 carry.lo = 0; 112 113 return bc_rand_addition2(c0, carry); 114 } 115 116 #endif // BC_RAND_BUILTIN 117 118 static void bc_rand_setModified(BcRNGData *r) { 119 120 #if BC_RAND_BUILTIN 121 r->inc |= (BcRandState) 1UL; 122 #else // BC_RAND_BUILTIN 123 r->inc.lo |= (uint_fast64_t) 1UL; 124 #endif // BC_RAND_BUILTIN 125 } 126 127 static void bc_rand_clearModified(BcRNGData *r) { 128 129 #if BC_RAND_BUILTIN 130 r->inc &= ~((BcRandState) 1UL); 131 #else // BC_RAND_BUILTIN 132 r->inc.lo &= ~(1UL); 133 #endif // BC_RAND_BUILTIN 134 } 135 136 static void bc_rand_copy(BcRNGData *d, BcRNGData *s) { 137 bool unmod = BC_RAND_NOTMODIFIED(d); 138 memcpy(d, s, sizeof(BcRNGData)); 139 if (!unmod) bc_rand_setModified(d); 140 else if (!BC_RAND_NOTMODIFIED(s)) bc_rand_clearModified(d); 141 } 142 143 static ulong bc_rand_frand(void *ptr) { 144 145 ulong buf[1]; 146 int fd; 147 ssize_t nread; 148 149 assert(ptr != NULL); 150 151 fd = *((int*) ptr); 152 153 nread = read(fd, buf, sizeof(ulong)); 154 155 if (BC_ERR(nread != sizeof(ulong))) bc_vm_fatalError(BC_ERR_FATAL_IO_ERR); 156 157 return *((ulong*) buf); 158 } 159 160 static ulong bc_rand_rand(void *ptr) { 161 162 size_t i; 163 ulong res = 0; 164 165 BC_UNUSED(ptr); 166 167 for (i = 0; i < sizeof(ulong); ++i) 168 res |= ((ulong) (rand() & BC_RAND_SRAND_BITS)) << (i * CHAR_BIT); 169 170 return res; 171 } 172 173 static BcRandState bc_rand_inc(BcRNGData *r) { 174 175 BcRandState inc; 176 177 #if BC_RAND_BUILTIN 178 inc = r->inc | 1; 179 #else // BC_RAND_BUILTIN 180 inc.lo = r->inc.lo | 1; 181 inc.hi = r->inc.hi; 182 #endif // BC_RAND_BUILTIN 183 184 return inc; 185 } 186 187 static void bc_rand_setInc(BcRNGData *r) { 188 189 #if BC_RAND_BUILTIN 190 r->inc <<= 1UL; 191 #else // BC_RAND_BUILTIN 192 r->inc.hi <<= 1UL; 193 r->inc.hi |= (r->inc.lo & (1UL << (BC_LONG_BIT - 1))) >> (BC_LONG_BIT - 1); 194 r->inc.lo <<= 1UL; 195 #endif // BC_RAND_BUILTIN 196 } 197 198 static void bc_rand_seedState(BcRandState *state, ulong val1, ulong val2) { 199 200 #if BC_RAND_BUILTIN 201 *state = ((BcRandState) val1) | ((BcRandState) val2) << (BC_LONG_BIT); 202 #else // BC_RAND_BUILTIN 203 state->lo = val1; 204 state->hi = val2; 205 #endif // BC_RAND_BUILTIN 206 } 207 208 static void bc_rand_seedRNG(BcRNGData *r, ulong state1, ulong state2, 209 ulong inc1, ulong inc2) 210 { 211 bc_rand_seedState(&r->state, state1, state2); 212 bc_rand_seedState(&r->inc, inc1, inc2); 213 bc_rand_setInc(r); 214 } 215 216 static void bc_rand_fill(BcRNGData *r, BcRandUlong fulong, void *ptr) { 217 218 ulong state1, state2, inc1, inc2; 219 220 state1 = fulong(ptr); 221 state2 = fulong(ptr); 222 223 inc1 = fulong(ptr); 224 inc2 = fulong(ptr); 225 226 bc_rand_seedRNG(r, state1, state2, inc1, inc2); 227 } 228 229 static void bc_rand_step(BcRNGData *r) { 230 BcRandState temp = bc_rand_mul2(r->state, bc_rand_multiplier); 231 r->state = bc_rand_add2(temp, bc_rand_inc(r)); 232 } 233 234 static BcRand bc_rand_output(BcRNGData *r) { 235 return BC_RAND_ROT(BC_RAND_FOLD(r->state), BC_RAND_ROTAMT(r->state)); 236 } 237 238 static void bc_rand_seedZeroes(BcRNG *r, BcRNGData *rng, size_t idx) { 239 240 BcRNGData *rng2; 241 242 if (r->v.len <= idx) return; 243 244 rng2 = bc_vec_item_rev(&r->v, idx); 245 246 if (BC_RAND_ZERO(rng2)) { 247 size_t i; 248 for (i = 1; i < r->v.len; ++i) 249 bc_rand_copy(bc_vec_item_rev(&r->v, i), rng); 250 } 251 } 252 253 void bc_rand_srand(BcRNGData *rng) { 254 255 int fd; 256 257 BC_SIG_LOCK; 258 259 fd = open("/dev/urandom", O_RDONLY); 260 261 if (BC_NO_ERR(fd >= 0)) { 262 bc_rand_fill(rng, bc_rand_frand, &fd); 263 close(fd); 264 } 265 else { 266 267 fd = open("/dev/random", O_RDONLY); 268 269 if (BC_NO_ERR(fd >= 0)) { 270 bc_rand_fill(rng, bc_rand_frand, &fd); 271 close(fd); 272 } 273 } 274 275 while (BC_ERR(BC_RAND_ZERO(rng))) bc_rand_fill(rng, bc_rand_rand, NULL); 276 277 BC_SIG_UNLOCK; 278 } 279 280 static void bc_rand_propagate(BcRNG *r, BcRNGData *rng) { 281 282 if (r->v.len <= 1) return; 283 284 if (BC_RAND_NOTMODIFIED(rng)) { 285 286 size_t i; 287 bool go = true; 288 289 for (i = 1; go && i < r->v.len; ++i) { 290 BcRNGData *rng2 = bc_vec_item_rev(&r->v, i); 291 go = BC_RAND_NOTMODIFIED(rng2); 292 bc_rand_copy(rng2, rng); 293 } 294 295 bc_rand_seedZeroes(r, rng, i); 296 } 297 else bc_rand_seedZeroes(r, rng, 1); 298 } 299 300 BcRand bc_rand_int(BcRNG *r) { 301 302 BcRNGData *rng = bc_vec_top(&r->v); 303 304 if (BC_ERR(BC_RAND_ZERO(rng))) bc_rand_srand(rng); 305 306 bc_rand_step(rng); 307 bc_rand_propagate(r, rng); 308 309 return bc_rand_output(rng); 310 } 311 312 BcRand bc_rand_bounded(BcRNG *r, BcRand bound) { 313 314 BcRand rand, threshold = (0 - bound) % bound; 315 316 do { 317 rand = bc_rand_int(r); 318 } while (rand < threshold); 319 320 return rand % bound; 321 } 322 323 void bc_rand_seed(BcRNG *r, ulong state1, ulong state2, ulong inc1, ulong inc2) 324 { 325 BcRNGData *rng = bc_vec_top(&r->v); 326 327 bc_rand_seedState(&rng->inc, inc1, inc2); 328 bc_rand_setInc(rng); 329 bc_rand_setModified(rng); 330 331 if (!state1 && !state2) { 332 memcpy(&rng->state, &rng->inc, sizeof(BcRandState)); 333 bc_rand_step(rng); 334 } 335 else bc_rand_seedState(&rng->state, state1, state2); 336 337 bc_rand_propagate(r, rng); 338 } 339 340 static BcRandState bc_rand_getInc(BcRNGData *r) { 341 342 BcRandState res; 343 344 #if BC_RAND_BUILTIN 345 res = r->inc >> 1; 346 #else // BC_RAND_BUILTIN 347 res = r->inc; 348 res.lo >>= 1; 349 res.lo |= (res.hi & 1) << (BC_LONG_BIT - 1); 350 res.hi >>= 1; 351 #endif // BC_RAND_BUILTIN 352 353 return res; 354 } 355 356 void bc_rand_getRands(BcRNG *r, BcRand *s1, BcRand *s2, BcRand *i1, BcRand *i2) 357 { 358 BcRandState inc; 359 BcRNGData *rng = bc_vec_top(&r->v); 360 361 if (BC_ERR(BC_RAND_ZERO(rng))) bc_rand_srand(rng); 362 363 inc = bc_rand_getInc(rng); 364 365 *s1 = BC_RAND_TRUNC(rng->state); 366 *s2 = BC_RAND_CHOP(rng->state); 367 368 *i1 = BC_RAND_TRUNC(inc); 369 *i2 = BC_RAND_CHOP(inc); 370 } 371 372 void bc_rand_push(BcRNG *r) { 373 BcRNGData rng; 374 memset(&rng, 0, sizeof(BcRNGData)); 375 if (r->v.len > 0) bc_rand_copy(&rng, bc_vec_top(&r->v)); 376 bc_vec_push(&r->v, &rng); 377 } 378 379 void bc_rand_pop(BcRNG *r, bool reset) { 380 bc_vec_npop(&r->v, reset ? r->v.len - 1 : 1); 381 } 382 383 void bc_rand_init(BcRNG *r) { 384 BC_SIG_ASSERT_LOCKED; 385 bc_vec_init(&r->v, sizeof(BcRNGData), NULL); 386 bc_rand_push(r); 387 } 388 389 #ifndef NDEBUG 390 void bc_rand_free(BcRNG *r) { 391 BC_SIG_ASSERT_LOCKED; 392 bc_vec_free(&r->v); 393 } 394 #endif // NDEBUG 395 396 #endif // BC_ENABLE_EXTRA_MATH && BC_ENABLE_RAND 397