Fix base::RandGenerator bug (it had non-uniform random distribution).

base/rand_util.cc

 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "base/rand_util.h"
 
 #include <math.h>
 
 #include <limits>
 
@@ skipping 27 matching lines @@
   static const int kBits = std::numeric_limits<double>::digits;
   uint64 random_bits = bits & ((GG_UINT64_C(1) << kBits) - 1);
   double result = ldexp(static_cast<double>(random_bits), -1 * kBits);
   DCHECK_GE(result, 0.0);
   DCHECK_LT(result, 1.0);
   return result;
 }
 
 uint64 RandGenerator(uint64 max) {
   DCHECK_GT(max, 0ULL);
-  return base::RandUint64() % max;
+
+  // We must discard random results above this number, as they would
+  // make the random generator non-uniform (consider e.g. if
+  // MAX_UINT64 was 4 and max was 3, then a result of 1 would be twice
+  // as likely as a result of 0 or 2).
+  uint64 max_acceptable_value =
+      (std::numeric_limits<uint64>::max() / max) * max;
+
+  uint64 value;
+  do {
+    value = base::RandUint64();
+  } while (value >= max_acceptable_value);
+
+  return value % max;
 }
 
 void RandBytes(void* output, size_t output_length) {
   uint64 random_int;
   size_t random_int_size = sizeof(random_int);
   for (size_t i = 0; i < output_length; i += random_int_size) {
     random_int = base::RandUint64();
     size_t copy_count = std::min(output_length - i, random_int_size);
     memcpy(((uint8*)output) + i, &random_int, copy_count);
   }
 }
 
 std::string RandBytesAsString(size_t length) {
   std::string result;
   RandBytes(WriteInto(&result, length + 1), length);
   return result;
 }
 
 }  // namespace base