diff options
author | Mathias Stearn <redbeard0531@gmail.com> | 2016-03-04 13:29:11 -0500 |
---|---|---|
committer | Mathias Stearn <redbeard0531@gmail.com> | 2016-03-04 18:39:55 -0500 |
commit | ec270ef20b801d249b17d2ea9a115350ddd64de9 (patch) | |
tree | afb0105712cdaaf181a425e67f29c6026ba55076 | |
parent | a463cb21c887e6532d0be271a3b3f163be06261c (diff) | |
download | mongo-ec270ef20b801d249b17d2ea9a115350ddd64de9.tar.gz |
SERVER-20121 Use unsigned arithmetic in PsuedoRandom
(cherry picked from commit 1c5fdf8)
Fully manual cherry pick.
-rw-r--r-- | src/mongo/platform/random.cpp | 26 | ||||
-rw-r--r-- | src/mongo/platform/random.h | 20 | ||||
-rw-r--r-- | src/mongo/platform/random_test.cpp | 67 |
3 files changed, 95 insertions, 18 deletions
diff --git a/src/mongo/platform/random.cpp b/src/mongo/platform/random.cpp index d1a620d6a74..10c197f6d6a 100644 --- a/src/mongo/platform/random.cpp +++ b/src/mongo/platform/random.cpp @@ -35,8 +35,8 @@ namespace mongo { // ---- PseudoRandom ----- - int32_t PseudoRandom::nextInt32() { - int32_t t = _x ^ (_x << 11); + uint32_t PseudoRandom::nextUInt32() { + uint32_t t = _x ^ (_x << 11); _x = _y; _y = _z; _z = _w; @@ -44,13 +44,13 @@ namespace mongo { } namespace { - const int32_t default_y = 362436069; - const int32_t default_z = 521288629; - const int32_t default_w = 88675123; + const uint32_t default_y = 362436069; + const uint32_t default_z = 521288629; + const uint32_t default_w = 88675123; } PseudoRandom::PseudoRandom( int32_t seed ) { - _x = seed; + _x = static_cast<uint32_t>(seed); _y = default_y; _z = default_z; _w = default_w; @@ -58,7 +58,7 @@ namespace mongo { PseudoRandom::PseudoRandom( uint32_t seed ) { - _x = static_cast<int32_t>(seed); + _x = seed; _y = default_y; _z = default_z; _w = default_w; @@ -66,8 +66,8 @@ namespace mongo { PseudoRandom::PseudoRandom( int64_t seed ) { - int32_t high = seed >> 32; - int32_t low = seed & 0xFFFFFFFF; + uint32_t high = seed >> 32; + uint32_t low = seed & 0xFFFFFFFF; _x = high ^ low; _y = default_y; @@ -75,9 +75,13 @@ namespace mongo { _w = default_w; } + int32_t PseudoRandom::nextInt32() { + return nextUInt32(); + } + int64_t PseudoRandom::nextInt64() { - int64_t a = nextInt32(); - int64_t b = nextInt32(); + uint64_t a = nextUInt32(); + uint64_t b = nextUInt32(); return ( a << 32 ) | b; } diff --git a/src/mongo/platform/random.h b/src/mongo/platform/random.h index 823ea6a08db..da52d05248f 100644 --- a/src/mongo/platform/random.h +++ b/src/mongo/platform/random.h @@ -39,17 +39,21 @@ namespace mongo { /** * @return a number between 0 and max */ - int32_t nextInt32( int32_t max ) { return nextInt32() % max; } + int32_t nextInt32( int32_t max ) { + return static_cast<uint32_t>(nextInt32()) % static_cast<uint32_t>(max); + } /** * @return a number between 0 and max */ - int64_t nextInt64( int64_t max ) { return nextInt64() % max; } + int64_t nextInt64( int64_t max ) { + return static_cast<uint64_t>(nextInt64()) % static_cast<uint64_t>(max); + } /** * @return a number between 0 and max * - * This makes PsuedoRandom instances passable as the third argument to std::random_shuffle + * This makes PseudoRandom instances passable as the third argument to std::random_shuffle */ intptr_t operator()(intptr_t max) { if (sizeof(intptr_t) == 4) @@ -58,10 +62,12 @@ namespace mongo { } private: - int32_t _x; - int32_t _y; - int32_t _z; - int32_t _w; + uint32_t nextUInt32(); + + uint32_t _x; + uint32_t _y; + uint32_t _z; + uint32_t _w; }; /** diff --git a/src/mongo/platform/random_test.cpp b/src/mongo/platform/random_test.cpp index 1f93e78f31f..4e081ac92de 100644 --- a/src/mongo/platform/random_test.cpp +++ b/src/mongo/platform/random_test.cpp @@ -17,6 +17,7 @@ */ #include <set> +#include <vector> #include "mongo/platform/random.h" @@ -86,6 +87,72 @@ namespace mongo { ASSERT_EQUALS( 100U, s.size() ); } + TEST(RandomTest, NextInt32SanityCheck) { + // Generate 1000 int32s and assert that each bit is set between 40% and 60% of the time. + // This is a bare minimum sanity check, not an attempt to ensure quality random numbers. + + PseudoRandom a(11); + std::vector<int32_t> nums; + for (int i = 0; i < 1000; i++) { + nums.push_back(a.nextInt32()); + } + + for (int bit = 0; bit < 32; bit++) { + int onesCount = 0; + for (size_t i=0; i < nums.size(); i++) { + bool isSet = (nums[i] >> bit) & 1; + if (isSet) + onesCount++; + } + + if (onesCount < 400 || onesCount > 600) + FAIL(str::stream() << "bit " << bit << " was set " << (onesCount / 10.) + << "% of the time."); + } + } + + TEST(RandomTest, NextInt64SanityCheck) { + // Generate 1000 int64s and assert that each bit is set between 40% and 60% of the time. + // This is a bare minimum sanity check, not an attempt to ensure quality random numbers. + + PseudoRandom a(11); + std::vector<int64_t> nums; + for (int i = 0; i < 1000; i++) { + nums.push_back(a.nextInt64()); + } + + for (int bit = 0; bit < 64; bit++) { + int onesCount = 0; + for (size_t i=0; i < nums.size(); i++) { + bool isSet = (nums[i] >> bit) & 1; + if (isSet) + onesCount++; + } + + if (onesCount < 400 || onesCount > 600) + FAIL(str::stream() << "bit " << bit << " was set " << (onesCount / 10.) + << "% of the time."); + } + } + + TEST(RandomTest, NextInt32InRange) { + PseudoRandom a(11); + for (int i = 0; i < 1000; i++) { + int32_t res = a.nextInt32(10); + ASSERT_GREATER_THAN_OR_EQUALS(res, 0); + ASSERT_LESS_THAN(res, 10); + } + } + + TEST(RandomTest, NextInt64InRange) { + PseudoRandom a(11); + for (int i = 0; i < 1000; i++) { + int64_t res = a.nextInt64(10); + ASSERT_GREATER_THAN_OR_EQUALS(res, 0); + ASSERT_LESS_THAN(res, 10); + } + } + TEST( RandomTest, Secure1 ) { SecureRandom* a = SecureRandom::create(); |