Annotation of embedaddon/php/ext/standard/rand.c, revision 1.1
1.1 ! misho 1: /*
! 2: +----------------------------------------------------------------------+
! 3: | PHP Version 5 |
! 4: +----------------------------------------------------------------------+
! 5: | Copyright (c) 1997-2012 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: rand.c 321634 2012-01-01 13:15:04Z felipe $ */
! 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: */
! 42: PHPAPI 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: */
! 63: PHPAPI 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: */
! 154: static 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: */
! 175: static 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: */
! 196: PHPAPI 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: */
! 209: PHPAPI 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 */
! 231: PHP_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 */
! 247: PHP_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 */
! 290: PHP_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 */
! 311: PHP_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 */
! 350: PHP_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 */
! 362: PHP_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: */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>