[linux.git] / lib / prime_numbers.c

#define pr_fmt(fmt) "prime numbers: " fmt "\n"

#include <linux/module.h>
#include <linux/mutex.h>
#include <linux/prime_numbers.h>
#include <linux/slab.h>

#define bitmap_size(nbits) (BITS_TO_LONGS(nbits) * sizeof(unsigned long))

struct primes {
	struct rcu_head rcu;
	unsigned long last, sz;
	unsigned long primes[];
};

#if BITS_PER_LONG == 64
static const struct primes small_primes = {
	.last = 61,
	.sz = 64,
	.primes = {
		BIT(2) |
		BIT(3) |
		BIT(5) |
		BIT(7) |
		BIT(11) |
		BIT(13) |
		BIT(17) |
		BIT(19) |
		BIT(23) |
		BIT(29) |
		BIT(31) |
		BIT(37) |
		BIT(41) |
		BIT(43) |
		BIT(47) |
		BIT(53) |
		BIT(59) |
		BIT(61)
	}
};
#elif BITS_PER_LONG == 32
static const struct primes small_primes = {
	.last = 31,
	.sz = 32,
	.primes = {
		BIT(2) |
		BIT(3) |
		BIT(5) |
		BIT(7) |
		BIT(11) |
		BIT(13) |
		BIT(17) |
		BIT(19) |
		BIT(23) |
		BIT(29) |
		BIT(31)
	}
};
#else
#error "unhandled BITS_PER_LONG"
#endif

static DEFINE_MUTEX(lock);
static const struct primes __rcu *primes = RCU_INITIALIZER(&small_primes);

static unsigned long selftest_max;

static bool slow_is_prime_number(unsigned long x)
{
	unsigned long y = int_sqrt(x);

	while (y > 1) {
		if ((x % y) == 0)
			break;
		y--;
	}

	return y == 1;
}

static unsigned long slow_next_prime_number(unsigned long x)
{
	while (x < ULONG_MAX && !slow_is_prime_number(++x))
		;

	return x;
}

static unsigned long clear_multiples(unsigned long x,
				     unsigned long *p,
				     unsigned long start,
				     unsigned long end)
{
	unsigned long m;

	m = 2 * x;
	if (m < start)
		m = roundup(start, x);

	while (m < end) {
		__clear_bit(m, p);
		m += x;
	}

	return x;
}

static bool expand_to_next_prime(unsigned long x)
{
	const struct primes *p;
	struct primes *new;
	unsigned long sz, y;

	/* Betrand's Postulate (or Chebyshev's theorem) states that if n > 3,
	 * there is always at least one prime p between n and 2n - 2.
	 * Equivalently, if n > 1, then there is always at least one prime p
	 * such that n < p < 2n.
	 *
	 * http://mathworld.wolfram.com/BertrandsPostulate.html
	 * https://en.wikipedia.org/wiki/Bertrand's_postulate
	 */
	sz = 2 * x;
	if (sz < x)
		return false;

	sz = round_up(sz, BITS_PER_LONG);
	new = kmalloc(sizeof(*new) + bitmap_size(sz), GFP_KERNEL);
	if (!new)
		return false;

	mutex_lock(&lock);
	p = rcu_dereference_protected(primes, lockdep_is_held(&lock));
	if (x < p->last) {
		kfree(new);
		goto unlock;
	}

	/* Where memory permits, track the primes using the
	 * Sieve of Eratosthenes. The sieve is to remove all multiples of known
	 * primes from the set, what remains in the set is therefore prime.
	 */
	bitmap_fill(new->primes, sz);
	bitmap_copy(new->primes, p->primes, p->sz);
	for (y = 2UL; y < sz; y = find_next_bit(new->primes, sz, y + 1))
		new->last = clear_multiples(y, new->primes, p->sz, sz);
	new->sz = sz;

	BUG_ON(new->last <= x);

	rcu_assign_pointer(primes, new);
	if (p != &small_primes)
		kfree_rcu((struct primes *)p, rcu);

unlock:
	mutex_unlock(&lock);
	return true;
}

static void free_primes(void)
{
	const struct primes *p;

	mutex_lock(&lock);
	p = rcu_dereference_protected(primes, lockdep_is_held(&lock));
	if (p != &small_primes) {
		rcu_assign_pointer(primes, &small_primes);
		kfree_rcu((struct primes *)p, rcu);
	}
	mutex_unlock(&lock);
}

/**
 * next_prime_number - return the next prime number
 * @x: the starting point for searching to test
 *
 * A prime number is an integer greater than 1 that is only divisible by
 * itself and 1.  The set of prime numbers is computed using the Sieve of
 * Eratoshenes (on finding a prime, all multiples of that prime are removed
 * from the set) enabling a fast lookup of the next prime number larger than
 * @x. If the sieve fails (memory limitation), the search falls back to using
 * slow trial-divison, up to the value of ULONG_MAX (which is reported as the
 * final prime as a sentinel).
 *
 * Returns: the next prime number larger than @x
 */
unsigned long next_prime_number(unsigned long x)
{
	const struct primes *p;

	rcu_read_lock();
	p = rcu_dereference(primes);
	while (x >= p->last) {
		rcu_read_unlock();

		if (!expand_to_next_prime(x))
			return slow_next_prime_number(x);

		rcu_read_lock();
		p = rcu_dereference(primes);
	}
	x = find_next_bit(p->primes, p->last, x + 1);
	rcu_read_unlock();

	return x;
}
EXPORT_SYMBOL(next_prime_number);

/**
 * is_prime_number - test whether the given number is prime
 * @x: the number to test
 *
 * A prime number is an integer greater than 1 that is only divisible by
 * itself and 1. Internally a cache of prime numbers is kept (to speed up
 * searching for sequential primes, see next_prime_number()), but if the number
 * falls outside of that cache, its primality is tested using trial-divison.
 *
 * Returns: true if @x is prime, false for composite numbers.
 */
bool is_prime_number(unsigned long x)
{
	const struct primes *p;
	bool result;

	rcu_read_lock();
	p = rcu_dereference(primes);
	while (x >= p->sz) {
		rcu_read_unlock();

		if (!expand_to_next_prime(x))
			return slow_is_prime_number(x);

		rcu_read_lock();
		p = rcu_dereference(primes);
	}
	result = test_bit(x, p->primes);
	rcu_read_unlock();

	return result;
}
EXPORT_SYMBOL(is_prime_number);

static void dump_primes(void)
{
	const struct primes *p;
	char *buf;

	buf = kmalloc(PAGE_SIZE, GFP_KERNEL);

	rcu_read_lock();
	p = rcu_dereference(primes);

	if (buf)
		bitmap_print_to_pagebuf(true, buf, p->primes, p->sz);
	pr_info("primes.{last=%lu, .sz=%lu, .primes[]=...x%lx} = %s",
		p->last, p->sz, p->primes[BITS_TO_LONGS(p->sz) - 1], buf);

	rcu_read_unlock();

	kfree(buf);
}

static int selftest(unsigned long max)
{
	unsigned long x, last;

	if (!max)
		return 0;

	for (last = 0, x = 2; x < max; x++) {
		bool slow = slow_is_prime_number(x);
		bool fast = is_prime_number(x);

		if (slow != fast) {
			pr_err("inconsistent result for is-prime(%lu): slow=%s, fast=%s!",
			       x, slow ? "yes" : "no", fast ? "yes" : "no");
			goto err;
		}

		if (!slow)
			continue;

		if (next_prime_number(last) != x) {
			pr_err("incorrect result for next-prime(%lu): expected %lu, got %lu",
			       last, x, next_prime_number(last));
			goto err;
		}
		last = x;
	}

	pr_info("selftest(%lu) passed, last prime was %lu", x, last);
	return 0;

err:
	dump_primes();
	return -EINVAL;
}

static int __init primes_init(void)
{
	return selftest(selftest_max);
}

static void __exit primes_exit(void)
{
	free_primes();
}

module_init(primes_init);
module_exit(primes_exit);

module_param_named(selftest, selftest_max, ulong, 0400);

MODULE_AUTHOR("Intel Corporation");
MODULE_LICENSE("GPL");
Commit	Line	Data
cf4a7207 CW	1	#define pr_fmt(fmt) "prime numbers: " fmt "\n"
	2
	3	#include <linux/module.h>
	4	#include <linux/mutex.h>
	5	#include <linux/prime_numbers.h>
	6	#include <linux/slab.h>
	7
	8	#define bitmap_size(nbits) (BITS_TO_LONGS(nbits) * sizeof(unsigned long))
	9
	10	struct primes {
	11	struct rcu_head rcu;
	12	unsigned long last, sz;
	13	unsigned long primes[];
	14	};
	15
	16	#if BITS_PER_LONG == 64
	17	static const struct primes small_primes = {
	18	.last = 61,
	19	.sz = 64,
	20	.primes = {
	21	BIT(2) \|
	22	BIT(3) \|
	23	BIT(5) \|
	24	BIT(7) \|
	25	BIT(11) \|
	26	BIT(13) \|
	27	BIT(17) \|
	28	BIT(19) \|
	29	BIT(23) \|
	30	BIT(29) \|
	31	BIT(31) \|
	32	BIT(37) \|
	33	BIT(41) \|
	34	BIT(43) \|
	35	BIT(47) \|
	36	BIT(53) \|
	37	BIT(59) \|
	38	BIT(61)
	39	}
	40	};
	41	#elif BITS_PER_LONG == 32
	42	static const struct primes small_primes = {
	43	.last = 31,
	44	.sz = 32,
	45	.primes = {
	46	BIT(2) \|
	47	BIT(3) \|
	48	BIT(5) \|
	49	BIT(7) \|
	50	BIT(11) \|
	51	BIT(13) \|
	52	BIT(17) \|
	53	BIT(19) \|
	54	BIT(23) \|
	55	BIT(29) \|
	56	BIT(31)
	57	}
	58	};
	59	#else
	60	#error "unhandled BITS_PER_LONG"
	61	#endif
	62
	63	static DEFINE_MUTEX(lock);
	64	static const struct primes __rcu *primes = RCU_INITIALIZER(&small_primes);
65
66	static unsigned long selftest_max;
67
68	static bool slow_is_prime_number(unsigned long x)
69	{
70	unsigned long y = int_sqrt(x);
71
72	while (y > 1) {
73	if ((x % y) == 0)
74	break;
75	y--;
76	}
77
78	return y == 1;
79	}
80
81	static unsigned long slow_next_prime_number(unsigned long x)
82	{
83	while (x < ULONG_MAX && !slow_is_prime_number(++x))
84	;
85
86	return x;
87	}
88
89	static unsigned long clear_multiples(unsigned long x,
90	unsigned long *p,
91	unsigned long start,
92	unsigned long end)
93	{
94	unsigned long m;
95
96	m = 2 * x;
97	if (m < start)
98	m = roundup(start, x);
99
100	while (m < end) {
101	__clear_bit(m, p);
102	m += x;
103	}
104
105	return x;
106	}
107
108	static bool expand_to_next_prime(unsigned long x)
109	{
110	const struct primes *p;
111	struct primes *new;
112	unsigned long sz, y;
113
114	/* Betrand's Postulate (or Chebyshev's theorem) states that if n > 3,
115	* there is always at least one prime p between n and 2n - 2.
116	* Equivalently, if n > 1, then there is always at least one prime p
117	* such that n < p < 2n.
118	*
119	* http://mathworld.wolfram.com/BertrandsPostulate.html
120	* https://en.wikipedia.org/wiki/Bertrand's_postulate
121	*/
122	sz = 2 * x;
123	if (sz < x)
124	return false;
125
126	sz = round_up(sz, BITS_PER_LONG);
127	new = kmalloc(sizeof(*new) + bitmap_size(sz), GFP_KERNEL);
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
154	unlock:
155	mutex_unlock(&lock);
156	return true;
157	}
158
159	static 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	*/
186	unsigned 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	}
206	EXPORT_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	*/
219	bool 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	}
240	EXPORT_SYMBOL(is_prime_number);
241
242	static 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",
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
262	static 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!",
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",
284	last, x, next_prime_number(last));
285	goto err;
286	}
287	last = x;
288	}
289
290	pr_info("selftest(%lu) passed, last prime was %lu", x, last);
291	return 0;
292
293	err:
294	dump_primes();
295	return -EINVAL;
296	}
297
298	static int __init primes_init(void)
299	{
300	return selftest(selftest_max);
301	}
302
303	static void __exit primes_exit(void)
304	{
305	free_primes();
306	}
307
308	module_init(primes_init);
309	module_exit(primes_exit);
310
311	module_param_named(selftest, selftest_max, ulong, 0400);
312
313	MODULE_AUTHOR("Intel Corporation");
314	MODULE_LICENSE("GPL");