From cf4a7207b1cb4a3c3fe3aa11a83c9d673722a7f5 Mon Sep 17 00:00:00 2001 From: Chris Wilson Date: Thu, 22 Dec 2016 14:45:14 +0000 Subject: lib: Add a simple prime number generator Prime numbers are interesting for testing components that use multiplies and divides, such as testing DRM's struct drm_mm alignment computations. v2: Move to lib/, add selftest v3: Fix initial constants (exclude 0/1 from being primes) v4: More RCU markup to keep 0day/sparse happy v5: Fix RCU unwind on module exit, add to kselftests v6: Tidy computation of bitmap size v7: for_each_prime_number_from() v8: Compose small-primes using BIT() for easier verification v9: Move rcu dance entirely into callers. v10: Improve quote for Betrand's Postulate (aka Chebyshev's theorem) Signed-off-by: Chris Wilson Cc: Lukas Wunner Reviewed-by: Joonas Lahtinen Signed-off-by: Daniel Vetter Link: http://patchwork.freedesktop.org/patch/msgid/20161222144514.3911-1-chris@chris-wilson.co.uk --- include/linux/prime_numbers.h | 37 +++++++++++++++++++++++++++++++++++++ 1 file changed, 37 insertions(+) create mode 100644 include/linux/prime_numbers.h (limited to 'include/linux') diff --git a/include/linux/prime_numbers.h b/include/linux/prime_numbers.h new file mode 100644 index 000000000000..14ec4f567342 --- /dev/null +++ b/include/linux/prime_numbers.h @@ -0,0 +1,37 @@ +#ifndef __LINUX_PRIME_NUMBERS_H +#define __LINUX_PRIME_NUMBERS_H + +#include + +bool is_prime_number(unsigned long x); +unsigned long next_prime_number(unsigned long x); + +/** + * for_each_prime_number - iterate over each prime upto a value + * @prime: the current prime number in this iteration + * @max: the upper limit + * + * Starting from the first prime number 2 iterate over each prime number up to + * the @max value. On each iteration, @prime is set to the current prime number. + * @max should be less than ULONG_MAX to ensure termination. To begin with + * @prime set to 1 on the first iteration use for_each_prime_number_from() + * instead. + */ +#define for_each_prime_number(prime, max) \ + for_each_prime_number_from((prime), 2, (max)) + +/** + * for_each_prime_number_from - iterate over each prime upto a value + * @prime: the current prime number in this iteration + * @from: the initial value + * @max: the upper limit + * + * Starting from @from iterate over each successive prime number up to the + * @max value. On each iteration, @prime is set to the current prime number. + * @max should be less than ULONG_MAX, and @from less than @max, to ensure + * termination. + */ +#define for_each_prime_number_from(prime, from, max) \ + for (prime = (from); prime <= (max); prime = next_prime_number(prime)) + +#endif /* !__LINUX_PRIME_NUMBERS_H */ -- cgit v1.2.3