1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * This is a maximally equidistributed combined Tausworthe generator 4 * based on code from GNU Scientific Library 1.5 (30 Jun 2004) 5 * 6 * lfsr113 version: 7 * 8 * x_n = (s1_n ^ s2_n ^ s3_n ^ s4_n) 9 * 10 * s1_{n+1} = (((s1_n & 4294967294) << 18) ^ (((s1_n << 6) ^ s1_n) >> 13)) 11 * s2_{n+1} = (((s2_n & 4294967288) << 2) ^ (((s2_n << 2) ^ s2_n) >> 27)) 12 * s3_{n+1} = (((s3_n & 4294967280) << 7) ^ (((s3_n << 13) ^ s3_n) >> 21)) 13 * s4_{n+1} = (((s4_n & 4294967168) << 13) ^ (((s4_n << 3) ^ s4_n) >> 12)) 14 * 15 * The period of this generator is about 2^113 (see erratum paper). 16 * 17 * From: P. L'Ecuyer, "Maximally Equidistributed Combined Tausworthe 18 * Generators", Mathematics of Computation, 65, 213 (1996), 203--213: 19 * http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps 20 * ftp://ftp.iro.umontreal.ca/pub/simulation/lecuyer/papers/tausme.ps 21 * 22 * There is an erratum in the paper "Tables of Maximally Equidistributed 23 * Combined LFSR Generators", Mathematics of Computation, 68, 225 (1999), 24 * 261--269: http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps 25 * 26 * ... the k_j most significant bits of z_j must be non-zero, 27 * for each j. (Note: this restriction also applies to the 28 * computer code given in [4], but was mistakenly not mentioned 29 * in that paper.) 30 * 31 * This affects the seeding procedure by imposing the requirement 32 * s1 > 1, s2 > 7, s3 > 15, s4 > 127. 33 */ 34 35 #include <linux/types.h> 36 #include <linux/percpu.h> 37 #include <linux/export.h> 38 #include <linux/jiffies.h> 39 #include <linux/prandom.h> 40 #include <linux/sched.h> 41 #include <linux/bitops.h> 42 #include <linux/slab.h> 43 #include <linux/unaligned.h> 44 #include <kunit/visibility.h> 45 46 /** 47 * prandom_u32_state - seeded pseudo-random number generator. 48 * @state: pointer to state structure holding seeded state. 49 * 50 * This is used for pseudo-randomness with no outside seeding. 51 * For more random results, use get_random_u32(). 52 */ 53 u32 prandom_u32_state(struct rnd_state *state) 54 { 55 #define TAUSWORTHE(s, a, b, c, d) ((s & c) << d) ^ (((s << a) ^ s) >> b) 56 state->s1 = TAUSWORTHE(state->s1, 6U, 13U, 4294967294U, 18U); 57 state->s2 = TAUSWORTHE(state->s2, 2U, 27U, 4294967288U, 2U); 58 state->s3 = TAUSWORTHE(state->s3, 13U, 21U, 4294967280U, 7U); 59 state->s4 = TAUSWORTHE(state->s4, 3U, 12U, 4294967168U, 13U); 60 61 return (state->s1 ^ state->s2 ^ state->s3 ^ state->s4); 62 } 63 EXPORT_SYMBOL(prandom_u32_state); 64 65 /** 66 * prandom_bytes_state - get the requested number of pseudo-random bytes 67 * 68 * @state: pointer to state structure holding seeded state. 69 * @buf: where to copy the pseudo-random bytes to 70 * @bytes: the requested number of bytes 71 * 72 * This is used for pseudo-randomness with no outside seeding. 73 * For more random results, use get_random_bytes(). 74 */ 75 void prandom_bytes_state(struct rnd_state *state, void *buf, size_t bytes) 76 { 77 u8 *ptr = buf; 78 79 while (bytes >= sizeof(u32)) { 80 put_unaligned(prandom_u32_state(state), (u32 *) ptr); 81 ptr += sizeof(u32); 82 bytes -= sizeof(u32); 83 } 84 85 if (bytes > 0) { 86 u32 rem = prandom_u32_state(state); 87 do { 88 *ptr++ = (u8) rem; 89 bytes--; 90 rem >>= BITS_PER_BYTE; 91 } while (bytes > 0); 92 } 93 } 94 EXPORT_SYMBOL(prandom_bytes_state); 95 96 /* 97 * Only declared here so that it has a prototype when made 98 * non-static for KUnit testing (avoids -Wmissing-prototypes). 99 */ 100 #if IS_ENABLED(CONFIG_KUNIT) 101 void prandom_warmup(struct rnd_state *state); 102 #endif 103 VISIBLE_IF_KUNIT void prandom_warmup(struct rnd_state *state) 104 { 105 /* Calling RNG ten times to satisfy recurrence condition */ 106 prandom_u32_state(state); 107 prandom_u32_state(state); 108 prandom_u32_state(state); 109 prandom_u32_state(state); 110 prandom_u32_state(state); 111 prandom_u32_state(state); 112 prandom_u32_state(state); 113 prandom_u32_state(state); 114 prandom_u32_state(state); 115 prandom_u32_state(state); 116 } 117 EXPORT_SYMBOL_IF_KUNIT(prandom_warmup); 118 119 void prandom_seed_full_state(struct rnd_state __percpu *pcpu_state) 120 { 121 int i; 122 123 for_each_possible_cpu(i) { 124 struct rnd_state *state = per_cpu_ptr(pcpu_state, i); 125 u32 seeds[4]; 126 127 get_random_bytes(&seeds, sizeof(seeds)); 128 state->s1 = __seed(seeds[0], 2U); 129 state->s2 = __seed(seeds[1], 8U); 130 state->s3 = __seed(seeds[2], 16U); 131 state->s4 = __seed(seeds[3], 128U); 132 133 prandom_warmup(state); 134 } 135 } 136 EXPORT_SYMBOL(prandom_seed_full_state); 137