random32.c 5.21 KB
 Stephen Hemminger committed Oct 17, 2006 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 ``````/* 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 #include `````` Paul Gortmaker committed Mar 07, 2012 38 ``````#include `````` Al Viro committed Dec 04, 2006 39 ``````#include `````` Stephen Hemminger committed Oct 17, 2006 40 41 42 43 ``````#include static DEFINE_PER_CPU(struct rnd_state, net_rand_state); `````` Joe Eykholt committed May 27, 2010 44 ``````/** `````` Akinobu Mita committed Dec 17, 2012 45 `````` * prandom_u32_state - seeded pseudo-random number generator. `````` Joe Eykholt committed May 27, 2010 46 47 48 `````` * @state: pointer to state structure holding seeded state. * * This is used for pseudo-randomness with no outside seeding. `````` Akinobu Mita committed Dec 17, 2012 49 `````` * For more random results, use prandom_u32(). `````` Joe Eykholt committed May 27, 2010 50 `````` */ `````` Akinobu Mita committed Dec 17, 2012 51 ``````u32 prandom_u32_state(struct rnd_state *state) `````` Stephen Hemminger committed Oct 17, 2006 52 53 54 55 56 57 58 59 60 ``````{ #define TAUSWORTHE(s,a,b,c,d) ((s&c)<>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); } `````` Akinobu Mita committed Dec 17, 2012 61 ``````EXPORT_SYMBOL(prandom_u32_state); `````` Stephen Hemminger committed Oct 17, 2006 62 63 `````` /** `````` Akinobu Mita committed Dec 17, 2012 64 `````` * prandom_u32 - pseudo random number generator `````` Stephen Hemminger committed Oct 17, 2006 65 66 67 68 69 `````` * * A 32 bit pseudo-random number is generated using a fast * algorithm suitable for simulation. This algorithm is NOT * considered safe for cryptographic use. */ `````` Akinobu Mita committed Dec 17, 2012 70 ``````u32 prandom_u32(void) `````` Stephen Hemminger committed Oct 17, 2006 71 72 73 ``````{ unsigned long r; struct rnd_state *state = &get_cpu_var(net_rand_state); `````` Akinobu Mita committed Dec 17, 2012 74 `````` r = prandom_u32_state(state); `````` Stephen Hemminger committed Oct 17, 2006 75 76 77 `````` put_cpu_var(state); return r; } `````` Akinobu Mita committed Dec 17, 2012 78 ``````EXPORT_SYMBOL(prandom_u32); `````` Stephen Hemminger committed Oct 17, 2006 79 `````` `````` Akinobu Mita committed Dec 17, 2012 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 ``````/* * prandom_bytes_state - get the requested number of pseudo-random bytes * * @state: pointer to state structure holding seeded state. * @buf: where to copy the pseudo-random bytes to * @bytes: the requested number of bytes * * This is used for pseudo-randomness with no outside seeding. * For more random results, use prandom_bytes(). */ void prandom_bytes_state(struct rnd_state *state, void *buf, int bytes) { unsigned char *p = buf; int i; for (i = 0; i < round_down(bytes, sizeof(u32)); i += sizeof(u32)) { u32 random = prandom_u32_state(state); int j; for (j = 0; j < sizeof(u32); j++) { p[i + j] = random; random >>= BITS_PER_BYTE; } } if (i < bytes) { u32 random = prandom_u32_state(state); for (; i < bytes; i++) { p[i] = random; random >>= BITS_PER_BYTE; } } } EXPORT_SYMBOL(prandom_bytes_state); /** * prandom_bytes - get the requested number of pseudo-random bytes * @buf: where to copy the pseudo-random bytes to * @bytes: the requested number of bytes */ void prandom_bytes(void *buf, int bytes) { struct rnd_state *state = &get_cpu_var(net_rand_state); prandom_bytes_state(state, buf, bytes); put_cpu_var(state); } EXPORT_SYMBOL(prandom_bytes); `````` Stephen Hemminger committed Oct 17, 2006 129 ``````/** `````` Akinobu Mita committed Dec 17, 2012 130 `````` * prandom_seed - add entropy to pseudo random number generator `````` Stephen Hemminger committed Oct 17, 2006 131 132 `````` * @seed: seed value * `````` Akinobu Mita committed Dec 17, 2012 133 `````` * Add some additional seeding to the prandom pool. `````` Stephen Hemminger committed Oct 17, 2006 134 `````` */ `````` Akinobu Mita committed Dec 17, 2012 135 ``````void prandom_seed(u32 entropy) `````` Stephen Hemminger committed Oct 17, 2006 136 ``````{ `````` Andi Kleen committed Apr 03, 2008 137 138 139 140 141 142 143 `````` 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); `````` Stephen Hemminger committed Jul 30, 2008 144 `````` state->s1 = __seed(state->s1 ^ entropy, 1); `````` Andi Kleen committed Apr 03, 2008 145 `````` } `````` Stephen Hemminger committed Oct 17, 2006 146 ``````} `````` Akinobu Mita committed Dec 17, 2012 147 ``````EXPORT_SYMBOL(prandom_seed); `````` Stephen Hemminger committed Oct 17, 2006 148 149 150 `````` /* * Generate some initially weak seeding values to allow `````` Akinobu Mita committed Dec 17, 2012 151 `````` * to start the prandom_u32() engine. `````` Stephen Hemminger committed Oct 17, 2006 152 `````` */ `````` Akinobu Mita committed Dec 17, 2012 153 ``````static int __init prandom_init(void) `````` Stephen Hemminger committed Oct 17, 2006 154 155 156 157 158 ``````{ int i; for_each_possible_cpu(i) { struct rnd_state *state = &per_cpu(net_rand_state,i); `````` Stephen Hemminger committed Jul 30, 2008 159 160 161 162 163 164 165 `````` #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" */ `````` Akinobu Mita committed Dec 17, 2012 166 167 168 169 170 171 `````` prandom_u32_state(state); prandom_u32_state(state); prandom_u32_state(state); prandom_u32_state(state); prandom_u32_state(state); prandom_u32_state(state); `````` Stephen Hemminger committed Oct 17, 2006 172 173 174 `````` } return 0; } `````` Akinobu Mita committed Dec 17, 2012 175 ``````core_initcall(prandom_init); `````` Stephen Hemminger committed Oct 17, 2006 176 177 178 `````` /* * Generate better values after random number generator `````` Uwe Kleine-König committed Jun 16, 2010 179 `````` * is fully initialized. `````` Stephen Hemminger committed Oct 17, 2006 180 `````` */ `````` Akinobu Mita committed Dec 17, 2012 181 ``````static int __init prandom_reseed(void) `````` Stephen Hemminger committed Oct 17, 2006 182 183 184 185 186 ``````{ int i; for_each_possible_cpu(i) { struct rnd_state *state = &per_cpu(net_rand_state,i); `````` Stephen Hemminger committed Jul 30, 2008 187 188 189 190 191 192 `````` 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); `````` Stephen Hemminger committed Oct 17, 2006 193 `````` `````` Stephen Hemminger committed Jul 30, 2008 194 `````` /* mix it in */ `````` Akinobu Mita committed Dec 17, 2012 195 `````` prandom_u32_state(state); `````` Stephen Hemminger committed Oct 17, 2006 196 197 198 `````` } return 0; } `````` Akinobu Mita committed Dec 17, 2012 199 ``late_initcall(prandom_reseed);``