LCOV - code coverage report
Current view: top level - src/base/utils - random-number-generator.h (source / functions) Hit Total Coverage
Test: app.info Lines: 13 13 100.0 %
Date: 2019-03-21 Functions: 0 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 <unordered_set>
       9             : #include <vector>
      10             : 
      11             : #include "src/base/base-export.h"
      12             : #include "src/base/macros.h"
      13             : 
      14             : namespace v8 {
      15             : namespace base {
      16             : 
      17             : // -----------------------------------------------------------------------------
      18             : // RandomNumberGenerator
      19             : 
      20             : // This class is used to generate a stream of pseudo-random numbers. The class
      21             : // uses a 64-bit seed, which is passed through MurmurHash3 to create two 64-bit
      22             : // state values. This pair of state values is then used in xorshift128+.
      23             : // The resulting stream of pseudo-random numbers has a period length of 2^128-1.
      24             : // See Marsaglia: http://www.jstatsoft.org/v08/i14/paper
      25             : // And Vigna: http://vigna.di.unimi.it/ftp/papers/xorshiftplus.pdf
      26             : // NOTE: Any changes to the algorithm must be tested against TestU01.
      27             : //       Please find instructions for this in the internal repository.
      28             : 
      29             : // If two instances of RandomNumberGenerator are created with the same seed, and
      30             : // the same sequence of method calls is made for each, they will generate and
      31             : // return identical sequences of numbers.
      32             : // This class uses (probably) weak entropy by default, but it's sufficient,
      33             : // because it is the responsibility of the embedder to install an entropy source
      34             : // using v8::V8::SetEntropySource(), which provides reasonable entropy, see:
      35             : // https://code.google.com/p/v8/issues/detail?id=2905
      36             : // This class is neither reentrant nor threadsafe.
      37             : 
      38             : class V8_BASE_EXPORT RandomNumberGenerator final {
      39             :  public:
      40             :   // EntropySource is used as a callback function when V8 needs a source of
      41             :   // entropy.
      42             :   typedef bool (*EntropySource)(unsigned char* buffer, size_t buflen);
      43             :   static void SetEntropySource(EntropySource entropy_source);
      44             : 
      45             :   RandomNumberGenerator();
      46       60294 :   explicit RandomNumberGenerator(int64_t seed) { SetSeed(seed); }
      47             : 
      48             :   // Returns the next pseudorandom, uniformly distributed int value from this
      49             :   // random number generator's sequence. The general contract of |NextInt()| is
      50             :   // that one int value is pseudorandomly generated and returned.
      51             :   // All 2^32 possible integer values are produced with (approximately) equal
      52             :   // probability.
      53   411683929 :   V8_INLINE int NextInt() V8_WARN_UNUSED_RESULT { return Next(32); }
      54             : 
      55             :   // Returns a pseudorandom, uniformly distributed int value between 0
      56             :   // (inclusive) and the specified max value (exclusive), drawn from this random
      57             :   // number generator's sequence. The general contract of |NextInt(int)| is that
      58             :   // one int value in the specified range is pseudorandomly generated and
      59             :   // returned. All max possible int values are produced with (approximately)
      60             :   // equal probability.
      61             :   int NextInt(int max) V8_WARN_UNUSED_RESULT;
      62             : 
      63             :   // Returns the next pseudorandom, uniformly distributed boolean value from
      64             :   // this random number generator's sequence. The general contract of
      65             :   // |NextBoolean()| is that one boolean value is pseudorandomly generated and
      66             :   // returned. The values true and false are produced with (approximately) equal
      67             :   // probability.
      68      141105 :   V8_INLINE bool NextBool() V8_WARN_UNUSED_RESULT { return Next(1) != 0; }
      69             : 
      70             :   // Returns the next pseudorandom, uniformly distributed double value between
      71             :   // 0.0 and 1.0 from this random number generator's sequence.
      72             :   // The general contract of |NextDouble()| is that one double value, chosen
      73             :   // (approximately) uniformly from the range 0.0 (inclusive) to 1.0
      74             :   // (exclusive), is pseudorandomly generated and returned.
      75             :   double NextDouble() V8_WARN_UNUSED_RESULT;
      76             : 
      77             :   // Returns the next pseudorandom, uniformly distributed int64 value from this
      78             :   // random number generator's sequence. The general contract of |NextInt64()|
      79             :   // is that one 64-bit int value is pseudorandomly generated and returned.
      80             :   // All 2^64 possible integer values are produced with (approximately) equal
      81             :   // probability.
      82             :   int64_t NextInt64() V8_WARN_UNUSED_RESULT;
      83             : 
      84             :   // Fills the elements of a specified array of bytes with random numbers.
      85             :   void NextBytes(void* buffer, size_t buflen);
      86             : 
      87             :   // Returns the next pseudorandom set of n unique uint64 values smaller than
      88             :   // max.
      89             :   // n must be less or equal to max.
      90             :   std::vector<uint64_t> NextSample(uint64_t max,
      91             :                                    size_t n) V8_WARN_UNUSED_RESULT;
      92             : 
      93             :   // Returns the next pseudorandom set of n unique uint64 values smaller than
      94             :   // max.
      95             :   // n must be less or equal to max.
      96             :   // max - |excluded| must be less or equal to n.
      97             :   //
      98             :   // Generates list of all possible values and removes random values from it
      99             :   // until size reaches n.
     100             :   std::vector<uint64_t> NextSampleSlow(
     101             :       uint64_t max, size_t n,
     102             :       const std::unordered_set<uint64_t>& excluded =
     103             :           std::unordered_set<uint64_t>{}) V8_WARN_UNUSED_RESULT;
     104             : 
     105             :   // Override the current ssed.
     106             :   void SetSeed(int64_t seed);
     107             : 
     108             :   int64_t initial_seed() const { return initial_seed_; }
     109             : 
     110             :   // Static and exposed for external use.
     111             :   static inline double ToDouble(uint64_t state0) {
     112             :     // Exponent for double values for [1.0 .. 2.0)
     113             :     static const uint64_t kExponentBits = uint64_t{0x3FF0000000000000};
     114    10555244 :     uint64_t random = (state0 >> 12) | kExponentBits;
     115    10555244 :     return bit_cast<double>(random) - 1;
     116             :   }
     117             : 
     118             :   // Static and exposed for external use.
     119             :   static inline void XorShift128(uint64_t* state0, uint64_t* state1) {
     120  1516224676 :     uint64_t s1 = *state0;
     121  1516224676 :     uint64_t s0 = *state1;
     122  1516224676 :     *state0 = s0;
     123  1516224676 :     s1 ^= s1 << 23;
     124  1516224676 :     s1 ^= s1 >> 17;
     125  1516224676 :     s1 ^= s0;
     126  1516224676 :     s1 ^= s0 >> 26;
     127  1516224676 :     *state1 = s1;
     128             :   }
     129             : 
     130             :   static uint64_t MurmurHash3(uint64_t);
     131             : 
     132             :  private:
     133             :   static const int64_t kMultiplier = V8_2PART_UINT64_C(0x5, deece66d);
     134             :   static const int64_t kAddend = 0xb;
     135             :   static const int64_t kMask = V8_2PART_UINT64_C(0xffff, ffffffff);
     136             : 
     137             :   int Next(int bits) V8_WARN_UNUSED_RESULT;
     138             : 
     139             :   int64_t initial_seed_;
     140             :   uint64_t state0_;
     141             :   uint64_t state1_;
     142             : };
     143             : 
     144             : }  // namespace base
     145             : }  // namespace v8
     146             : 
     147             : #endif  // V8_BASE_UTILS_RANDOM_NUMBER_GENERATOR_H_

Generated by: LCOV version 1.10