1*25210b06SDavid du Colombier /* 2*25210b06SDavid du Colombier * libc pseudo-random number generators, but without locks. 3*25210b06SDavid du Colombier */ 4*25210b06SDavid du Colombier #include "u.h" 5*25210b06SDavid du Colombier #include "../port/lib.h" 6*25210b06SDavid du Colombier #include "mem.h" 7*25210b06SDavid du Colombier #include "dat.h" 8*25210b06SDavid du Colombier #include "fns.h" 9*25210b06SDavid du Colombier #include "io.h" 10*25210b06SDavid du Colombier #include "ureg.h" 11*25210b06SDavid du Colombier #include "pool.h" 12*25210b06SDavid du Colombier 13*25210b06SDavid du Colombier /* stubs to emulate random.c */ 14*25210b06SDavid du Colombier ulong randomread(void *,ulong)15*25210b06SDavid du Colombierrandomread(void *, ulong) 16*25210b06SDavid du Colombier { 17*25210b06SDavid du Colombier return 0; 18*25210b06SDavid du Colombier } 19*25210b06SDavid du Colombier 20*25210b06SDavid du Colombier void randominit(void)21*25210b06SDavid du Colombierrandominit(void) 22*25210b06SDavid du Colombier { 23*25210b06SDavid du Colombier } 24*25210b06SDavid du Colombier 25*25210b06SDavid du Colombier /* 26*25210b06SDavid du Colombier * algorithm by 27*25210b06SDavid du Colombier * D. P. Mitchell & J. A. Reeds 28*25210b06SDavid du Colombier */ 29*25210b06SDavid du Colombier 30*25210b06SDavid du Colombier #define LEN 607 31*25210b06SDavid du Colombier #define TAP 273 32*25210b06SDavid du Colombier #define MASK 0x7fffffffL 33*25210b06SDavid du Colombier #define A 48271 34*25210b06SDavid du Colombier #define M 2147483647 35*25210b06SDavid du Colombier #define Q 44488 36*25210b06SDavid du Colombier #define R 3399 37*25210b06SDavid du Colombier #define NORM (1.0/(1.0+MASK)) 38*25210b06SDavid du Colombier 39*25210b06SDavid du Colombier static ulong rng_vec[LEN]; 40*25210b06SDavid du Colombier static ulong* rng_tap = rng_vec; 41*25210b06SDavid du Colombier static ulong* rng_feed = 0; 42*25210b06SDavid du Colombier 43*25210b06SDavid du Colombier static void isrand(long seed)44*25210b06SDavid du Colombierisrand(long seed) 45*25210b06SDavid du Colombier { 46*25210b06SDavid du Colombier long lo, hi, x; 47*25210b06SDavid du Colombier int i; 48*25210b06SDavid du Colombier 49*25210b06SDavid du Colombier rng_tap = rng_vec; 50*25210b06SDavid du Colombier rng_feed = rng_vec+LEN-TAP; 51*25210b06SDavid du Colombier seed = seed%M; 52*25210b06SDavid du Colombier if(seed < 0) 53*25210b06SDavid du Colombier seed += M; 54*25210b06SDavid du Colombier if(seed == 0) 55*25210b06SDavid du Colombier seed = 89482311; 56*25210b06SDavid du Colombier x = seed; 57*25210b06SDavid du Colombier /* 58*25210b06SDavid du Colombier * Initialize by x[n+1] = 48271 * x[n] mod (2**31 - 1) 59*25210b06SDavid du Colombier */ 60*25210b06SDavid du Colombier for(i = -20; i < LEN; i++) { 61*25210b06SDavid du Colombier hi = x / Q; 62*25210b06SDavid du Colombier lo = x % Q; 63*25210b06SDavid du Colombier x = A*lo - R*hi; 64*25210b06SDavid du Colombier if(x < 0) 65*25210b06SDavid du Colombier x += M; 66*25210b06SDavid du Colombier if(i >= 0) 67*25210b06SDavid du Colombier rng_vec[i] = x; 68*25210b06SDavid du Colombier } 69*25210b06SDavid du Colombier } 70*25210b06SDavid du Colombier 71*25210b06SDavid du Colombier void srand(long seed)72*25210b06SDavid du Colombiersrand(long seed) 73*25210b06SDavid du Colombier { 74*25210b06SDavid du Colombier isrand(seed); 75*25210b06SDavid du Colombier } 76*25210b06SDavid du Colombier 77*25210b06SDavid du Colombier long lrand(void)78*25210b06SDavid du Colombierlrand(void) 79*25210b06SDavid du Colombier { 80*25210b06SDavid du Colombier ulong x; 81*25210b06SDavid du Colombier 82*25210b06SDavid du Colombier rng_tap--; 83*25210b06SDavid du Colombier if(rng_tap < rng_vec) { 84*25210b06SDavid du Colombier if(rng_feed == 0) { 85*25210b06SDavid du Colombier isrand(1); 86*25210b06SDavid du Colombier rng_tap--; 87*25210b06SDavid du Colombier } 88*25210b06SDavid du Colombier rng_tap += LEN; 89*25210b06SDavid du Colombier } 90*25210b06SDavid du Colombier rng_feed--; 91*25210b06SDavid du Colombier if(rng_feed < rng_vec) 92*25210b06SDavid du Colombier rng_feed += LEN; 93*25210b06SDavid du Colombier x = (*rng_feed + *rng_tap) & MASK; 94*25210b06SDavid du Colombier *rng_feed = x; 95*25210b06SDavid du Colombier return x; 96*25210b06SDavid du Colombier } 97