1 : /*
2 : +----------------------------------------------------------------------+
3 : | PHP Version 5 |
4 : +----------------------------------------------------------------------+
5 : | Copyright (c) 1997-2007 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,v 1.70.2.1.2.2 2007/01/01 09:36:08 sebastian Exp $ */
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 2 : {
44 : #ifdef ZTS
45 : BG(rand_seed) = (unsigned int) seed;
46 : #else
47 : # if defined(HAVE_SRANDOM)
48 2 : 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 2 : BG(rand_is_seeded) = 1;
58 2 : }
59 : /* }}} */
60 :
61 : /* {{{ php_rand
62 : */
63 : PHPAPI long php_rand(TSRMLS_D)
64 5032 : {
65 : long ret;
66 :
67 5032 : if (!BG(rand_is_seeded)) {
68 1 : 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 5032 : ret = random();
76 : # elif defined(HAVE_LRAND48)
77 : ret = lrand48();
78 : # else
79 : ret = rand();
80 : # endif
81 : #endif
82 :
83 5032 : 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 : The original code included the following notice:
143 :
144 : When you use this, send an email to: matumoto@math.keio.ac.jp
145 : with an appropriate reference to your work.
146 :
147 : It would be nice to CC: rjwagner@writeme.com and Cokus@math.washington.edu
148 : when you write.
149 : */
150 :
151 : #define N MT_N /* length of state vector */
152 : #define M (397) /* a period parameter */
153 : #define hiBit(u) ((u) & 0x80000000U) /* mask all but highest bit of u */
154 : #define loBit(u) ((u) & 0x00000001U) /* mask all but lowest bit of u */
155 : #define loBits(u) ((u) & 0x7FFFFFFFU) /* mask the highest bit of u */
156 : #define mixBits(u, v) (hiBit(u)|loBits(v)) /* move hi bit of u to hi bit of v */
157 :
158 : #define twist(m,u,v) (m ^ (mixBits(u,v)>>1) ^ ((php_uint32)(-(php_int32)(loBit(u))) & 0x9908b0dfU))
159 :
160 : /* {{{ php_mt_initialize
161 : */
162 : static inline void php_mt_initialize(php_uint32 seed, php_uint32 *state)
163 0 : {
164 : /* Initialize generator state with seed
165 : See Knuth TAOCP Vol 2, 3rd Ed, p.106 for multiplier.
166 : In previous versions, most significant bits (MSBs) of the seed affect
167 : only MSBs of the state array. Modified 9 Jan 2002 by Makoto Matsumoto. */
168 :
169 0 : register php_uint32 *s = state;
170 0 : register php_uint32 *r = state;
171 0 : register int i = 1;
172 :
173 0 : *s++ = seed & 0xffffffffU;
174 0 : for( ; i < N; ++i ) {
175 0 : *s++ = ( 1812433253U * ( *r ^ (*r >> 30) ) + i ) & 0xffffffffU;
176 0 : r++;
177 : }
178 0 : }
179 : /* }}} */
180 :
181 : /* {{{ php_mt_reload
182 : */
183 : static inline void php_mt_reload(TSRMLS_D)
184 0 : {
185 : /* Generate N new values in state
186 : Made clearer and faster by Matthew Bellew (matthew.bellew@home.com) */
187 :
188 0 : register php_uint32 *state = BG(state);
189 0 : register php_uint32 *p = state;
190 : register int i;
191 :
192 0 : for (i = N - M; i--; ++p)
193 0 : *p = twist(p[M], p[0], p[1]);
194 0 : for (i = M; --i; ++p)
195 0 : *p = twist(p[M-N], p[0], p[1]);
196 0 : *p = twist(p[M-N], p[0], state[0]);
197 0 : BG(left) = N;
198 0 : BG(next) = state;
199 0 : }
200 : /* }}} */
201 :
202 : /* {{{ php_mt_srand
203 : */
204 : PHPAPI void php_mt_srand(php_uint32 seed TSRMLS_DC)
205 0 : {
206 : /* Seed the generator with a simple uint32 */
207 0 : php_mt_initialize(seed, BG(state));
208 0 : php_mt_reload(TSRMLS_C);
209 :
210 : /* Seed only once */
211 0 : BG(mt_rand_is_seeded) = 1;
212 0 : }
213 : /* }}} */
214 :
215 : /* {{{ php_mt_rand
216 : */
217 : PHPAPI php_uint32 php_mt_rand(TSRMLS_D)
218 0 : {
219 : /* Pull a 32-bit integer from the generator state
220 : Every other access function simply transforms the numbers extracted here */
221 :
222 : register php_uint32 s1;
223 :
224 0 : if (BG(left) == 0) {
225 0 : php_mt_reload(TSRMLS_C);
226 : }
227 0 : --BG(left);
228 :
229 0 : s1 = *BG(next)++;
230 0 : s1 ^= (s1 >> 11);
231 0 : s1 ^= (s1 << 7) & 0x9d2c5680U;
232 0 : s1 ^= (s1 << 15) & 0xefc60000U;
233 0 : return ( s1 ^ (s1 >> 18) );
234 : }
235 : /* }}} */
236 :
237 : /* {{{ proto void srand([int seed])
238 : Seeds random number generator */
239 : PHP_FUNCTION(srand)
240 1 : {
241 : long seed;
242 :
243 1 : if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "|l", &seed) == FAILURE)
244 0 : return;
245 :
246 1 : if (ZEND_NUM_ARGS() == 0)
247 0 : seed = GENERATE_SEED();
248 :
249 1 : php_srand(seed TSRMLS_CC);
250 : }
251 : /* }}} */
252 :
253 : /* {{{ proto void mt_srand([int seed])
254 : Seeds Mersenne Twister random number generator */
255 : PHP_FUNCTION(mt_srand)
256 0 : {
257 : long seed;
258 :
259 0 : if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "|l", &seed) == FAILURE)
260 0 : return;
261 :
262 0 : if (ZEND_NUM_ARGS() == 0)
263 0 : seed = GENERATE_SEED();
264 :
265 0 : php_mt_srand(seed TSRMLS_CC);
266 : }
267 : /* }}} */
268 :
269 :
270 : /*
271 : * A bit of tricky math here. We want to avoid using a modulus because
272 : * that simply tosses the high-order bits and might skew the distribution
273 : * of random values over the range. Instead we map the range directly.
274 : *
275 : * We need to map the range from 0...M evenly to the range a...b
276 : * Let n = the random number and n' = the mapped random number
277 : *
278 : * Then we have: n' = a + n(b-a)/M
279 : *
280 : * We have a problem here in that only n==M will get mapped to b which
281 : # means the chances of getting b is much much less than getting any of
282 : # the other values in the range. We can fix this by increasing our range
283 : # artifically and using:
284 : #
285 : # n' = a + n(b-a+1)/M
286 : *
287 : # Now we only have a problem if n==M which would cause us to produce a
288 : # number of b+1 which would be bad. So we bump M up by one to make sure
289 : # this will never happen, and the final algorithm looks like this:
290 : #
291 : # n' = a + n(b-a+1)/(M+1)
292 : *
293 : * -RL
294 : */
295 :
296 : /* {{{ proto int rand([int min, int max])
297 : Returns a random number */
298 : PHP_FUNCTION(rand)
299 5032 : {
300 : long min;
301 : long max;
302 : long number;
303 5032 : int argc = ZEND_NUM_ARGS();
304 :
305 5032 : if (argc != 0 && zend_parse_parameters(argc TSRMLS_CC, "ll", &min, &max) == FAILURE)
306 0 : return;
307 :
308 5032 : number = php_rand(TSRMLS_C);
309 5032 : if (argc == 2) {
310 5032 : RAND_RANGE(number, min, max, PHP_RAND_MAX);
311 : }
312 :
313 5032 : RETURN_LONG(number);
314 : }
315 : /* }}} */
316 :
317 : /* {{{ proto int mt_rand([int min, int max])
318 : Returns a random number from Mersenne Twister */
319 : PHP_FUNCTION(mt_rand)
320 0 : {
321 : long min;
322 : long max;
323 : long number;
324 0 : int argc = ZEND_NUM_ARGS();
325 :
326 0 : if (argc != 0 && zend_parse_parameters(argc TSRMLS_CC, "ll", &min, &max) == FAILURE)
327 0 : return;
328 :
329 0 : if (!BG(mt_rand_is_seeded)) {
330 0 : php_mt_srand(GENERATE_SEED() TSRMLS_CC);
331 : }
332 :
333 : /*
334 : * Melo: hmms.. randomMT() returns 32 random bits...
335 : * Yet, the previous php_rand only returns 31 at most.
336 : * So I put a right shift to loose the lsb. It *seems*
337 : * better than clearing the msb.
338 : * Update:
339 : * I talked with Cokus via email and it won't ruin the algorithm
340 : */
341 0 : number = (long) (php_mt_rand(TSRMLS_C) >> 1);
342 0 : if (argc == 2) {
343 0 : RAND_RANGE(number, min, max, PHP_MT_RAND_MAX);
344 : }
345 :
346 0 : RETURN_LONG(number);
347 : }
348 : /* }}} */
349 :
350 : /* {{{ proto int getrandmax(void)
351 : Returns the maximum value a random number can have */
352 : PHP_FUNCTION(getrandmax)
353 0 : {
354 0 : if (ZEND_NUM_ARGS() != 0) {
355 0 : WRONG_PARAM_COUNT;
356 : }
357 :
358 0 : RETURN_LONG(PHP_RAND_MAX);
359 : }
360 : /* }}} */
361 :
362 : /* {{{ proto int mt_getrandmax(void)
363 : Returns the maximum value a random number from Mersenne Twister can have */
364 : PHP_FUNCTION(mt_getrandmax)
365 0 : {
366 0 : if (ZEND_NUM_ARGS() != 0) {
367 0 : WRONG_PARAM_COUNT;
368 : }
369 :
370 : /*
371 : * Melo: it could be 2^^32 but we only use 2^^31 to maintain
372 : * compatibility with the previous php_rand
373 : */
374 0 : RETURN_LONG(PHP_MT_RAND_MAX); /* 2^^31 */
375 : }
376 : /* }}} */
377 :
378 : /*
379 : * Local variables:
380 : * tab-width: 4
381 : * c-basic-offset: 4
382 : * End:
383 : * vim600: noet sw=4 ts=4 fdm=marker
384 : * vim<600: noet sw=4 ts=4
385 : */
|
