Debian Codegraph @

lib/util/randmersenne.c

raw
1 #include "netpbm/pm.h"
2 #include "netpbm/rand.h"
3
4 /* +++++ Start of Mersenne Twister pseudorandom number generator code +++++ */
5
6 /*
7 Original source code from:
8 http://www.math.sci.hiroshima-u.ac.jp/m-mat/MT/VERSIONS/C-LANG/c-lang.html
9
10 A C-program for MT19937, with initialization improved 2002/1/26.
11 Coded by Takuji Nishimura and Makoto Matsumoto.
12
13 Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
14 All rights reserved.
15
16 Redistribution and use in source and binary forms, with or without
17 modification, are permitted provided that the following conditions
18 are met:
19
20 1. Redistributions of source code must retain the above copyright
21 notice, this list of conditions and the following disclaimer.
22
23 2. Redistributions in binary form must reproduce the above copyright
24 notice, this list of conditions and the following disclaimer in the
25 documentation and/or other materials provided with the distribution.
26
27 3. The names of its contributors may not be used to endorse or promote
28 products derived from this software without specific prior written
29 permission.
30
31 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
32 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
33 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
34 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
35 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
36 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
37 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
38 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
39 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
40 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
41 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
42
43 Any feedback is very welcome.
44 http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
45 email: m-mat @ math.sci.hiroshima-u.ac.jp (remove space)
46
47 Above conditions apply in the following code to the line which says:
48 +++++ End of Mersenne Twister pseudorandom number generator code +++++
49 */
50
51 /* Period parameters */
52
53 #define MT_N 624
54 #define MT_M 397
55 #define MT_MATRIX_A 0x9908b0dfUL /* constant vector a */
56
57 struct MtState {
58 uint32_t mt[MT_N]; /* the array for the state vector */
59 unsigned int mtIndex;
60 };
61
62
63
64 static void
65 randMtAlloc(struct MtState ** const statePP) {
66
67 struct MtState * stateP;
68
69 MALLOCVAR_NOFAIL(stateP);
70
71 *statePP = stateP;
72 }
73
74
75
76 /* 32 bit masks */
77
78 static uint32_t const FMASK = 0xffffffffUL; /* all bits */
79 static uint32_t const UMASK = 0x80000000UL; /* most significant bit */
80 static uint32_t const LMASK = 0x7fffffffUL; /* least significant 31 bits */
81
82
83
84 static void
85 srandMt(struct MtState * const stateP,
86 unsigned int const seed) {
87 /*-----------------------------------------------------------------------------
88 Initialize state array mt[MT_N] with seed
89 -----------------------------------------------------------------------------*/
90 unsigned int mtIndex;
91 uint32_t * const mt = stateP->mt;
92
93 mt[0]= seed & FMASK;
94
95 for (mtIndex = 1; mtIndex < MT_N; ++mtIndex) {
96 mt[mtIndex] = (1812433253UL * (mt[mtIndex-1]
97 ^ (mt[mtIndex-1] >> 30)) + mtIndex);
98
99 /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
100 }
101
102 stateP->mtIndex = mtIndex;
103 }
104
105
106
107 static unsigned long int
108 randMt32(struct MtState * const stateP) {
109 /*----------------------------------------------------------------------------
110 Generate a 32 bit random number interval: [0, 0xffffffff]
111 ----------------------------------------------------------------------------*/
112 unsigned int mtIndex;
113 uint32_t retval;
114
115 if (stateP->mtIndex >= MT_N) {
116 /* generate N words at one time */
117 uint32_t * const mt = stateP->mt;
118 uint32_t const mag01[2]={0x0UL, MT_MATRIX_A};
119 /* mag01[x] = x * MT_MATRIX_A for x=0, 1 */
120
121 int k;
122 uint32_t y;
123
124 if (stateP->mtIndex >= MT_N+1) {
125 pm_error("Internal error in Mersenne Twister random number"
126 "generator");
127 }
128
129 for (k = 0; k < MT_N-MT_M; ++k) {
130 y = (mt[k] & UMASK) | (mt[k+1] & LMASK);
131 mt[k] = mt[k + MT_M] ^ (y >> 1) ^ mag01[y & 0x1UL];
132 }
133 for (; k < MT_N-1; ++k) {
134 y = (mt[k] & UMASK) | (mt[k+1] & LMASK);
135 mt[k] = mt[k+(MT_M-MT_N)] ^ (y >> 1) ^ mag01[y & 0x1UL];
136 }
137 y = (mt[MT_N - 1] & UMASK) | (mt[0] & LMASK);
138 mt[MT_N - 1] = mt[MT_M - 1] ^ (y >> 1) ^ mag01[y & 0x1UL];
139
140 mtIndex = 0;
141 } else
142 mtIndex = stateP->mtIndex;
143
144 retval = stateP->mt[mtIndex];
145
146 /* Tempering */
147 retval ^= (retval >> 11);
148 retval ^= (retval << 7) & 0x9d2c5680UL;
149 retval ^= (retval << 15) & 0xefc60000UL;
150 retval ^= (retval >> 18);
151
152 stateP->mtIndex = mtIndex + 1;
153
154 return retval;
155 }
156
157 /* +++++ End of Mersenne Twister pseudorandom number generator code +++++ */
158
159
160 static void
161 vinit(struct pm_randSt * const randStP) {
162
163 randMtAlloc((struct MtState ** const) &randStP->stateP);
164 randStP->max = 0xffffffffUL;
165 }
166
167
168
169 static void
170 vsrand(struct pm_randSt * const randStP,
171 unsigned int const seed) {
172
173 srandMt(randStP->stateP, seed);
174 }
175
176
177
178 static unsigned long int
179 vrand(struct pm_randSt * const randStP) {
180
181 return randMt32(randStP->stateP);
182 }
183
184
185
186 struct pm_rand_vtable const pm_randmersenne_vtable = {
187 &vinit,
188 &vsrand,
189 &vrand
190 };
191
192