1 /* 2 * ***************************************************************************** 3 * 4 * SPDX-License-Identifier: BSD-2-Clause 5 * 6 * Copyright (c) 2018-2019 Gavin D. Howard and contributors. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions are met: 10 * 11 * * Redistributions of source code must retain the above copyright notice, this 12 * list of conditions and the following disclaimer. 13 * 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. 17 * 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. 29 * 30 * ***************************************************************************** 31 * 32 * Parts of this code are adapted from the following: 33 * 34 * PCG, A Family of Better Random Number Generators. 35 * 36 * You can find the original source code at: 37 * https://github.com/imneme/pcg-c 38 * 39 * ----------------------------------------------------------------------------- 40 * 41 * Parts of this code are also under the following license: 42 * 43 * Copyright (c) 2014-2017 Melissa O'Neill and PCG Project contributors 44 * 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: 51 * 52 * The above copyright notice and this permission notice shall be included in 53 * all copies or substantial portions of the Software. 54 * 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 61 * SOFTWARE. 62 * 63 * ***************************************************************************** 64 * 65 * Code for the RNG. 66 * 67 */ 68 69 #include <assert.h> 70 #include <stdlib.h> 71 #include <string.h> 72 #include <time.h> 73 #include <fcntl.h> 74 #include <unistd.h> 75 76 #include <status.h> 77 #include <rand.h> 78 #include <vm.h> 79 80 #if BC_ENABLE_EXTRA_MATH && BC_ENABLE_RAND 81 82 #if !BC_RAND_BUILTIN 83 84 static BcRandState bc_rand_addition(uint_fast64_t a, uint_fast64_t b) { 85 86 BcRandState res; 87 88 res.lo = a + b; 89 res.hi = (res.lo < a); 90 91 return res; 92 } 93 94 static BcRandState bc_rand_addition2(BcRandState a, BcRandState b) { 95 96 BcRandState temp, res; 97 98 res = bc_rand_addition(a.lo, b.lo); 99 temp = bc_rand_addition(a.hi, b.hi); 100 res.hi += temp.lo; 101 102 return res; 103 } 104 105 static BcRandState 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 static BcRandState bc_rand_multiply2(BcRandState a, BcRandState b) { 129 130 BcRandState c0, c1, c2, carry; 131 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); 135 136 carry = bc_rand_addition2(c1, c2); 137 carry.hi = carry.lo; 138 carry.lo = 0; 139 140 return bc_rand_addition2(c0, carry); 141 } 142 143 #endif // BC_RAND_BUILTIN 144 145 static void bc_rand_setModified(BcRNGData *r) { 146 147 #if BC_RAND_BUILTIN 148 r->inc |= (BcRandState) 1UL; 149 #else // BC_RAND_BUILTIN 150 r->inc.lo |= (uint_fast64_t) 1UL; 151 #endif // BC_RAND_BUILTIN 152 } 153 154 static void bc_rand_clearModified(BcRNGData *r) { 155 156 #if BC_RAND_BUILTIN 157 r->inc &= ~((BcRandState) 1UL); 158 #else // BC_RAND_BUILTIN 159 r->inc.lo &= ~(1UL); 160 #endif // BC_RAND_BUILTIN 161 } 162 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); 168 } 169 170 static ulong bc_rand_frand(void *ptr) { 171 172 ulong buf[1]; 173 int fd; 174 ssize_t nread; 175 176 assert(ptr != NULL); 177 178 fd = *((int*) ptr); 179 180 nread = read(fd, buf, sizeof(ulong)); 181 182 if (BC_ERR(nread != sizeof(ulong))) bc_vm_err(BC_ERR_FATAL_IO_ERR); 183 184 return *((ulong*) buf); 185 } 186 187 static ulong bc_rand_rand(void *ptr) { 188 189 size_t i; 190 ulong res = 0; 191 192 BC_UNUSED(ptr); 193 194 for (i = 0; i < sizeof(ulong); ++i) 195 res |= ((ulong) (rand() & BC_RAND_SRAND_BITS)) << (i * CHAR_BIT); 196 197 return res; 198 } 199 200 static BcRandState bc_rand_inc(BcRNGData *r) { 201 202 BcRandState inc; 203 204 #if BC_RAND_BUILTIN 205 inc = r->inc | 1; 206 #else // BC_RAND_BUILTIN 207 inc.lo = r->inc.lo | 1; 208 inc.hi = r->inc.hi; 209 #endif // BC_RAND_BUILTIN 210 211 return inc; 212 } 213 214 static void bc_rand_setInc(BcRNGData *r) { 215 216 #if BC_RAND_BUILTIN 217 r->inc <<= 1UL; 218 #else // BC_RAND_BUILTIN 219 r->inc.hi <<= 1UL; 220 r->inc.hi |= (r->inc.lo & (1UL << (BC_LONG_BIT - 1))) >> (BC_LONG_BIT - 1); 221 r->inc.lo <<= 1UL; 222 #endif // BC_RAND_BUILTIN 223 } 224 225 static void bc_rand_seedState(BcRandState *state, ulong val1, ulong val2) { 226 227 #if BC_RAND_BUILTIN 228 *state = ((BcRandState) val1) | ((BcRandState) val2) << (BC_LONG_BIT); 229 #else // BC_RAND_BUILTIN 230 state->lo = val1; 231 state->hi = val2; 232 #endif // BC_RAND_BUILTIN 233 } 234 235 static void bc_rand_seedRNG(BcRNGData *r, ulong state1, ulong state2, 236 ulong inc1, ulong inc2) 237 { 238 bc_rand_seedState(&r->state, state1, state2); 239 bc_rand_seedState(&r->inc, inc1, inc2); 240 bc_rand_setInc(r); 241 } 242 243 static void bc_rand_fill(BcRNGData *r, BcRandUlong fulong, void *ptr) { 244 245 ulong state1, state2, inc1, inc2; 246 247 state1 = fulong(ptr); 248 state2 = fulong(ptr); 249 250 inc1 = fulong(ptr); 251 inc2 = fulong(ptr); 252 253 bc_rand_seedRNG(r, state1, state2, inc1, inc2); 254 } 255 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)); 259 } 260 261 static BcRand bc_rand_output(BcRNGData *r) { 262 return BC_RAND_ROT(BC_RAND_FOLD(r->state), BC_RAND_ROTAMT(r->state)); 263 } 264 265 static void bc_rand_seedZeroes(BcRNG *r, BcRNGData *rng, size_t idx) { 266 267 BcRNGData *rng2; 268 269 if (r->v.len <= idx) return; 270 271 rng2 = bc_vec_item_rev(&r->v, idx); 272 273 if (BC_RAND_ZERO(rng2)) { 274 size_t i; 275 for (i = 1; i < r->v.len; ++i) 276 bc_rand_copy(bc_vec_item_rev(&r->v, i), rng); 277 } 278 } 279 280 void bc_rand_srand(BcRNGData *rng) { 281 282 int fd; 283 284 BC_SIG_LOCK; 285 286 fd = open("/dev/urandom", O_RDONLY); 287 288 if (BC_NO_ERR(fd >= 0)) { 289 bc_rand_fill(rng, bc_rand_frand, &fd); 290 close(fd); 291 } 292 293 while (BC_ERR(BC_RAND_ZERO(rng))) bc_rand_fill(rng, bc_rand_rand, NULL); 294 295 BC_SIG_UNLOCK; 296 } 297 298 static void bc_rand_propagate(BcRNG *r, BcRNGData *rng) { 299 300 if (r->v.len <= 1) return; 301 302 if (BC_RAND_NOTMODIFIED(rng)) { 303 304 size_t i; 305 bool go = true; 306 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); 311 } 312 313 bc_rand_seedZeroes(r, rng, i); 314 } 315 else bc_rand_seedZeroes(r, rng, 1); 316 } 317 318 BcRand bc_rand_int(BcRNG *r) { 319 320 BcRNGData *rng = bc_vec_top(&r->v); 321 322 if (BC_ERR(BC_RAND_ZERO(rng))) bc_rand_srand(rng); 323 324 bc_rand_step(rng); 325 bc_rand_propagate(r, rng); 326 327 return bc_rand_output(rng); 328 } 329 330 BcRand bc_rand_bounded(BcRNG *r, BcRand bound) { 331 332 BcRand rand, threshold = (0 - bound) % bound; 333 334 do { 335 rand = bc_rand_int(r); 336 } while (rand < threshold); 337 338 return rand % bound; 339 } 340 341 void bc_rand_seed(BcRNG *r, ulong state1, ulong state2, ulong inc1, ulong inc2) 342 { 343 BcRNGData *rng = bc_vec_top(&r->v); 344 345 bc_rand_seedState(&rng->inc, inc1, inc2); 346 bc_rand_setInc(rng); 347 bc_rand_setModified(rng); 348 349 if (!state1 && !state2) { 350 memcpy(&rng->state, &rng->inc, sizeof(BcRandState)); 351 bc_rand_step(rng); 352 } 353 else bc_rand_seedState(&rng->state, state1, state2); 354 355 bc_rand_propagate(r, rng); 356 } 357 358 static BcRandState bc_rand_getInc(BcRNGData *r) { 359 360 BcRandState res; 361 362 #if BC_RAND_BUILTIN 363 res = r->inc >> 1; 364 #else // BC_RAND_BUILTIN 365 res = r->inc; 366 res.lo >>= 1; 367 res.lo |= (res.hi & 1) << (BC_LONG_BIT - 1); 368 res.hi >>= 1; 369 #endif // BC_RAND_BUILTIN 370 371 return res; 372 } 373 374 void bc_rand_getRands(BcRNG *r, BcRand *s1, BcRand *s2, BcRand *i1, BcRand *i2) 375 { 376 BcRandState inc; 377 BcRNGData *rng = bc_vec_top(&r->v); 378 379 if (BC_ERR(BC_RAND_ZERO(rng))) bc_rand_srand(rng); 380 381 inc = bc_rand_getInc(rng); 382 383 *s1 = BC_RAND_TRUNC(rng->state); 384 *s2 = BC_RAND_CHOP(rng->state); 385 386 *i1 = BC_RAND_TRUNC(inc); 387 *i2 = BC_RAND_CHOP(inc); 388 } 389 390 void bc_rand_push(BcRNG *r) { 391 BcRNGData rng; 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); 395 } 396 397 void bc_rand_pop(BcRNG *r, bool reset) { 398 bc_vec_npop(&r->v, reset ? r->v.len - 1 : 1); 399 } 400 401 void bc_rand_init(BcRNG *r) { 402 BC_SIG_ASSERT_LOCKED; 403 bc_vec_init(&r->v, sizeof(BcRNGData), NULL); 404 bc_rand_push(r); 405 } 406 407 #ifndef NDEBUG 408 void bc_rand_free(BcRNG *r) { 409 BC_SIG_ASSERT_LOCKED; 410 bc_vec_free(&r->v); 411 } 412 #endif // NDEBUG 413 414 #endif // BC_ENABLE_EXTRA_MATH && BC_ENABLE_RAND 415