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