This repository has been archived by the owner on Feb 23, 2018. It is now read-only.
forked from katahiromz/XScreenSaverWin
-
Notifications
You must be signed in to change notification settings - Fork 0
/
yarandom.c
151 lines (127 loc) · 5.08 KB
/
yarandom.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
/* yarandom.c -- Yet Another Random Number Generator.
* Copyright (c) 1997-2010 by Jamie Zawinski <[email protected]>
*
* Permission to use, copy, modify, distribute, and sell this software and its
* documentation for any purpose is hereby granted without fee, provided that
* the above copyright notice appear in all copies and that both that
* copyright notice and this permission notice appear in supporting
* documentation. No representations are made about the suitability of this
* software for any purpose. It is provided "as is" without express or
* implied warranty.
*/
/* The unportable mess that is rand(), random(), drand48() and friends led me
to ask Phil Karlton <[email protected]> what the Right Thing to Do was.
He responded with this. It is non-cryptographically secure, reasonably
random (more so than anything that is in any C library), and very fast.
I don't understand how it works at all, but he says "look at Knuth,
Vol. 2 (original edition), page 26, Algorithm A. In this case n=55,
k=24 and m=2^32."
So there you have it.
---------------------------
Note: xlockmore 4.03a10 uses this very simple RNG:
if ((seed = seed % 44488 * 48271 - seed / 44488 * 3399) < 0)
seed += 2147483647;
return seed-1;
of which it says
``Dr. Park's algorithm published in the Oct. '88 ACM "Random Number
Generators: Good Ones Are Hard To Find" His version available at
ftp://cs.wm.edu/pub/rngs.tar Present form by many authors.''
Karlton says: ``the usual problem with that kind of RNG turns out to
be unexepected short cycles for some word lengths.''
Karlton's RNG is faster, since it does three adds and two stores, while the
xlockmore RNG does two multiplies, two divides, three adds, and one store.
Compiler optimizations make a big difference here:
gcc -O: difference is 1.2x.
gcc -O2: difference is 1.4x.
gcc -O3: difference is 1.5x.
SGI cc -O: difference is 2.4x.
SGI cc -O2: difference is 2.4x.
SGI cc -O3: difference is 5.1x.
Irix 6.2; Indy r5k; SGI cc version 6; gcc version 2.7.2.1.
*/
#if 0
#ifdef HAVE_CONFIG_H
# include "config.h"
#endif
#ifdef HAVE_UNISTD_H
# include <unistd.h> /* for getpid() */
#endif
#include <sys/time.h> /* for gettimeofday() */
#endif
#include "xlockmore.h"
#include "yarandom.h"
# undef ya_rand_init
/* The following 'random' numbers are taken from CRC, 18th Edition, page 622.
Each array element was taken from the corresponding line in the table,
except that a[0] was from line 100. 8s and 9s in the table were simply
skipped. The high order digit was taken mod 4.
*/
#define VectorSize 55
static unsigned int a[VectorSize] = {
035340171546, 010401501101, 022364657325, 024130436022, 002167303062, /* 5 */
037570375137, 037210607110, 016272055420, 023011770546, 017143426366, /* 10 */
014753657433, 021657231332, 023553406142, 004236526362, 010365611275, /* 14 */
007117336710, 011051276551, 002362132524, 001011540233, 012162531646, /* 20 */
007056762337, 006631245521, 014164542224, 032633236305, 023342700176, /* 25 */
002433062234, 015257225043, 026762051606, 000742573230, 005366042132, /* 30 */
012126416411, 000520471171, 000725646277, 020116577576, 025765742604, /* 35 */
007633473735, 015674255275, 017555634041, 006503154145, 021576344247, /* 40 */
014577627653, 002707523333, 034146376720, 030060227734, 013765414060, /* 45 */
036072251540, 007255221037, 024364674123, 006200353166, 010126373326, /* 50 */
015664104320, 016401041535, 016215305520, 033115351014, 017411670323 /* 55 */
};
static unsigned int i1 = 0, i2 = 0;
unsigned int
ya_random (void)
{
int ret = a[i1] + a[i2];
a[i1] = ret;
if (++i1 >= VectorSize) i1 = 0;
if (++i2 >= VectorSize) i2 = 0;
return ret;
}
void
ya_rand_init(unsigned int seed)
{
int i;
if (seed == 0)
{
/*
struct timeval tp;
#ifdef GETTIMEOFDAY_TWO_ARGS
struct timezone tzp;
gettimeofday(&tp, &tzp);
#else
gettimeofday(&tp);
#endif*/
/* Since the multiplications will have a larger effect on the
upper bits than the lower bits, after every addition in the
seed, perform a bitwise rotate by an odd number, resulting
in a better distribution of randomness throughout the bits.
-- Brian Carlson, 2010.
*/
#define ROT(X,N) (((X)<<(N)) | ((X)>>((sizeof(unsigned int)*8)-(N))))
//seed = (999 * tp.tv_sec);
//seed = ROT (seed, 11);
//seed += (1001 * tp.tv_usec);
//seed = ROT (seed, 7);
//seed += (1003 * getpid());
//seed = ROT (seed, 13);
seed = GetCurrentProcessId();
seed <<= 16;
seed ^= (DWORD)(DWORD_PTR)GetForegroundWindow();
seed <<= 8;
seed ^= GetTickCount();
}
a[0] += seed;
for (i = 1; i < VectorSize; i++)
{
seed = seed*999;
seed = ROT (seed, 9);
seed += a[i-1]*1001;
seed = ROT (seed, 15);
a[i] += seed;
}
i1 = a[0] % VectorSize;
i2 = (i1 + 24) % VectorSize;
}