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   int left;
 109   uint32_t state[N];
 110   uint32_t* next;
 111
 112   bool seeded;
 113   bool lcg_seeded;
 114   int32_t lcg_s1;
 115   int32_t lcg_s2;
 116 };
 117
 118 namespace {
 119
 120 /*
 121  * Use a RdsLocalNoCheck to hold RandData instead of directly using __thread.
 122  * RandData is large, and we don't want our non-PHP threads to be needlessly
 123  * holding it in TLS.
 124  */
 125 RDS_LOCAL_NO_CHECK(RandData, s_data);
 126
 127 void php_mt_initialize(uint32_t seed, uint32_t* state) {
 128   /* Initialize generator state with seed
 129      See Knuth TAOCP Vol 2, 3rd Ed, p.106 for multiplier.
 130      In previous versions, most significant bits (MSBs) of the seed affect
 131      only MSBs of the state array.  Modified 9 Jan 2002 by Makoto Matsumoto. */
 132
 133   register uint32_t* s = state;
 134   register uint32_t* r = state;
 135   register int i = 1;
 136
 137   *s++ = seed & 0xffffffffU;
 138   for( ; i < N; ++i ) {
 139     *s++ = ( 1812433253U * ( *r ^ (*r >> 30) ) + i ) & 0xffffffffU;
 140     r++;
 141   }
 142 }
 143
 144 void php_mt_reload() {
 145   /* Generate N new values in state
 146      Made clearer and faster by Matthew Bellew (matthew.bellew@home.com) */
 147
 148   register uint32_t* state = s_data->state;
 149   register uint32_t* p = state;
 150   register int i;
 151
 152   for (i = N - M; i--; ++p)
 153     *p = twist(p[M], p[0], p[1]);
 154   for (i = M; --i; ++p)
 155     *p = twist(p[M-N], p[0], p[1]);
 156   *p = twist(p[M-N], p[0], state[0]);
 157   s_data->left = N;
 158   s_data->next = state;
 159 }
 160
 161 uint32_t php_mt_rand() {
 162   // Pull a 32-bit integer from the generator state
 163   // Every other access function simply transforms the numbers extracted here
 164
 165   register uint32_t s1;
 166
 167   if (s_data->left == 0) {
 168     php_mt_reload();
 169   }
 170   --s_data->left;
 171
 172   s1 = *s_data->next++;
 173   s1 ^= (s1 >> 11);
 174   s1 ^= (s1 <<  7) & 0x9d2c5680U;
 175   s1 ^= (s1 << 15) & 0xefc60000U;
 176   return s1 ^ (s1 >> 18);
 177 }
 178
 179 ////////////////////////////////////////////////////////////////////////////////
 180
 181 #define MODMULT(a, b, c, m, s) q = s/a;s=b*(s-a*q)-c*q;if (s<0)s+=m
 182
 183 void lcg_seed() {
 184   timeval tv;
 185
 186   s_data->lcg_s1 = gettimeofday(&tv, nullptr) == 0
 187     ? tv.tv_sec ^ (tv.tv_usec << 11)
 188     : 1;
 189
 190   s_data->lcg_s2 = (long)getpid();
 191
 192   /* Add entropy to s2 by calling gettimeofday() again */
 193   if (gettimeofday(&tv, nullptr) == 0) {
 194     s_data->lcg_s2 ^= (tv.tv_usec << 11);
 195   }
 196
 197   s_data->lcg_seeded = true;
 198 }
 199
 200 ////////////////////////////////////////////////////////////////////////////////
 201 }
 202
 203 void math_mt_srand(uint32_t seed) {
 204   /* Seed the generator with a simple uint32 */
 205   php_mt_initialize(seed, s_data->state);
 206   php_mt_reload();
 207
 208   /* Seed only once */
 209   s_data->seeded = true;
 210 }
 211
 212 // Returns a random number from Mersenne Twister
 213 int64_t math_mt_rand(int64_t min /* = 0 */, int64_t max /* = RAND_MAX */) {
 214   if (!s_data->seeded) {
 215     math_mt_srand(math_generate_seed());
 216   }
 217
 218   /*
 219    * Melo: hmms.. randomMT() returns 32 random bits...
 220    * Yet, the previous php_rand only returns 31 at most.
 221    * So I put a right shift to loose the lsb. It *seems*
 222    * better than clearing the msb.
 223    * Update:
 224    * I talked with Cokus via email and it won't ruin the algorithm
 225    */
 226   int64_t number = (php_mt_rand() >> 1);
 227   if (min != 0 || max != RAND_MAX) {
 228     RAND_RANGE(number, min, max, MT_RAND_MAX);
 229   }
 230   return number;
 231 }
 232
 233 ///////////////////////////////////////////////////////////////////////////////
 234
 235
 236 /*
 237  * math_combined_lcg() returns a pseudo random number in the range of (0, 1).
 238  * The function combines two CGs with periods of 2^31 - 85 and 2^31 - 249. The
 239  * period of this function is equal to the product of both primes.
 240  */
 241 double math_combined_lcg() {
 242   int32_t q;
 243   int32_t z;
 244
 245   if (!s_data->lcg_seeded) {
 246     lcg_seed();
 247   }
 248
 249   MODMULT(53668, 40014, 12211, 2147483563L, s_data->lcg_s1);
 250   MODMULT(52774, 40692, 3791, 2147483399L, s_data->lcg_s2);
 251
 252   z = s_data->lcg_s1 - s_data->lcg_s2;
 253   if (z < 1) {
 254     z += 2147483562;
 255   }
 256
 257   return z * 4.656613e-10;
 258 }
 259
 260 int64_t math_generate_seed() {
 261 #ifdef VALGRIND
 262   // Valgrind treats memory from RAND_bytes as uninitialized.
 263   return GENERATE_SEED();
 264 #endif
 265   int64_t value;
 266   if (RAND_bytes((unsigned char*)&value, sizeof(value)) < 1) {
 267     return GENERATE_SEED();
 268   }
 269   return value;
 270 }
 271
 272 ////////////////////////////////////////////////////////////////////////////////
 273
 274 void zend_rand_init() {
 275   s_data.getCheck();
 276 }
 277
 278 void zend_rand_unseed() {
 279   s_data->seeded = false;
 280   s_data->lcg_seeded = false;
 281 }
 282
 283 ///////////////////////////////////////////////////////////////////////////////
 284 }