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 if (zend_parse_parameters(ZEND_NUM_ARGS(), "|ll", &seed, &mode) == FAILURE)
195 return;
196
197 if (ZEND_NUM_ARGS() == 0)
198 seed = GENERATE_SEED();
199
200 switch (mode) {
201 case MT_RAND_PHP:
202 BG(mt_rand_mode) = MT_RAND_PHP;
203 break;
204 default:
205 BG(mt_rand_mode) = MT_RAND_MT19937;
206 }
207
208 php_mt_srand(seed);
209 }
210 /* }}} */
211
212 /* {{{ php_mt_rand_range
213 */
php_mt_rand_range(zend_long min,zend_long max)214 PHPAPI zend_long php_mt_rand_range(zend_long min, zend_long max)
215 {
216 zend_ulong umax = max - min;
217 zend_ulong limit;
218 zend_ulong result;
219
220 result = php_mt_rand();
221 #if ZEND_ULONG_MAX > UINT32_MAX
222 if (umax > UINT32_MAX) {
223 result = (result << 32) | php_mt_rand();
224 }
225 #endif
226
227 /* Special case where no modulus is required */
228 if (UNEXPECTED(umax == ZEND_ULONG_MAX)) {
229 return (zend_long)result;
230 }
231
232 /* Increment the max so the range is inclusive of max */
233 umax++;
234
235 /* Powers of two are not biased */
236 if (EXPECTED((umax & (umax - 1)) != 0)) {
237 /* Ceiling under which ZEND_LONG_MAX % max == 0 */
238 limit = ZEND_ULONG_MAX - (ZEND_ULONG_MAX % umax) - 1;
239
240 /* Discard numbers over the limit to avoid modulo bias */
241 while (UNEXPECTED(result > limit)) {
242 #if ZEND_ULONG_MAX > UINT32_MAX
243 if (umax > UINT32_MAX) {
244 result = (result << 32) | php_mt_rand();
245 }
246 else {
247 result = php_mt_rand();
248 }
249 #else
250 result = php_mt_rand();
251 #endif
252 }
253 }
254
255 return (zend_long)((result % umax) + min);
256 }
257 /* }}} */
258
259 /* {{{ php_mt_rand_common
260 * rand() allows min > max, mt_rand does not */
php_mt_rand_common(zend_long min,zend_long max)261 PHPAPI zend_long php_mt_rand_common(zend_long min, zend_long max)
262 {
263 int64_t n;
264
265 if (BG(mt_rand_mode) == MT_RAND_MT19937) {
266 return php_mt_rand_range(min, max);
267 }
268
269 /* Legacy mode deliberately not inside php_mt_rand_range()
270 * to prevent other functions being affected */
271 n = (int64_t)php_mt_rand() >> 1;
272 RAND_RANGE_BADSCALING(n, min, max, PHP_MT_RAND_MAX);
273
274 return n;
275 }
276 /* }}} */
277
278 /* {{{ proto int mt_rand([int min, int max])
279 Returns a random number from Mersenne Twister */
PHP_FUNCTION(mt_rand)280 PHP_FUNCTION(mt_rand)
281 {
282 zend_long min;
283 zend_long max;
284 int argc = ZEND_NUM_ARGS();
285
286 if (argc == 0) {
287 // genrand_int31 in mt19937ar.c performs a right shift
288 RETURN_LONG(php_mt_rand() >> 1);
289 }
290
291 if (zend_parse_parameters(argc, "ll", &min, &max) == FAILURE) {
292 return;
293 }
294
295 if (UNEXPECTED(max < min)) {
296 php_error_docref(NULL, E_WARNING, "max(" ZEND_LONG_FMT ") is smaller than min(" ZEND_LONG_FMT ")", max, min);
297 RETURN_FALSE;
298 }
299
300 RETURN_LONG(php_mt_rand_common(min, max));
301 }
302 /* }}} */
303
304 /* {{{ proto int mt_getrandmax(void)
305 Returns the maximum value a random number from Mersenne Twister can have */
PHP_FUNCTION(mt_getrandmax)306 PHP_FUNCTION(mt_getrandmax)
307 {
308 if (zend_parse_parameters_none() == FAILURE) {
309 return;
310 }
311
312 /*
313 * Melo: it could be 2^^32 but we only use 2^^31 to maintain
314 * compatibility with the previous php_rand
315 */
316 RETURN_LONG(PHP_MT_RAND_MAX); /* 2^^31 */
317 }
318 /* }}} */
319
PHP_MINIT_FUNCTION(mt_rand)320 PHP_MINIT_FUNCTION(mt_rand)
321 {
322 REGISTER_LONG_CONSTANT("MT_RAND_MT19937", MT_RAND_MT19937, CONST_CS | CONST_PERSISTENT);
323 REGISTER_LONG_CONSTANT("MT_RAND_PHP", MT_RAND_PHP, CONST_CS | CONST_PERSISTENT);
324
325 return SUCCESS;
326 }
327
328 /*
329 * Local variables:
330 * tab-width: 4
331 * c-basic-offset: 4
332 * End:
333 * vim600: noet sw=4 ts=4 fdm=marker
334 * vim<600: noet sw=4 ts=4
335 */
336
