src/v8/src/utils/random-number-generator.h

   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_UTILS_RANDOM_NUMBER_GENERATOR_H_
   6 #define V8_UTILS_RANDOM_NUMBER_GENERATOR_H_
   7
   8 #include "globals.h"
   9
  10 namespace v8 {
  11 namespace internal {
  12
  13 // -----------------------------------------------------------------------------
  14 // RandomNumberGenerator
  15 //
  16 // This class is used to generate a stream of pseudorandom numbers. The class
  17 // uses a 48-bit seed, which is modified using a linear congruential formula.
  18 // (See Donald Knuth, The Art of Computer Programming, Volume 3, Section 3.2.1.)
  19 // If two instances of RandomNumberGenerator are created with the same seed, and
  20 // the same sequence of method calls is made for each, they will generate and
  21 // return identical sequences of numbers.
  22 // This class uses (probably) weak entropy by default, but it's sufficient,
  23 // because it is the responsibility of the embedder to install an entropy source
  24 // using v8::V8::SetEntropySource(), which provides reasonable entropy, see:
  25 // https://code.google.com/p/v8/issues/detail?id=2905
  26 // This class is neither reentrant nor threadsafe.
  27
  28 class RandomNumberGenerator V8_FINAL {
  29  public:
  30   // EntropySource is used as a callback function when V8 needs a source of
  31   // entropy.
  32   typedef bool (*EntropySource)(unsigned char* buffer, size_t buflen);
  33   static void SetEntropySource(EntropySource entropy_source);
  34
  35   RandomNumberGenerator();
  36   explicit RandomNumberGenerator(int64_t seed) { SetSeed(seed); }
  37
  38   // Returns the next pseudorandom, uniformly distributed int value from this
  39   // random number generator's sequence. The general contract of |NextInt()| is
  40   // that one int value is pseudorandomly generated and returned.
  41   // All 2^32 possible integer values are produced with (approximately) equal
  42   // probability.
  43   V8_INLINE int NextInt() V8_WARN_UNUSED_RESULT {
  44     return Next(32);
  45   }
  46
  47   // Returns a pseudorandom, uniformly distributed int value between 0
  48   // (inclusive) and the specified max value (exclusive), drawn from this random
  49   // number generator's sequence. The general contract of |NextInt(int)| is that
  50   // one int value in the specified range is pseudorandomly generated and
  51   // returned. All max possible int values are produced with (approximately)
  52   // equal probability.
  53   int NextInt(int max) V8_WARN_UNUSED_RESULT;
  54
  55   // Returns the next pseudorandom, uniformly distributed boolean value from
  56   // this random number generator's sequence. The general contract of
  57   // |NextBoolean()| is that one boolean value is pseudorandomly generated and
  58   // returned. The values true and false are produced with (approximately) equal
  59   // probability.
  60   V8_INLINE bool NextBool() V8_WARN_UNUSED_RESULT {
  61     return Next(1) != 0;
  62   }
  63
  64   // Returns the next pseudorandom, uniformly distributed double value between
  65   // 0.0 and 1.0 from this random number generator's sequence.
  66   // The general contract of |NextDouble()| is that one double value, chosen
  67   // (approximately) uniformly from the range 0.0 (inclusive) to 1.0
  68   // (exclusive), is pseudorandomly generated and returned.
  69   double NextDouble() V8_WARN_UNUSED_RESULT;
  70
  71   // Fills the elements of a specified array of bytes with random numbers.
  72   void NextBytes(void* buffer, size_t buflen);
  73
  74  private:
  75   static const int64_t kMultiplier = V8_2PART_UINT64_C(0x5, deece66d);
  76   static const int64_t kAddend = 0xb;
  77   static const int64_t kMask = V8_2PART_UINT64_C(0xffff, ffffffff);
  78
  79   int Next(int bits) V8_WARN_UNUSED_RESULT;
  80   void SetSeed(int64_t seed);
  81
  82   int64_t seed_;
  83 };
  84
  85 } }  // namespace v8::internal
  86
  87 #endif  // V8_UTILS_RANDOM_NUMBER_GENERATOR_H_