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