310 lines
12 KiB
C++
310 lines
12 KiB
C++
|
/*
|
||
|
|
* 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/mathutils.h" // unsigned difference
|
||
|
|
#include "webrtc/base/random.h"
|
||
|
|
|
||
|
|
namespace webrtc {
|
||
|
|
|
||
|
|
namespace {
|
||
|
|
// Computes the positive remainder of x/n.
|
||
|
|
template <typename T>
|
||
|
|
T fdiv_remainder(T x, T n) {
|
||
|
|
RTC_CHECK_GE(n, static_cast<T>(0));
|
||
|
|
T remainder = x % n;
|
||
|
|
if (remainder < 0)
|
||
|
|
remainder += n;
|
||
|
|
return remainder;
|
||
|
|
}
|
||
|
|
} // namespace
|
||
|
|
|
||
|
|
// Sample a number of random integers of type T. Divide them into buckets
|
||
|
|
// based on the remainder when dividing by bucket_count and check that each
|
||
|
|
// bucket gets roughly the expected number of elements.
|
||
|
|
template <typename T>
|
||
|
|
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_GT(upper_limit, std::numeric_limits<T>::max() / 2);
|
||
|
|
|
||
|
|
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 of 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);
|
||
|
|
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_GE(high, low);
|
||
|
|
ASSERT_GE(bucket_count, 2u);
|
||
|
|
uint32_t interval = unsigned_difference<int32_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_EQ(bucket_count & (bucket_count - 1), 0u);
|
||
|
|
numbers_per_bucket = (0x80000000u / bucket_count) * 2;
|
||
|
|
} else {
|
||
|
|
ASSERT_EQ(interval % bucket_count, 0u);
|
||
|
|
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[unsigned_difference<int32_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_GE(high, low);
|
||
|
|
ASSERT_GE(bucket_count, 2u);
|
||
|
|
uint32_t interval = 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_EQ(bucket_count & (bucket_count - 1), 0u);
|
||
|
|
numbers_per_bucket = (0x80000000u / bucket_count) * 2;
|
||
|
|
} else {
|
||
|
|
ASSERT_EQ(interval % bucket_count, 0u);
|
||
|
|
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[(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);
|
||
|
|
}
|
||
|
|
|
||
|
|
// Disabled for UBSan: https://bugs.chromium.org/p/webrtc/issues/detail?id=5491
|
||
|
|
#ifdef UNDEFINED_SANITIZER
|
||
|
|
#define MAYBE_UniformSignedInterval DISABLED_UniformSignedInterval
|
||
|
|
#else
|
||
|
|
#define MAYBE_UniformSignedInterval UniformSignedInterval
|
||
|
|
#endif
|
||
|
|
TEST(RandomNumberGeneratorTest, MAYBE_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_GE(bucket_count, 2u);
|
||
|
|
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].
|
||
|
|
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
|