lib: Move mathematic helpers to separate folder

For better maintenance and expansion move the mathematic helpers to the
separate folder.

No functional change intended.

Note, the int_sqrt() is not used as a part of lib, so, moved to regular
obj.

Link: http://lkml.kernel.org/r/20190323172531.80025-1-andriy.shevchenko@linux.intel.com
Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Signed-off-by: Mauro Carvalho Chehab <mchehab+samsung@kernel.org>
Cc: Randy Dunlap <rdunlap@infradead.org>
Cc: Thierry Reding <thierry.reding@gmail.com>
Cc: Lee Jones <lee.jones@linaro.org>
Cc: Daniel Thompson <daniel.thompson@linaro.org>
Cc: Ray Jui <rjui@broadcom.com>
[mchehab+samsung@kernel.org: fix broken doc references for div64.c and gcd.c]
  Link: http://lkml.kernel.org/r/734f49bae5d4052b3c25691dfefad59bea2e5843.1555580999.git.mchehab+samsung@kernel.org
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

1 files changed, 0 insertions, 315 deletions

diff --git a/lib/prime_numbers.c b/lib/prime_numbers.c
deleted file mode 100644
index 550eec457c2e..000000000000
--- a/lib/prime_numbers.c
+++ /dev/null
@@ -1,315 +0,0 @@
-#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");