1 : /*
2 : +----------------------------------------------------------------------+
3 : | PHP Version 5 |
4 : +----------------------------------------------------------------------+
5 : | Copyright (c) 1997-2009 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 272374 2008-12-31 11:17:49Z sebastian $ */
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 105 : {
44 : #ifdef ZTS
45 : BG(rand_seed) = (unsigned int) seed;
46 : #else
47 : # if defined(HAVE_SRANDOM)
48 105 : 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 105 : BG(rand_is_seeded) = 1;
58 105 : }
59 : /* }}} */
60 :
61 : /* {{{ php_rand
62 : */
63 : PHPAPI long php_rand(TSRMLS_D)
64 609775 : {
65 : long ret;
66 :
67 609775 : if (!BG(rand_is_seeded)) {
68 76 : 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 609775 : ret = random();
76 : # elif defined(HAVE_LRAND48)
77 : ret = lrand48();
78 : # else
79 : ret = rand();
80 : # endif
81 : #endif
82 :
83 609775 : 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 33 : {
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 33 : register php_uint32 *s = state;
162 33 : register php_uint32 *r = state;
163 33 : register int i = 1;
164 :
165 33 : *s++ = seed & 0xffffffffU;
166 20592 : for( ; i < N; ++i ) {
167 20559 : *s++ = ( 1812433253U * ( *r ^ (*r >> 30) ) + i ) & 0xffffffffU;
168 20559 : r++;
169 : }
170 33 : }
171 : /* }}} */
172 :
173 : /* {{{ php_mt_reload
174 : */
175 : static inline void php_mt_reload(TSRMLS_D)
176 35 : {
177 : /* Generate N new values in state
178 : Made clearer and faster by Matthew Bellew (matthew.bellew@home.com) */
179 :
180 35 : register php_uint32 *state = BG(state);
181 35 : register php_uint32 *p = state;
182 : register int i;
183 :
184 7980 : for (i = N - M; i--; ++p)
185 7945 : *p = twist(p[M], p[0], p[1]);
186 13895 : for (i = M; --i; ++p)
187 13860 : *p = twist(p[M-N], p[0], p[1]);
188 35 : *p = twist(p[M-N], p[0], state[0]);
189 35 : BG(left) = N;
190 35 : BG(next) = state;
191 35 : }
192 : /* }}} */
193 :
194 : /* {{{ php_mt_srand
195 : */
196 : PHPAPI void php_mt_srand(php_uint32 seed TSRMLS_DC)
197 33 : {
198 : /* Seed the generator with a simple uint32 */
199 33 : php_mt_initialize(seed, BG(state));
200 33 : php_mt_reload(TSRMLS_C);
201 :
202 : /* Seed only once */
203 33 : BG(mt_rand_is_seeded) = 1;
204 33 : }
205 : /* }}} */
206 :
207 : /* {{{ php_mt_rand
208 : */
209 : PHPAPI php_uint32 php_mt_rand(TSRMLS_D)
210 1339 : {
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 1339 : if (BG(left) == 0) {
217 2 : php_mt_reload(TSRMLS_C);
218 : }
219 1339 : --BG(left);
220 :
221 1339 : s1 = *BG(next)++;
222 1339 : s1 ^= (s1 >> 11);
223 1339 : s1 ^= (s1 << 7) & 0x9d2c5680U;
224 1339 : s1 ^= (s1 << 15) & 0xefc60000U;
225 1339 : return ( s1 ^ (s1 >> 18) );
226 : }
227 : /* }}} */
228 :
229 : /* {{{ proto void srand([int seed])
230 : Seeds random number generator */
231 : PHP_FUNCTION(srand)
232 40 : {
233 : long seed;
234 :
235 40 : if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "|l", &seed) == FAILURE)
236 11 : return;
237 :
238 29 : if (ZEND_NUM_ARGS() == 0)
239 2 : seed = GENERATE_SEED();
240 :
241 29 : 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 40 : {
249 : long seed;
250 :
251 40 : if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "|l", &seed) == FAILURE)
252 11 : return;
253 :
254 29 : if (ZEND_NUM_ARGS() == 0)
255 2 : seed = GENERATE_SEED();
256 :
257 29 : 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 64490 : {
292 : long min;
293 : long max;
294 : long number;
295 64490 : int argc = ZEND_NUM_ARGS();
296 :
297 64490 : if (argc != 0 && zend_parse_parameters(argc TSRMLS_CC, "ll", &min, &max) == FAILURE)
298 21 : return;
299 :
300 64469 : number = php_rand(TSRMLS_C);
301 64469 : if (argc == 2) {
302 51567 : RAND_RANGE(number, min, max, PHP_RAND_MAX);
303 : }
304 :
305 64469 : 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 1360 : {
313 : long min;
314 : long max;
315 : long number;
316 1360 : int argc = ZEND_NUM_ARGS();
317 :
318 1360 : if (argc != 0 && zend_parse_parameters(argc TSRMLS_CC, "ll", &min, &max) == FAILURE)
319 21 : return;
320 :
321 1339 : if (!BG(mt_rand_is_seeded)) {
322 4 : php_mt_srand(GENERATE_SEED() TSRMLS_CC);
323 : }
324 :
325 : /*
326 : * Melo: hmms.. randomMT() returns 32 random bits...
327 : * Yet, the previous php_rand only returns 31 at most.
328 : * So I put a right shift to loose the lsb. It *seems*
329 : * better than clearing the msb.
330 : * Update:
331 : * I talked with Cokus via email and it won't ruin the algorithm
332 : */
333 1339 : number = (long) (php_mt_rand(TSRMLS_C) >> 1);
334 1339 : if (argc == 2) {
335 1238 : RAND_RANGE(number, min, max, PHP_MT_RAND_MAX);
336 : }
337 :
338 1339 : RETURN_LONG(number);
339 : }
340 : /* }}} */
341 :
342 : /* {{{ proto int getrandmax(void)
343 : Returns the maximum value a random number can have */
344 : PHP_FUNCTION(getrandmax)
345 6 : {
346 6 : if (ZEND_NUM_ARGS() != 0) {
347 2 : WRONG_PARAM_COUNT;
348 : }
349 :
350 4 : RETURN_LONG(PHP_RAND_MAX);
351 : }
352 : /* }}} */
353 :
354 : /* {{{ proto int mt_getrandmax(void)
355 : Returns the maximum value a random number from Mersenne Twister can have */
356 : PHP_FUNCTION(mt_getrandmax)
357 5 : {
358 5 : if (ZEND_NUM_ARGS() != 0) {
359 2 : WRONG_PARAM_COUNT;
360 : }
361 :
362 : /*
363 : * Melo: it could be 2^^32 but we only use 2^^31 to maintain
364 : * compatibility with the previous php_rand
365 : */
366 3 : RETURN_LONG(PHP_MT_RAND_MAX); /* 2^^31 */
367 : }
368 : /* }}} */
369 :
370 : /*
371 : * Local variables:
372 : * tab-width: 4
373 : * c-basic-offset: 4
374 : * End:
375 : * vim600: noet sw=4 ts=4 fdm=marker
376 : * vim<600: noet sw=4 ts=4
377 : */
|
