lib/math/prime_numbers.c - third_party/kernel - Git at Google

 // SPDX-License-Identifier: GPL-2.0-only
 #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 | __GFP_NOWARN);
 	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");
	// SPDX-License-Identifier: GPL-2.0-only
	#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 \| __GFP_NOWARN);
	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");