projects/linux·blob master · refs

136 lines · 4.2 KiB

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 */
53u32 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}
63EXPORT_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 */
75void 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}
94EXPORT_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)
101void prandom_warmup(struct rnd_state *state);
102#endif
103VISIBLE_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}
117EXPORT_SYMBOL_IF_KUNIT(prandom_warmup);
118
119void 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}
136EXPORT_SYMBOL(prandom_seed_full_state);