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