src/common/urand.c

#ifndef lint
static const char       RCSid[] = "$Id: urand.c,v 2.11 2015/05/27 08:42:06 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
)
{
        static const int        isize = sizeof(int);
        static const int        lsize = sizeof(long);
        static const int        llsize = sizeof(long long);

        if ((lsize == 8) | (isize == 8))
                return((random()*modulus)>>31);

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

        return(random() % 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.12
Committed:	Thu Apr 21 02:52:40 2022 UTC (2 years ago) by greg
Content type:	text/plain
Branch:	MAIN
Changes since 2.11:	+20 -2 lines
Log Message:	perf(cnt): improved randomness of cnt -s option with new irandom(modulus) call
#	User	Rev	Content
1	greg	1.1	#ifndef lint
2	greg	2.12	static const char RCSid[] = "$Id: urand.c,v 2.11 2015/05/27 08:42:06 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			static const int isize = sizeof(int);
29			static const int lsize = sizeof(long);
30			static const int llsize = sizeof(long long);
31
32			if ((lsize == 8) \| (isize == 8))
33			return((random()*modulus)>>31);
34
35			if (llsize == 8)
36			return((random()*(long long)modulus)>>31);
37
38			return(random() % modulus);
39			}
40
41	gregl	2.3	int
42	greg	2.11	initurand( /* initialize urand() for size entries */
43			int size
44			)
45	greg	1.1	{
46			int order, n;
47	greg	2.11	int i, offset;
48	greg	1.1
49	greg	2.10	if ((urperm != NULL) & (urperm != &empty_tab))
50	greg	2.5	free((void *)urperm);
51			if (--size <= 0) {
52	greg	2.10	empty_tab = 0;
53			urperm = &empty_tab;
54	greg	2.5	urmask = 0;
55			return(0);
56			}
57	greg	2.8	for (i = 1; (size >>= 1); i++)
58			if (i == MAXORDER)
59			break;
60			order = i;
61			urmask = (1<<order) - 1;
62	gregl	2.4	urperm = (unsigned short )malloc((urmask+1)sizeof(unsigned short));
63	greg	1.1	if (urperm == NULL) {
64			eputs("out of memory in initurand\n");
65			quit(1);
66			}
67	greg	2.9	urperm[0] = 0;
68	greg	1.1	for (n = 1, offset = 1; n <= order; n++, offset <<= 1)
69			for (i = offset; i--; ) {
70	greg	2.8	urperm[i+offset] = urperm[i] <<= 1;
71	greg	1.1	if (random() & 0x4000)
72			urperm[i]++;
73			else
74			urperm[i+offset]++;
75			}
76	greg	2.8	return(urmask+1);
77	greg	1.2	}
78
79
80			int
81	greg	2.11	ilhash( /* hash a set of integer values */
82			int *d,
83			int n
84			)
85	greg	1.2	{
86	greg	2.10	static int tab[8] = {103699,96289,73771,65203,81119,87037,92051,98899};
87	greg	2.11	int hval;
88	greg	1.2
89			hval = 0;
90			while (n-- > 0)
91	greg	2.10	hval ^= d++ tab[n&7];
92			return(hval & 0x7fffffff);
93	greg	1.1	}