[PATCH 06/34] drm: Add a simple linear congruent generator PRNG

[Chris Wilson]

For testing, we want a reproducible PRNG, a plain linear congruent
generator is suitable for our very limited selftests.

Signed-off-by: Chris Wilson <chris at chris-wilson.co.uk>
---
 drivers/gpu/drm/Kconfig        |  5 +++++
 drivers/gpu/drm/Makefile       |  1 +
 drivers/gpu/drm/lib/drm_rand.c | 51 ++++++++++++++++++++++++++++++++++++++++++
 drivers/gpu/drm/lib/drm_rand.h |  9 ++++++++
 4 files changed, 66 insertions(+)
 create mode 100644 drivers/gpu/drm/lib/drm_rand.c
 create mode 100644 drivers/gpu/drm/lib/drm_rand.h

diff --git a/drivers/gpu/drm/Kconfig b/drivers/gpu/drm/Kconfig
index fd341ab69c46..04d1d0a32c5c 100644
--- a/drivers/gpu/drm/Kconfig
+++ b/drivers/gpu/drm/Kconfig
@@ -48,10 +48,15 @@ config DRM_DEBUG_MM
 
 	  If in doubt, say "N".
 
+config DRM_LIB_RAND
+	bool
+	default n
+
 config DRM_DEBUG_MM_SELFTEST
 	tristate "kselftests for DRM range manager (struct drm_mm)"
 	depends on DRM
 	depends on DEBUG_KERNEL
+	select DRM_LIB_RAND
 	default n
 	help
 	  This option provides a kernel module that can be used to test
diff --git a/drivers/gpu/drm/Makefile b/drivers/gpu/drm/Makefile
index c8aed3688b20..363eb1a23151 100644
--- a/drivers/gpu/drm/Makefile
+++ b/drivers/gpu/drm/Makefile
@@ -18,6 +18,7 @@ drm-y       :=	drm_auth.o drm_bufs.o drm_cache.o \
 		drm_plane.o drm_color_mgmt.o drm_print.o \
 		drm_dumb_buffers.o drm_mode_config.o
 
+drm-$(CONFIG_DRM_LIB_RAND) += lib/drm_rand.o
 obj-$(CONFIG_DRM_DEBUG_MM_SELFTEST) += selftests/test-drm_mm.o
 
 drm-$(CONFIG_COMPAT) += drm_ioc32.o
diff --git a/drivers/gpu/drm/lib/drm_rand.c b/drivers/gpu/drm/lib/drm_rand.c
new file mode 100644
index 000000000000..f203c47bb525
--- /dev/null
+++ b/drivers/gpu/drm/lib/drm_rand.c
@@ -0,0 +1,51 @@
+#include <linux/kernel.h>
+#include <linux/slab.h>
+#include <linux/types.h>
+
+#include "drm_rand.h"
+
+u32 drm_lcg_random(u32 *state)
+{
+	u32 s = *state;
+
+#define rol(x, k) (((x) << (k)) | ((x) >> (32 - (k))))
+	s = (s ^ rol(s, 5) ^ rol(s, 24)) + 0x37798849;
+#undef rol
+
+	*state = s;
+	return s;
+}
+EXPORT_SYMBOL(drm_lcg_random);
+
+int *drm_random_reorder(int *order, int count, u32 *state)
+{
+	int n;
+
+	for (n = count-1; n > 1; n--) {
+		int r = drm_lcg_random(state) % (n + 1);
+		if (r != n) {
+			int tmp = order[n];
+			order[n] = order[r];
+			order[r] = tmp;
+		}
+	}
+
+	return order;
+}
+EXPORT_SYMBOL(drm_random_reorder);
+
+int *drm_random_order(int count, u32 *state)
+{
+	int *order;
+	int n;
+
+	order = kmalloc_array(count, sizeof(*order), GFP_TEMPORARY);
+	if (!order)
+		return order;
+
+	for (n = 0; n < count; n++)
+		order[n] = n;
+
+	return drm_random_reorder(order, count, state);
+}
+EXPORT_SYMBOL(drm_random_order);
diff --git a/drivers/gpu/drm/lib/drm_rand.h b/drivers/gpu/drm/lib/drm_rand.h
new file mode 100644
index 000000000000..a3f22d115aac
--- /dev/null
+++ b/drivers/gpu/drm/lib/drm_rand.h
@@ -0,0 +1,9 @@
+#ifndef __DRM_RAND_H__
+#define __DRM_RAND_H
+
+u32 drm_lcg_random(u32 *state);
+
+int *drm_random_reorder(int *order, int count, u32 *state);
+int *drm_random_order(int count, u32 *state);
+
+#endif /* __DRM_RAND_H__ */
-- 
2.11.0