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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
|
/*
* SPDX-FileCopyrightText: Alejandro Colomar <alx@kernel.org>
*
* SPDX-License-Identifier: BSD-3-Clause
*/
#include <config.h>
#ident "$Id$"
#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#if HAVE_SYS_RANDOM_H
#include <sys/random.h>
#endif
#include "bit.h"
#include "defines.h"
#include "prototypes.h"
#include "shadowlog.h"
#include "sizeof.h"
static uint32_t csrand32(void);
static uint32_t csrand_uniform32(uint32_t n);
static unsigned long csrand_uniform_slow(unsigned long n);
/*
* Return a uniformly-distributed CS random u_long value.
*/
unsigned long
csrand(void)
{
FILE *fp;
unsigned long r;
#ifdef HAVE_GETENTROPY
/* getentropy may exist but lack kernel support. */
if (getentropy(&r, sizeof(r)) == 0)
return r;
#endif
#ifdef HAVE_GETRANDOM
/* Likewise getrandom. */
if (getrandom(&r, sizeof(r), 0) == sizeof(r))
return r;
#endif
#ifdef HAVE_ARC4RANDOM_BUF
/* arc4random_buf can never fail. */
arc4random_buf(&r, sizeof(r));
return r;
#endif
/* Use /dev/urandom as a last resort. */
fp = fopen("/dev/urandom", "r");
if (NULL == fp) {
goto fail;
}
if (fread(&r, sizeof(r), 1, fp) != 1) {
fclose(fp);
goto fail;
}
fclose(fp);
return r;
fail:
fprintf(log_get_logfd(), _("Unable to obtain random bytes.\n"));
exit(1);
}
/*
* Return a uniformly-distributed CS random value in the interval [0, n-1].
*/
unsigned long
csrand_uniform(unsigned long n)
{
if (n == 0 || n > UINT32_MAX)
return csrand_uniform_slow(n);
return csrand_uniform32(n);
}
/*
* Return a uniformly-distributed CS random value in the interval [min, max].
*/
unsigned long
csrand_interval(unsigned long min, unsigned long max)
{
return csrand_uniform(max - min + 1) + min;
}
static uint32_t
csrand32(void)
{
return csrand();
}
/*
* Fast Random Integer Generation in an Interval
* ACM Transactions on Modeling and Computer Simulation 29 (1), 2019
* <https://arxiv.org/abs/1805.10941>
*/
static uint32_t
csrand_uniform32(uint32_t n)
{
uint32_t bound, rem;
uint64_t r, mult;
if (n == 0)
return csrand32();
bound = -n % n; // analogous to `2^32 % n`, since `x % y == (x-y) % y`
do {
r = csrand32();
mult = r * n;
rem = mult; // analogous to `mult % 2^32`
} while (rem < bound); // p = (2^32 % n) / 2^32; W.C.: n=2^31+1, p=0.5
r = mult >> WIDTHOF(n); // analogous to `mult / 2^32`
return r;
}
static unsigned long
csrand_uniform_slow(unsigned long n)
{
unsigned long r, max, mask;
max = n - 1;
mask = bit_ceil_wrapul(n) - 1;
do {
r = csrand();
r &= mask; // optimization
} while (r > max); // p = ((mask+1) % n) / (mask+1); W.C.: p=0.5
return r;
}
|
