hphp/zend/zend-rand.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   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    +----------------------------------------------------------------------+
  16 */
  17
  18 #include <folly/portability/SysTime.h>
  19
  20 #include <openssl/rand.h>
  21
  22 #include "hphp/util/rds-local.h"
  23 #include "hphp/zend/zend-math.h"
  24
  25 namespace HPHP {
  26 ///////////////////////////////////////////////////////////////////////////////
  27 /* MT RAND FUNCTIONS */
  28
  29 /*
  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
  33
  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
  37
  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
  44
  45   Reference
  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.
  49
  50   Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
  51   Copyright (C) 2000 - 2003, Richard J. Wagner
  52   All rights reserved.
  53
  54   Redistribution and use in source and binary forms, with or without
  55   modification, are permitted provided that the following conditions
  56   are met:
  57
  58   1. Redistributions of source code must retain the above copyright
  59      notice, this list of conditions and the following disclaimer.
  60
  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.
  64
  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
  67      permission.
  68
  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.
  80
  81   The original code included the following notice:
  82
  83   When you use this, send an email to: matumoto@math.keio.ac.jp
  84     with an appropriate reference to your work.
  85
  86   It would be nice to CC: rjwagner@writeme.com and Cokus@math.washington.edu
  87   when you write.
  88 */
  89
  90 #define MT_N          (624)
  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
  97
  98 #define twist(m,u,v) \
  99   (m ^ (mixBits(u,v)>>1) ^ ((uint32_t)(-(int32_t)(loBit(u))) & 0x9908b0dfU))
 100
 101 ////////////////////////////////////////////////////////////////////////////////
 102
 103 struct RandData {
 104   RandData() {
 105     memset(this, 0, sizeof(*this));
 106   }
 107
 108   uint32_t state[N];
 109   uint32_t* next;
 110
 111   bool seeded;
 112   bool lcg_seeded;
 113   int32_t lcg_s1;
 114   int32_t lcg_s2;
 115 };
 116
 117 namespace {
 118
 119 /*
 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
 122  * holding it in TLS.
 123  */
 124 RDS_LOCAL_NO_CHECK(RandData, s_data);
 125
 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. */
 131
 132   uint32_t* s = state;
 133   uint32_t* r = state;
 134   int i = 1;
 135
 136   *s++ = seed & 0xffffffffU;
 137   for( ; i < N; ++i ) {
 138     *s++ = ( 1812433253U * ( *r ^ (*r >> 30) ) + i ) & 0xffffffffU;
 139     r++;
 140   }
 141 }
 142
 143 void php_mt_reload() {
 144   /* Generate N new values in state
 145      Made clearer and faster by Matthew Bellew (matthew.bellew@home.com) */
 146
 147   uint32_t* state = s_data->state;
 148   uint32_t* p = state;
 149   int i;
 150
 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;
 157 }
 158
 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
 162
 163   uint32_t s1;
 164
 165   if (s_data->next == s_data->state + N) {
 166     php_mt_reload();
 167   }
 168
 169   s1 = *s_data->next++;
 170   s1 ^= (s1 >> 11);
 171   s1 ^= (s1 <<  7) & 0x9d2c5680U;
 172   s1 ^= (s1 << 15) & 0xefc60000U;
 173   return s1 ^ (s1 >> 18);
 174 }
 175
 176 ////////////////////////////////////////////////////////////////////////////////
 177
 178 #define MODMULT(a, b, c, m, s) q = s/a;s=b*(s-a*q)-c*q;if (s<0)s+=m
 179
 180 void lcg_seed() {
 181   timeval tv;
 182
 183   s_data->lcg_s1 = gettimeofday(&tv, nullptr) == 0
 184     ? tv.tv_sec ^ (tv.tv_usec << 11)
 185     : 1;
 186
 187   s_data->lcg_s2 = (long)getpid();
 188
 189   /* Add entropy to s2 by calling gettimeofday() again */
 190   if (gettimeofday(&tv, nullptr) == 0) {
 191     s_data->lcg_s2 ^= (tv.tv_usec << 11);
 192   }
 193
 194   s_data->lcg_seeded = true;
 195 }
 196
 197 ////////////////////////////////////////////////////////////////////////////////
 198 }
 199
 200 uint32_t RDSLocalPRNG::operator()() {
 201   RandData* data = s_data.get();
 202
 203   if (!data->seeded) {
 204     math_mt_srand(math_generate_seed());
 205   }
 206
 207   return php_mt_rand();
 208 }
 209
 210 void math_mt_srand(uint32_t seed) {
 211   /* Seed the generator with a simple uint32 */
 212   php_mt_initialize(seed, s_data->state);
 213   php_mt_reload();
 214
 215   /* Seed only once */
 216   s_data->seeded = true;
 217 }
 218
 219 // Returns a random number from Mersenne Twister
 220 int64_t math_mt_rand(int64_t min /* = 0 */, int64_t max /* = RAND_MAX */) {
 221   RDSLocalPRNG rng;
 222   int64_t number = rng() >> 1;
 223   if (min != 0 || max != RAND_MAX) {
 224     RAND_RANGE(number, min, max, MT_RAND_MAX);
 225   }
 226   return number;
 227 }
 228
 229 ///////////////////////////////////////////////////////////////////////////////
 230
 231
 232 /*
 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.
 236  */
 237 double math_combined_lcg() {
 238   int32_t q;
 239   int32_t z;
 240
 241   if (!s_data->lcg_seeded) {
 242     lcg_seed();
 243   }
 244
 245   MODMULT(53668, 40014, 12211, 2147483563L, s_data->lcg_s1);
 246   MODMULT(52774, 40692, 3791, 2147483399L, s_data->lcg_s2);
 247
 248   z = s_data->lcg_s1 - s_data->lcg_s2;
 249   if (z < 1) {
 250     z += 2147483562;
 251   }
 252
 253   return z * 4.656613e-10;
 254 }
 255
 256 int64_t math_generate_seed() {
 257 #ifdef VALGRIND
 258   // Valgrind treats memory from RAND_bytes as uninitialized.
 259   return GENERATE_SEED();
 260 #endif
 261   int64_t value;
 262   if (RAND_bytes((unsigned char*)&value, sizeof(value)) < 1) {
 263     return GENERATE_SEED();
 264   }
 265   return value;
 266 }
 267
 268 ////////////////////////////////////////////////////////////////////////////////
 269
 270 void zend_rand_init() {
 271   s_data.getCheck();
 272 }
 273
 274 void zend_rand_unseed() {
 275   s_data->seeded = false;
 276   s_data->lcg_seeded = false;
 277 }
 278
 279 ///////////////////////////////////////////////////////////////////////////////
 280 }