Back to index

php5  5.3.10
rand.c
Go to the documentation of this file.
00001 /*
00002    +----------------------------------------------------------------------+
00003    | PHP Version 5                                                        |
00004    +----------------------------------------------------------------------+
00005    | Copyright (c) 1997-2012 The PHP Group                                |
00006    +----------------------------------------------------------------------+
00007    | This source file is subject to version 3.01 of the PHP license,      |
00008    | that is bundled with this package in the file LICENSE, and is        |
00009    | available through the world-wide-web at the following url:           |
00010    | http://www.php.net/license/3_01.txt                                  |
00011    | If you did not receive a copy of the PHP license and are unable to   |
00012    | obtain it through the world-wide-web, please send a note to          |
00013    | license@php.net so we can mail you a copy immediately.               |
00014    +----------------------------------------------------------------------+
00015    | Authors: Rasmus Lerdorf <rasmus@php.net>                             |
00016    |          Zeev Suraski <zeev@zend.com>                                |
00017    |          Pedro Melo <melo@ip.pt>                                     |
00018    |          Sterling Hughes <sterling@php.net>                          |
00019    |                                                                      |
00020    | Based on code from: Richard J. Wagner <rjwagner@writeme.com>         |
00021    |                     Makoto Matsumoto <matumoto@math.keio.ac.jp>      |
00022    |                     Takuji Nishimura                                 |
00023    |                     Shawn Cokus <Cokus@math.washington.edu>          |
00024    +----------------------------------------------------------------------+
00025  */
00026 /* $Id: rand.c 321634 2012-01-01 13:15:04Z felipe $ */
00027 
00028 #include <stdlib.h>
00029 
00030 #include "php.h"
00031 #include "php_math.h"
00032 #include "php_rand.h"
00033 #include "php_lcg.h"
00034 
00035 #include "basic_functions.h"
00036 
00037 
00038 /* SYSTEM RAND FUNCTIONS */
00039 
00040 /* {{{ php_srand
00041  */
00042 PHPAPI void php_srand(long seed TSRMLS_DC)
00043 {
00044 #ifdef ZTS
00045        BG(rand_seed) = (unsigned int) seed;
00046 #else
00047 # if defined(HAVE_SRANDOM)
00048        srandom((unsigned int) seed);
00049 # elif defined(HAVE_SRAND48)
00050        srand48(seed);
00051 # else
00052        srand((unsigned int) seed);
00053 # endif
00054 #endif
00055 
00056        /* Seed only once */
00057        BG(rand_is_seeded) = 1;
00058 }
00059 /* }}} */
00060 
00061 /* {{{ php_rand
00062  */
00063 PHPAPI long php_rand(TSRMLS_D)
00064 {
00065        long ret;
00066 
00067        if (!BG(rand_is_seeded)) {
00068               php_srand(GENERATE_SEED() TSRMLS_CC);
00069        }
00070 
00071 #ifdef ZTS
00072        ret = php_rand_r(&BG(rand_seed));
00073 #else
00074 # if defined(HAVE_RANDOM)
00075        ret = random();
00076 # elif defined(HAVE_LRAND48)
00077        ret = lrand48();
00078 # else
00079        ret = rand();
00080 # endif
00081 #endif
00082 
00083        return ret;
00084 }
00085 /* }}} */
00086 
00087 
00088 /* MT RAND FUNCTIONS */
00089 
00090 /*
00091        The following php_mt_...() functions are based on a C++ class MTRand by
00092        Richard J. Wagner. For more information see the web page at
00093        http://www-personal.engin.umich.edu/~wagnerr/MersenneTwister.html
00094 
00095        Mersenne Twister random number generator -- a C++ class MTRand
00096        Based on code by Makoto Matsumoto, Takuji Nishimura, and Shawn Cokus
00097        Richard J. Wagner  v1.0  15 May 2003  rjwagner@writeme.com
00098 
00099        The Mersenne Twister is an algorithm for generating random numbers.  It
00100        was designed with consideration of the flaws in various other generators.
00101        The period, 2^19937-1, and the order of equidistribution, 623 dimensions,
00102        are far greater.  The generator is also fast; it avoids multiplication and
00103        division, and it benefits from caches and pipelines.  For more information
00104        see the inventors' web page at http://www.math.keio.ac.jp/~matumoto/emt.html
00105 
00106        Reference
00107        M. Matsumoto and T. Nishimura, "Mersenne Twister: A 623-Dimensionally
00108        Equidistributed Uniform Pseudo-Random Number Generator", ACM Transactions on
00109        Modeling and Computer Simulation, Vol. 8, No. 1, January 1998, pp 3-30.
00110 
00111        Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
00112        Copyright (C) 2000 - 2003, Richard J. Wagner
00113        All rights reserved.                          
00114 
00115        Redistribution and use in source and binary forms, with or without
00116        modification, are permitted provided that the following conditions
00117        are met:
00118 
00119        1. Redistributions of source code must retain the above copyright
00120           notice, this list of conditions and the following disclaimer.
00121 
00122        2. Redistributions in binary form must reproduce the above copyright
00123           notice, this list of conditions and the following disclaimer in the
00124           documentation and/or other materials provided with the distribution.
00125 
00126        3. The names of its contributors may not be used to endorse or promote 
00127           products derived from this software without specific prior written 
00128           permission.
00129 
00130        THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
00131        "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
00132        LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
00133        A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
00134        CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00135        EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00136        PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00137        PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00138        LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00139        NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00140        SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00141 */
00142 
00143 #define N             MT_N                 /* length of state vector */
00144 #define M             (397)                /* a period parameter */
00145 #define hiBit(u)      ((u) & 0x80000000U)  /* mask all but highest   bit of u */
00146 #define loBit(u)      ((u) & 0x00000001U)  /* mask all but lowest    bit of u */
00147 #define loBits(u)     ((u) & 0x7FFFFFFFU)  /* mask     the highest   bit of u */
00148 #define mixBits(u, v) (hiBit(u)|loBits(v)) /* move hi bit of u to hi bit of v */
00149 
00150 #define twist(m,u,v)  (m ^ (mixBits(u,v)>>1) ^ ((php_uint32)(-(php_int32)(loBit(u))) & 0x9908b0dfU))
00151 
00152 /* {{{ php_mt_initialize
00153  */
00154 static inline void php_mt_initialize(php_uint32 seed, php_uint32 *state)
00155 {
00156        /* Initialize generator state with seed
00157           See Knuth TAOCP Vol 2, 3rd Ed, p.106 for multiplier.
00158           In previous versions, most significant bits (MSBs) of the seed affect
00159           only MSBs of the state array.  Modified 9 Jan 2002 by Makoto Matsumoto. */
00160 
00161        register php_uint32 *s = state;
00162        register php_uint32 *r = state;
00163        register int i = 1;
00164 
00165        *s++ = seed & 0xffffffffU;
00166        for( ; i < N; ++i ) {
00167               *s++ = ( 1812433253U * ( *r ^ (*r >> 30) ) + i ) & 0xffffffffU;
00168               r++;
00169        }
00170 }
00171 /* }}} */
00172 
00173 /* {{{ php_mt_reload
00174  */
00175 static inline void php_mt_reload(TSRMLS_D)
00176 {
00177        /* Generate N new values in state
00178           Made clearer and faster by Matthew Bellew (matthew.bellew@home.com) */
00179 
00180        register php_uint32 *state = BG(state);
00181        register php_uint32 *p = state;
00182        register int i;
00183 
00184        for (i = N - M; i--; ++p)
00185               *p = twist(p[M], p[0], p[1]);
00186        for (i = M; --i; ++p)
00187               *p = twist(p[M-N], p[0], p[1]);
00188        *p = twist(p[M-N], p[0], state[0]);
00189        BG(left) = N;
00190        BG(next) = state;
00191 }
00192 /* }}} */
00193 
00194 /* {{{ php_mt_srand
00195  */
00196 PHPAPI void php_mt_srand(php_uint32 seed TSRMLS_DC)
00197 {
00198        /* Seed the generator with a simple uint32 */
00199        php_mt_initialize(seed, BG(state));
00200        php_mt_reload(TSRMLS_C);
00201 
00202        /* Seed only once */
00203        BG(mt_rand_is_seeded) = 1;
00204 }
00205 /* }}} */
00206 
00207 /* {{{ php_mt_rand
00208  */
00209 PHPAPI php_uint32 php_mt_rand(TSRMLS_D)
00210 {
00211        /* Pull a 32-bit integer from the generator state
00212           Every other access function simply transforms the numbers extracted here */
00213        
00214        register php_uint32 s1;
00215 
00216        if (BG(left) == 0) {
00217               php_mt_reload(TSRMLS_C);
00218        }
00219        --BG(left);
00220               
00221        s1 = *BG(next)++;
00222        s1 ^= (s1 >> 11);
00223        s1 ^= (s1 <<  7) & 0x9d2c5680U;
00224        s1 ^= (s1 << 15) & 0xefc60000U;
00225        return ( s1 ^ (s1 >> 18) );
00226 }
00227 /* }}} */
00228 
00229 /* {{{ proto void srand([int seed])
00230    Seeds random number generator */
00231 PHP_FUNCTION(srand)
00232 {
00233        long seed = 0;
00234 
00235        if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "|l", &seed) == FAILURE)
00236               return;
00237 
00238        if (ZEND_NUM_ARGS() == 0)
00239               seed = GENERATE_SEED();
00240 
00241        php_srand(seed TSRMLS_CC);
00242 }
00243 /* }}} */
00244 
00245 /* {{{ proto void mt_srand([int seed])
00246    Seeds Mersenne Twister random number generator */
00247 PHP_FUNCTION(mt_srand)
00248 {
00249        long seed = 0;
00250 
00251        if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "|l", &seed) == FAILURE) 
00252               return;
00253 
00254        if (ZEND_NUM_ARGS() == 0)
00255               seed = GENERATE_SEED();
00256 
00257        php_mt_srand(seed TSRMLS_CC);
00258 }
00259 /* }}} */
00260 
00261 
00262 /*
00263  * A bit of tricky math here.  We want to avoid using a modulus because
00264  * that simply tosses the high-order bits and might skew the distribution
00265  * of random values over the range.  Instead we map the range directly.
00266  *
00267  * We need to map the range from 0...M evenly to the range a...b
00268  * Let n = the random number and n' = the mapped random number
00269  *
00270  * Then we have: n' = a + n(b-a)/M
00271  *
00272  * We have a problem here in that only n==M will get mapped to b which
00273  # means the chances of getting b is much much less than getting any of
00274  # the other values in the range.  We can fix this by increasing our range
00275  # artifically and using:
00276  #
00277  #               n' = a + n(b-a+1)/M
00278  *
00279  # Now we only have a problem if n==M which would cause us to produce a
00280  # number of b+1 which would be bad.  So we bump M up by one to make sure
00281  # this will never happen, and the final algorithm looks like this:
00282  #
00283  #               n' = a + n(b-a+1)/(M+1) 
00284  *
00285  * -RL
00286  */    
00287 
00288 /* {{{ proto int rand([int min, int max])
00289    Returns a random number */
00290 PHP_FUNCTION(rand)
00291 {
00292        long min;
00293        long max;
00294        long number;
00295        int  argc = ZEND_NUM_ARGS();
00296 
00297        if (argc != 0 && zend_parse_parameters(argc TSRMLS_CC, "ll", &min, &max) == FAILURE)
00298               return;
00299 
00300        number = php_rand(TSRMLS_C);
00301        if (argc == 2) {
00302               RAND_RANGE(number, min, max, PHP_RAND_MAX);
00303        }
00304 
00305        RETURN_LONG(number);
00306 }
00307 /* }}} */
00308 
00309 /* {{{ proto int mt_rand([int min, int max])
00310    Returns a random number from Mersenne Twister */
00311 PHP_FUNCTION(mt_rand)
00312 {
00313        long min;
00314        long max;
00315        long number;
00316        int  argc = ZEND_NUM_ARGS();
00317 
00318        if (argc != 0) {
00319               if (zend_parse_parameters(argc TSRMLS_CC, "ll", &min, &max) == FAILURE) {
00320                      return;
00321               } else if (max < min) {
00322                      php_error_docref(NULL TSRMLS_CC, E_WARNING, "max(%ld) is smaller than min(%ld)", max, min);
00323                      RETURN_FALSE;
00324               }
00325        }
00326 
00327        if (!BG(mt_rand_is_seeded)) {
00328               php_mt_srand(GENERATE_SEED() TSRMLS_CC);
00329        }
00330 
00331        /*
00332         * Melo: hmms.. randomMT() returns 32 random bits...
00333         * Yet, the previous php_rand only returns 31 at most.
00334         * So I put a right shift to loose the lsb. It *seems*
00335         * better than clearing the msb. 
00336         * Update: 
00337         * I talked with Cokus via email and it won't ruin the algorithm
00338         */
00339        number = (long) (php_mt_rand(TSRMLS_C) >> 1);
00340        if (argc == 2) {
00341               RAND_RANGE(number, min, max, PHP_MT_RAND_MAX);
00342        }
00343 
00344        RETURN_LONG(number);
00345 }
00346 /* }}} */
00347 
00348 /* {{{ proto int getrandmax(void)
00349    Returns the maximum value a random number can have */
00350 PHP_FUNCTION(getrandmax)
00351 {
00352        if (zend_parse_parameters_none() == FAILURE) {
00353               return;
00354        }
00355 
00356        RETURN_LONG(PHP_RAND_MAX);
00357 }
00358 /* }}} */
00359 
00360 /* {{{ proto int mt_getrandmax(void)
00361    Returns the maximum value a random number from Mersenne Twister can have */
00362 PHP_FUNCTION(mt_getrandmax)
00363 {
00364        if (zend_parse_parameters_none() == FAILURE) {
00365               return;
00366        }
00367 
00368        /*
00369         * Melo: it could be 2^^32 but we only use 2^^31 to maintain
00370         * compatibility with the previous php_rand
00371         */
00372        RETURN_LONG(PHP_MT_RAND_MAX); /* 2^^31 */
00373 }
00374 /* }}} */
00375 
00376 /*
00377  * Local variables:
00378  * tab-width: 4
00379  * c-basic-offset: 4
00380  * End:
00381  * vim600: noet sw=4 ts=4 fdm=marker
00382  * vim<600: noet sw=4 ts=4
00383  */