1// SPDX-License-Identifier: GPL-2.0-only
2
3#include <linux/module.h>
4#include <linux/mutex.h>
5#include <linux/prime_numbers.h>
6#include <linux/slab.h>
7
8#include "prime_numbers_private.h"
9
10#if BITS_PER_LONG == 64
11static const struct primes small_primes = {
12 .last = 61,
13 .sz = 64,
14 .primes = {
15 BIT(2) |
16 BIT(3) |
17 BIT(5) |
18 BIT(7) |
19 BIT(11) |
20 BIT(13) |
21 BIT(17) |
22 BIT(19) |
23 BIT(23) |
24 BIT(29) |
25 BIT(31) |
26 BIT(37) |
27 BIT(41) |
28 BIT(43) |
29 BIT(47) |
30 BIT(53) |
31 BIT(59) |
32 BIT(61)
33 }
34};
35#elif BITS_PER_LONG == 32
36static const struct primes small_primes = {
37 .last = 31,
38 .sz = 32,
39 .primes = {
40 BIT(2) |
41 BIT(3) |
42 BIT(5) |
43 BIT(7) |
44 BIT(11) |
45 BIT(13) |
46 BIT(17) |
47 BIT(19) |
48 BIT(23) |
49 BIT(29) |
50 BIT(31)
51 }
52};
53#else
54#error "unhandled BITS_PER_LONG"
55#endif
56
57static DEFINE_MUTEX(lock);
58static const struct primes __rcu *primes = RCU_INITIALIZER(&small_primes);
59
60#if IS_ENABLED(CONFIG_PRIME_NUMBERS_KUNIT_TEST)
61/*
62 * Calls the callback under RCU lock. The callback must not retain
63 * the primes pointer.
64 */
65void with_primes(void *ctx, primes_fn fn)
66{
67 rcu_read_lock();
68 fn(ctx, rcu_dereference(primes));
69 rcu_read_unlock();
70}
71EXPORT_SYMBOL(with_primes);
72
73EXPORT_SYMBOL(slow_is_prime_number);
74
75#else
76static
77#endif
78bool slow_is_prime_number(unsigned long x)
79{
80 unsigned long y = int_sqrt(x);
81
82 while (y > 1) {
83 if ((x % y) == 0)
84 break;
85 y--;
86 }
87
88 return y == 1;
89}
90
91static unsigned long slow_next_prime_number(unsigned long x)
92{
93 while (x < ULONG_MAX && !slow_is_prime_number(x: ++x))
94 ;
95
96 return x;
97}
98
99static unsigned long clear_multiples(unsigned long x,
100 unsigned long *p,
101 unsigned long start,
102 unsigned long end)
103{
104 unsigned long m;
105
106 m = 2 * x;
107 if (m < start)
108 m = roundup(start, x);
109
110 while (m < end) {
111 __clear_bit(m, p);
112 m += x;
113 }
114
115 return x;
116}
117
118static bool expand_to_next_prime(unsigned long x)
119{
120 const struct primes *p;
121 struct primes *new;
122 unsigned long sz, y;
123
124 /* Betrand's Postulate (or Chebyshev's theorem) states that if n > 3,
125 * there is always at least one prime p between n and 2n - 2.
126 * Equivalently, if n > 1, then there is always at least one prime p
127 * such that n < p < 2n.
128 *
129 * http://mathworld.wolfram.com/BertrandsPostulate.html
130 * https://en.wikipedia.org/wiki/Bertrand's_postulate
131 */
132 sz = 2 * x;
133 if (sz < x)
134 return false;
135
136 sz = round_up(sz, BITS_PER_LONG);
137 new = kmalloc(sizeof(*new) + bitmap_size(sz),
138 GFP_KERNEL | __GFP_NOWARN);
139 if (!new)
140 return false;
141
142 mutex_lock(&lock);
143 p = rcu_dereference_protected(primes, lockdep_is_held(&lock));
144 if (x < p->last) {
145 kfree(objp: new);
146 goto unlock;
147 }
148
149 /* Where memory permits, track the primes using the
150 * Sieve of Eratosthenes. The sieve is to remove all multiples of known
151 * primes from the set, what remains in the set is therefore prime.
152 */
153 bitmap_fill(dst: new->primes, nbits: sz);
154 bitmap_copy(dst: new->primes, src: p->primes, nbits: p->sz);
155 for (y = 2UL; y < sz; y = find_next_bit(addr: new->primes, size: sz, offset: y + 1))
156 new->last = clear_multiples(x: y, p: new->primes, start: p->sz, end: sz);
157 new->sz = sz;
158
159 BUG_ON(new->last <= x);
160
161 rcu_assign_pointer(primes, new);
162 if (p != &small_primes)
163 kfree_rcu((struct primes *)p, rcu);
164
165unlock:
166 mutex_unlock(lock: &lock);
167 return true;
168}
169
170static void free_primes(void)
171{
172 const struct primes *p;
173
174 mutex_lock(&lock);
175 p = rcu_dereference_protected(primes, lockdep_is_held(&lock));
176 if (p != &small_primes) {
177 rcu_assign_pointer(primes, &small_primes);
178 kfree_rcu((struct primes *)p, rcu);
179 }
180 mutex_unlock(lock: &lock);
181}
182
183/**
184 * next_prime_number - return the next prime number
185 * @x: the starting point for searching to test
186 *
187 * A prime number is an integer greater than 1 that is only divisible by
188 * itself and 1. The set of prime numbers is computed using the Sieve of
189 * Eratoshenes (on finding a prime, all multiples of that prime are removed
190 * from the set) enabling a fast lookup of the next prime number larger than
191 * @x. If the sieve fails (memory limitation), the search falls back to using
192 * slow trial-divison, up to the value of ULONG_MAX (which is reported as the
193 * final prime as a sentinel).
194 *
195 * Returns: the next prime number larger than @x
196 */
197unsigned long next_prime_number(unsigned long x)
198{
199 const struct primes *p;
200
201 rcu_read_lock();
202 p = rcu_dereference(primes);
203 while (x >= p->last) {
204 rcu_read_unlock();
205
206 if (!expand_to_next_prime(x))
207 return slow_next_prime_number(x);
208
209 rcu_read_lock();
210 p = rcu_dereference(primes);
211 }
212 x = find_next_bit(addr: p->primes, size: p->last, offset: x + 1);
213 rcu_read_unlock();
214
215 return x;
216}
217EXPORT_SYMBOL(next_prime_number);
218
219/**
220 * is_prime_number - test whether the given number is prime
221 * @x: the number to test
222 *
223 * A prime number is an integer greater than 1 that is only divisible by
224 * itself and 1. Internally a cache of prime numbers is kept (to speed up
225 * searching for sequential primes, see next_prime_number()), but if the number
226 * falls outside of that cache, its primality is tested using trial-divison.
227 *
228 * Returns: true if @x is prime, false for composite numbers.
229 */
230bool is_prime_number(unsigned long x)
231{
232 const struct primes *p;
233 bool result;
234
235 rcu_read_lock();
236 p = rcu_dereference(primes);
237 while (x >= p->sz) {
238 rcu_read_unlock();
239
240 if (!expand_to_next_prime(x))
241 return slow_is_prime_number(x);
242
243 rcu_read_lock();
244 p = rcu_dereference(primes);
245 }
246 result = test_bit(x, p->primes);
247 rcu_read_unlock();
248
249 return result;
250}
251EXPORT_SYMBOL(is_prime_number);
252
253static void __exit primes_exit(void)
254{
255 free_primes();
256}
257
258module_exit(primes_exit);
259
260MODULE_AUTHOR("Intel Corporation");
261MODULE_DESCRIPTION("Prime number library");
262MODULE_LICENSE("GPL");
263

source code of linux/lib/math/prime_numbers.c