1 /*
2 +----------------------------------------------------------------------+
3 | Copyright (c) The PHP Group |
4 +----------------------------------------------------------------------+
5 | This source file is subject to version 3.01 of the PHP license, |
6 | that is bundled with this package in the file LICENSE, and is |
7 | available through the world-wide-web at the following url: |
8 | https://www.php.net/license/3_01.txt |
9 | If you did not receive a copy of the PHP license and are unable to |
10 | obtain it through the world-wide-web, please send a note to |
11 | license@php.net so we can mail you a copy immediately. |
12 +----------------------------------------------------------------------+
13 | Authors: Rasmus Lerdorf <rasmus@php.net> |
14 | Zeev Suraski <zeev@php.net> |
15 | Pedro Melo <melo@ip.pt> |
16 | Sterling Hughes <sterling@php.net> |
17 | |
18 | Based on code from: Richard J. Wagner <rjwagner@writeme.com> |
19 | Makoto Matsumoto <matumoto@math.keio.ac.jp> |
20 | Takuji Nishimura |
21 | Shawn Cokus <Cokus@math.washington.edu> |
22 +----------------------------------------------------------------------+
23 */
24
25 #include "php.h"
26 #include "php_rand.h"
27 #include "php_random.h"
28 #include "php_mt_rand.h"
29
30 /* MT RAND FUNCTIONS */
31
32 /*
33 The following php_mt_...() functions are based on a C++ class MTRand by
34 Richard J. Wagner. For more information see the web page at
35 http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/C-LANG/MersenneTwister.h
36
37 Mersenne Twister random number generator -- a C++ class MTRand
38 Based on code by Makoto Matsumoto, Takuji Nishimura, and Shawn Cokus
39 Richard J. Wagner v1.0 15 May 2003 rjwagner@writeme.com
40
41 The Mersenne Twister is an algorithm for generating random numbers. It
42 was designed with consideration of the flaws in various other generators.
43 The period, 2^19937-1, and the order of equidistribution, 623 dimensions,
44 are far greater. The generator is also fast; it avoids multiplication and
45 division, and it benefits from caches and pipelines. For more information
46 see the inventors' web page at http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
47
48 Reference
49 M. Matsumoto and T. Nishimura, "Mersenne Twister: A 623-Dimensionally
50 Equidistributed Uniform Pseudo-Random Number Generator", ACM Transactions on
51 Modeling and Computer Simulation, Vol. 8, No. 1, January 1998, pp 3-30.
52
53 Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
54 Copyright (C) 2000 - 2003, Richard J. Wagner
55 All rights reserved.
56
57 Redistribution and use in source and binary forms, with or without
58 modification, are permitted provided that the following conditions
59 are met:
60
61 1. Redistributions of source code must retain the above copyright
62 notice, this list of conditions and the following disclaimer.
63
64 2. Redistributions in binary form must reproduce the above copyright
65 notice, this list of conditions and the following disclaimer in the
66 documentation and/or other materials provided with the distribution.
67
68 3. The names of its contributors may not be used to endorse or promote
69 products derived from this software without specific prior written
70 permission.
71
72 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
73 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
74 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
75 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
76 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
77 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
78 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
79 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
80 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
81 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
82 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
83 */
84
85 #define N MT_N /* length of state vector */
86 #define M (397) /* a period parameter */
87 #define hiBit(u) ((u) & 0x80000000U) /* mask all but highest bit of u */
88 #define loBit(u) ((u) & 0x00000001U) /* mask all but lowest bit of u */
89 #define loBits(u) ((u) & 0x7FFFFFFFU) /* mask the highest bit of u */
90 #define mixBits(u, v) (hiBit(u)|loBits(v)) /* move hi bit of u to hi bit of v */
91
92 #define twist(m,u,v) (m ^ (mixBits(u,v)>>1) ^ ((uint32_t)(-(int32_t)(loBit(v))) & 0x9908b0dfU))
93 #define twist_php(m,u,v) (m ^ (mixBits(u,v)>>1) ^ ((uint32_t)(-(int32_t)(loBit(u))) & 0x9908b0dfU))
94
95 /* {{{ php_mt_initialize */
php_mt_initialize(uint32_t seed,uint32_t * state)96 static inline void php_mt_initialize(uint32_t seed, uint32_t *state)
97 {
98 /* Initialize generator state with seed
99 See Knuth TAOCP Vol 2, 3rd Ed, p.106 for multiplier.
100 In previous versions, most significant bits (MSBs) of the seed affect
101 only MSBs of the state array. Modified 9 Jan 2002 by Makoto Matsumoto. */
102
103 uint32_t *s = state;
104 uint32_t *r = state;
105 int i = 1;
106
107 *s++ = seed & 0xffffffffU;
108 for( ; i < N; ++i ) {
109 *s++ = ( 1812433253U * ( *r ^ (*r >> 30) ) + i ) & 0xffffffffU;
110 r++;
111 }
112 }
113 /* }}} */
114
115 /* {{{ php_mt_reload */
php_mt_reload(void)116 static inline void php_mt_reload(void)
117 {
118 /* Generate N new values in state
119 Made clearer and faster by Matthew Bellew (matthew.bellew@home.com) */
120
121 uint32_t *state = BG(state);
122 uint32_t *p = state;
123 int i;
124
125 if (BG(mt_rand_mode) == MT_RAND_MT19937) {
126 for (i = N - M; i--; ++p)
127 *p = twist(p[M], p[0], p[1]);
128 for (i = M; --i; ++p)
129 *p = twist(p[M-N], p[0], p[1]);
130 *p = twist(p[M-N], p[0], state[0]);
131 }
132 else {
133 for (i = N - M; i--; ++p)
134 *p = twist_php(p[M], p[0], p[1]);
135 for (i = M; --i; ++p)
136 *p = twist_php(p[M-N], p[0], p[1]);
137 *p = twist_php(p[M-N], p[0], state[0]);
138 }
139 BG(left) = N;
140 BG(next) = state;
141 }
142 /* }}} */
143
144 /* {{{ php_mt_srand */
php_mt_srand(uint32_t seed)145 PHPAPI void php_mt_srand(uint32_t seed)
146 {
147 /* Seed the generator with a simple uint32 */
148 php_mt_initialize(seed, BG(state));
149 php_mt_reload();
150
151 /* Seed only once */
152 BG(mt_rand_is_seeded) = 1;
153 }
154 /* }}} */
155
156 /* {{{ php_mt_rand */
php_mt_rand(void)157 PHPAPI uint32_t php_mt_rand(void)
158 {
159 /* Pull a 32-bit integer from the generator state
160 Every other access function simply transforms the numbers extracted here */
161
162 uint32_t s1;
163
164 if (UNEXPECTED(!BG(mt_rand_is_seeded))) {
165 zend_long bytes;
166 if (php_random_bytes_silent(&bytes, sizeof(zend_long)) == FAILURE) {
167 bytes = GENERATE_SEED();
168 }
169 php_mt_srand(bytes);
170 }
171
172 if (BG(left) == 0) {
173 php_mt_reload();
174 }
175 --BG(left);
176
177 s1 = *BG(next)++;
178 s1 ^= (s1 >> 11);
179 s1 ^= (s1 << 7) & 0x9d2c5680U;
180 s1 ^= (s1 << 15) & 0xefc60000U;
181 return ( s1 ^ (s1 >> 18) );
182 }
183 /* }}} */
184
185 /* {{{ Seeds Mersenne Twister random number generator */
PHP_FUNCTION(mt_srand)186 PHP_FUNCTION(mt_srand)
187 {
188 zend_long seed = 0;
189 zend_long mode = MT_RAND_MT19937;
190
191 ZEND_PARSE_PARAMETERS_START(0, 2)
192 Z_PARAM_OPTIONAL
193 Z_PARAM_LONG(seed)
194 Z_PARAM_LONG(mode)
195 ZEND_PARSE_PARAMETERS_END();
196
197 if (ZEND_NUM_ARGS() == 0) {
198 if (php_random_bytes_silent(&seed, sizeof(zend_long)) == FAILURE) {
199 seed = GENERATE_SEED();
200 }
201 }
202
203 switch (mode) {
204 case MT_RAND_PHP:
205 BG(mt_rand_mode) = MT_RAND_PHP;
206 break;
207 default:
208 BG(mt_rand_mode) = MT_RAND_MT19937;
209 }
210
211 php_mt_srand(seed);
212 }
213 /* }}} */
214
rand_range32(uint32_t umax)215 static uint32_t rand_range32(uint32_t umax) {
216 uint32_t result, limit;
217
218 result = php_mt_rand();
219
220 /* Special case where no modulus is required */
221 if (UNEXPECTED(umax == UINT32_MAX)) {
222 return result;
223 }
224
225 /* Increment the max so the range is inclusive of max */
226 umax++;
227
228 /* Powers of two are not biased */
229 if ((umax & (umax - 1)) == 0) {
230 return result & (umax - 1);
231 }
232
233 /* Ceiling under which UINT32_MAX % max == 0 */
234 limit = UINT32_MAX - (UINT32_MAX % umax) - 1;
235
236 /* Discard numbers over the limit to avoid modulo bias */
237 while (UNEXPECTED(result > limit)) {
238 result = php_mt_rand();
239 }
240
241 return result % umax;
242 }
243
244 #if ZEND_ULONG_MAX > UINT32_MAX
rand_range64(uint64_t umax)245 static uint64_t rand_range64(uint64_t umax) {
246 uint64_t result, limit;
247
248 result = php_mt_rand();
249 result = (result << 32) | php_mt_rand();
250
251 /* Special case where no modulus is required */
252 if (UNEXPECTED(umax == UINT64_MAX)) {
253 return result;
254 }
255
256 /* Increment the max so the range is inclusive of max */
257 umax++;
258
259 /* Powers of two are not biased */
260 if ((umax & (umax - 1)) == 0) {
261 return result & (umax - 1);
262 }
263
264 /* Ceiling under which UINT64_MAX % max == 0 */
265 limit = UINT64_MAX - (UINT64_MAX % umax) - 1;
266
267 /* Discard numbers over the limit to avoid modulo bias */
268 while (UNEXPECTED(result > limit)) {
269 result = php_mt_rand();
270 result = (result << 32) | php_mt_rand();
271 }
272
273 return result % umax;
274 }
275 #endif
276
277 /* {{{ php_mt_rand_range */
php_mt_rand_range(zend_long min,zend_long max)278 PHPAPI zend_long php_mt_rand_range(zend_long min, zend_long max)
279 {
280 zend_ulong umax = max - min;
281
282 #if ZEND_ULONG_MAX > UINT32_MAX
283 if (umax > UINT32_MAX) {
284 return (zend_long) (rand_range64(umax) + min);
285 }
286 #endif
287
288 return (zend_long) (rand_range32(umax) + min);
289 }
290 /* }}} */
291
292 /* {{{ php_mt_rand_common
293 * rand() allows min > max, mt_rand does not */
php_mt_rand_common(zend_long min,zend_long max)294 PHPAPI zend_long php_mt_rand_common(zend_long min, zend_long max)
295 {
296 int64_t n;
297
298 if (BG(mt_rand_mode) == MT_RAND_MT19937) {
299 return php_mt_rand_range(min, max);
300 }
301
302 /* Legacy mode deliberately not inside php_mt_rand_range()
303 * to prevent other functions being affected */
304 n = (int64_t)php_mt_rand() >> 1;
305 RAND_RANGE_BADSCALING(n, min, max, PHP_MT_RAND_MAX);
306
307 return n;
308 }
309 /* }}} */
310
311 /* {{{ Returns a random number from Mersenne Twister */
PHP_FUNCTION(mt_rand)312 PHP_FUNCTION(mt_rand)
313 {
314 zend_long min;
315 zend_long max;
316 int argc = ZEND_NUM_ARGS();
317
318 if (argc == 0) {
319 // genrand_int31 in mt19937ar.c performs a right shift
320 RETURN_LONG(php_mt_rand() >> 1);
321 }
322
323 ZEND_PARSE_PARAMETERS_START(2, 2)
324 Z_PARAM_LONG(min)
325 Z_PARAM_LONG(max)
326 ZEND_PARSE_PARAMETERS_END();
327
328 if (UNEXPECTED(max < min)) {
329 zend_argument_value_error(2, "must be greater than or equal to argument #1 ($min)");
330 RETURN_THROWS();
331 }
332
333 RETURN_LONG(php_mt_rand_common(min, max));
334 }
335 /* }}} */
336
337 /* {{{ Returns the maximum value a random number from Mersenne Twister can have */
PHP_FUNCTION(mt_getrandmax)338 PHP_FUNCTION(mt_getrandmax)
339 {
340 ZEND_PARSE_PARAMETERS_NONE();
341
342 /*
343 * Melo: it could be 2^^32 but we only use 2^^31 to maintain
344 * compatibility with the previous php_rand
345 */
346 RETURN_LONG(PHP_MT_RAND_MAX); /* 2^^31 */
347 }
348 /* }}} */
349
PHP_MINIT_FUNCTION(mt_rand)350 PHP_MINIT_FUNCTION(mt_rand)
351 {
352 REGISTER_LONG_CONSTANT("MT_RAND_MT19937", MT_RAND_MT19937, CONST_CS | CONST_PERSISTENT);
353 REGISTER_LONG_CONSTANT("MT_RAND_PHP", MT_RAND_PHP, CONST_CS | CONST_PERSISTENT);
354
355 return SUCCESS;
356 }
357
