2 +----------------------------------------------------------------------+
4 +----------------------------------------------------------------------+
5 | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com) |
6 | Copyright (c) 1998-2010 Zend Technologies Ltd. (http://www.zend.com) |
7 +----------------------------------------------------------------------+
8 | This source file is subject to version 2.00 of the Zend license, |
9 | that is bundled with this package in the file LICENSE, and is |
10 | available through the world-wide-web at the following url: |
11 | http://www.zend.com/license/2_00.txt. |
12 | If you did not receive a copy of the Zend license and are unable to |
13 | obtain it through the world-wide-web, please send a note to |
14 | license@zend.com so we can mail you a copy immediately. |
15 +----------------------------------------------------------------------+
18 #include <folly/portability/SysTime.h>
20 #include <openssl/rand.h>
22 #include "hphp/util/rds-local.h"
23 #include "hphp/zend/zend-math.h"
26 ///////////////////////////////////////////////////////////////////////////////
27 /* MT RAND FUNCTIONS */
30 The following php_mt_...() functions are based on a C++ class MTRand by
31 Richard J. Wagner. For more information see the web page at
32 http://www-personal.engin.umich.edu/~wagnerr/MersenneTwister.html
34 Mersenne Twister random number generator -- a C++ class MTRand
35 Based on code by Makoto Matsumoto, Takuji Nishimura, and Shawn Cokus
36 Richard J. Wagner v1.0 15 May 2003 rjwagner@writeme.com
38 The Mersenne Twister is an algorithm for generating random numbers. It
39 was designed with consideration of the flaws in various other generators.
40 The period, 2^19937-1, and the order of equidistribution, 623 dimensions,
41 are far greater. The generator is also fast; it avoids multiplication and
42 division, and it benefits from caches and pipelines. For more information
43 see the inventors' web page at http://www.math.keio.ac.jp/~matumoto/emt.html
46 M. Matsumoto and T. Nishimura, "Mersenne Twister: A 623-Dimensionally
47 Equidistributed Uniform Pseudo-Random Number Generator", ACM Transactions on
48 Modeling and Computer Simulation, Vol. 8, No. 1, January 1998, pp 3-30.
50 Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
51 Copyright (C) 2000 - 2003, Richard J. Wagner
54 Redistribution and use in source and binary forms, with or without
55 modification, are permitted provided that the following conditions
58 1. Redistributions of source code must retain the above copyright
59 notice, this list of conditions and the following disclaimer.
61 2. Redistributions in binary form must reproduce the above copyright
62 notice, this list of conditions and the following disclaimer in the
63 documentation and/or other materials provided with the distribution.
65 3. The names of its contributors may not be used to endorse or promote
66 products derived from this software without specific prior written
69 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
70 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
71 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
72 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
73 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
74 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
75 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
76 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
77 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
78 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
79 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
81 The original code included the following notice:
83 When you use this, send an email to: matumoto@math.keio.ac.jp
84 with an appropriate reference to your work.
86 It would be nice to CC: rjwagner@writeme.com and Cokus@math.washington.edu
91 #define N MT_N // length of state vector
92 #define M (397) // a period parameter
93 #define hiBit(u) ((u) & 0x80000000U) // mask all but highest bit of u
94 #define loBit(u) ((u) & 0x00000001U) // mask all but lowest bit of u
95 #define loBits(u) ((u) & 0x7FFFFFFFU) // mask the highest bit of u
96 #define mixBits(u, v) (hiBit(u)|loBits(v)) // move hi bit of u to hi bit of v
98 #define twist(m,u,v) \
99 (m ^ (mixBits(u,v)>>1) ^ ((uint32_t)(-(int32_t)(loBit(u))) & 0x9908b0dfU))
101 ////////////////////////////////////////////////////////////////////////////////
105 memset(this, 0, sizeof(*this));
120 * Use a RdsLocalNoCheck to hold RandData instead of directly using __thread.
121 * RandData is large, and we don't want our non-PHP threads to be needlessly
124 RDS_LOCAL_NO_CHECK(RandData
, s_data
);
126 void php_mt_initialize(uint32_t seed
, uint32_t* state
) {
127 /* Initialize generator state with seed
128 See Knuth TAOCP Vol 2, 3rd Ed, p.106 for multiplier.
129 In previous versions, most significant bits (MSBs) of the seed affect
130 only MSBs of the state array. Modified 9 Jan 2002 by Makoto Matsumoto. */
136 *s
++ = seed
& 0xffffffffU
;
137 for( ; i
< N
; ++i
) {
138 *s
++ = ( 1812433253U * ( *r
^ (*r
>> 30) ) + i
) & 0xffffffffU
;
143 void php_mt_reload() {
144 /* Generate N new values in state
145 Made clearer and faster by Matthew Bellew (matthew.bellew@home.com) */
147 uint32_t* state
= s_data
->state
;
151 for (i
= N
- M
; i
--; ++p
)
152 *p
= twist(p
[M
], p
[0], p
[1]);
153 for (i
= M
; --i
; ++p
)
154 *p
= twist(p
[M
-N
], p
[0], p
[1]);
155 *p
= twist(p
[M
-N
], p
[0], state
[0]);
156 s_data
->next
= state
;
159 uint32_t php_mt_rand() {
160 // Pull a 32-bit integer from the generator state
161 // Every other access function simply transforms the numbers extracted here
165 if (s_data
->next
== s_data
->state
+ N
) {
169 s1
= *s_data
->next
++;
171 s1
^= (s1
<< 7) & 0x9d2c5680U
;
172 s1
^= (s1
<< 15) & 0xefc60000U
;
173 return s1
^ (s1
>> 18);
176 ////////////////////////////////////////////////////////////////////////////////
178 #define MODMULT(a, b, c, m, s) q = s/a;s=b*(s-a*q)-c*q;if (s<0)s+=m
183 s_data
->lcg_s1
= gettimeofday(&tv
, nullptr) == 0
184 ? tv
.tv_sec
^ (tv
.tv_usec
<< 11)
187 s_data
->lcg_s2
= (long)getpid();
189 /* Add entropy to s2 by calling gettimeofday() again */
190 if (gettimeofday(&tv
, nullptr) == 0) {
191 s_data
->lcg_s2
^= (tv
.tv_usec
<< 11);
194 s_data
->lcg_seeded
= true;
197 ////////////////////////////////////////////////////////////////////////////////
200 uint32_t RDSLocalPRNG::operator()() {
201 RandData
* data
= s_data
.get();
204 math_mt_srand(math_generate_seed());
207 return php_mt_rand();
210 void math_mt_srand(uint32_t seed
) {
211 /* Seed the generator with a simple uint32 */
212 php_mt_initialize(seed
, s_data
->state
);
216 s_data
->seeded
= true;
219 // Returns a random number from Mersenne Twister
220 int64_t math_mt_rand(int64_t min
/* = 0 */, int64_t max
/* = RAND_MAX */) {
222 int64_t number
= rng() >> 1;
223 if (min
!= 0 || max
!= RAND_MAX
) {
224 RAND_RANGE(number
, min
, max
, MT_RAND_MAX
);
229 ///////////////////////////////////////////////////////////////////////////////
233 * math_combined_lcg() returns a pseudo random number in the range of (0, 1).
234 * The function combines two CGs with periods of 2^31 - 85 and 2^31 - 249. The
235 * period of this function is equal to the product of both primes.
237 double math_combined_lcg() {
241 if (!s_data
->lcg_seeded
) {
245 MODMULT(53668, 40014, 12211, 2147483563L, s_data
->lcg_s1
);
246 MODMULT(52774, 40692, 3791, 2147483399L, s_data
->lcg_s2
);
248 z
= s_data
->lcg_s1
- s_data
->lcg_s2
;
253 return z
* 4.656613e-10;
256 int64_t math_generate_seed() {
258 // Valgrind treats memory from RAND_bytes as uninitialized.
259 return GENERATE_SEED();
262 if (RAND_bytes((unsigned char*)&value
, sizeof(value
)) < 1) {
263 return GENERATE_SEED();
268 ////////////////////////////////////////////////////////////////////////////////
270 void zend_rand_init() {
274 void zend_rand_unseed() {
275 s_data
->seeded
= false;
276 s_data
->lcg_seeded
= false;
279 ///////////////////////////////////////////////////////////////////////////////