xref: /openbmc/linux/lib/math/prime_numbers.c (revision 2c64e9cb0b6b858901e9a386860d7d929d1cbaeb)
1 *2c64e9cbSAndy Shevchenko #define pr_fmt(fmt) "prime numbers: " fmt "\n"
2 *2c64e9cbSAndy Shevchenko 
3 *2c64e9cbSAndy Shevchenko #include <linux/module.h>
4 *2c64e9cbSAndy Shevchenko #include <linux/mutex.h>
5 *2c64e9cbSAndy Shevchenko #include <linux/prime_numbers.h>
6 *2c64e9cbSAndy Shevchenko #include <linux/slab.h>
7 *2c64e9cbSAndy Shevchenko 
8 *2c64e9cbSAndy Shevchenko #define bitmap_size(nbits) (BITS_TO_LONGS(nbits) * sizeof(unsigned long))
9 *2c64e9cbSAndy Shevchenko 
10 *2c64e9cbSAndy Shevchenko struct primes {
11 *2c64e9cbSAndy Shevchenko 	struct rcu_head rcu;
12 *2c64e9cbSAndy Shevchenko 	unsigned long last, sz;
13 *2c64e9cbSAndy Shevchenko 	unsigned long primes[];
14 *2c64e9cbSAndy Shevchenko };
15 *2c64e9cbSAndy Shevchenko 
16 *2c64e9cbSAndy Shevchenko #if BITS_PER_LONG == 64
17 *2c64e9cbSAndy Shevchenko static const struct primes small_primes = {
18 *2c64e9cbSAndy Shevchenko 	.last = 61,
19 *2c64e9cbSAndy Shevchenko 	.sz = 64,
20 *2c64e9cbSAndy Shevchenko 	.primes = {
21 *2c64e9cbSAndy Shevchenko 		BIT(2) |
22 *2c64e9cbSAndy Shevchenko 		BIT(3) |
23 *2c64e9cbSAndy Shevchenko 		BIT(5) |
24 *2c64e9cbSAndy Shevchenko 		BIT(7) |
25 *2c64e9cbSAndy Shevchenko 		BIT(11) |
26 *2c64e9cbSAndy Shevchenko 		BIT(13) |
27 *2c64e9cbSAndy Shevchenko 		BIT(17) |
28 *2c64e9cbSAndy Shevchenko 		BIT(19) |
29 *2c64e9cbSAndy Shevchenko 		BIT(23) |
30 *2c64e9cbSAndy Shevchenko 		BIT(29) |
31 *2c64e9cbSAndy Shevchenko 		BIT(31) |
32 *2c64e9cbSAndy Shevchenko 		BIT(37) |
33 *2c64e9cbSAndy Shevchenko 		BIT(41) |
34 *2c64e9cbSAndy Shevchenko 		BIT(43) |
35 *2c64e9cbSAndy Shevchenko 		BIT(47) |
36 *2c64e9cbSAndy Shevchenko 		BIT(53) |
37 *2c64e9cbSAndy Shevchenko 		BIT(59) |
38 *2c64e9cbSAndy Shevchenko 		BIT(61)
39 *2c64e9cbSAndy Shevchenko 	}
40 *2c64e9cbSAndy Shevchenko };
41 *2c64e9cbSAndy Shevchenko #elif BITS_PER_LONG == 32
42 *2c64e9cbSAndy Shevchenko static const struct primes small_primes = {
43 *2c64e9cbSAndy Shevchenko 	.last = 31,
44 *2c64e9cbSAndy Shevchenko 	.sz = 32,
45 *2c64e9cbSAndy Shevchenko 	.primes = {
46 *2c64e9cbSAndy Shevchenko 		BIT(2) |
47 *2c64e9cbSAndy Shevchenko 		BIT(3) |
48 *2c64e9cbSAndy Shevchenko 		BIT(5) |
49 *2c64e9cbSAndy Shevchenko 		BIT(7) |
50 *2c64e9cbSAndy Shevchenko 		BIT(11) |
51 *2c64e9cbSAndy Shevchenko 		BIT(13) |
52 *2c64e9cbSAndy Shevchenko 		BIT(17) |
53 *2c64e9cbSAndy Shevchenko 		BIT(19) |
54 *2c64e9cbSAndy Shevchenko 		BIT(23) |
55 *2c64e9cbSAndy Shevchenko 		BIT(29) |
56 *2c64e9cbSAndy Shevchenko 		BIT(31)
57 *2c64e9cbSAndy Shevchenko 	}
58 *2c64e9cbSAndy Shevchenko };
59 *2c64e9cbSAndy Shevchenko #else
60 *2c64e9cbSAndy Shevchenko #error "unhandled BITS_PER_LONG"
61 *2c64e9cbSAndy Shevchenko #endif
62 *2c64e9cbSAndy Shevchenko 
63 *2c64e9cbSAndy Shevchenko static DEFINE_MUTEX(lock);
64 *2c64e9cbSAndy Shevchenko static const struct primes __rcu *primes = RCU_INITIALIZER(&small_primes);
65 *2c64e9cbSAndy Shevchenko 
66 *2c64e9cbSAndy Shevchenko static unsigned long selftest_max;
67 *2c64e9cbSAndy Shevchenko 
68 *2c64e9cbSAndy Shevchenko static bool slow_is_prime_number(unsigned long x)
69 *2c64e9cbSAndy Shevchenko {
70 *2c64e9cbSAndy Shevchenko 	unsigned long y = int_sqrt(x);
71 *2c64e9cbSAndy Shevchenko 
72 *2c64e9cbSAndy Shevchenko 	while (y > 1) {
73 *2c64e9cbSAndy Shevchenko 		if ((x % y) == 0)
74 *2c64e9cbSAndy Shevchenko 			break;
75 *2c64e9cbSAndy Shevchenko 		y--;
76 *2c64e9cbSAndy Shevchenko 	}
77 *2c64e9cbSAndy Shevchenko 
78 *2c64e9cbSAndy Shevchenko 	return y == 1;
79 *2c64e9cbSAndy Shevchenko }
80 *2c64e9cbSAndy Shevchenko 
81 *2c64e9cbSAndy Shevchenko static unsigned long slow_next_prime_number(unsigned long x)
82 *2c64e9cbSAndy Shevchenko {
83 *2c64e9cbSAndy Shevchenko 	while (x < ULONG_MAX && !slow_is_prime_number(++x))
84 *2c64e9cbSAndy Shevchenko 		;
85 *2c64e9cbSAndy Shevchenko 
86 *2c64e9cbSAndy Shevchenko 	return x;
87 *2c64e9cbSAndy Shevchenko }
88 *2c64e9cbSAndy Shevchenko 
89 *2c64e9cbSAndy Shevchenko static unsigned long clear_multiples(unsigned long x,
90 *2c64e9cbSAndy Shevchenko 				     unsigned long *p,
91 *2c64e9cbSAndy Shevchenko 				     unsigned long start,
92 *2c64e9cbSAndy Shevchenko 				     unsigned long end)
93 *2c64e9cbSAndy Shevchenko {
94 *2c64e9cbSAndy Shevchenko 	unsigned long m;
95 *2c64e9cbSAndy Shevchenko 
96 *2c64e9cbSAndy Shevchenko 	m = 2 * x;
97 *2c64e9cbSAndy Shevchenko 	if (m < start)
98 *2c64e9cbSAndy Shevchenko 		m = roundup(start, x);
99 *2c64e9cbSAndy Shevchenko 
100 *2c64e9cbSAndy Shevchenko 	while (m < end) {
101 *2c64e9cbSAndy Shevchenko 		__clear_bit(m, p);
102 *2c64e9cbSAndy Shevchenko 		m += x;
103 *2c64e9cbSAndy Shevchenko 	}
104 *2c64e9cbSAndy Shevchenko 
105 *2c64e9cbSAndy Shevchenko 	return x;
106 *2c64e9cbSAndy Shevchenko }
107 *2c64e9cbSAndy Shevchenko 
108 *2c64e9cbSAndy Shevchenko static bool expand_to_next_prime(unsigned long x)
109 *2c64e9cbSAndy Shevchenko {
110 *2c64e9cbSAndy Shevchenko 	const struct primes *p;
111 *2c64e9cbSAndy Shevchenko 	struct primes *new;
112 *2c64e9cbSAndy Shevchenko 	unsigned long sz, y;
113 *2c64e9cbSAndy Shevchenko 
114 *2c64e9cbSAndy Shevchenko 	/* Betrand's Postulate (or Chebyshev's theorem) states that if n > 3,
115 *2c64e9cbSAndy Shevchenko 	 * there is always at least one prime p between n and 2n - 2.
116 *2c64e9cbSAndy Shevchenko 	 * Equivalently, if n > 1, then there is always at least one prime p
117 *2c64e9cbSAndy Shevchenko 	 * such that n < p < 2n.
118 *2c64e9cbSAndy Shevchenko 	 *
119 *2c64e9cbSAndy Shevchenko 	 * http://mathworld.wolfram.com/BertrandsPostulate.html
120 *2c64e9cbSAndy Shevchenko 	 * https://en.wikipedia.org/wiki/Bertrand's_postulate
121 *2c64e9cbSAndy Shevchenko 	 */
122 *2c64e9cbSAndy Shevchenko 	sz = 2 * x;
123 *2c64e9cbSAndy Shevchenko 	if (sz < x)
124 *2c64e9cbSAndy Shevchenko 		return false;
125 *2c64e9cbSAndy Shevchenko 
126 *2c64e9cbSAndy Shevchenko 	sz = round_up(sz, BITS_PER_LONG);
127 *2c64e9cbSAndy Shevchenko 	new = kmalloc(sizeof(*new) + bitmap_size(sz),
128 *2c64e9cbSAndy Shevchenko 		      GFP_KERNEL | __GFP_NOWARN);
129 *2c64e9cbSAndy Shevchenko 	if (!new)
130 *2c64e9cbSAndy Shevchenko 		return false;
131 *2c64e9cbSAndy Shevchenko 
132 *2c64e9cbSAndy Shevchenko 	mutex_lock(&lock);
133 *2c64e9cbSAndy Shevchenko 	p = rcu_dereference_protected(primes, lockdep_is_held(&lock));
134 *2c64e9cbSAndy Shevchenko 	if (x < p->last) {
135 *2c64e9cbSAndy Shevchenko 		kfree(new);
136 *2c64e9cbSAndy Shevchenko 		goto unlock;
137 *2c64e9cbSAndy Shevchenko 	}
138 *2c64e9cbSAndy Shevchenko 
139 *2c64e9cbSAndy Shevchenko 	/* Where memory permits, track the primes using the
140 *2c64e9cbSAndy Shevchenko 	 * Sieve of Eratosthenes. The sieve is to remove all multiples of known
141 *2c64e9cbSAndy Shevchenko 	 * primes from the set, what remains in the set is therefore prime.
142 *2c64e9cbSAndy Shevchenko 	 */
143 *2c64e9cbSAndy Shevchenko 	bitmap_fill(new->primes, sz);
144 *2c64e9cbSAndy Shevchenko 	bitmap_copy(new->primes, p->primes, p->sz);
145 *2c64e9cbSAndy Shevchenko 	for (y = 2UL; y < sz; y = find_next_bit(new->primes, sz, y + 1))
146 *2c64e9cbSAndy Shevchenko 		new->last = clear_multiples(y, new->primes, p->sz, sz);
147 *2c64e9cbSAndy Shevchenko 	new->sz = sz;
148 *2c64e9cbSAndy Shevchenko 
149 *2c64e9cbSAndy Shevchenko 	BUG_ON(new->last <= x);
150 *2c64e9cbSAndy Shevchenko 
151 *2c64e9cbSAndy Shevchenko 	rcu_assign_pointer(primes, new);
152 *2c64e9cbSAndy Shevchenko 	if (p != &small_primes)
153 *2c64e9cbSAndy Shevchenko 		kfree_rcu((struct primes *)p, rcu);
154 *2c64e9cbSAndy Shevchenko 
155 *2c64e9cbSAndy Shevchenko unlock:
156 *2c64e9cbSAndy Shevchenko 	mutex_unlock(&lock);
157 *2c64e9cbSAndy Shevchenko 	return true;
158 *2c64e9cbSAndy Shevchenko }
159 *2c64e9cbSAndy Shevchenko 
160 *2c64e9cbSAndy Shevchenko static void free_primes(void)
161 *2c64e9cbSAndy Shevchenko {
162 *2c64e9cbSAndy Shevchenko 	const struct primes *p;
163 *2c64e9cbSAndy Shevchenko 
164 *2c64e9cbSAndy Shevchenko 	mutex_lock(&lock);
165 *2c64e9cbSAndy Shevchenko 	p = rcu_dereference_protected(primes, lockdep_is_held(&lock));
166 *2c64e9cbSAndy Shevchenko 	if (p != &small_primes) {
167 *2c64e9cbSAndy Shevchenko 		rcu_assign_pointer(primes, &small_primes);
168 *2c64e9cbSAndy Shevchenko 		kfree_rcu((struct primes *)p, rcu);
169 *2c64e9cbSAndy Shevchenko 	}
170 *2c64e9cbSAndy Shevchenko 	mutex_unlock(&lock);
171 *2c64e9cbSAndy Shevchenko }
172 *2c64e9cbSAndy Shevchenko 
173 *2c64e9cbSAndy Shevchenko /**
174 *2c64e9cbSAndy Shevchenko  * next_prime_number - return the next prime number
175 *2c64e9cbSAndy Shevchenko  * @x: the starting point for searching to test
176 *2c64e9cbSAndy Shevchenko  *
177 *2c64e9cbSAndy Shevchenko  * A prime number is an integer greater than 1 that is only divisible by
178 *2c64e9cbSAndy Shevchenko  * itself and 1.  The set of prime numbers is computed using the Sieve of
179 *2c64e9cbSAndy Shevchenko  * Eratoshenes (on finding a prime, all multiples of that prime are removed
180 *2c64e9cbSAndy Shevchenko  * from the set) enabling a fast lookup of the next prime number larger than
181 *2c64e9cbSAndy Shevchenko  * @x. If the sieve fails (memory limitation), the search falls back to using
182 *2c64e9cbSAndy Shevchenko  * slow trial-divison, up to the value of ULONG_MAX (which is reported as the
183 *2c64e9cbSAndy Shevchenko  * final prime as a sentinel).
184 *2c64e9cbSAndy Shevchenko  *
185 *2c64e9cbSAndy Shevchenko  * Returns: the next prime number larger than @x
186 *2c64e9cbSAndy Shevchenko  */
187 *2c64e9cbSAndy Shevchenko unsigned long next_prime_number(unsigned long x)
188 *2c64e9cbSAndy Shevchenko {
189 *2c64e9cbSAndy Shevchenko 	const struct primes *p;
190 *2c64e9cbSAndy Shevchenko 
191 *2c64e9cbSAndy Shevchenko 	rcu_read_lock();
192 *2c64e9cbSAndy Shevchenko 	p = rcu_dereference(primes);
193 *2c64e9cbSAndy Shevchenko 	while (x >= p->last) {
194 *2c64e9cbSAndy Shevchenko 		rcu_read_unlock();
195 *2c64e9cbSAndy Shevchenko 
196 *2c64e9cbSAndy Shevchenko 		if (!expand_to_next_prime(x))
197 *2c64e9cbSAndy Shevchenko 			return slow_next_prime_number(x);
198 *2c64e9cbSAndy Shevchenko 
199 *2c64e9cbSAndy Shevchenko 		rcu_read_lock();
200 *2c64e9cbSAndy Shevchenko 		p = rcu_dereference(primes);
201 *2c64e9cbSAndy Shevchenko 	}
202 *2c64e9cbSAndy Shevchenko 	x = find_next_bit(p->primes, p->last, x + 1);
203 *2c64e9cbSAndy Shevchenko 	rcu_read_unlock();
204 *2c64e9cbSAndy Shevchenko 
205 *2c64e9cbSAndy Shevchenko 	return x;
206 *2c64e9cbSAndy Shevchenko }
207 *2c64e9cbSAndy Shevchenko EXPORT_SYMBOL(next_prime_number);
208 *2c64e9cbSAndy Shevchenko 
209 *2c64e9cbSAndy Shevchenko /**
210 *2c64e9cbSAndy Shevchenko  * is_prime_number - test whether the given number is prime
211 *2c64e9cbSAndy Shevchenko  * @x: the number to test
212 *2c64e9cbSAndy Shevchenko  *
213 *2c64e9cbSAndy Shevchenko  * A prime number is an integer greater than 1 that is only divisible by
214 *2c64e9cbSAndy Shevchenko  * itself and 1. Internally a cache of prime numbers is kept (to speed up
215 *2c64e9cbSAndy Shevchenko  * searching for sequential primes, see next_prime_number()), but if the number
216 *2c64e9cbSAndy Shevchenko  * falls outside of that cache, its primality is tested using trial-divison.
217 *2c64e9cbSAndy Shevchenko  *
218 *2c64e9cbSAndy Shevchenko  * Returns: true if @x is prime, false for composite numbers.
219 *2c64e9cbSAndy Shevchenko  */
220 *2c64e9cbSAndy Shevchenko bool is_prime_number(unsigned long x)
221 *2c64e9cbSAndy Shevchenko {
222 *2c64e9cbSAndy Shevchenko 	const struct primes *p;
223 *2c64e9cbSAndy Shevchenko 	bool result;
224 *2c64e9cbSAndy Shevchenko 
225 *2c64e9cbSAndy Shevchenko 	rcu_read_lock();
226 *2c64e9cbSAndy Shevchenko 	p = rcu_dereference(primes);
227 *2c64e9cbSAndy Shevchenko 	while (x >= p->sz) {
228 *2c64e9cbSAndy Shevchenko 		rcu_read_unlock();
229 *2c64e9cbSAndy Shevchenko 
230 *2c64e9cbSAndy Shevchenko 		if (!expand_to_next_prime(x))
231 *2c64e9cbSAndy Shevchenko 			return slow_is_prime_number(x);
232 *2c64e9cbSAndy Shevchenko 
233 *2c64e9cbSAndy Shevchenko 		rcu_read_lock();
234 *2c64e9cbSAndy Shevchenko 		p = rcu_dereference(primes);
235 *2c64e9cbSAndy Shevchenko 	}
236 *2c64e9cbSAndy Shevchenko 	result = test_bit(x, p->primes);
237 *2c64e9cbSAndy Shevchenko 	rcu_read_unlock();
238 *2c64e9cbSAndy Shevchenko 
239 *2c64e9cbSAndy Shevchenko 	return result;
240 *2c64e9cbSAndy Shevchenko }
241 *2c64e9cbSAndy Shevchenko EXPORT_SYMBOL(is_prime_number);
242 *2c64e9cbSAndy Shevchenko 
243 *2c64e9cbSAndy Shevchenko static void dump_primes(void)
244 *2c64e9cbSAndy Shevchenko {
245 *2c64e9cbSAndy Shevchenko 	const struct primes *p;
246 *2c64e9cbSAndy Shevchenko 	char *buf;
247 *2c64e9cbSAndy Shevchenko 
248 *2c64e9cbSAndy Shevchenko 	buf = kmalloc(PAGE_SIZE, GFP_KERNEL);
249 *2c64e9cbSAndy Shevchenko 
250 *2c64e9cbSAndy Shevchenko 	rcu_read_lock();
251 *2c64e9cbSAndy Shevchenko 	p = rcu_dereference(primes);
252 *2c64e9cbSAndy Shevchenko 
253 *2c64e9cbSAndy Shevchenko 	if (buf)
254 *2c64e9cbSAndy Shevchenko 		bitmap_print_to_pagebuf(true, buf, p->primes, p->sz);
255 *2c64e9cbSAndy Shevchenko 	pr_info("primes.{last=%lu, .sz=%lu, .primes[]=...x%lx} = %s",
256 *2c64e9cbSAndy Shevchenko 		p->last, p->sz, p->primes[BITS_TO_LONGS(p->sz) - 1], buf);
257 *2c64e9cbSAndy Shevchenko 
258 *2c64e9cbSAndy Shevchenko 	rcu_read_unlock();
259 *2c64e9cbSAndy Shevchenko 
260 *2c64e9cbSAndy Shevchenko 	kfree(buf);
261 *2c64e9cbSAndy Shevchenko }
262 *2c64e9cbSAndy Shevchenko 
263 *2c64e9cbSAndy Shevchenko static int selftest(unsigned long max)
264 *2c64e9cbSAndy Shevchenko {
265 *2c64e9cbSAndy Shevchenko 	unsigned long x, last;
266 *2c64e9cbSAndy Shevchenko 
267 *2c64e9cbSAndy Shevchenko 	if (!max)
268 *2c64e9cbSAndy Shevchenko 		return 0;
269 *2c64e9cbSAndy Shevchenko 
270 *2c64e9cbSAndy Shevchenko 	for (last = 0, x = 2; x < max; x++) {
271 *2c64e9cbSAndy Shevchenko 		bool slow = slow_is_prime_number(x);
272 *2c64e9cbSAndy Shevchenko 		bool fast = is_prime_number(x);
273 *2c64e9cbSAndy Shevchenko 
274 *2c64e9cbSAndy Shevchenko 		if (slow != fast) {
275 *2c64e9cbSAndy Shevchenko 			pr_err("inconsistent result for is-prime(%lu): slow=%s, fast=%s!",
276 *2c64e9cbSAndy Shevchenko 			       x, slow ? "yes" : "no", fast ? "yes" : "no");
277 *2c64e9cbSAndy Shevchenko 			goto err;
278 *2c64e9cbSAndy Shevchenko 		}
279 *2c64e9cbSAndy Shevchenko 
280 *2c64e9cbSAndy Shevchenko 		if (!slow)
281 *2c64e9cbSAndy Shevchenko 			continue;
282 *2c64e9cbSAndy Shevchenko 
283 *2c64e9cbSAndy Shevchenko 		if (next_prime_number(last) != x) {
284 *2c64e9cbSAndy Shevchenko 			pr_err("incorrect result for next-prime(%lu): expected %lu, got %lu",
285 *2c64e9cbSAndy Shevchenko 			       last, x, next_prime_number(last));
286 *2c64e9cbSAndy Shevchenko 			goto err;
287 *2c64e9cbSAndy Shevchenko 		}
288 *2c64e9cbSAndy Shevchenko 		last = x;
289 *2c64e9cbSAndy Shevchenko 	}
290 *2c64e9cbSAndy Shevchenko 
291 *2c64e9cbSAndy Shevchenko 	pr_info("selftest(%lu) passed, last prime was %lu", x, last);
292 *2c64e9cbSAndy Shevchenko 	return 0;
293 *2c64e9cbSAndy Shevchenko 
294 *2c64e9cbSAndy Shevchenko err:
295 *2c64e9cbSAndy Shevchenko 	dump_primes();
296 *2c64e9cbSAndy Shevchenko 	return -EINVAL;
297 *2c64e9cbSAndy Shevchenko }
298 *2c64e9cbSAndy Shevchenko 
299 *2c64e9cbSAndy Shevchenko static int __init primes_init(void)
300 *2c64e9cbSAndy Shevchenko {
301 *2c64e9cbSAndy Shevchenko 	return selftest(selftest_max);
302 *2c64e9cbSAndy Shevchenko }
303 *2c64e9cbSAndy Shevchenko 
304 *2c64e9cbSAndy Shevchenko static void __exit primes_exit(void)
305 *2c64e9cbSAndy Shevchenko {
306 *2c64e9cbSAndy Shevchenko 	free_primes();
307 *2c64e9cbSAndy Shevchenko }
308 *2c64e9cbSAndy Shevchenko 
309 *2c64e9cbSAndy Shevchenko module_init(primes_init);
310 *2c64e9cbSAndy Shevchenko module_exit(primes_exit);
311 *2c64e9cbSAndy Shevchenko 
312 *2c64e9cbSAndy Shevchenko module_param_named(selftest, selftest_max, ulong, 0400);
313 *2c64e9cbSAndy Shevchenko 
314 *2c64e9cbSAndy Shevchenko MODULE_AUTHOR("Intel Corporation");
315 *2c64e9cbSAndy Shevchenko MODULE_LICENSE("GPL");
316