1 #include	<lib9.h>
2 
3 /*
4  *	algorithm by
5  *	D. P. Mitchell & J. A. Reeds
6  */
7 
8 #define	LEN	607
9 #define	TAP	273
10 #define	MASK	0x7fffffffL
11 #define	A	48271
12 #define	M	2147483647
13 #define	Q	44488
14 #define	R	3399
15 #define	NORM	(1.0/(1.0+MASK))
16 
17 static	ulong	rng_vec[LEN];
18 static	ulong*	rng_tap = rng_vec;
19 static	ulong*	rng_feed = 0;
20 static	Lock	lk;
21 
22 static void
23 isrand(long seed)
24 {
25 	long lo, hi, x;
26 	int i;
27 
28 	rng_tap = rng_vec;
29 	rng_feed = rng_vec+LEN-TAP;
30 	seed = seed%M;
31 	if(seed < 0)
32 		seed += M;
33 	if(seed == 0)
34 		seed = 89482311;
35 	x = seed;
36 	/*
37 	 *	Initialize by x[n+1] = 48271 * x[n] mod (2**31 - 1)
38 	 */
39 	for(i = -20; i < LEN; i++) {
40 		hi = x / Q;
41 		lo = x % Q;
42 		x = A*lo - R*hi;
43 		if(x < 0)
44 			x += M;
45 		if(i >= 0)
46 			rng_vec[i] = x;
47 	}
48 }
49 
50 void
51 srand(long seed)
52 {
53 	lock(&lk);
54 	isrand(seed);
55 	unlock(&lk);
56 }
57 
58 long
59 lrand(void)
60 {
61 	ulong x;
62 
63 	lock(&lk);
64 
65 	rng_tap--;
66 	if(rng_tap < rng_vec) {
67 		if(rng_feed == 0) {
68 			isrand(1);
69 			rng_tap--;
70 		}
71 		rng_tap += LEN;
72 	}
73 	rng_feed--;
74 	if(rng_feed < rng_vec)
75 		rng_feed += LEN;
76 	x = (*rng_feed + *rng_tap) & MASK;
77 	*rng_feed = x;
78 
79 	unlock(&lk);
80 
81 	return x;
82 }
83 
84 int
85 rand(void)
86 {
87 	return lrand() & 0x7fff;
88 }
89