xref: /PHP-5.4/ext/standard/rand.c (revision 68283c9f)
1 /*
2    +----------------------------------------------------------------------+
3    | PHP Version 5                                                        |
4    +----------------------------------------------------------------------+
5    | Copyright (c) 1997-2014 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 <stdlib.h>
29 
30 #include "php.h"
31 #include "php_math.h"
32 #include "php_rand.h"
33 
34 #include "basic_functions.h"
35 
36 
37 /* SYSTEM RAND FUNCTIONS */
38 
39 /* {{{ php_srand
40  */
php_srand(long seed TSRMLS_DC)41 PHPAPI void php_srand(long seed TSRMLS_DC)
42 {
43 #ifdef ZTS
44 	BG(rand_seed) = (unsigned int) seed;
45 #else
46 # if defined(HAVE_SRANDOM)
47 	srandom((unsigned int) seed);
48 # elif defined(HAVE_SRAND48)
49 	srand48(seed);
50 # else
51 	srand((unsigned int) seed);
52 # endif
53 #endif
54 
55 	/* Seed only once */
56 	BG(rand_is_seeded) = 1;
57 }
58 /* }}} */
59 
60 /* {{{ php_rand
61  */
php_rand(TSRMLS_D)62 PHPAPI long php_rand(TSRMLS_D)
63 {
64 	long ret;
65 
66 	if (!BG(rand_is_seeded)) {
67 		php_srand(GENERATE_SEED() TSRMLS_CC);
68 	}
69 
70 #ifdef ZTS
71 	ret = php_rand_r(&BG(rand_seed));
72 #else
73 # if defined(HAVE_RANDOM)
74 	ret = random();
75 # elif defined(HAVE_LRAND48)
76 	ret = lrand48();
77 # else
78 	ret = rand();
79 # endif
80 #endif
81 
82 	return ret;
83 }
84 /* }}} */
85 
86 
87 /* MT RAND FUNCTIONS */
88 
89 /*
90 	The following php_mt_...() functions are based on a C++ class MTRand by
91 	Richard J. Wagner. For more information see the web page at
92 	http://www-personal.engin.umich.edu/~wagnerr/MersenneTwister.html
93 
94 	Mersenne Twister random number generator -- a C++ class MTRand
95 	Based on code by Makoto Matsumoto, Takuji Nishimura, and Shawn Cokus
96 	Richard J. Wagner  v1.0  15 May 2003  rjwagner@writeme.com
97 
98 	The Mersenne Twister is an algorithm for generating random numbers.  It
99 	was designed with consideration of the flaws in various other generators.
100 	The period, 2^19937-1, and the order of equidistribution, 623 dimensions,
101 	are far greater.  The generator is also fast; it avoids multiplication and
102 	division, and it benefits from caches and pipelines.  For more information
103 	see the inventors' web page at http://www.math.keio.ac.jp/~matumoto/emt.html
104 
105 	Reference
106 	M. Matsumoto and T. Nishimura, "Mersenne Twister: A 623-Dimensionally
107 	Equidistributed Uniform Pseudo-Random Number Generator", ACM Transactions on
108 	Modeling and Computer Simulation, Vol. 8, No. 1, January 1998, pp 3-30.
109 
110 	Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
111 	Copyright (C) 2000 - 2003, Richard J. Wagner
112 	All rights reserved.
113 
114 	Redistribution and use in source and binary forms, with or without
115 	modification, are permitted provided that the following conditions
116 	are met:
117 
118 	1. Redistributions of source code must retain the above copyright
119 	   notice, this list of conditions and the following disclaimer.
120 
121 	2. Redistributions in binary form must reproduce the above copyright
122 	   notice, this list of conditions and the following disclaimer in the
123 	   documentation and/or other materials provided with the distribution.
124 
125 	3. The names of its contributors may not be used to endorse or promote
126 	   products derived from this software without specific prior written
127 	   permission.
128 
129 	THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
130 	"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
131 	LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
132 	A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
133 	CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
134 	EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
135 	PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
136 	PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
137 	LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
138 	NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
139 	SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
140 */
141 
142 #define N             MT_N                 /* length of state vector */
143 #define M             (397)                /* a period parameter */
144 #define hiBit(u)      ((u) & 0x80000000U)  /* mask all but highest   bit of u */
145 #define loBit(u)      ((u) & 0x00000001U)  /* mask all but lowest    bit of u */
146 #define loBits(u)     ((u) & 0x7FFFFFFFU)  /* mask     the highest   bit of u */
147 #define mixBits(u, v) (hiBit(u)|loBits(v)) /* move hi bit of u to hi bit of v */
148 
149 #define twist(m,u,v)  (m ^ (mixBits(u,v)>>1) ^ ((php_uint32)(-(php_int32)(loBit(u))) & 0x9908b0dfU))
150 
151 /* {{{ php_mt_initialize
152  */
php_mt_initialize(php_uint32 seed,php_uint32 * state)153 static inline void php_mt_initialize(php_uint32 seed, php_uint32 *state)
154 {
155 	/* Initialize generator state with seed
156 	   See Knuth TAOCP Vol 2, 3rd Ed, p.106 for multiplier.
157 	   In previous versions, most significant bits (MSBs) of the seed affect
158 	   only MSBs of the state array.  Modified 9 Jan 2002 by Makoto Matsumoto. */
159 
160 	register php_uint32 *s = state;
161 	register php_uint32 *r = state;
162 	register int i = 1;
163 
164 	*s++ = seed & 0xffffffffU;
165 	for( ; i < N; ++i ) {
166 		*s++ = ( 1812433253U * ( *r ^ (*r >> 30) ) + i ) & 0xffffffffU;
167 		r++;
168 	}
169 }
170 /* }}} */
171 
172 /* {{{ php_mt_reload
173  */
php_mt_reload(TSRMLS_D)174 static inline void php_mt_reload(TSRMLS_D)
175 {
176 	/* Generate N new values in state
177 	   Made clearer and faster by Matthew Bellew (matthew.bellew@home.com) */
178 
179 	register php_uint32 *state = BG(state);
180 	register php_uint32 *p = state;
181 	register int i;
182 
183 	for (i = N - M; i--; ++p)
184 		*p = twist(p[M], p[0], p[1]);
185 	for (i = M; --i; ++p)
186 		*p = twist(p[M-N], p[0], p[1]);
187 	*p = twist(p[M-N], p[0], state[0]);
188 	BG(left) = N;
189 	BG(next) = state;
190 }
191 /* }}} */
192 
193 /* {{{ php_mt_srand
194  */
php_mt_srand(php_uint32 seed TSRMLS_DC)195 PHPAPI void php_mt_srand(php_uint32 seed TSRMLS_DC)
196 {
197 	/* Seed the generator with a simple uint32 */
198 	php_mt_initialize(seed, BG(state));
199 	php_mt_reload(TSRMLS_C);
200 
201 	/* Seed only once */
202 	BG(mt_rand_is_seeded) = 1;
203 }
204 /* }}} */
205 
206 /* {{{ php_mt_rand
207  */
php_mt_rand(TSRMLS_D)208 PHPAPI php_uint32 php_mt_rand(TSRMLS_D)
209 {
210 	/* Pull a 32-bit integer from the generator state
211 	   Every other access function simply transforms the numbers extracted here */
212 
213 	register php_uint32 s1;
214 
215 	if (BG(left) == 0) {
216 		php_mt_reload(TSRMLS_C);
217 	}
218 	--BG(left);
219 
220 	s1 = *BG(next)++;
221 	s1 ^= (s1 >> 11);
222 	s1 ^= (s1 <<  7) & 0x9d2c5680U;
223 	s1 ^= (s1 << 15) & 0xefc60000U;
224 	return ( s1 ^ (s1 >> 18) );
225 }
226 /* }}} */
227 
228 /* {{{ proto void srand([int seed])
229    Seeds random number generator */
PHP_FUNCTION(srand)230 PHP_FUNCTION(srand)
231 {
232 	long seed = 0;
233 
234 	if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "|l", &seed) == FAILURE)
235 		return;
236 
237 	if (ZEND_NUM_ARGS() == 0)
238 		seed = GENERATE_SEED();
239 
240 	php_srand(seed TSRMLS_CC);
241 }
242 /* }}} */
243 
244 /* {{{ proto void mt_srand([int seed])
245    Seeds Mersenne Twister random number generator */
PHP_FUNCTION(mt_srand)246 PHP_FUNCTION(mt_srand)
247 {
248 	long seed = 0;
249 
250 	if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "|l", &seed) == FAILURE)
251 		return;
252 
253 	if (ZEND_NUM_ARGS() == 0)
254 		seed = GENERATE_SEED();
255 
256 	php_mt_srand(seed TSRMLS_CC);
257 }
258 /* }}} */
259 
260 
261 /*
262  * A bit of tricky math here.  We want to avoid using a modulus because
263  * that simply tosses the high-order bits and might skew the distribution
264  * of random values over the range.  Instead we map the range directly.
265  *
266  * We need to map the range from 0...M evenly to the range a...b
267  * Let n = the random number and n' = the mapped random number
268  *
269  * Then we have: n' = a + n(b-a)/M
270  *
271  * We have a problem here in that only n==M will get mapped to b which
272  # means the chances of getting b is much much less than getting any of
273  # the other values in the range.  We can fix this by increasing our range
274  # artifically and using:
275  #
276  #               n' = a + n(b-a+1)/M
277  *
278  # Now we only have a problem if n==M which would cause us to produce a
279  # number of b+1 which would be bad.  So we bump M up by one to make sure
280  # this will never happen, and the final algorithm looks like this:
281  #
282  #               n' = a + n(b-a+1)/(M+1)
283  *
284  * -RL
285  */
286 
287 /* {{{ proto int rand([int min, int max])
288    Returns a random number */
PHP_FUNCTION(rand)289 PHP_FUNCTION(rand)
290 {
291 	long min;
292 	long max;
293 	long number;
294 	int  argc = ZEND_NUM_ARGS();
295 
296 	if (argc != 0 && zend_parse_parameters(argc TSRMLS_CC, "ll", &min, &max) == FAILURE)
297 		return;
298 
299 	number = php_rand(TSRMLS_C);
300 	if (argc == 2) {
301 		RAND_RANGE(number, min, max, PHP_RAND_MAX);
302 	}
303 
304 	RETURN_LONG(number);
305 }
306 /* }}} */
307 
308 /* {{{ proto int mt_rand([int min, int max])
309    Returns a random number from Mersenne Twister */
PHP_FUNCTION(mt_rand)310 PHP_FUNCTION(mt_rand)
311 {
312 	long min;
313 	long max;
314 	long number;
315 	int  argc = ZEND_NUM_ARGS();
316 
317 	if (argc != 0) {
318 		if (zend_parse_parameters(argc TSRMLS_CC, "ll", &min, &max) == FAILURE) {
319 			return;
320 		} else if (max < min) {
321 			php_error_docref(NULL TSRMLS_CC, E_WARNING, "max(%ld) is smaller than min(%ld)", max, min);
322 			RETURN_FALSE;
323 		}
324 	}
325 
326 	if (!BG(mt_rand_is_seeded)) {
327 		php_mt_srand(GENERATE_SEED() TSRMLS_CC);
328 	}
329 
330 	/*
331 	 * Melo: hmms.. randomMT() returns 32 random bits...
332 	 * Yet, the previous php_rand only returns 31 at most.
333 	 * So I put a right shift to loose the lsb. It *seems*
334 	 * better than clearing the msb.
335 	 * Update:
336 	 * I talked with Cokus via email and it won't ruin the algorithm
337 	 */
338 	number = (long) (php_mt_rand(TSRMLS_C) >> 1);
339 	if (argc == 2) {
340 		RAND_RANGE(number, min, max, PHP_MT_RAND_MAX);
341 	}
342 
343 	RETURN_LONG(number);
344 }
345 /* }}} */
346 
347 /* {{{ proto int getrandmax(void)
348    Returns the maximum value a random number can have */
PHP_FUNCTION(getrandmax)349 PHP_FUNCTION(getrandmax)
350 {
351 	if (zend_parse_parameters_none() == FAILURE) {
352 		return;
353 	}
354 
355 	RETURN_LONG(PHP_RAND_MAX);
356 }
357 /* }}} */
358 
359 /* {{{ proto int mt_getrandmax(void)
360    Returns the maximum value a random number from Mersenne Twister can have */
PHP_FUNCTION(mt_getrandmax)361 PHP_FUNCTION(mt_getrandmax)
362 {
363 	if (zend_parse_parameters_none() == FAILURE) {
364 		return;
365 	}
366 
367 	/*
368 	 * Melo: it could be 2^^32 but we only use 2^^31 to maintain
369 	 * compatibility with the previous php_rand
370 	 */
371   	RETURN_LONG(PHP_MT_RAND_MAX); /* 2^^31 */
372 }
373 /* }}} */
374 
375 /*
376  * Local variables:
377  * tab-width: 4
378  * c-basic-offset: 4
379  * End:
380  * vim600: noet sw=4 ts=4 fdm=marker
381  * vim<600: noet sw=4 ts=4
382  */
383