1*9a747e4fSDavid du Colombier #include <u.h> 2*9a747e4fSDavid du Colombier #include <libc.h> 3*9a747e4fSDavid du Colombier 4*9a747e4fSDavid du Colombier ulong ntruerand(ulong n)5*9a747e4fSDavid du Colombierntruerand(ulong n) 6*9a747e4fSDavid du Colombier { 7*9a747e4fSDavid du Colombier ulong m, r; 8*9a747e4fSDavid du Colombier 9*9a747e4fSDavid du Colombier /* 10*9a747e4fSDavid du Colombier * set m to the one less than the maximum multiple of n <= 2^32, 11*9a747e4fSDavid du Colombier * so we want a random number <= m. 12*9a747e4fSDavid du Colombier */ 13*9a747e4fSDavid du Colombier if(n > (1UL<<31)) 14*9a747e4fSDavid du Colombier m = n-1; 15*9a747e4fSDavid du Colombier else 16*9a747e4fSDavid du Colombier /* 2^32 - 2^32%n - 1 = (2^32 - 1) - (2*(2^31%n))%n */ 17*9a747e4fSDavid du Colombier m = 0xFFFFFFFFUL - (2*((1UL<<31)%n))%n; 18*9a747e4fSDavid du Colombier 19*9a747e4fSDavid du Colombier while((r = truerand()) > m) 20*9a747e4fSDavid du Colombier ; 21*9a747e4fSDavid du Colombier 22*9a747e4fSDavid du Colombier return r%n; 23*9a747e4fSDavid du Colombier } 24