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-2024 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 #if BC_DEBUG 57 #define BC_RAND_USE_FREE (1) 58 #else // BC_DEBUG 59 #define BC_RAND_USE_FREE (0) 60 #endif // BC_DEBUG 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) { .lo = (l), .hi = (h) } 245 246 /** 247 * Truncates a PCG state to the number of bits in a random integer. 248 * @param s The state to truncate. 249 * @return The truncated state. 250 */ 251 #define BC_RAND_TRUNC(s) ((s).lo) 252 253 /** 254 * Chops a PCG state in half and returns the top bits. 255 * @param s The state to chop. 256 * @return The chopped state's top bits. 257 */ 258 #define BC_RAND_CHOP(s) ((s).hi) 259 260 /** 261 * Returns the rotate amount for a PCG state. 262 * @param s The state to rotate. 263 * @return The semi-rotated state. 264 */ 265 #define BC_RAND_ROTAMT(s) ((unsigned int) ((s).hi >> 58UL)) 266 267 /// A 64-bit integer with the bottom 32 bits set. 268 #define BC_RAND_BOTTOM32 (((uint_fast64_t) 0xffffffffULL)) 269 270 /** 271 * Returns the 32-bit truncated value of @a n. 272 * @param n The integer to truncate. 273 * @return The bottom 32 bits of @a n. 274 */ 275 #define BC_RAND_TRUNC32(n) ((n) & (BC_RAND_BOTTOM32)) 276 277 /** 278 * Returns the second 32 bits of @a n. 279 * @param n The integer to truncate. 280 * @return The second 32 bits of @a n. 281 */ 282 #define BC_RAND_CHOP32(n) ((n) >> 32) 283 284 #endif // BC_RAND_BUILTIN 285 286 /// A constant defined by PCG. 287 #define BC_RAND_MULTIPLIER \ 288 BC_RAND_CONSTANT(2549297995355413924ULL, 4865540595714422341ULL) 289 290 /** 291 * Returns the result of a PCG fold. 292 * @param s The state to fold. 293 * @return The folded state. 294 */ 295 #define BC_RAND_FOLD(s) ((BcRand) (BC_RAND_CHOP(s) ^ BC_RAND_TRUNC(s))) 296 297 #else // BC_LONG_BIT >= 64 298 299 // If we are using 32-bit longs, we need to set these so. 300 #undef BC_RAND_BUILTIN 301 #define BC_RAND_BUILTIN (1) 302 303 /// The type for random integers. 304 typedef uint32_t BcRand; 305 306 /// A constant defined by PCG. 307 #define BC_RAND_ROTC (31) 308 309 /// A typedef for the PCG state. 310 typedef uint_fast64_t BcRandState; 311 312 /** 313 * Multiply two integers, worrying about overflow. 314 * @param a The first integer. 315 * @param b The second integer. 316 * @return The product of the PCG states. 317 */ 318 #define bc_rand_mul(a, b) (((BcRandState) (a)) * ((BcRandState) (b))) 319 320 /** 321 * Add two integers, worrying about overflow. 322 * @param a The first integer. 323 * @param b The second integer. 324 * @return The sum of the PCG states. 325 */ 326 #define bc_rand_add(a, b) (((BcRandState) (a)) + ((BcRandState) (b))) 327 328 /** 329 * Multiply two PCG states. 330 * @param a The first PCG state. 331 * @param b The second PCG state. 332 * @return The product of the PCG states. 333 */ 334 #define bc_rand_mul2(a, b) (((BcRandState) (a)) * ((BcRandState) (b))) 335 336 /** 337 * Add two PCG states. 338 * @param a The first PCG state. 339 * @param b The second PCG state. 340 * @return The sum of the PCG states. 341 */ 342 #define bc_rand_add2(a, b) (((BcRandState) (a)) + ((BcRandState) (b))) 343 344 /** 345 * Figure out if the PRNG has been modified. Since the increment of the PRNG has 346 * to be odd, we use the extra bit to store whether it has been modified or not. 347 * @param r The PRNG. 348 * @return True if the PRNG has *not* been modified, false otherwise. 349 */ 350 #define BC_RAND_NOTMODIFIED(r) (((r)->inc & 1UL) == 0) 351 352 /** 353 * Return true if the PRNG has not been seeded yet. 354 * @param r The PRNG. 355 * @return True if the PRNG has not been seeded yet, false otherwise. 356 */ 357 #define BC_RAND_ZERO(r) (!(r)->state) 358 359 /** 360 * Returns a constant built from a number. 361 * @param n The number. 362 * @return The constant built from @a n. 363 */ 364 #define BC_RAND_CONSTANT(n) UINT64_C(n) 365 366 /// A constant defined by PCG. 367 #define BC_RAND_MULTIPLIER BC_RAND_CONSTANT(6364136223846793005) 368 369 /** 370 * Truncates a PCG state to the number of bits in a random integer. 371 * @param s The state to truncate. 372 * @return The truncated state. 373 */ 374 #define BC_RAND_TRUNC(s) ((uint32_t) (s)) 375 376 /** 377 * Chops a PCG state in half and returns the top bits. 378 * @param s The state to chop. 379 * @return The chopped state's top bits. 380 */ 381 #define BC_RAND_CHOP(s) ((uint32_t) ((s) >> 32UL)) 382 383 /** 384 * Returns the rotate amount for a PCG state. 385 * @param s The state to rotate. 386 * @return The semi-rotated state. 387 */ 388 #define BC_RAND_ROTAMT(s) ((unsigned int) ((s) >> 59UL)) 389 390 /** 391 * Returns the result of a PCG fold. 392 * @param s The state to fold. 393 * @return The folded state. 394 */ 395 #define BC_RAND_FOLD(s) ((BcRand) ((((s) >> 18U) ^ (s)) >> 27U)) 396 397 #endif // BC_LONG_BIT >= 64 398 399 /** 400 * Rotates @a v by @a r bits. 401 * @param v The value to rotate. 402 * @param r The amount to rotate by. 403 * @return The rotated value. 404 */ 405 #define BC_RAND_ROT(v, r) \ 406 ((BcRand) (((v) >> (r)) | ((v) << ((0 - (r)) & BC_RAND_ROTC)))) 407 408 /// The number of bits in a random integer. 409 #define BC_RAND_BITS (sizeof(BcRand) * CHAR_BIT) 410 411 /// The number of bits in a PCG state. 412 #define BC_RAND_STATE_BITS (sizeof(BcRandState) * CHAR_BIT) 413 414 /// The size of a BcNum with the max random integer. This isn't exact; it's 415 /// actually rather crude. But it's always enough. 416 #define BC_RAND_NUM_SIZE (BC_NUM_BIGDIG_LOG10 * 2 + 2) 417 418 /// The mask for how many bits bc_rand_srand() can set per iteration. 419 #define BC_RAND_SRAND_BITS ((1 << CHAR_BIT) - 1) 420 421 /// The actual RNG data. These are the actual PRNG's. 422 typedef struct BcRNGData 423 { 424 /// The state. 425 BcRandState state; 426 427 /// The increment and the modified bit. 428 BcRandState inc; 429 430 } BcRNGData; 431 432 /// The public PRNG. This is just a stack of PRNG's to maintain the globals 433 /// stack illusion. 434 typedef struct BcRNG 435 { 436 /// The stack of PRNG's. 437 BcVec v; 438 439 } BcRNG; 440 441 /** 442 * Initializes a BcRNG. 443 * @param r The BcRNG to initialize. 444 */ 445 void 446 bc_rand_init(BcRNG* r); 447 448 #if BC_RAND_USE_FREE 449 450 /** 451 * Frees a BcRNG. This is only in debug builds because it would only be freed on 452 * exit. 453 * @param r The BcRNG to free. 454 */ 455 void 456 bc_rand_free(BcRNG* r); 457 458 #endif // BC_RAND_USE_FREE 459 460 /** 461 * Returns a random integer from the PRNG. 462 * @param r The PRNG. 463 * @return A random integer. 464 */ 465 BcRand 466 bc_rand_int(BcRNG* r); 467 468 /** 469 * Returns a random integer from the PRNG bounded by @a bound. Bias is 470 * eliminated. 471 * @param r The PRNG. 472 * @param bound The bound for the random integer. 473 * @return A bounded random integer. 474 */ 475 BcRand 476 bc_rand_bounded(BcRNG* r, BcRand bound); 477 478 /** 479 * Seed the PRNG with the state in two parts and the increment in two parts. 480 * @param r The PRNG. 481 * @param state1 The first part of the state. 482 * @param state2 The second part of the state. 483 * @param inc1 The first part of the increment. 484 * @param inc2 The second part of the increment. 485 */ 486 void 487 bc_rand_seed(BcRNG* r, ulong state1, ulong state2, ulong inc1, ulong inc2); 488 489 /** 490 * Pushes a new PRNG onto the PRNG stack. 491 * @param r The PRNG. 492 */ 493 void 494 bc_rand_push(BcRNG* r); 495 496 /** 497 * Pops one or all but one items off of the PRNG stack. 498 * @param r The PRNG. 499 * @param reset True if all but one PRNG should be popped off the stack, false 500 * if only one should be popped. 501 */ 502 void 503 bc_rand_pop(BcRNG* r, bool reset); 504 505 /** 506 * Returns, via pointers, the state of the PRNG in pieces. 507 * @param r The PRNG. 508 * @param s1 The return value for the first part of the state. 509 * @param s2 The return value for the second part of the state. 510 * @param i1 The return value for the first part of the increment. 511 * @param i2 The return value for the second part of the increment. 512 */ 513 void 514 bc_rand_getRands(BcRNG* r, BcRand* s1, BcRand* s2, BcRand* i1, BcRand* i2); 515 516 /** 517 * Seed the PRNG with random data. 518 * @param rng The PRNG. 519 */ 520 void 521 bc_rand_srand(BcRNGData* rng); 522 523 /// A reference to a constant multiplier. 524 extern const BcRandState bc_rand_multiplier; 525 526 #endif // BC_ENABLE_EXTRA_MATH 527 528 #endif // BC_RAND_H 529