aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorStephane Eranian <eranian@hpl.hp.com>2006-10-11 04:21:45 -0400
committerLinus Torvalds <torvalds@g5.osdl.org>2006-10-11 14:14:21 -0400
commite0ab2928cc2202f13f0574d4c6f567f166d307eb (patch)
tree3df0b8e340b1a98cd8a2daa19672ff008e8fb7f9 /lib
parentb611967de4dc5c52049676c4369dcac622a7cdfe (diff)
[PATCH] Add carta_random32() library routine
This is a follow-up patch based on the review for perfmon2. This patch adds the carta_random32() library routine + carta_random32.h header file. This is fast, simple, and efficient pseudo number generator algorithm. We use it in perfmon2 to randomize the sampling periods. In this context, we do not need any fancy randomizer. Signed-off-by: stephane eranian <eranian@hpl.hp.com> Cc: David Mosberger <david.mosberger@acm.org> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
Diffstat (limited to 'lib')
-rw-r--r--lib/Makefile2
-rw-r--r--lib/carta_random32.c41
2 files changed, 42 insertions, 1 deletions
diff --git a/lib/Makefile b/lib/Makefile
index 8e6662bb9c37..59070dbfbeb4 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -5,7 +5,7 @@
5lib-y := ctype.o string.o vsprintf.o cmdline.o \ 5lib-y := ctype.o string.o vsprintf.o cmdline.o \
6 bust_spinlocks.o rbtree.o radix-tree.o dump_stack.o \ 6 bust_spinlocks.o rbtree.o radix-tree.o dump_stack.o \
7 idr.o div64.o int_sqrt.o bitmap.o extable.o prio_tree.o \ 7 idr.o div64.o int_sqrt.o bitmap.o extable.o prio_tree.o \
8 sha1.o irq_regs.o 8 sha1.o irq_regs.o carta_random32.o
9 9
10lib-$(CONFIG_MMU) += ioremap.o 10lib-$(CONFIG_MMU) += ioremap.o
11lib-$(CONFIG_SMP) += cpumask.o 11lib-$(CONFIG_SMP) += cpumask.o
diff --git a/lib/carta_random32.c b/lib/carta_random32.c
new file mode 100644
index 000000000000..ca82df70eee4
--- /dev/null
+++ b/lib/carta_random32.c
@@ -0,0 +1,41 @@
1/*
2 * Copyright (c) 2002-2006 Hewlett-Packard Development Company, L.P.
3 * Contributed by David Mosberger-Tang <davidm@hpl.hp.com>
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of version 2 of the GNU General Public
7 * License as published by the Free Software Foundation.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
17 * 02111-1307 USA
18 */
19#include <linux/types.h>
20#include <linux/module.h>
21
22/*
23 * Fast, simple, yet decent quality random number generator based on
24 * a paper by David G. Carta ("Two Fast Implementations of the
25 * `Minimal Standard' Random Number Generator," Communications of the
26 * ACM, January, 1990).
27 */
28u64 carta_random32 (u64 seed)
29{
30# define A 16807
31# define M ((u32) 1 << 31)
32 u64 s, prod = A * seed, p, q;
33
34 p = (prod >> 31) & (M - 1);
35 q = (prod >> 0) & (M - 1);
36 s = p + q;
37 if (s >= M)
38 s -= M - 1;
39 return s;
40}
41EXPORT_SYMBOL_GPL(carta_random32);