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