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#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