1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
// SPDX-License-Identifier: BSD-3-Clause
/* Copyright 2019, Intel Corporation */
/*
* rand.c -- random utils
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <unistd.h>
#include "rand.h"
#ifdef _WIN32
# include <bcrypt.h>
# include <process.h>
#else
# include <sys/syscall.h>
# include <pthread.h>
# ifdef __APPLE__
# include <sys/random.h>
# endif
#endif
/*
* hash64 -- a u64 -> u64 hash
*/
uint64_t
hash64(uint64_t x)
{
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
/*
* xoshiro256** random generator
*
* Fastest available good PRNG as of 2018 (sub-nanosecond per entry), produces
* much better output than old stuff like rand() or Mersenne's Twister.
*
* By David Blackman and Sebastiano Vigna; PD/CC0 2018.
*
* It has a period of 2²⁵⁶-1, excluding all-zero state; it must always get
* initialized to avoid that zero.
*/
static inline uint64_t rotl(const uint64_t x, int k)
{
/* optimized to a single instruction on x86 */
return (x << k) | (x >> (64 - k));
}
/*
* rnd64_r -- return 64-bits of randomness
*/
uint64_t
rnd64_r(rng_t *state)
{
uint64_t *s = (void *)state;
const uint64_t result = rotl(s[1] * 5, 7) * 9;
const uint64_t t = s[1] << 17;
s[2] ^= s[0];
s[3] ^= s[1];
s[1] ^= s[2];
s[0] ^= s[3];
s[2] ^= t;
s[3] = rotl(s[3], 45);
return result;
}
/*
* randomize_r -- initialize random generator
*
* Seed of 0 means random.
*/
void
randomize_r(rng_t *state, uint64_t seed)
{
if (!seed) {
#ifdef SYS_getrandom
/* We want getentropy() but ancient Red Hat lacks it. */
if (syscall(SYS_getrandom, state, sizeof(rng_t), 0)
== sizeof(rng_t)) {
return; /* nofail, but ENOSYS on kernel < 3.16 */
}
#elif _WIN32
#pragma comment(lib, "Bcrypt.lib")
if (BCryptGenRandom(NULL, (PUCHAR)state, sizeof(rng_t),
BCRYPT_USE_SYSTEM_PREFERRED_RNG)) {
return;
}
#else
if (!getentropy(state, sizeof(rng_t)))
return;
#endif
// best effort fallback
seed = (uint64_t)pthread_self();
}
uint64_t *s = (void *)state;
s[0] = hash64(seed);
s[1] = hash64(s[0]);
s[2] = hash64(s[1]);
s[3] = hash64(s[2]);
}
static rng_t global_rng;
/*
* rnd64 -- global state version of rnd64_t
*/
uint64_t
rnd64(void)
{
return rnd64_r(&global_rng);
}
/*
* randomize -- initialize global RNG
*/
void
randomize(uint64_t seed)
{
randomize_r(&global_rng, seed);
}
|
