xref: /php-src/ext/standard/mt_rand.c (revision 6111d64c)
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
95  */
php_mt_initialize(uint32_t seed,uint32_t * state)96 static inline void php_mt_initialize(uint32_t seed, uint32_t *state)
97 {
98 	/* Initialize generator state with seed
99 	   See Knuth TAOCP Vol 2, 3rd Ed, p.106 for multiplier.
100 	   In previous versions, most significant bits (MSBs) of the seed affect
101 	   only MSBs of the state array.  Modified 9 Jan 2002 by Makoto Matsumoto. */
102 
103 	register uint32_t *s = state;
104 	register uint32_t *r = state;
105 	register int i = 1;
106 
107 	*s++ = seed & 0xffffffffU;
108 	for( ; i < N; ++i ) {
109 		*s++ = ( 1812433253U * ( *r ^ (*r >> 30) ) + i ) & 0xffffffffU;
110 		r++;
111 	}
112 }
113 /* }}} */
114 
115 /* {{{ php_mt_reload
116  */
php_mt_reload(void)117 static inline void php_mt_reload(void)
118 {
119 	/* Generate N new values in state
120 	   Made clearer and faster by Matthew Bellew (matthew.bellew@home.com) */
121 
122 	register uint32_t *state = BG(state);
123 	register uint32_t *p = state;
124 	register int i;
125 
126 	if (BG(mt_rand_mode) == MT_RAND_MT19937) {
127 		for (i = N - M; i--; ++p)
128 			*p = twist(p[M], p[0], p[1]);
129 		for (i = M; --i; ++p)
130 			*p = twist(p[M-N], p[0], p[1]);
131 		*p = twist(p[M-N], p[0], state[0]);
132 	}
133 	else {
134 		for (i = N - M; i--; ++p)
135 			*p = twist_php(p[M], p[0], p[1]);
136 		for (i = M; --i; ++p)
137 			*p = twist_php(p[M-N], p[0], p[1]);
138 		*p = twist_php(p[M-N], p[0], state[0]);
139 	}
140 	BG(left) = N;
141 	BG(next) = state;
142 }
143 /* }}} */
144 
145 /* {{{ php_mt_srand
146  */
php_mt_srand(uint32_t seed)147 PHPAPI void php_mt_srand(uint32_t seed)
148 {
149 	/* Seed the generator with a simple uint32 */
150 	php_mt_initialize(seed, BG(state));
151 	php_mt_reload();
152 
153 	/* Seed only once */
154 	BG(mt_rand_is_seeded) = 1;
155 }
156 /* }}} */
157 
158 /* {{{ php_mt_rand
159  */
php_mt_rand(void)160 PHPAPI uint32_t php_mt_rand(void)
161 {
162 	/* Pull a 32-bit integer from the generator state
163 	   Every other access function simply transforms the numbers extracted here */
164 
165 	register uint32_t s1;
166 
167 	if (UNEXPECTED(!BG(mt_rand_is_seeded))) {
168 		php_mt_srand(GENERATE_SEED());
169 	}
170 
171 	if (BG(left) == 0) {
172 		php_mt_reload();
173 	}
174 	--BG(left);
175 
176 	s1 = *BG(next)++;
177 	s1 ^= (s1 >> 11);
178 	s1 ^= (s1 <<  7) & 0x9d2c5680U;
179 	s1 ^= (s1 << 15) & 0xefc60000U;
180 	return ( s1 ^ (s1 >> 18) );
181 }
182 /* }}} */
183 
184 /* {{{ proto void mt_srand([int seed])
185    Seeds Mersenne Twister random number generator */
PHP_FUNCTION(mt_srand)186 PHP_FUNCTION(mt_srand)
187 {
188 	zend_long seed = 0;
189 	zend_long mode = MT_RAND_MT19937;
190 
191 	ZEND_PARSE_PARAMETERS_START(0, 2)
192 		Z_PARAM_OPTIONAL
193 		Z_PARAM_LONG(seed)
194 		Z_PARAM_LONG(mode)
195 	ZEND_PARSE_PARAMETERS_END();
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 
rand_range32(uint32_t umax)212 static uint32_t rand_range32(uint32_t umax) {
213 	uint32_t result, limit;
214 
215 	result = php_mt_rand();
216 
217 	/* Special case where no modulus is required */
218 	if (UNEXPECTED(umax == UINT32_MAX)) {
219 		return result;
220 	}
221 
222 	/* Increment the max so the range is inclusive of max */
223 	umax++;
224 
225 	/* Powers of two are not biased */
226 	if ((umax & (umax - 1)) == 0) {
227 		return result & (umax - 1);
228 	}
229 
230 	/* Ceiling under which UINT32_MAX % max == 0 */
231 	limit = UINT32_MAX - (UINT32_MAX % umax) - 1;
232 
233 	/* Discard numbers over the limit to avoid modulo bias */
234 	while (UNEXPECTED(result > limit)) {
235 		result = php_mt_rand();
236 	}
237 
238 	return result % umax;
239 }
240 
241 #if ZEND_ULONG_MAX > UINT32_MAX
rand_range64(uint64_t umax)242 static uint64_t rand_range64(uint64_t umax) {
243 	uint64_t result, limit;
244 
245 	result = php_mt_rand();
246 	result = (result << 32) | php_mt_rand();
247 
248 	/* Special case where no modulus is required */
249 	if (UNEXPECTED(umax == UINT64_MAX)) {
250 		return result;
251 	}
252 
253 	/* Increment the max so the range is inclusive of max */
254 	umax++;
255 
256 	/* Powers of two are not biased */
257 	if ((umax & (umax - 1)) == 0) {
258 		return result & (umax - 1);
259 	}
260 
261 	/* Ceiling under which UINT64_MAX % max == 0 */
262 	limit = UINT64_MAX - (UINT64_MAX % umax) - 1;
263 
264 	/* Discard numbers over the limit to avoid modulo bias */
265 	while (UNEXPECTED(result > limit)) {
266 		result = php_mt_rand();
267 		result = (result << 32) | php_mt_rand();
268 	}
269 
270 	return result % umax;
271 }
272 #endif
273 
274 /* {{{ php_mt_rand_range
275  */
php_mt_rand_range(zend_long min,zend_long max)276 PHPAPI zend_long php_mt_rand_range(zend_long min, zend_long max)
277 {
278 	zend_ulong umax = max - min;
279 
280 #if ZEND_ULONG_MAX > UINT32_MAX
281 	if (umax > UINT32_MAX) {
282 		return (zend_long) (rand_range64(umax) + min);
283 	}
284 #endif
285 
286 	return (zend_long) (rand_range32(umax) + min);
287 }
288 /* }}} */
289 
290 /* {{{ php_mt_rand_common
291  * rand() allows min > max, mt_rand does not */
php_mt_rand_common(zend_long min,zend_long max)292 PHPAPI zend_long php_mt_rand_common(zend_long min, zend_long max)
293 {
294 	int64_t n;
295 
296 	if (BG(mt_rand_mode) == MT_RAND_MT19937) {
297 		return php_mt_rand_range(min, max);
298 	}
299 
300 	/* Legacy mode deliberately not inside php_mt_rand_range()
301 	 * to prevent other functions being affected */
302 	n = (int64_t)php_mt_rand() >> 1;
303 	RAND_RANGE_BADSCALING(n, min, max, PHP_MT_RAND_MAX);
304 
305 	return n;
306 }
307 /* }}} */
308 
309 /* {{{ proto int mt_rand([int min, int max])
310    Returns a random number from Mersenne Twister */
PHP_FUNCTION(mt_rand)311 PHP_FUNCTION(mt_rand)
312 {
313 	zend_long min;
314 	zend_long max;
315 	int argc = ZEND_NUM_ARGS();
316 
317 	if (argc == 0) {
318 		// genrand_int31 in mt19937ar.c performs a right shift
319 		RETURN_LONG(php_mt_rand() >> 1);
320 	}
321 
322 	ZEND_PARSE_PARAMETERS_START(2, 2)
323 		Z_PARAM_LONG(min)
324 		Z_PARAM_LONG(max)
325 	ZEND_PARSE_PARAMETERS_END();
326 
327 	if (UNEXPECTED(max < min)) {
328 		zend_argument_value_error(2, "must be greater than or equal to argument #1 ($min)");
329 		RETURN_THROWS();
330 	}
331 
332 	RETURN_LONG(php_mt_rand_common(min, max));
333 }
334 /* }}} */
335 
336 /* {{{ proto int mt_getrandmax(void)
337    Returns the maximum value a random number from Mersenne Twister can have */
PHP_FUNCTION(mt_getrandmax)338 PHP_FUNCTION(mt_getrandmax)
339 {
340 	ZEND_PARSE_PARAMETERS_NONE();
341 
342 	/*
343 	 * Melo: it could be 2^^32 but we only use 2^^31 to maintain
344 	 * compatibility with the previous php_rand
345 	 */
346   	RETURN_LONG(PHP_MT_RAND_MAX); /* 2^^31 */
347 }
348 /* }}} */
349 
PHP_MINIT_FUNCTION(mt_rand)350 PHP_MINIT_FUNCTION(mt_rand)
351 {
352 	REGISTER_LONG_CONSTANT("MT_RAND_MT19937", MT_RAND_MT19937, CONST_CS | CONST_PERSISTENT);
353 	REGISTER_LONG_CONSTANT("MT_RAND_PHP",     MT_RAND_PHP, CONST_CS | CONST_PERSISTENT);
354 
355 	return SUCCESS;
356 }
357