1 /*
2 +----------------------------------------------------------------------+
3 | Copyright (c) The PHP Group |
4 +----------------------------------------------------------------------+
5 | This source file is subject to version 3.01 of the PHP license, |
6 | that is bundled with this package in the file LICENSE, and is |
7 | available through the world-wide-web at the following url: |
8 | http://www.php.net/license/3_01.txt |
9 | If you did not receive a copy of the PHP license and are unable to |
10 | obtain it through the world-wide-web, please send a note to |
11 | license@php.net so we can mail you a copy immediately. |
12 +----------------------------------------------------------------------+
13 | Authors: Rasmus Lerdorf <rasmus@php.net> |
14 | Zeev Suraski <zeev@php.net> |
15 | Pedro Melo <melo@ip.pt> |
16 | Sterling Hughes <sterling@php.net> |
17 | |
18 | Based on code from: Richard J. Wagner <rjwagner@writeme.com> |
19 | Makoto Matsumoto <matumoto@math.keio.ac.jp> |
20 | Takuji Nishimura |
21 | Shawn Cokus <Cokus@math.washington.edu> |
22 +----------------------------------------------------------------------+
23 */
24
25 #include "php.h"
26 #include "php_rand.h"
27 #include "php_mt_rand.h"
28
29 /* MT RAND FUNCTIONS */
30
31 /*
32 The following php_mt_...() functions are based on a C++ class MTRand by
33 Richard J. Wagner. For more information see the web page at
34 http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/C-LANG/MersenneTwister.h
35
36 Mersenne Twister random number generator -- a C++ class MTRand
37 Based on code by Makoto Matsumoto, Takuji Nishimura, and Shawn Cokus
38 Richard J. Wagner v1.0 15 May 2003 rjwagner@writeme.com
39
40 The Mersenne Twister is an algorithm for generating random numbers. It
41 was designed with consideration of the flaws in various other generators.
42 The period, 2^19937-1, and the order of equidistribution, 623 dimensions,
43 are far greater. The generator is also fast; it avoids multiplication and
44 division, and it benefits from caches and pipelines. For more information
45 see the inventors' web page at http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
46
47 Reference
48 M. Matsumoto and T. Nishimura, "Mersenne Twister: A 623-Dimensionally
49 Equidistributed Uniform Pseudo-Random Number Generator", ACM Transactions on
50 Modeling and Computer Simulation, Vol. 8, No. 1, January 1998, pp 3-30.
51
52 Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
53 Copyright (C) 2000 - 2003, Richard J. Wagner
54 All rights reserved.
55
56 Redistribution and use in source and binary forms, with or without
57 modification, are permitted provided that the following conditions
58 are met:
59
60 1. Redistributions of source code must retain the above copyright
61 notice, this list of conditions and the following disclaimer.
62
63 2. Redistributions in binary form must reproduce the above copyright
64 notice, this list of conditions and the following disclaimer in the
65 documentation and/or other materials provided with the distribution.
66
67 3. The names of its contributors may not be used to endorse or promote
68 products derived from this software without specific prior written
69 permission.
70
71 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
72 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
73 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
74 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
75 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
76 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
77 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
78 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
79 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
80 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
81 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
82 */
83
84 #define N MT_N /* length of state vector */
85 #define M (397) /* a period parameter */
86 #define hiBit(u) ((u) & 0x80000000U) /* mask all but highest bit of u */
87 #define loBit(u) ((u) & 0x00000001U) /* mask all but lowest bit of u */
88 #define loBits(u) ((u) & 0x7FFFFFFFU) /* mask the highest bit of u */
89 #define mixBits(u, v) (hiBit(u)|loBits(v)) /* move hi bit of u to hi bit of v */
90
91 #define twist(m,u,v) (m ^ (mixBits(u,v)>>1) ^ ((uint32_t)(-(int32_t)(loBit(v))) & 0x9908b0dfU))
92 #define twist_php(m,u,v) (m ^ (mixBits(u,v)>>1) ^ ((uint32_t)(-(int32_t)(loBit(u))) & 0x9908b0dfU))
93
94 /* {{{ php_mt_initialize */
php_mt_initialize(uint32_t seed,uint32_t * state)95 static inline void php_mt_initialize(uint32_t seed, uint32_t *state)
96 {
97 /* Initialize generator state with seed
98 See Knuth TAOCP Vol 2, 3rd Ed, p.106 for multiplier.
99 In previous versions, most significant bits (MSBs) of the seed affect
100 only MSBs of the state array. Modified 9 Jan 2002 by Makoto Matsumoto. */
101
102 register uint32_t *s = state;
103 register uint32_t *r = state;
104 register int i = 1;
105
106 *s++ = seed & 0xffffffffU;
107 for( ; i < N; ++i ) {
108 *s++ = ( 1812433253U * ( *r ^ (*r >> 30) ) + i ) & 0xffffffffU;
109 r++;
110 }
111 }
112 /* }}} */
113
114 /* {{{ php_mt_reload */
php_mt_reload(void)115 static inline void php_mt_reload(void)
116 {
117 /* Generate N new values in state
118 Made clearer and faster by Matthew Bellew (matthew.bellew@home.com) */
119
120 register uint32_t *state = BG(state);
121 register uint32_t *p = state;
122 register int i;
123
124 if (BG(mt_rand_mode) == MT_RAND_MT19937) {
125 for (i = N - M; i--; ++p)
126 *p = twist(p[M], p[0], p[1]);
127 for (i = M; --i; ++p)
128 *p = twist(p[M-N], p[0], p[1]);
129 *p = twist(p[M-N], p[0], state[0]);
130 }
131 else {
132 for (i = N - M; i--; ++p)
133 *p = twist_php(p[M], p[0], p[1]);
134 for (i = M; --i; ++p)
135 *p = twist_php(p[M-N], p[0], p[1]);
136 *p = twist_php(p[M-N], p[0], state[0]);
137 }
138 BG(left) = N;
139 BG(next) = state;
140 }
141 /* }}} */
142
143 /* {{{ php_mt_srand */
php_mt_srand(uint32_t seed)144 PHPAPI void php_mt_srand(uint32_t seed)
145 {
146 /* Seed the generator with a simple uint32 */
147 php_mt_initialize(seed, BG(state));
148 php_mt_reload();
149
150 /* Seed only once */
151 BG(mt_rand_is_seeded) = 1;
152 }
153 /* }}} */
154
155 /* {{{ php_mt_rand */
php_mt_rand(void)156 PHPAPI uint32_t php_mt_rand(void)
157 {
158 /* Pull a 32-bit integer from the generator state
159 Every other access function simply transforms the numbers extracted here */
160
161 register uint32_t s1;
162
163 if (UNEXPECTED(!BG(mt_rand_is_seeded))) {
164 php_mt_srand(GENERATE_SEED());
165 }
166
167 if (BG(left) == 0) {
168 php_mt_reload();
169 }
170 --BG(left);
171
172 s1 = *BG(next)++;
173 s1 ^= (s1 >> 11);
174 s1 ^= (s1 << 7) & 0x9d2c5680U;
175 s1 ^= (s1 << 15) & 0xefc60000U;
176 return ( s1 ^ (s1 >> 18) );
177 }
178 /* }}} */
179
180 /* {{{ Seeds Mersenne Twister random number generator */
PHP_FUNCTION(mt_srand)181 PHP_FUNCTION(mt_srand)
182 {
183 zend_long seed = 0;
184 zend_long mode = MT_RAND_MT19937;
185
186 ZEND_PARSE_PARAMETERS_START(0, 2)
187 Z_PARAM_OPTIONAL
188 Z_PARAM_LONG(seed)
189 Z_PARAM_LONG(mode)
190 ZEND_PARSE_PARAMETERS_END();
191
192 if (ZEND_NUM_ARGS() == 0)
193 seed = GENERATE_SEED();
194
195 switch (mode) {
196 case MT_RAND_PHP:
197 BG(mt_rand_mode) = MT_RAND_PHP;
198 break;
199 default:
200 BG(mt_rand_mode) = MT_RAND_MT19937;
201 }
202
203 php_mt_srand(seed);
204 }
205 /* }}} */
206
rand_range32(uint32_t umax)207 static uint32_t rand_range32(uint32_t umax) {
208 uint32_t result, limit;
209
210 result = php_mt_rand();
211
212 /* Special case where no modulus is required */
213 if (UNEXPECTED(umax == UINT32_MAX)) {
214 return result;
215 }
216
217 /* Increment the max so the range is inclusive of max */
218 umax++;
219
220 /* Powers of two are not biased */
221 if ((umax & (umax - 1)) == 0) {
222 return result & (umax - 1);
223 }
224
225 /* Ceiling under which UINT32_MAX % max == 0 */
226 limit = UINT32_MAX - (UINT32_MAX % umax) - 1;
227
228 /* Discard numbers over the limit to avoid modulo bias */
229 while (UNEXPECTED(result > limit)) {
230 result = php_mt_rand();
231 }
232
233 return result % umax;
234 }
235
236 #if ZEND_ULONG_MAX > UINT32_MAX
rand_range64(uint64_t umax)237 static uint64_t rand_range64(uint64_t umax) {
238 uint64_t result, limit;
239
240 result = php_mt_rand();
241 result = (result << 32) | php_mt_rand();
242
243 /* Special case where no modulus is required */
244 if (UNEXPECTED(umax == UINT64_MAX)) {
245 return result;
246 }
247
248 /* Increment the max so the range is inclusive of max */
249 umax++;
250
251 /* Powers of two are not biased */
252 if ((umax & (umax - 1)) == 0) {
253 return result & (umax - 1);
254 }
255
256 /* Ceiling under which UINT64_MAX % max == 0 */
257 limit = UINT64_MAX - (UINT64_MAX % umax) - 1;
258
259 /* Discard numbers over the limit to avoid modulo bias */
260 while (UNEXPECTED(result > limit)) {
261 result = php_mt_rand();
262 result = (result << 32) | php_mt_rand();
263 }
264
265 return result % umax;
266 }
267 #endif
268
269 /* {{{ php_mt_rand_range */
php_mt_rand_range(zend_long min,zend_long max)270 PHPAPI zend_long php_mt_rand_range(zend_long min, zend_long max)
271 {
272 zend_ulong umax = max - min;
273
274 #if ZEND_ULONG_MAX > UINT32_MAX
275 if (umax > UINT32_MAX) {
276 return (zend_long) (rand_range64(umax) + min);
277 }
278 #endif
279
280 return (zend_long) (rand_range32(umax) + min);
281 }
282 /* }}} */
283
284 /* {{{ php_mt_rand_common
285 * rand() allows min > max, mt_rand does not */
php_mt_rand_common(zend_long min,zend_long max)286 PHPAPI zend_long php_mt_rand_common(zend_long min, zend_long max)
287 {
288 int64_t n;
289
290 if (BG(mt_rand_mode) == MT_RAND_MT19937) {
291 return php_mt_rand_range(min, max);
292 }
293
294 /* Legacy mode deliberately not inside php_mt_rand_range()
295 * to prevent other functions being affected */
296 n = (int64_t)php_mt_rand() >> 1;
297 RAND_RANGE_BADSCALING(n, min, max, PHP_MT_RAND_MAX);
298
299 return n;
300 }
301 /* }}} */
302
303 /* {{{ Returns a random number from Mersenne Twister */
PHP_FUNCTION(mt_rand)304 PHP_FUNCTION(mt_rand)
305 {
306 zend_long min;
307 zend_long max;
308 int argc = ZEND_NUM_ARGS();
309
310 if (argc == 0) {
311 // genrand_int31 in mt19937ar.c performs a right shift
312 RETURN_LONG(php_mt_rand() >> 1);
313 }
314
315 ZEND_PARSE_PARAMETERS_START(2, 2)
316 Z_PARAM_LONG(min)
317 Z_PARAM_LONG(max)
318 ZEND_PARSE_PARAMETERS_END();
319
320 if (UNEXPECTED(max < min)) {
321 zend_argument_value_error(2, "must be greater than or equal to argument #1 ($min)");
322 RETURN_THROWS();
323 }
324
325 RETURN_LONG(php_mt_rand_common(min, max));
326 }
327 /* }}} */
328
329 /* {{{ Returns the maximum value a random number from Mersenne Twister can have */
PHP_FUNCTION(mt_getrandmax)330 PHP_FUNCTION(mt_getrandmax)
331 {
332 ZEND_PARSE_PARAMETERS_NONE();
333
334 /*
335 * Melo: it could be 2^^32 but we only use 2^^31 to maintain
336 * compatibility with the previous php_rand
337 */
338 RETURN_LONG(PHP_MT_RAND_MAX); /* 2^^31 */
339 }
340 /* }}} */
341
PHP_MINIT_FUNCTION(mt_rand)342 PHP_MINIT_FUNCTION(mt_rand)
343 {
344 REGISTER_LONG_CONSTANT("MT_RAND_MT19937", MT_RAND_MT19937, CONST_CS | CONST_PERSISTENT);
345 REGISTER_LONG_CONSTANT("MT_RAND_PHP", MT_RAND_PHP, CONST_CS | CONST_PERSISTENT);
346
347 return SUCCESS;
348 }
349
