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 */
41PHPAPI 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 */
62PHPAPI 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 */
153static 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 */
174static 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 */
195PHPAPI 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 */
208PHPAPI 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 */
230PHP_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 */
246PHP_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 */
289PHP_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 */
310PHP_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 */
349PHP_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 */
361PHP_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