Rewrote the PRNG using an xorshift* algorithm and moved the files from test/ to base/.

webrtc/base/random_unittest.cc

Index: webrtc/base/random_unittest.cc
diff --git a/webrtc/base/random_unittest.cc b/webrtc/base/random_unittest.cc
new file mode 100644
index 0000000000000000000000000000000000000000..9f5fbe6e617a630027f4d68976c20e75568177d7
--- /dev/null
+++ b/webrtc/base/random_unittest.cc
@@ -0,0 +1,299 @@
+/*
+ *  Copyright (c) 2015 The WebRTC project authors. All Rights Reserved.
+ *
+ *  Use of this source code is governed by a BSD-style license
+ *  that can be found in the LICENSE file in the root of the source
+ *  tree. An additional intellectual property rights grant can be found
+ *  in the file PATENTS.  All contributing project authors may
+ *  be found in the AUTHORS file in the root of the source tree.
+ */
+
+#include <math.h>
+
+#include <limits>
+#include <vector>
+
+#include "testing/gtest/include/gtest/gtest.h"
+#include "webrtc/base/checks.h"

[the sun, 2015/11/25 10:12:37]

Not needed?

[terelius, 2015/11/27 10:35:23]

Done.

+#include "webrtc/base/random.h"
+
+namespace webrtc {
+
+namespace {
+template <typename T>
+T fdiv_remainder(T x, T n) {
+  assert(n > 0);

[the sun, 2015/11/25 10:12:37]

ASSERT_GT()

[terelius, 2015/11/27 10:35:24]

ASSERT requires a void function. In this case I think it is perfectly reasonable
to kill the test upon triggering the assertion since the assertion is a sanity
check on the test case itself. The assertion essentially says that the number of
buckets needs to be positive, or equivalently that we need space for at least
one element in a vector to store the result.

[the sun, 2015/11/27 11:02:10]

Don't use stdlib assert(). gtest's ASSERT_nn or EXPECT_nn should work fine here.

[pbos-webrtc, 2015/11/27 11:06:28]

Feel free to use RTC_(D)CHECK_GT if all else fails. :)

[terelius, 2015/11/27 11:46:07]

ASSERT does not work since the function does not return void. EXPECT would
compile, but the program would likely crash when trying to execute the
subsequent lines after a failure.

[terelius, 2015/11/27 11:46:07]

Yeah, that would work. Thanks.

+  T remainder = x % n;
+  if (remainder < 0)
+    remainder += n;
+  return remainder;
+}
+}  // namespace
+
+template <typename T>

[the sun, 2015/11/25 10:12:37]

Can you describe the test method, or provide a link?

[terelius, 2015/11/27 10:35:24]

Done. This is not some sophisticated test for randomness.
It merely samples some numbers, divides them into buckets
(in this case based on the remainder when dividing by
the number of buckets) and verifies that all buckets receive
approximately the same number of elements.

I've added a comment to this effect. 

+void UniformBucketTest(T bucket_count, int samples, Random* prng) {
+  std::vector<int> buckets(bucket_count, 0);
+
+  uint64_t total_values = 1ull << (std::numeric_limits<T>::digits +
+                                   std::numeric_limits<T>::is_signed);
+  T upper_limit =
+      std::numeric_limits<T>::max() -
+      static_cast<T>(total_values % static_cast<uint64_t>(bucket_count));
+  assert(upper_limit > std::numeric_limits<T>::max() / 2);

[the sun, 2015/11/25 10:12:38]

ASSERT_GT()

...and other assert()s below.

[terelius, 2015/11/27 10:35:24]

Done.

+
+  for (int i = 0; i < samples; i++) {
+    T sample;
+    do {
+      // We exclude a few numbers from the range so that it is divisible by
+      // the number of buckets. If we are unlucky and hit one of the excluded
+      // numbers we just resample. Note that if the number buckets is a power
+      // of 2, then we don't have to exclude anything.
+      sample = prng->Rand<T>();
+    } while (sample > upper_limit);
+    buckets[fdiv_remainder(sample, bucket_count)]++;
+  }
+
+  for (T i = 0; i < bucket_count; i++) {
+    // Expect the result to be within 3 standard deviations of the mean.
+    EXPECT_NEAR(buckets[i], samples / bucket_count,
+                3 * sqrt(samples / bucket_count));
+  }
+}
+
+TEST(RandomNumberGeneratorTest, BucketTestSignedChar) {
+  Random prng(7297352569824ull);
+  UniformBucketTest<signed char>(64, 640000, &prng);

[the sun, 2015/11/25 10:12:37]

Are these number empiric or from some calculation?

[terelius, 2015/11/27 10:35:24]

Neither. It is just a call that says "Generate 640000 random numbers, distribute
them evenly in 64 buckets and check that each bucket has approximately the same
number of elements in them." I vary the number of buckets to test powers of two,
odd numbers close to powers of two and odd numbers far from powers of two.

+  UniformBucketTest<signed char>(11, 440000, &prng);
+  UniformBucketTest<signed char>(3, 270000, &prng);
+}
+
+TEST(RandomNumberGeneratorTest, BucketTestUnsignedChar) {
+  Random prng(7297352569824ull);
+  UniformBucketTest<unsigned char>(64, 640000, &prng);
+  UniformBucketTest<unsigned char>(11, 440000, &prng);
+  UniformBucketTest<unsigned char>(3, 270000, &prng);
+}
+
+TEST(RandomNumberGeneratorTest, BucketTestSignedShort) {
+  Random prng(7297352569824ull);
+  UniformBucketTest<int16_t>(64, 640000, &prng);
+  UniformBucketTest<int16_t>(11, 440000, &prng);
+  UniformBucketTest<int16_t>(3, 270000, &prng);
+}
+
+TEST(RandomNumberGeneratorTest, BucketTestUnsignedShort) {
+  Random prng(7297352569824ull);
+  UniformBucketTest<uint16_t>(64, 640000, &prng);
+  UniformBucketTest<uint16_t>(11, 440000, &prng);
+  UniformBucketTest<uint16_t>(3, 270000, &prng);
+}
+
+TEST(RandomNumberGeneratorTest, BucketTestSignedInt) {
+  Random prng(7297352569824ull);
+  UniformBucketTest<signed int>(64, 640000, &prng);
+  UniformBucketTest<signed int>(11, 440000, &prng);
+  UniformBucketTest<signed int>(3, 270000, &prng);
+}
+
+TEST(RandomNumberGeneratorTest, BucketTestUnsignedInt) {
+  Random prng(7297352569824ull);
+  UniformBucketTest<unsigned int>(64, 640000, &prng);
+  UniformBucketTest<unsigned int>(11, 440000, &prng);
+  UniformBucketTest<unsigned int>(3, 270000, &prng);
+}
+
+// The range of the random numbers is divided into bucket count intervals
+// of consecutive numbers. Check that approximately equally many numbers
+// from each inteval are generated.
+void BucketTestSignedInterval(unsigned int bucket_count,
+                              unsigned int samples,
+                              int32_t low,
+                              int32_t high,
+                              int sigma_level,
+                              Random* prng) {
+  std::vector<unsigned int> buckets(bucket_count, 0);
+
+  assert(high >= low);
+  assert(bucket_count >= 2);
+  uint32_t interval = static_cast<uint32_t>(high - low + 1);
+  uint32_t numbers_per_bucket;
+  if (interval == 0) {
+    // The computation high - low + 1 should be 2^32 but overflowed
+    // Hence, bucket_count must be a power of 2
+    assert((bucket_count & (bucket_count - 1)) == 0);
+    numbers_per_bucket = (0x80000000u / bucket_count) * 2;
+  } else {
+    assert(interval % bucket_count == 0);
+    numbers_per_bucket = interval / bucket_count;
+  }
+
+  for (unsigned int i = 0; i < samples; i++) {
+    int32_t sample = prng->Rand(low, high);
+    EXPECT_LE(low, sample);
+    EXPECT_GE(high, sample);
+    buckets[static_cast<uint32_t>(sample - low) / numbers_per_bucket]++;
+  }
+
+  for (unsigned int i = 0; i < bucket_count; i++) {
+    // Expect the result to be within 3 standard deviations of the mean,
+    // or more generally, within sigma_level standard deviations of the mean.
+    double mean = static_cast<double>(samples) / bucket_count;
+    EXPECT_NEAR(buckets[i], mean, sigma_level * sqrt(mean));
+  }
+}
+
+// The range of the random numbers is divided into bucket count intervals
+// of consecutive numbers. Check that approximately equally many numbers
+// from each inteval are generated.
+void BucketTestUnsignedInterval(unsigned int bucket_count,
+                                unsigned int samples,
+                                uint32_t low,
+                                uint32_t high,
+                                int sigma_level,
+                                Random* prng) {
+  std::vector<unsigned int> buckets(bucket_count, 0);
+
+  assert(high >= low);
+  assert(bucket_count >= 2);
+  uint32_t interval = static_cast<uint32_t>(high - low + 1);
+  uint32_t numbers_per_bucket;
+  if (interval == 0) {
+    // The computation high - low + 1 should be 2^32 but overflowed
+    // Hence, bucket_count must be a power of 2
+    assert((bucket_count & (bucket_count - 1)) == 0);
+    numbers_per_bucket = (0x80000000u / bucket_count) * 2;
+  } else {
+    assert(interval % bucket_count == 0);
+    numbers_per_bucket = interval / bucket_count;
+  }
+
+  for (unsigned int i = 0; i < samples; i++) {
+    uint32_t sample = prng->Rand(low, high);
+    EXPECT_LE(low, sample);
+    EXPECT_GE(high, sample);
+    buckets[static_cast<uint32_t>(sample - low) / numbers_per_bucket]++;
+  }
+
+  for (unsigned int i = 0; i < bucket_count; i++) {
+    // Expect the result to be within 3 standard deviations of the mean,
+    // or more generally, within sigma_level standard deviations of the mean.
+    double mean = static_cast<double>(samples) / bucket_count;
+    EXPECT_NEAR(buckets[i], mean, sigma_level * sqrt(mean));
+  }
+}
+
+TEST(RandomNumberGeneratorTest, UniformUnsignedInterval) {
+  Random prng(299792458ull);
+  BucketTestUnsignedInterval(2, 100000, 0, 1, 3, &prng);
+  BucketTestUnsignedInterval(7, 100000, 1, 14, 3, &prng);
+  BucketTestUnsignedInterval(11, 100000, 1000, 1010, 3, &prng);
+  BucketTestUnsignedInterval(100, 100000, 0, 99, 3, &prng);
+  BucketTestUnsignedInterval(2, 100000, 0, 4294967295, 3, &prng);
+  BucketTestUnsignedInterval(17, 100000, 455, 2147484110, 3, &prng);
+  // 99.7% of all samples will be within 3 standard deviations of the mean,
+  // but since we test 1000 buckets we allow an interval of 4 sigma.
+  BucketTestUnsignedInterval(1000, 1000000, 0, 2147483999, 4, &prng);
+}
+
+TEST(RandomNumberGeneratorTest, UniformSignedInterval) {
+  Random prng(66260695729ull);
+  BucketTestSignedInterval(2, 100000, 0, 1, 3, &prng);
+  BucketTestSignedInterval(7, 100000, -2, 4, 3, &prng);
+  BucketTestSignedInterval(11, 100000, 1000, 1010, 3, &prng);
+  BucketTestSignedInterval(100, 100000, 0, 99, 3, &prng);
+  BucketTestSignedInterval(2, 100000, std::numeric_limits<int32_t>::min(),
+                           std::numeric_limits<int32_t>::max(), 3, &prng);
+  BucketTestSignedInterval(17, 100000, -1073741826, 1073741829, 3, &prng);
+  // 99.7% of all samples will be within 3 standard deviations of the mean,
+  // but since we test 1000 buckets we allow an interval of 4 sigma.
+  BucketTestSignedInterval(1000, 1000000, -352, 2147483647, 4, &prng);
+}
+
+// The range of the random numbers is divided into bucket count intervals
+// of consecutive numbers. Check that approximately equally many numbers
+// from each inteval are generated.
+void BucketTestFloat(unsigned int bucket_count,
+                     unsigned int samples,
+                     int sigma_level,
+                     Random* prng) {
+  assert(bucket_count >= 2);
+  std::vector<unsigned int> buckets(bucket_count, 0);
+
+  for (unsigned int i = 0; i < samples; i++) {
+    uint32_t sample = bucket_count * prng->Rand<float>();
+    EXPECT_LE(0u, sample);
+    EXPECT_GE(bucket_count - 1, sample);
+    buckets[sample]++;
+  }
+
+  for (unsigned int i = 0; i < bucket_count; i++) {
+    // Expect the result to be within 3 standard deviations of the mean,
+    // or more generally, within sigma_level standard deviations of the mean.
+    double mean = static_cast<double>(samples) / bucket_count;
+    EXPECT_NEAR(buckets[i], mean, sigma_level * sqrt(mean));
+  }
+}
+
+TEST(RandomNumberGeneratorTest, UniformFloatInterval) {
+  Random prng(1380648813ull);
+  BucketTestFloat(100, 100000, 3, &prng);
+  // 99.7% of all samples will be within 3 standard deviations of the mean,
+  // but since we test 1000 buckets we allow an interval of 4 sigma.
+  // BucketTestSignedInterval(1000, 1000000, -352, 2147483647, 4, &prng);
+}
+
+TEST(RandomNumberGeneratorTest, SignedHasSameBitPattern) {
+  Random prng_signed(66738480ull), prng_unsigned(66738480ull);
+
+  for (int i = 0; i < 1000; i++) {
+    signed int s = prng_signed.Rand<signed int>();
+    unsigned int u = prng_unsigned.Rand<unsigned int>();
+    EXPECT_EQ(u, static_cast<unsigned int>(s));
+  }
+
+  for (int i = 0; i < 1000; i++) {
+    int16_t s = prng_signed.Rand<int16_t>();
+    uint16_t u = prng_unsigned.Rand<uint16_t>();
+    EXPECT_EQ(u, static_cast<uint16_t>(s));
+  }
+
+  for (int i = 0; i < 1000; i++) {
+    signed char s = prng_signed.Rand<signed char>();
+    unsigned char u = prng_unsigned.Rand<unsigned char>();
+    EXPECT_EQ(u, static_cast<unsigned char>(s));
+  }
+}
+
+TEST(RandomNumberGeneratorTest, Gaussian) {
+  const int kN = 100000;
+  const int kBuckets = 100;
+  const double kMean = 49;
+  const double kStddev = 10;
+
+  Random prng(1256637061);
+
+  std::vector<unsigned int> buckets(kBuckets, 0);
+  for (int i = 0; i < kN; i++) {
+    int index = prng.Gaussian(kMean, kStddev) + 0.5;
+    if (index >= 0 && index < kBuckets) {
+      buckets[index]++;
+    }
+  }
+
+  const double kPi = 3.14159265358979323846;
+  const double kScale = 1 / (kStddev * sqrt(2.0 * kPi));
+  const double kDiv = -2.0 * kStddev * kStddev;
+  for (int n = 0; n < kBuckets; ++n) {
+    // Use Simpsons rule to estimate the probability that a random gaussian
+    // sample is in the interval [n-0.5, n-0.5].

[the sun, 2015/11/25 10:12:37]

That's an awfully small interval.

[terelius, 2015/11/27 10:35:24]

In this test, we draw a real number x from a gaussian distribution and round it
to the nearest integer n.

We want to know the probability of getting a particular integer n. If x is
rounded to n, then x must be in the interval [n-0.5, n+0.5). The probability
that x is in [a, b) is the integral from a to b of the probability density
function p(x). Since the interval is fairly small, we can estimate the integral
using a small number of points. The previous version of this test (located in
remote_bitrate_estimator) used only one point. I increased it to 3 points to get
a more accurate estimate, but the difference is likely small for the parameters
we are testing.

[the sun, 2015/11/27 11:02:10]

But isn't the comment wrong? "[n-0.5, n-0.5]"

[terelius, 2015/11/27 11:46:07]

Oh, sorry. Updated comment.

+    double f_left = kScale * exp((n - kMean - 0.5) * (n - kMean - 0.5) / kDiv);
+    double f_mid = kScale * exp((n - kMean) * (n - kMean) / kDiv);
+    double f_right = kScale * exp((n - kMean + 0.5) * (n - kMean + 0.5) / kDiv);
+    double normal_dist = (f_left + 4 * f_mid + f_right) / 6;
+    // Expect the number of samples to be within 3 standard deviations
+    // (rounded up) of the expected number of samples in the bucket.
+    EXPECT_NEAR(buckets[n], kN * normal_dist, 3 * sqrt(kN * normal_dist) + 1);
+  }
+}
+
+}  // namespace webrtc