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 * Definitions for the RNG. 39 * 40 */ 41 42 #ifndef BC_RAND_H 43 #define BC_RAND_H 44 45 #include <stdint.h> 46 #include <inttypes.h> 47 48 #include <vector.h> 49 #include <num.h> 50 51 #if BC_ENABLE_EXTRA_MATH 52 53 #if BC_ENABLE_LIBRARY 54 #define BC_RAND_USE_FREE (1) 55 #else // BC_ENABLE_LIBRARY 56 #ifndef NDEBUG 57 #define BC_RAND_USE_FREE (1) 58 #else // NDEBUG 59 #define BC_RAND_USE_FREE (0) 60 #endif // NDEBUG 61 #endif // BC_ENABLE_LIBRARY 62 63 /** 64 * A function to return a random unsigned long. 65 * @param ptr A void ptr to some data that will help generate the random ulong. 66 * @return The random ulong. 67 */ 68 typedef ulong (*BcRandUlong)(void* ptr); 69 70 #if BC_LONG_BIT >= 64 71 72 // If longs are 64 bits, we have the option of 128-bit integers on some 73 // compilers. These two sections test that. 74 #ifdef BC_RAND_BUILTIN 75 #if BC_RAND_BUILTIN 76 #ifndef __SIZEOF_INT128__ 77 #undef BC_RAND_BUILTIN 78 #define BC_RAND_BUILTIN (0) 79 #endif // __SIZEOF_INT128__ 80 #endif // BC_RAND_BUILTIN 81 #endif // BC_RAND_BUILTIN 82 83 #ifndef BC_RAND_BUILTIN 84 #ifdef __SIZEOF_INT128__ 85 #define BC_RAND_BUILTIN (1) 86 #else // __SIZEOF_INT128__ 87 #define BC_RAND_BUILTIN (0) 88 #endif // __SIZEOF_INT128__ 89 #endif // BC_RAND_BUILTIN 90 91 /// The type for random integers. 92 typedef uint64_t BcRand; 93 94 /// A constant defined by PCG. 95 #define BC_RAND_ROTC (63) 96 97 #if BC_RAND_BUILTIN 98 99 /// A typedef for the PCG state. 100 typedef __uint128_t BcRandState; 101 102 /** 103 * Multiply two integers, worrying about overflow. 104 * @param a The first integer. 105 * @param b The second integer. 106 * @return The product of the PCG states. 107 */ 108 #define bc_rand_mul(a, b) (((BcRandState) (a)) * ((BcRandState) (b))) 109 110 /** 111 * Add two integers, worrying about overflow. 112 * @param a The first integer. 113 * @param b The second integer. 114 * @return The sum of the PCG states. 115 */ 116 #define bc_rand_add(a, b) (((BcRandState) (a)) + ((BcRandState) (b))) 117 118 /** 119 * Multiply two PCG states. 120 * @param a The first PCG state. 121 * @param b The second PCG state. 122 * @return The product of the PCG states. 123 */ 124 #define bc_rand_mul2(a, b) (((BcRandState) (a)) * ((BcRandState) (b))) 125 126 /** 127 * Add two PCG states. 128 * @param a The first PCG state. 129 * @param b The second PCG state. 130 * @return The sum of the PCG states. 131 */ 132 #define bc_rand_add2(a, b) (((BcRandState) (a)) + ((BcRandState) (b))) 133 134 /** 135 * Figure out if the PRNG has been modified. Since the increment of the PRNG has 136 * to be odd, we use the extra bit to store whether it has been modified or not. 137 * @param r The PRNG. 138 * @return True if the PRNG has *not* been modified, false otherwise. 139 */ 140 #define BC_RAND_NOTMODIFIED(r) (((r)->inc & 1UL) == 0) 141 142 /** 143 * Return true if the PRNG has not been seeded yet. 144 * @param r The PRNG. 145 * @return True if the PRNG has not been seeded yet, false otherwise. 146 */ 147 #define BC_RAND_ZERO(r) (!(r)->state) 148 149 /** 150 * Returns a constant built from @a h and @a l. 151 * @param h The high 64 bits. 152 * @param l The low 64 bits. 153 * @return The constant built from @a h and @a l. 154 */ 155 #define BC_RAND_CONSTANT(h, l) ((((BcRandState) (h)) << 64) + (BcRandState) (l)) 156 157 /** 158 * Truncates a PCG state to the number of bits in a random integer. 159 * @param s The state to truncate. 160 * @return The truncated state. 161 */ 162 #define BC_RAND_TRUNC(s) ((uint64_t) (s)) 163 164 /** 165 * Chops a PCG state in half and returns the top bits. 166 * @param s The state to chop. 167 * @return The chopped state's top bits. 168 */ 169 #define BC_RAND_CHOP(s) ((uint64_t) ((s) >> 64UL)) 170 171 /** 172 * Rotates a PCG state. 173 * @param s The state to rotate. 174 * @return The rotated state. 175 */ 176 #define BC_RAND_ROTAMT(s) ((unsigned int) ((s) >> 122UL)) 177 178 #else // BC_RAND_BUILTIN 179 180 /// A typedef for the PCG state. 181 typedef struct BcRandState 182 { 183 /// The low bits. 184 uint_fast64_t lo; 185 186 /// The high bits. 187 uint_fast64_t hi; 188 189 } BcRandState; 190 191 /** 192 * Multiply two integers, worrying about overflow. 193 * @param a The first integer. 194 * @param b The second integer. 195 * @return The product of the PCG states. 196 */ 197 #define bc_rand_mul(a, b) (bc_rand_multiply((a), (b))) 198 199 /** 200 * Add two integers, worrying about overflow. 201 * @param a The first integer. 202 * @param b The second integer. 203 * @return The sum of the PCG states. 204 */ 205 #define bc_rand_add(a, b) (bc_rand_addition((a), (b))) 206 207 /** 208 * Multiply two PCG states. 209 * @param a The first PCG state. 210 * @param b The second PCG state. 211 * @return The product of the PCG states. 212 */ 213 #define bc_rand_mul2(a, b) (bc_rand_multiply2((a), (b))) 214 215 /** 216 * Add two PCG states. 217 * @param a The first PCG state. 218 * @param b The second PCG state. 219 * @return The sum of the PCG states. 220 */ 221 #define bc_rand_add2(a, b) (bc_rand_addition2((a), (b))) 222 223 /** 224 * Figure out if the PRNG has been modified. Since the increment of the PRNG has 225 * to be odd, we use the extra bit to store whether it has been modified or not. 226 * @param r The PRNG. 227 * @return True if the PRNG has *not* been modified, false otherwise. 228 */ 229 #define BC_RAND_NOTMODIFIED(r) (((r)->inc.lo & 1) == 0) 230 231 /** 232 * Return true if the PRNG has not been seeded yet. 233 * @param r The PRNG. 234 * @return True if the PRNG has not been seeded yet, false otherwise. 235 */ 236 #define BC_RAND_ZERO(r) (!(r)->state.lo && !(r)->state.hi) 237 238 /** 239 * Returns a constant built from @a h and @a l. 240 * @param h The high 64 bits. 241 * @param l The low 64 bits. 242 * @return The constant built from @a h and @a l. 243 */ 244 #define BC_RAND_CONSTANT(h, l) \ 245 { \ 246 .lo = (l), .hi = (h) \ 247 } 248 249 /** 250 * Truncates a PCG state to the number of bits in a random integer. 251 * @param s The state to truncate. 252 * @return The truncated state. 253 */ 254 #define BC_RAND_TRUNC(s) ((s).lo) 255 256 /** 257 * Chops a PCG state in half and returns the top bits. 258 * @param s The state to chop. 259 * @return The chopped state's top bits. 260 */ 261 #define BC_RAND_CHOP(s) ((s).hi) 262 263 /** 264 * Returns the rotate amount for a PCG state. 265 * @param s The state to rotate. 266 * @return The semi-rotated state. 267 */ 268 #define BC_RAND_ROTAMT(s) ((unsigned int) ((s).hi >> 58UL)) 269 270 /// A 64-bit integer with the bottom 32 bits set. 271 #define BC_RAND_BOTTOM32 (((uint_fast64_t) 0xffffffffULL)) 272 273 /** 274 * Returns the 32-bit truncated value of @a n. 275 * @param n The integer to truncate. 276 * @return The bottom 32 bits of @a n. 277 */ 278 #define BC_RAND_TRUNC32(n) ((n) & (BC_RAND_BOTTOM32)) 279 280 /** 281 * Returns the second 32 bits of @a n. 282 * @param n The integer to truncate. 283 * @return The second 32 bits of @a n. 284 */ 285 #define BC_RAND_CHOP32(n) ((n) >> 32) 286 287 #endif // BC_RAND_BUILTIN 288 289 /// A constant defined by PCG. 290 #define BC_RAND_MULTIPLIER \ 291 BC_RAND_CONSTANT(2549297995355413924ULL, 4865540595714422341ULL) 292 293 /** 294 * Returns the result of a PCG fold. 295 * @param s The state to fold. 296 * @return The folded state. 297 */ 298 #define BC_RAND_FOLD(s) ((BcRand) (BC_RAND_CHOP(s) ^ BC_RAND_TRUNC(s))) 299 300 #else // BC_LONG_BIT >= 64 301 302 // If we are using 32-bit longs, we need to set these so. 303 #undef BC_RAND_BUILTIN 304 #define BC_RAND_BUILTIN (1) 305 306 /// The type for random integers. 307 typedef uint32_t BcRand; 308 309 /// A constant defined by PCG. 310 #define BC_RAND_ROTC (31) 311 312 /// A typedef for the PCG state. 313 typedef uint_fast64_t BcRandState; 314 315 /** 316 * Multiply two integers, worrying about overflow. 317 * @param a The first integer. 318 * @param b The second integer. 319 * @return The product of the PCG states. 320 */ 321 #define bc_rand_mul(a, b) (((BcRandState) (a)) * ((BcRandState) (b))) 322 323 /** 324 * Add two integers, worrying about overflow. 325 * @param a The first integer. 326 * @param b The second integer. 327 * @return The sum of the PCG states. 328 */ 329 #define bc_rand_add(a, b) (((BcRandState) (a)) + ((BcRandState) (b))) 330 331 /** 332 * Multiply two PCG states. 333 * @param a The first PCG state. 334 * @param b The second PCG state. 335 * @return The product of the PCG states. 336 */ 337 #define bc_rand_mul2(a, b) (((BcRandState) (a)) * ((BcRandState) (b))) 338 339 /** 340 * Add two PCG states. 341 * @param a The first PCG state. 342 * @param b The second PCG state. 343 * @return The sum of the PCG states. 344 */ 345 #define bc_rand_add2(a, b) (((BcRandState) (a)) + ((BcRandState) (b))) 346 347 /** 348 * Figure out if the PRNG has been modified. Since the increment of the PRNG has 349 * to be odd, we use the extra bit to store whether it has been modified or not. 350 * @param r The PRNG. 351 * @return True if the PRNG has *not* been modified, false otherwise. 352 */ 353 #define BC_RAND_NOTMODIFIED(r) (((r)->inc & 1UL) == 0) 354 355 /** 356 * Return true if the PRNG has not been seeded yet. 357 * @param r The PRNG. 358 * @return True if the PRNG has not been seeded yet, false otherwise. 359 */ 360 #define BC_RAND_ZERO(r) (!(r)->state) 361 362 /** 363 * Returns a constant built from a number. 364 * @param n The number. 365 * @return The constant built from @a n. 366 */ 367 #define BC_RAND_CONSTANT(n) UINT64_C(n) 368 369 /// A constant defined by PCG. 370 #define BC_RAND_MULTIPLIER BC_RAND_CONSTANT(6364136223846793005) 371 372 /** 373 * Truncates a PCG state to the number of bits in a random integer. 374 * @param s The state to truncate. 375 * @return The truncated state. 376 */ 377 #define BC_RAND_TRUNC(s) ((uint32_t) (s)) 378 379 /** 380 * Chops a PCG state in half and returns the top bits. 381 * @param s The state to chop. 382 * @return The chopped state's top bits. 383 */ 384 #define BC_RAND_CHOP(s) ((uint32_t) ((s) >> 32UL)) 385 386 /** 387 * Returns the rotate amount for a PCG state. 388 * @param s The state to rotate. 389 * @return The semi-rotated state. 390 */ 391 #define BC_RAND_ROTAMT(s) ((unsigned int) ((s) >> 59UL)) 392 393 /** 394 * Returns the result of a PCG fold. 395 * @param s The state to fold. 396 * @return The folded state. 397 */ 398 #define BC_RAND_FOLD(s) ((BcRand) ((((s) >> 18U) ^ (s)) >> 27U)) 399 400 #endif // BC_LONG_BIT >= 64 401 402 /** 403 * Rotates @a v by @a r bits. 404 * @param v The value to rotate. 405 * @param r The amount to rotate by. 406 * @return The rotated value. 407 */ 408 #define BC_RAND_ROT(v, r) \ 409 ((BcRand) (((v) >> (r)) | ((v) << ((0 - (r)) & BC_RAND_ROTC)))) 410 411 /// The number of bits in a random integer. 412 #define BC_RAND_BITS (sizeof(BcRand) * CHAR_BIT) 413 414 /// The number of bits in a PCG state. 415 #define BC_RAND_STATE_BITS (sizeof(BcRandState) * CHAR_BIT) 416 417 /// The size of a BcNum with the max random integer. This isn't exact; it's 418 /// actually rather crude. But it's always enough. 419 #define BC_RAND_NUM_SIZE (BC_NUM_BIGDIG_LOG10 * 2 + 2) 420 421 /// The mask for how many bits bc_rand_srand() can set per iteration. 422 #define BC_RAND_SRAND_BITS ((1 << CHAR_BIT) - 1) 423 424 /// The actual RNG data. These are the actual PRNG's. 425 typedef struct BcRNGData 426 { 427 /// The state. 428 BcRandState state; 429 430 /// The increment and the modified bit. 431 BcRandState inc; 432 433 } BcRNGData; 434 435 /// The public PRNG. This is just a stack of PRNG's to maintain the globals 436 /// stack illusion. 437 typedef struct BcRNG 438 { 439 /// The stack of PRNG's. 440 BcVec v; 441 442 } BcRNG; 443 444 /** 445 * Initializes a BcRNG. 446 * @param r The BcRNG to initialize. 447 */ 448 void 449 bc_rand_init(BcRNG* r); 450 451 #if BC_RAND_USE_FREE 452 453 /** 454 * Frees a BcRNG. This is only in debug builds because it would only be freed on 455 * exit. 456 * @param r The BcRNG to free. 457 */ 458 void 459 bc_rand_free(BcRNG* r); 460 461 #endif // BC_RAND_USE_FREE 462 463 /** 464 * Returns a random integer from the PRNG. 465 * @param r The PRNG. 466 * @return A random integer. 467 */ 468 BcRand 469 bc_rand_int(BcRNG* r); 470 471 /** 472 * Returns a random integer from the PRNG bounded by @a bound. Bias is 473 * eliminated. 474 * @param r The PRNG. 475 * @param bound The bound for the random integer. 476 * @return A bounded random integer. 477 */ 478 BcRand 479 bc_rand_bounded(BcRNG* r, BcRand bound); 480 481 /** 482 * Seed the PRNG with the state in two parts and the increment in two parts. 483 * @param r The PRNG. 484 * @param state1 The first part of the state. 485 * @param state2 The second part of the state. 486 * @param inc1 The first part of the increment. 487 * @param inc2 The second part of the increment. 488 */ 489 void 490 bc_rand_seed(BcRNG* r, ulong state1, ulong state2, ulong inc1, ulong inc2); 491 492 /** 493 * Pushes a new PRNG onto the PRNG stack. 494 * @param r The PRNG. 495 */ 496 void 497 bc_rand_push(BcRNG* r); 498 499 /** 500 * Pops one or all but one items off of the PRNG stack. 501 * @param r The PRNG. 502 * @param reset True if all but one PRNG should be popped off the stack, false 503 * if only one should be popped. 504 */ 505 void 506 bc_rand_pop(BcRNG* r, bool reset); 507 508 /** 509 * Returns, via pointers, the state of the PRNG in pieces. 510 * @param r The PRNG. 511 * @param s1 The return value for the first part of the state. 512 * @param s2 The return value for the second part of the state. 513 * @param i1 The return value for the first part of the increment. 514 * @param i2 The return value for the second part of the increment. 515 */ 516 void 517 bc_rand_getRands(BcRNG* r, BcRand* s1, BcRand* s2, BcRand* i1, BcRand* i2); 518 519 /** 520 * Seed the PRNG with random data. 521 * @param rng The PRNG. 522 */ 523 void 524 bc_rand_srand(BcRNGData* rng); 525 526 /// A reference to a constant multiplier. 527 extern const BcRandState bc_rand_multiplier; 528 529 #endif // BC_ENABLE_EXTRA_MATH 530 531 #endif // BC_RAND_H 532