SERVER-20121 Use unsigned arithmetic in PsuedoRandom

6 files changed, 96 insertions, 41 deletions

diff --git a/src/mongo/db/pipeline/document_source_test.cpp b/src/mongo/db/pipeline/document_source_test.cpp
index 3fe97dec7b0..545dc2b24f0 100644
--- a/src/mongo/db/pipeline/document_source_test.cpp
+++ b/src/mongo/db/pipeline/document_source_test.cpp
@@ -1315,10 +1315,7 @@ TEST_F(SampleFromRandomCursorBasics, MissingIdField) {
 /**
  * The $sampleFromRandomCursor stage should set the random meta value in a way that mimics the
  * non-optimized case.
- *
- * This fails currently, but should be re-enabled once SERVER-20121 is resolved.
  */
-#if 0
 TEST_F(SampleFromRandomCursorBasics, MimicNonOptimized) {
     // Compute the average random meta value on the each doc returned.
     double firstTotal = 0.0;
@@ -1350,7 +1347,6 @@ TEST_F(SampleFromRandomCursorBasics, MimicNonOptimized) {
     ASSERT_GTE(secondTotal / nTrials, 0.49);
     ASSERT_LTE(secondTotal / nTrials, 0.51);
 }
-#endif
 }  // namespace DocumentSourceSampleFromRandomCursor
 
 }  // namespace DocumentSourceSample
diff --git a/src/mongo/platform/random.cpp b/src/mongo/platform/random.cpp
index ea641460037..2ec9ddea610 100644
--- a/src/mongo/platform/random.cpp
+++ b/src/mongo/platform/random.cpp
@@ -48,8 +48,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;
@@ -57,40 +57,30 @@ int32_t PseudoRandom::nextInt32() {
 }
 
 namespace {
-const int32_t default_y = 362436069;
-const int32_t default_z = 521288629;
-const int32_t default_w = 88675123;
-}
-
-PseudoRandom::PseudoRandom(int32_t seed) {
-    _x = seed;
-    _y = default_y;
-    _z = default_z;
-    _w = default_w;
-}
-
+const uint32_t default_y = 362436069;
+const uint32_t default_z = 521288629;
+const uint32_t default_w = 88675123;
+}  // namespace
 
 PseudoRandom::PseudoRandom(uint32_t seed) {
-    _x = static_cast<int32_t>(seed);
+    _x = seed;
     _y = default_y;
     _z = default_z;
     _w = default_w;
 }
 
+PseudoRandom::PseudoRandom(int32_t seed) : PseudoRandom(static_cast<uint32_t>(seed)) {}
 
-PseudoRandom::PseudoRandom(int64_t seed) {
-    int32_t high = seed >> 32;
-    int32_t low = seed & 0xFFFFFFFF;
+PseudoRandom::PseudoRandom(int64_t seed)
+    : PseudoRandom(static_cast<uint32_t>(seed >> 32) ^ static_cast<uint32_t>(seed)) {}
 
-    _x = high ^ low;
-    _y = default_y;
-    _z = default_z;
-    _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;
 }
 
@@ -179,4 +169,4 @@ SecureRandom* SecureRandom::create() {
 #error Must implement SecureRandom for platform
 
 #endif
-}
+}  // namespace mongo
diff --git a/src/mongo/platform/random.h b/src/mongo/platform/random.h
index 8d43284b9a1..76094e97690 100644
--- a/src/mongo/platform/random.h
+++ b/src/mongo/platform/random.h
@@ -57,20 +57,20 @@ public:
      * @return a number between 0 and max
      */
     int32_t nextInt32(int32_t max) {
-        return nextInt32() % 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;
+        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)
@@ -79,10 +79,12 @@ public:
     }
 
 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;
 };
 
 /**
@@ -98,4 +100,4 @@ public:
 
     static SecureRandom* create();
 };
-}
+}  // namespace mongo
diff --git a/src/mongo/platform/random_test.cpp b/src/mongo/platform/random_test.cpp
index c4e214f1af9..183ab03b3eb 100644
--- a/src/mongo/platform/random_test.cpp
+++ b/src/mongo/platform/random_test.cpp
@@ -29,6 +29,7 @@
  */
 
 #include <set>
+#include <vector>
 
 #include "mongo/platform/random.h"
 
@@ -145,6 +146,72 @@ TEST(RandomTest, NextCanonicalWithinRange) {
     }
 }
 
+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 (auto&& num : nums) {
+            bool isSet = (num >> 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 (auto&& num : nums) {
+            bool isSet = (num >> 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++) {
+        auto res = a.nextInt32(10);
+        ASSERT_GTE(res, 0);
+        ASSERT_LT(res, 10);
+    }
+}
+
+TEST(RandomTest, NextInt64InRange) {
+    PseudoRandom a(11);
+    for (int i = 0; i < 1000; i++) {
+        auto res = a.nextInt64(10);
+        ASSERT_GTE(res, 0);
+        ASSERT_LT(res, 10);
+    }
+}
+
 TEST(RandomTest, Secure1) {
     SecureRandom* a = SecureRandom::create();
     SecureRandom* b = SecureRandom::create();
diff --git a/src/mongo/scripting/bson_template_evaluator.cpp b/src/mongo/scripting/bson_template_evaluator.cpp
index 73efc05891c..6a1e15a644f 100644
--- a/src/mongo/scripting/bson_template_evaluator.cpp
+++ b/src/mongo/scripting/bson_template_evaluator.cpp
@@ -167,7 +167,7 @@ BsonTemplateEvaluator::Status BsonTemplateEvaluator::evalRandInt(BsonTemplateEva
     if (max <= min)
         return StatusOpEvaluationError;
     // range of max-min
-    int randomNum = min + (btl->rng.nextInt32() % (max - min));
+    int randomNum = min + (btl->rng.nextInt32(max - min));
     if (range.nFields() == 3) {
         if (!range[2].isNumber())
             return StatusOpEvaluationError;
@@ -189,7 +189,7 @@ BsonTemplateEvaluator::Status BsonTemplateEvaluator::evalRandPlusThread(BsonTemp
     const int max = range["1"].numberInt();
     if (max <= min)
         return StatusOpEvaluationError;
-    int randomNum = min + (btl->rng.nextInt32() % (max - min));
+    int randomNum = min + (btl->rng.nextInt32(max - min));
     randomNum += ((max - min) * btl->_id);
     out.append(fieldName, randomNum);
     return StatusSuccess;
@@ -267,7 +267,7 @@ BsonTemplateEvaluator::Status BsonTemplateEvaluator::evalRandString(BsonTemplate
         "0123456789+/";
     static const size_t alphaNumLength = sizeof(alphanum) - 1;
     static_assert(alphaNumLength == 64, "alphaNumLength == 64");
-    int32_t currentRand = 0;
+    uint32_t currentRand = 0;
     std::string str;
     for (int i = 0; i < length; ++i, currentRand >>= 6) {
         if (i % 5 == 0)
diff --git a/src/mongo/util/fail_point_test.cpp b/src/mongo/util/fail_point_test.cpp
index 4abed25d8b5..309361ca4a4 100644
--- a/src/mongo/util/fail_point_test.cpp
+++ b/src/mongo/util/fail_point_test.cpp
@@ -315,7 +315,7 @@ TEST(FailPoint, RandomActivationP5) {
     ASSERT_APPROX_EQUAL(500000,
                         runParallelFailPointTest(
                             FailPoint::random, std::numeric_limits<int32_t>::max() / 2, 10, 100000),
-                        500);
+                        1000);
 }
 
 TEST(FailPoint, RandomActivationP01) {