1/*
2 * random.h
3 *
4 */
5
6#ifndef BENCHMARKS_RANDOM_H_
7#define BENCHMARKS_RANDOM_H_
8
9#include <stdlib.h>
10
11struct pcg_state_setseq_64 { // Internals are *Private*.
12 uint64_t state; // RNG state. All values are possible.
13 uint64_t inc; // Controls which RNG sequence (stream) is
14 // selected. Must *always* be odd.
15};
16typedef struct pcg_state_setseq_64 pcg32_random_t;
17
18static pcg32_random_t pcg32_global = {0x853c49e6748fea9bULL,
19 0xda3e39cb94b95bdbULL};
20
21static inline uint32_t pcg32_random_r(pcg32_random_t *rng) {
22 uint64_t oldstate = rng->state;
23 rng->state = oldstate * 6364136223846793005ULL + rng->inc;
24 uint32_t xorshifted = (uint32_t)(((oldstate >> 18u) ^ oldstate) >> 27u);
25 uint32_t rot = oldstate >> 59u;
26 return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
27}
28
29static inline uint32_t pcg32_random() { return pcg32_random_r(&pcg32_global); }
30
31static inline uint32_t ranged_random(uint32_t range) {
32 uint64_t random32bit, multiresult;
33 uint32_t leftover;
34 uint32_t threshold;
35 random32bit = pcg32_random();
36 if ((range & (range - 1)) == 0) {
37 return random32bit & (range - 1);
38 }
39 if (range > 0x80000000) { // if range > 1<<31
40 while (random32bit >= range) {
41 random32bit = pcg32_random();
42 }
43 return (uint32_t)random32bit; // [0, range)
44 }
45 multiresult = random32bit * range;
46 leftover = (uint32_t)multiresult;
47 if (leftover < range) {
48 threshold = 0xFFFFFFFF % range;
49 while (leftover <= threshold) {
50 random32bit = pcg32_random();
51 multiresult = random32bit * range;
52 leftover = (uint32_t)multiresult;
53 }
54 }
55 return multiresult >> 32; // [0, range)
56}
57
58// Fisher-Yates shuffle, shuffling an array of integers
59static inline void shuffle_uint16(uint16_t *storage, uint32_t size) {
60 uint32_t i;
61 for (i = size; i > 1; i--) {
62 uint32_t nextpos = ranged_random(i);
63 uint16_t tmp = storage[i - 1]; // likely in cache
64 uint16_t val = storage[nextpos]; // could be costly
65 storage[i - 1] = val;
66 storage[nextpos] = tmp; // you might have to read this store later
67 }
68}
69
70// Fisher-Yates shuffle, shuffling an array of integers
71static inline void shuffle_uint32(uint32_t *storage, uint32_t size) {
72 uint32_t i;
73 for (i = size; i > 1; i--) {
74 uint32_t nextpos = ranged_random(i);
75 uint32_t tmp = storage[i - 1]; // likely in cache
76 uint32_t val = storage[nextpos]; // could be costly
77 storage[i - 1] = val;
78 storage[nextpos] = tmp; // you might have to read this store later
79 }
80}
81
82#endif /* BENCHMARKS_RANDOM_H_ */
83