SERVER-20121 Use unsigned arithmetic in PsuedoRandom

(cherry picked from commit 1c5fdf8)
Fully manual cherry pick.

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();