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