contrib/bc/src/rand.c

   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