LCOV - code coverage report
Current view: top level - src/base/utils - random-number-generator.h (source / functions) Hit Total Coverage
Test: app.info Lines: 15 15 100.0 %
Date: 2017-04-26 Functions: 2 2 100.0 %

          Line data    Source code
       1             : // Copyright 2013 the V8 project authors. All rights reserved.
       2             : // Use of this source code is governed by a BSD-style license that can be
       3             : // found in the LICENSE file.
       4             : 
       5             : #ifndef V8_BASE_UTILS_RANDOM_NUMBER_GENERATOR_H_
       6             : #define V8_BASE_UTILS_RANDOM_NUMBER_GENERATOR_H_
       7             : 
       8             : #include "src/base/base-export.h"
       9             : #include "src/base/macros.h"
      10             : 
      11             : namespace v8 {
      12             : namespace base {
      13             : 
      14             : // -----------------------------------------------------------------------------
      15             : // RandomNumberGenerator
      16             : 
      17             : // This class is used to generate a stream of pseudo-random numbers. The class
      18             : // uses a 64-bit seed, which is passed through MurmurHash3 to create two 64-bit
      19             : // state values. This pair of state values is then used in xorshift128+.
      20             : // The resulting stream of pseudo-random numbers has a period length of 2^128-1.
      21             : // See Marsaglia: http://www.jstatsoft.org/v08/i14/paper
      22             : // And Vigna: http://vigna.di.unimi.it/ftp/papers/xorshiftplus.pdf
      23             : // NOTE: Any changes to the algorithm must be tested against TestU01.
      24             : //       Please find instructions for this in the internal repository.
      25             : 
      26             : // If two instances of RandomNumberGenerator are created with the same seed, and
      27             : // the same sequence of method calls is made for each, they will generate and
      28             : // return identical sequences of numbers.
      29             : // This class uses (probably) weak entropy by default, but it's sufficient,
      30             : // because it is the responsibility of the embedder to install an entropy source
      31             : // using v8::V8::SetEntropySource(), which provides reasonable entropy, see:
      32             : // https://code.google.com/p/v8/issues/detail?id=2905
      33             : // This class is neither reentrant nor threadsafe.
      34             : 
      35             : class V8_BASE_EXPORT RandomNumberGenerator final {
      36             :  public:
      37             :   // EntropySource is used as a callback function when V8 needs a source of
      38             :   // entropy.
      39             :   typedef bool (*EntropySource)(unsigned char* buffer, size_t buflen);
      40             :   static void SetEntropySource(EntropySource entropy_source);
      41             : 
      42             :   RandomNumberGenerator();
      43       60781 :   explicit RandomNumberGenerator(int64_t seed) { SetSeed(seed); }
      44             : 
      45             :   // Returns the next pseudorandom, uniformly distributed int value from this
      46             :   // random number generator's sequence. The general contract of |NextInt()| is
      47             :   // that one int value is pseudorandomly generated and returned.
      48             :   // All 2^32 possible integer values are produced with (approximately) equal
      49             :   // probability.
      50             :   V8_INLINE int NextInt() WARN_UNUSED_RESULT {
      51    13963277 :     return Next(32);
      52             :   }
      53             : 
      54             :   // Returns a pseudorandom, uniformly distributed int value between 0
      55             :   // (inclusive) and the specified max value (exclusive), drawn from this random
      56             :   // number generator's sequence. The general contract of |NextInt(int)| is that
      57             :   // one int value in the specified range is pseudorandomly generated and
      58             :   // returned. All max possible int values are produced with (approximately)
      59             :   // equal probability.
      60             :   int NextInt(int max) WARN_UNUSED_RESULT;
      61             : 
      62             :   // Returns the next pseudorandom, uniformly distributed boolean value from
      63             :   // this random number generator's sequence. The general contract of
      64             :   // |NextBoolean()| is that one boolean value is pseudorandomly generated and
      65             :   // returned. The values true and false are produced with (approximately) equal
      66             :   // probability.
      67             :   V8_INLINE bool NextBool() WARN_UNUSED_RESULT {
      68             :     return Next(1) != 0;
      69             :   }
      70             : 
      71             :   // Returns the next pseudorandom, uniformly distributed double value between
      72             :   // 0.0 and 1.0 from this random number generator's sequence.
      73             :   // The general contract of |NextDouble()| is that one double value, chosen
      74             :   // (approximately) uniformly from the range 0.0 (inclusive) to 1.0
      75             :   // (exclusive), is pseudorandomly generated and returned.
      76             :   double NextDouble() WARN_UNUSED_RESULT;
      77             : 
      78             :   // Returns the next pseudorandom, uniformly distributed int64 value from this
      79             :   // random number generator's sequence. The general contract of |NextInt64()|
      80             :   // is that one 64-bit int value is pseudorandomly generated and returned.
      81             :   // All 2^64 possible integer values are produced with (approximately) equal
      82             :   // probability.
      83             :   int64_t NextInt64() WARN_UNUSED_RESULT;
      84             : 
      85             :   // Fills the elements of a specified array of bytes with random numbers.
      86             :   void NextBytes(void* buffer, size_t buflen);
      87             : 
      88             :   // Override the current ssed.
      89             :   void SetSeed(int64_t seed);
      90             : 
      91             :   int64_t initial_seed() const { return initial_seed_; }
      92             : 
      93             :   // Static and exposed for external use.
      94    33807360 :   static inline double ToDouble(uint64_t state0, uint64_t state1) {
      95             :     // Exponent for double values for [1.0 .. 2.0)
      96             :     static const uint64_t kExponentBits = V8_UINT64_C(0x3FF0000000000000);
      97             :     static const uint64_t kMantissaMask = V8_UINT64_C(0x000FFFFFFFFFFFFF);
      98    33940467 :     uint64_t random = ((state0 + state1) & kMantissaMask) | kExponentBits;
      99    33940467 :     return bit_cast<double>(random) - 1;
     100             :   }
     101             : 
     102             :   // Static and exposed for external use.
     103    33807360 :   static inline void XorShift128(uint64_t* state0, uint64_t* state1) {
     104   709400375 :     uint64_t s1 = *state0;
     105   709400375 :     uint64_t s0 = *state1;
     106   709400375 :     *state0 = s0;
     107   709400375 :     s1 ^= s1 << 23;
     108   709400375 :     s1 ^= s1 >> 17;
     109   709400375 :     s1 ^= s0;
     110   709400375 :     s1 ^= s0 >> 26;
     111   709400375 :     *state1 = s1;
     112    33807360 :   }
     113             : 
     114             :  private:
     115             :   static const int64_t kMultiplier = V8_2PART_UINT64_C(0x5, deece66d);
     116             :   static const int64_t kAddend = 0xb;
     117             :   static const int64_t kMask = V8_2PART_UINT64_C(0xffff, ffffffff);
     118             : 
     119             :   int Next(int bits) WARN_UNUSED_RESULT;
     120             : 
     121             :   static uint64_t MurmurHash3(uint64_t);
     122             : 
     123             :   int64_t initial_seed_;
     124             :   uint64_t state0_;
     125             :   uint64_t state1_;
     126             : };
     127             : 
     128             : }  // namespace base
     129             : }  // namespace v8
     130             : 
     131             : #endif  // V8_BASE_UTILS_RANDOM_NUMBER_GENERATOR_H_

Generated by: LCOV version 1.10