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-2023 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 */
68typedef 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.
92typedef 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.
100typedef __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.
181typedef 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.
307typedef uint32_t BcRand;
308
309/// A constant defined by PCG.
310#define BC_RAND_ROTC (31)
311
312/// A typedef for the PCG state.
313typedef 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.
425typedef 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.
437typedef 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 */
448void
449bc_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 */
458void
459bc_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 */
468BcRand
469bc_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 */
478BcRand
479bc_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 */
489void
490bc_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 */
496void
497bc_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 */
505void
506bc_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 */
516void
517bc_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 */
523void
524bc_rand_srand(BcRNGData* rng);
525
526/// A reference to a constant multiplier.
527extern const BcRandState bc_rand_multiplier;
528
529#endif // BC_ENABLE_EXTRA_MATH
530
531#endif // BC_RAND_H
532