This patch adds the carta_random32() routine to the library.
This is a very simple and very efficient random number generator
implementing Carta's algorithm. This routine is used by
perfmon2 to compute a randomized sampling period. On some
platforms, such as IA-64, this routine may be implemented in
assembly directly.
This routine is now part of Andrew's tree, so this portion of the
perfmon2 patch will not be needed anymore in the next release
--- linux-2.6.18.base/lib/carta_random32.c 1969-12-31 16:00:00.000000000 -0800
+++ linux-2.6.18/lib/carta_random32.c 2006-09-22 01:59:06.000000000 -0700
@@ -0,0 +1,29 @@
+/*
+ * Fast, simple, yet decent quality random number generator based on
+ * a paper by David G. Carta ("Two Fast Implementations of the
+ * `Minimal Standard' Random Number Generator," Communications of the
+ * ACM, January, 1990).
+ *
+ * Copyright (c) 2002-2005 Hewlett-Packard Development Company, L.P.
+ * Contributed by David Mosberger-Tang <[email protected]>
+ */
+#include <linux/types.h>
+#include <linux/module.h>
+#include <linux/perfmon.h>
+
+#ifndef __HAVE_ARCH_CARTA_RANDOM32
+u64 carta_random32 (u64 seed)
+{
+# define A 16807
+# define M ((u32) 1 << 31)
+ u64 s, prod = A * seed, p, q;
+
+ p = (prod >> 31) & (M - 1);
+ q = (prod >> 0) & (M - 1);
+ s = p + q;
+ if (s >= M)
+ s -= M - 1;
+ return s;
+}
+EXPORT_SYMBOL(carta_random32);
+#endif