[PATCH] lib: Add a simple prime number generator

[Chris Wilson]

On Fri, Dec 16, 2016 at 01:23:23PM +0000, Chris Wilson wrote:
> 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
> 
> Signed-off-by: Chris Wilson <chris at chris-wilson.co.uk>
> Cc: Lukas Wunner <lukas at wunner.de>
> ---
>  include/linux/prime_numbers.h |  13 +++
>  lib/Kconfig                   |   7 ++
>  lib/Makefile                  |   2 +
>  lib/prime_numbers.c           | 230 ++++++++++++++++++++++++++++++++++++++++++
>  4 files changed, 252 insertions(+)
>  create mode 100644 include/linux/prime_numbers.h
>  create mode 100644 lib/prime_numbers.c
> 
> diff --git a/include/linux/prime_numbers.h b/include/linux/prime_numbers.h
> new file mode 100644
> index 000000000000..877f6acbd0b6
> --- /dev/null
> +++ b/include/linux/prime_numbers.h
> @@ -0,0 +1,13 @@
> +#ifndef __LINUX_PRIME_NUMBERS_H
> +#define __LINUX_PRIME_NUMBERS_H
> +
> +#include <linux/types.h>
> +
> +bool is_prime_number(unsigned long x);
> +unsigned long next_prime_number(unsigned long x);
> +
> +/* A useful white-lie here is that 1 is prime. */
> +#define for_each_prime_number(prime, max) \
> +	for (prime = 1;	prime < (max); prime = next_prime_number(prime))
> +
> +#endif /* !__LINUX_PRIME_NUMBERS_H */
> diff --git a/lib/Kconfig b/lib/Kconfig
> index 260a80e313b9..1788a1f50d28 100644
> --- a/lib/Kconfig
> +++ b/lib/Kconfig
> @@ -550,4 +550,11 @@ config STACKDEPOT
>  config SBITMAP
>  	bool
>  
> +config PRIME_NUMBERS
> +	tristate "Prime number generator"
> +	default n
> +	help
> +	  Provides a helper module to generate prime numbers. Useful for writing
> +	  test code, especially when checking multiplication and divison.
> +
>  endmenu
> diff --git a/lib/Makefile b/lib/Makefile
> index 50144a3aeebd..c664143fd917 100644
> --- a/lib/Makefile
> +++ b/lib/Makefile
> @@ -197,6 +197,8 @@ obj-$(CONFIG_ASN1) += asn1_decoder.o
>  
>  obj-$(CONFIG_FONT_SUPPORT) += fonts/
>  
> +obj-$(CONFIG_PRIME_NUMBERS) += prime_numbers.o
> +
>  hostprogs-y	:= gen_crc32table
>  clean-files	:= crc32table.h
>  
> diff --git a/lib/prime_numbers.c b/lib/prime_numbers.c
> new file mode 100644
> index 000000000000..ba08be0ff1ed
> --- /dev/null
> +++ b/lib/prime_numbers.c
> @@ -0,0 +1,230 @@
> +#define pr_fmt(fmt) "prime numbers: " #fmt
> +
> +#include <linux/module.h>
> +#include <linux/mutex.h>
> +#include <linux/prime_numbers.h>
> +#include <linux/slab.h>
> +#include <linux/vmalloc.h>
> +
> +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 = { 0x28208a20a08a28ae }

Ugh, extracted this from primes[0] and forgot the mark up skips 0,1

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

Which didn't help!
-Chris

-- 
Chris Wilson, Intel Open Source Technology Centre