src/common/urand.c

#ifndef lint
static const char       RCSid[] = "$Id: urand.c,v 2.13 2022/04/21 02:55:19 greg Exp $";
#endif
/*
 * Anticorrelated random function due to Christophe Schlick
 */

#include "copyright.h"

#include  "rterror.h"
#include  "random.h"

#undef initurand

#define  MAXORDER       (8*sizeof(unsigned short))

static unsigned short  empty_tab = 0;

unsigned short  *urperm = &empty_tab;   /* urand() permutation */
int  urmask = 0;                        /* bits used in permutation */


long
irandom(                        /* better than using random() % modulus */
        long modulus
)
{
        if (sizeof(long) >= 8)
                return((random()*modulus)>>31);

        if (sizeof(long long) >= 8)
                return((random()*(long long)modulus)>>31);

        return(frandom()*modulus);
}

int
initurand(                      /* initialize urand() for size entries */
        int  size
)
{
        int  order, n;
        int  i, offset;

        if ((urperm != NULL) & (urperm != &empty_tab))
                free((void *)urperm);
        if (--size <= 0) {
                empty_tab = 0;
                urperm = &empty_tab;
                urmask = 0;
                return(0);
        }
        for (i = 1; (size >>= 1); i++)
                if (i == MAXORDER)
                        break;
        order = i;
        urmask = (1<<order) - 1;
        urperm = (unsigned short *)malloc((urmask+1)*sizeof(unsigned short));
        if (urperm == NULL) {
                eputs("out of memory in initurand\n");
                quit(1);
        }
        urperm[0] = 0;
        for (n = 1, offset = 1; n <= order; n++, offset <<= 1)
                for (i = offset; i--; ) {
                        urperm[i+offset] = urperm[i] <<= 1;
                        if (random() & 0x4000)
                                urperm[i]++;
                        else
                                urperm[i+offset]++;
                }
        return(urmask+1);
}


int
ilhash(                         /* hash a set of integer values */
        int  *d,
        int  n
)
{
        static int  tab[8] = {103699,96289,73771,65203,81119,87037,92051,98899};
        int  hval;

        hval = 0;
        while (n-- > 0)
                hval ^= *d++ * tab[n&7];
        return(hval & 0x7fffffff);
}
Revision:	2.14
Committed:	Thu Apr 21 15:22:30 2022 UTC (2 years ago) by greg
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rad5R4, HEAD
Changes since 2.13:	+4 -4 lines
Log Message:	fix: Better implementation of irandom()
#	User	Rev	Content
1	greg	1.1	#ifndef lint
2	greg	2.14	static const char RCSid[] = "$Id: urand.c,v 2.13 2022/04/21 02:55:19 greg Exp $";
3	greg	1.1	#endif
4			/*
5	greg	1.5	* Anticorrelated random function due to Christophe Schlick
6	greg	1.1	*/
7
8	greg	2.6	#include "copyright.h"
9	greg	2.5
10	greg	2.12	#include "rterror.h"
11	greg	1.1	#include "random.h"
12
13	greg	2.5	#undef initurand
14	greg	1.1
15	gregl	2.4	#define MAXORDER (8*sizeof(unsigned short))
16
17	greg	2.10	static unsigned short empty_tab = 0;
18
19			unsigned short urperm = &empty_tab; / urand() permutation */
20			int urmask = 0; /* bits used in permutation */
21	greg	1.1
22	greg	2.11
23	greg	2.12	long
24			irandom( /* better than using random() % modulus */
25			long modulus
26			)
27			{
28	greg	2.14	if (sizeof(long) >= 8)
29	greg	2.12	return((random()*modulus)>>31);
30
31	greg	2.14	if (sizeof(long long) >= 8)
32	greg	2.12	return((random()*(long long)modulus)>>31);
33
34	greg	2.14	return(frandom()*modulus);
35	greg	2.12	}
36
37	gregl	2.3	int
38	greg	2.11	initurand( /* initialize urand() for size entries */
39			int size
40			)
41	greg	1.1	{
42			int order, n;
43	greg	2.11	int i, offset;
44	greg	1.1
45	greg	2.10	if ((urperm != NULL) & (urperm != &empty_tab))
46	greg	2.5	free((void *)urperm);
47			if (--size <= 0) {
48	greg	2.10	empty_tab = 0;
49			urperm = &empty_tab;
50	greg	2.5	urmask = 0;
51			return(0);
52			}
53	greg	2.8	for (i = 1; (size >>= 1); i++)
54			if (i == MAXORDER)
55			break;
56			order = i;
57			urmask = (1<<order) - 1;
58	gregl	2.4	urperm = (unsigned short )malloc((urmask+1)sizeof(unsigned short));
59	greg	1.1	if (urperm == NULL) {
60			eputs("out of memory in initurand\n");
61			quit(1);
62			}
63	greg	2.9	urperm[0] = 0;
64	greg	1.1	for (n = 1, offset = 1; n <= order; n++, offset <<= 1)
65			for (i = offset; i--; ) {
66	greg	2.8	urperm[i+offset] = urperm[i] <<= 1;
67	greg	1.1	if (random() & 0x4000)
68			urperm[i]++;
69			else
70			urperm[i+offset]++;
71			}
72	greg	2.8	return(urmask+1);
73	greg	1.2	}
74
75
76			int
77	greg	2.11	ilhash( /* hash a set of integer values */
78			int *d,
79			int n
80			)
81	greg	1.2	{
82	greg	2.10	static int tab[8] = {103699,96289,73771,65203,81119,87037,92051,98899};
83	greg	2.11	int hval;
84	greg	1.2
85			hval = 0;
86			while (n-- > 0)
87	greg	2.10	hval ^= d++ tab[n&7];
88			return(hval & 0x7fffffff);
89	greg	1.1	}