random32.c
3.83 KB
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
151
152
153
154
/*
This is a maximally equidistributed combined Tausworthe generator
based on code from GNU Scientific Library 1.5 (30 Jun 2004)
x_n = (s1_n ^ s2_n ^ s3_n)
s1_{n+1} = (((s1_n & 4294967294) <<12) ^ (((s1_n <<13) ^ s1_n) >>19))
s2_{n+1} = (((s2_n & 4294967288) << 4) ^ (((s2_n << 2) ^ s2_n) >>25))
s3_{n+1} = (((s3_n & 4294967280) <<17) ^ (((s3_n << 3) ^ s3_n) >>11))
The period of this generator is about 2^88.
From: P. L'Ecuyer, "Maximally Equidistributed Combined Tausworthe
Generators", Mathematics of Computation, 65, 213 (1996), 203--213.
This is available on the net from L'Ecuyer's home page,
http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps
ftp://ftp.iro.umontreal.ca/pub/simulation/lecuyer/papers/tausme.ps
There is an erratum in the paper "Tables of Maximally
Equidistributed Combined LFSR Generators", Mathematics of
Computation, 68, 225 (1999), 261--269:
http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps
... the k_j most significant bits of z_j must be non-
zero, for each j. (Note: this restriction also applies to the
computer code given in [4], but was mistakenly not mentioned in
that paper.)
This affects the seeding procedure by imposing the requirement
s1 > 1, s2 > 7, s3 > 15.
*/
#include <linux/types.h>
#include <linux/percpu.h>
#include <linux/module.h>
#include <linux/jiffies.h>
#include <linux/random.h>
struct rnd_state {
u32 s1, s2, s3;
};
static DEFINE_PER_CPU(struct rnd_state, net_rand_state);
static u32 __random32(struct rnd_state *state)
{
#define TAUSWORTHE(s,a,b,c,d) ((s&c)<<d) ^ (((s <<a) ^ s)>>b)
state->s1 = TAUSWORTHE(state->s1, 13, 19, 4294967294UL, 12);
state->s2 = TAUSWORTHE(state->s2, 2, 25, 4294967288UL, 4);
state->s3 = TAUSWORTHE(state->s3, 3, 11, 4294967280UL, 17);
return (state->s1 ^ state->s2 ^ state->s3);
}
/*
* Handle minimum values for seeds
*/
static inline u32 __seed(u32 x, u32 m)
{
return (x < m) ? x + m : x;
}
/**
* random32 - pseudo random number generator
*
* A 32 bit pseudo-random number is generated using a fast
* algorithm suitable for simulation. This algorithm is NOT
* considered safe for cryptographic use.
*/
u32 random32(void)
{
unsigned long r;
struct rnd_state *state = &get_cpu_var(net_rand_state);
r = __random32(state);
put_cpu_var(state);
return r;
}
EXPORT_SYMBOL(random32);
/**
* srandom32 - add entropy to pseudo random number generator
* @seed: seed value
*
* Add some additional seeding to the random32() pool.
*/
void srandom32(u32 entropy)
{
int i;
/*
* No locking on the CPUs, but then somewhat random results are, well,
* expected.
*/
for_each_possible_cpu (i) {
struct rnd_state *state = &per_cpu(net_rand_state, i);
state->s1 = __seed(state->s1 ^ entropy, 1);
}
}
EXPORT_SYMBOL(srandom32);
/*
* Generate some initially weak seeding values to allow
* to start the random32() engine.
*/
static int __init random32_init(void)
{
int i;
for_each_possible_cpu(i) {
struct rnd_state *state = &per_cpu(net_rand_state,i);
#define LCG(x) ((x) * 69069) /* super-duper LCG */
state->s1 = __seed(LCG(i + jiffies), 1);
state->s2 = __seed(LCG(state->s1), 7);
state->s3 = __seed(LCG(state->s2), 15);
/* "warm it up" */
__random32(state);
__random32(state);
__random32(state);
__random32(state);
__random32(state);
__random32(state);
}
return 0;
}
core_initcall(random32_init);
/*
* Generate better values after random number generator
* is fully initalized.
*/
static int __init random32_reseed(void)
{
int i;
for_each_possible_cpu(i) {
struct rnd_state *state = &per_cpu(net_rand_state,i);
u32 seeds[3];
get_random_bytes(&seeds, sizeof(seeds));
state->s1 = __seed(seeds[0], 1);
state->s2 = __seed(seeds[1], 7);
state->s3 = __seed(seeds[2], 15);
/* mix it in */
__random32(state);
}
return 0;
}
late_initcall(random32_reseed);