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 * Definitions for the RNG. 66 * 67 */ 68 69 #ifndef BC_RAND_H 70 #define BC_RAND_H 71 72 #include <stdint.h> 73 #include <inttypes.h> 74 75 #include <vector.h> 76 #include <num.h> 77 78 #if BC_ENABLE_EXTRA_MATH 79 80 #if BC_ENABLE_RAND 81 82 typedef ulong (*BcRandUlong)(void*); 83 84 #if BC_LONG_BIT >= 64 85 86 #ifdef BC_RAND_BUILTIN 87 #if BC_RAND_BUILTIN 88 #ifndef __SIZEOF_INT128__ 89 #undef BC_RAND_BUILTIN 90 #define BC_RAND_BUILTIN (0) 91 #endif // __SIZEOF_INT128__ 92 #endif // BC_RAND_BUILTIN 93 #endif // BC_RAND_BUILTIN 94 95 #ifndef BC_RAND_BUILTIN 96 #ifdef __SIZEOF_INT128__ 97 #define BC_RAND_BUILTIN (1) 98 #else // __SIZEOF_INT128__ 99 #define BC_RAND_BUILTIN (0) 100 #endif // __SIZEOF_INT128__ 101 #endif // BC_RAND_BUILTIN 102 103 typedef uint64_t BcRand; 104 105 #define BC_RAND_ROTC (63) 106 107 #if BC_RAND_BUILTIN 108 109 typedef __uint128_t BcRandState; 110 111 #define bc_rand_mul(a, b) (((BcRandState) (a)) * ((BcRandState) (b))) 112 #define bc_rand_add(a, b) (((BcRandState) (a)) + ((BcRandState) (b))) 113 114 #define bc_rand_mul2(a, b) (((BcRandState) (a)) * ((BcRandState) (b))) 115 #define bc_rand_add2(a, b) (((BcRandState) (a)) + ((BcRandState) (b))) 116 117 #define BC_RAND_NOTMODIFIED(r) (((r)->inc & 1UL) == 0) 118 #define BC_RAND_ZERO(r) (!(r)->state) 119 120 #define BC_RAND_CONSTANT(h, l) ((((BcRandState) (h)) << 64) + (BcRandState) (l)) 121 122 #define BC_RAND_TRUNC(s) ((uint64_t) (s)) 123 #define BC_RAND_CHOP(s) ((uint64_t) ((s) >> 64UL)) 124 #define BC_RAND_ROTAMT(s) ((unsigned int) ((s) >> 122UL)) 125 126 #else // BC_RAND_BUILTIN 127 128 typedef struct BcRandState { 129 130 uint_fast64_t lo; 131 uint_fast64_t hi; 132 133 } BcRandState; 134 135 #define bc_rand_mul(a, b) (bc_rand_multiply((a), (b))) 136 #define bc_rand_add(a, b) (bc_rand_addition((a), (b))) 137 138 #define bc_rand_mul2(a, b) (bc_rand_multiply2((a), (b))) 139 #define bc_rand_add2(a, b) (bc_rand_addition2((a), (b))) 140 141 #define BC_RAND_NOTMODIFIED(r) (((r)->inc.lo & 1) == 0) 142 #define BC_RAND_ZERO(r) (!(r)->state.lo && !(r)->state.hi) 143 144 #define BC_RAND_CONSTANT(h, l) { .lo = (l), .hi = (h) } 145 146 #define BC_RAND_TRUNC(s) ((s).lo) 147 #define BC_RAND_CHOP(s) ((s).hi) 148 #define BC_RAND_ROTAMT(s) ((unsigned int) ((s).hi >> 58UL)) 149 150 #define BC_RAND_BOTTOM32 (((uint_fast64_t) 0xffffffffULL)) 151 #define BC_RAND_TRUNC32(n) ((n) & BC_RAND_BOTTOM32) 152 #define BC_RAND_CHOP32(n) ((n) >> 32) 153 154 #endif // BC_RAND_BUILTIN 155 156 #define BC_RAND_MULTIPLIER \ 157 BC_RAND_CONSTANT(2549297995355413924ULL, 4865540595714422341ULL) 158 159 #define BC_RAND_FOLD(s) ((BcRand) (BC_RAND_CHOP(s) ^ BC_RAND_TRUNC(s))) 160 161 #else // BC_LONG_BIT >= 64 162 163 #undef BC_RAND_BUILTIN 164 #define BC_RAND_BUILTIN (1) 165 166 typedef uint32_t BcRand; 167 168 #define BC_RAND_ROTC (31) 169 170 typedef uint_fast64_t BcRandState; 171 172 #define bc_rand_mul(a, b) (((BcRandState) (a)) * ((BcRandState) (b))) 173 #define bc_rand_add(a, b) (((BcRandState) (a)) + ((BcRandState) (b))) 174 175 #define bc_rand_mul2(a, b) (((BcRandState) (a)) * ((BcRandState) (b))) 176 #define bc_rand_add2(a, b) (((BcRandState) (a)) + ((BcRandState) (b))) 177 178 #define BC_RAND_NOTMODIFIED(r) (((r)->inc & 1UL) == 0) 179 #define BC_RAND_ZERO(r) (!(r)->state) 180 181 #define BC_RAND_CONSTANT UINT64_C 182 #define BC_RAND_MULTIPLIER BC_RAND_CONSTANT(6364136223846793005) 183 184 #define BC_RAND_TRUNC(s) ((uint32_t) (s)) 185 #define BC_RAND_CHOP(s) ((uint32_t) ((s) >> 32UL)) 186 #define BC_RAND_ROTAMT(s) ((unsigned int) ((s) >> 59UL)) 187 188 #define BC_RAND_FOLD(s) ((BcRand) ((((s) >> 18U) ^ (s)) >> 27U)) 189 190 #endif // BC_LONG_BIT >= 64 191 192 #define BC_RAND_ROT(v, r) \ 193 ((BcRand) (((v) >> (r)) | ((v) << ((0 - (r)) & BC_RAND_ROTC)))) 194 195 #define BC_RAND_BITS (sizeof(BcRand) * CHAR_BIT) 196 #define BC_RAND_STATE_BITS (sizeof(BcRandState) * CHAR_BIT) 197 198 #define BC_RAND_NUM_SIZE (BC_NUM_BIGDIG_LOG10 * 2 + 2) 199 200 #define BC_RAND_SRAND_BITS ((1 << CHAR_BIT) - 1) 201 202 typedef struct BcRNGData { 203 204 BcRandState state; 205 BcRandState inc; 206 207 } BcRNGData; 208 209 typedef struct BcRNG { 210 211 BcVec v; 212 213 } BcRNG; 214 215 void bc_rand_init(BcRNG *r); 216 #ifndef NDEBUG 217 void bc_rand_free(BcRNG *r); 218 #endif // NDEBUG 219 220 BcRand bc_rand_int(BcRNG *r); 221 BcRand bc_rand_bounded(BcRNG *r, BcRand bound); 222 void bc_rand_seed(BcRNG *r, ulong state1, ulong state2, ulong inc1, ulong inc2); 223 void bc_rand_push(BcRNG *r); 224 void bc_rand_pop(BcRNG *r, bool reset); 225 void bc_rand_getRands(BcRNG *r, BcRand *s1, BcRand *s2, BcRand *i1, BcRand *i2); 226 void bc_rand_srand(BcRNGData *rng); 227 228 extern const BcRandState bc_rand_multiplier; 229 230 #endif // BC_ENABLE_RAND 231 232 #endif // BC_ENABLE_EXTRA_MATH 233 234 #endif // BC_RAND_H 235