Annotation of embedaddon/php/ext/standard/rand.c, revision 1.1.1.1
1.1 misho 1: /*
2: +----------------------------------------------------------------------+
3: | PHP Version 5 |
4: +----------------------------------------------------------------------+
5: | Copyright (c) 1997-2012 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 321634 2012-01-01 13:15:04Z felipe $ */
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: {
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: */
63: PHPAPI 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: */
154: static 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: */
175: static 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: */
196: PHPAPI 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: */
209: PHPAPI 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 */
231: PHP_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 */
247: PHP_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 */
290: PHP_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 */
311: PHP_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 */
350: PHP_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 */
362: PHP_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: */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>