xref: /PHP-7.4/ext/standard/mt_rand.c (revision 92ac598a)
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