diff options
author | Timothy J Fontaine <tjfontaine@gmail.com> | 2013-10-22 15:14:25 -0700 |
---|---|---|
committer | Timothy J Fontaine <tjfontaine@gmail.com> | 2013-10-23 09:17:31 -0700 |
commit | a53c763c16eeabb0901a05dbcf38a72fa96d2f26 (patch) | |
tree | 309bf250e1521cedf0e945d7a7629db511e64498 /deps/v8/src/utils | |
parent | 54910044b33a6405c72ad085915a55c575c027fc (diff) | |
download | android-node-v8-a53c763c16eeabb0901a05dbcf38a72fa96d2f26.tar.gz android-node-v8-a53c763c16eeabb0901a05dbcf38a72fa96d2f26.tar.bz2 android-node-v8-a53c763c16eeabb0901a05dbcf38a72fa96d2f26.zip |
v8: upgrade 3.21.18.3
Diffstat (limited to 'deps/v8/src/utils')
-rw-r--r-- | deps/v8/src/utils/random-number-generator.cc | 136 | ||||
-rw-r--r-- | deps/v8/src/utils/random-number-generator.h | 106 |
2 files changed, 242 insertions, 0 deletions
diff --git a/deps/v8/src/utils/random-number-generator.cc b/deps/v8/src/utils/random-number-generator.cc new file mode 100644 index 0000000000..1e03ee2449 --- /dev/null +++ b/deps/v8/src/utils/random-number-generator.cc @@ -0,0 +1,136 @@ +// Copyright 2013 the V8 project authors. All rights reserved. +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following +// disclaimer in the documentation and/or other materials provided +// with the distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived +// from this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#include "utils/random-number-generator.h" + +#include <cstdio> + +#include "flags.h" +#include "platform/mutex.h" +#include "platform/time.h" +#include "utils.h" + +namespace v8 { +namespace internal { + +static LazyMutex entropy_mutex = LAZY_MUTEX_INITIALIZER; +static RandomNumberGenerator::EntropySource entropy_source = NULL; + + +// static +void RandomNumberGenerator::SetEntropySource(EntropySource source) { + LockGuard<Mutex> lock_guard(entropy_mutex.Pointer()); + entropy_source = source; +} + + +RandomNumberGenerator::RandomNumberGenerator() { + // Check --random-seed flag first. + if (FLAG_random_seed != 0) { + SetSeed(FLAG_random_seed); + return; + } + + // Check if embedder supplied an entropy source. + { LockGuard<Mutex> lock_guard(entropy_mutex.Pointer()); + if (entropy_source != NULL) { + int64_t seed; + if (entropy_source(reinterpret_cast<unsigned char*>(&seed), + sizeof(seed))) { + SetSeed(seed); + return; + } + } + } + + // Gather entropy from /dev/urandom if available. + FILE* fp = fopen("/dev/urandom", "rb"); + if (fp != NULL) { + int64_t seed; + size_t n = fread(&seed, sizeof(seed), 1, fp); + fclose(fp); + if (n == 1) { + SetSeed(seed); + return; + } + } + + // We cannot assume that random() or rand() were seeded + // properly, so instead of relying on random() or rand(), + // we just seed our PRNG using timing data as fallback. + int64_t seed = Time::NowFromSystemTime().ToInternalValue() << 24; + seed ^= TimeTicks::HighResNow().ToInternalValue() << 16; + seed ^= TimeTicks::Now().ToInternalValue() << 8; + SetSeed(seed); +} + + +int RandomNumberGenerator::NextInt(int max) { + ASSERT_LE(0, max); + + // Fast path if max is a power of 2. + if (IsPowerOf2(max)) { + return static_cast<int>((max * static_cast<int64_t>(Next(31))) >> 31); + } + + while (true) { + int rnd = Next(31); + int val = rnd % max; + if (rnd - val + (max - 1) >= 0) { + return val; + } + } +} + + +double RandomNumberGenerator::NextDouble() { + return ((static_cast<int64_t>(Next(26)) << 27) + Next(27)) / + static_cast<double>(static_cast<int64_t>(1) << 53); +} + + +void RandomNumberGenerator::NextBytes(void* buffer, size_t buflen) { + for (size_t n = 0; n < buflen; ++n) { + static_cast<uint8_t*>(buffer)[n] = static_cast<uint8_t>(Next(8)); + } +} + + +int RandomNumberGenerator::Next(int bits) { + ASSERT_LT(0, bits); + ASSERT_GE(32, bits); + int64_t seed = (seed_ * kMultiplier + kAddend) & kMask; + seed_ = seed; + return static_cast<int>(seed >> (48 - bits)); +} + + +void RandomNumberGenerator::SetSeed(int64_t seed) { + seed_ = (seed ^ kMultiplier) & kMask; +} + +} } // namespace v8::internal diff --git a/deps/v8/src/utils/random-number-generator.h b/deps/v8/src/utils/random-number-generator.h new file mode 100644 index 0000000000..bd7dca7e65 --- /dev/null +++ b/deps/v8/src/utils/random-number-generator.h @@ -0,0 +1,106 @@ +// Copyright 2013 the V8 project authors. All rights reserved. +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following +// disclaimer in the documentation and/or other materials provided +// with the distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived +// from this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#ifndef V8_UTILS_RANDOM_NUMBER_GENERATOR_H_ +#define V8_UTILS_RANDOM_NUMBER_GENERATOR_H_ + +#include "globals.h" + +namespace v8 { +namespace internal { + +// ----------------------------------------------------------------------------- +// RandomNumberGenerator +// +// This class is used to generate a stream of pseudorandom numbers. The class +// uses a 48-bit seed, which is modified using a linear congruential formula. +// (See Donald Knuth, The Art of Computer Programming, Volume 3, Section 3.2.1.) +// If two instances of RandomNumberGenerator are created with the same seed, and +// the same sequence of method calls is made for each, they will generate and +// return identical sequences of numbers. +// This class is neither reentrant nor threadsafe. + +class RandomNumberGenerator V8_FINAL { + public: + // EntropySource is used as a callback function when V8 needs a source of + // entropy. + typedef bool (*EntropySource)(unsigned char* buffer, size_t buflen); + static void SetEntropySource(EntropySource entropy_source); + + RandomNumberGenerator(); + explicit RandomNumberGenerator(int64_t seed) { SetSeed(seed); } + + // Returns the next pseudorandom, uniformly distributed int value from this + // random number generator's sequence. The general contract of |NextInt()| is + // that one int value is pseudorandomly generated and returned. + // All 2^32 possible integer values are produced with (approximately) equal + // probability. + V8_INLINE int NextInt() V8_WARN_UNUSED_RESULT { + return Next(32); + } + + // Returns a pseudorandom, uniformly distributed int value between 0 + // (inclusive) and the specified max value (exclusive), drawn from this random + // number generator's sequence. The general contract of |NextInt(int)| is that + // one int value in the specified range is pseudorandomly generated and + // returned. All max possible int values are produced with (approximately) + // equal probability. + int NextInt(int max) V8_WARN_UNUSED_RESULT; + + // Returns the next pseudorandom, uniformly distributed boolean value from + // this random number generator's sequence. The general contract of + // |NextBoolean()| is that one boolean value is pseudorandomly generated and + // returned. The values true and false are produced with (approximately) equal + // probability. + V8_INLINE bool NextBool() V8_WARN_UNUSED_RESULT { + return Next(1) != 0; + } + + // Returns the next pseudorandom, uniformly distributed double value between + // 0.0 and 1.0 from this random number generator's sequence. + // The general contract of |NextDouble()| is that one double value, chosen + // (approximately) uniformly from the range 0.0 (inclusive) to 1.0 + // (exclusive), is pseudorandomly generated and returned. + double NextDouble() V8_WARN_UNUSED_RESULT; + + // Fills the elements of a specified array of bytes with random numbers. + void NextBytes(void* buffer, size_t buflen); + + private: + static const int64_t kMultiplier = V8_2PART_UINT64_C(0x5, deece66d); + static const int64_t kAddend = 0xb; + static const int64_t kMask = V8_2PART_UINT64_C(0xffff, ffffffff); + + int Next(int bits) V8_WARN_UNUSED_RESULT; + void SetSeed(int64_t seed); + + int64_t seed_; +}; + +} } // namespace v8::internal + +#endif // V8_UTILS_RANDOM_NUMBER_GENERATOR_H_ |