| OLD | NEW |
|---|
| (Empty) |
| 1 /* | |
| 2 * Copyright (c) 2015 The WebRTC project authors. All Rights Reserved. | |
| 3 * | |
| 4 * Use of this source code is governed by a BSD-style license | |
| 5 * that can be found in the LICENSE file in the root of the source | |
| 6 * tree. An additional intellectual property rights grant can be found | |
| 7 * in the file PATENTS. All contributing project authors may | |
| 8 * be found in the AUTHORS file in the root of the source tree. | |
| 9 */ | |
| 10 | |
| 11 #include <math.h> | |
| 12 | |
| 13 #include <limits> | |
| 14 #include <vector> | |
| 15 | |
| 16 #include "webrtc/base/mathutils.h" // unsigned difference | |
| 17 #include "webrtc/base/random.h" | |
| 18 #include "webrtc/test/gtest.h" | |
| 19 | |
| 20 namespace webrtc { | |
| 21 | |
| 22 namespace { | |
| 23 // Computes the positive remainder of x/n. | |
| 24 template <typename T> | |
| 25 T fdiv_remainder(T x, T n) { | |
| 26 RTC_CHECK_GE(n, 0); | |
| 27 T remainder = x % n; | |
| 28 if (remainder < 0) | |
| 29 remainder += n; | |
| 30 return remainder; | |
| 31 } | |
| 32 } // namespace | |
| 33 | |
| 34 // Sample a number of random integers of type T. Divide them into buckets | |
| 35 // based on the remainder when dividing by bucket_count and check that each | |
| 36 // bucket gets roughly the expected number of elements. | |
| 37 template <typename T> | |
| 38 void UniformBucketTest(T bucket_count, int samples, Random* prng) { | |
| 39 std::vector<int> buckets(bucket_count, 0); | |
| 40 | |
| 41 uint64_t total_values = 1ull << (std::numeric_limits<T>::digits + | |
| 42 std::numeric_limits<T>::is_signed); | |
| 43 T upper_limit = | |
| 44 std::numeric_limits<T>::max() - | |
| 45 static_cast<T>(total_values % static_cast<uint64_t>(bucket_count)); | |
| 46 ASSERT_GT(upper_limit, std::numeric_limits<T>::max() / 2); | |
| 47 | |
| 48 for (int i = 0; i < samples; i++) { | |
| 49 T sample; | |
| 50 do { | |
| 51 // We exclude a few numbers from the range so that it is divisible by | |
| 52 // the number of buckets. If we are unlucky and hit one of the excluded | |
| 53 // numbers we just resample. Note that if the number of buckets is a | |
| 54 // power of 2, then we don't have to exclude anything. | |
| 55 sample = prng->Rand<T>(); | |
| 56 } while (sample > upper_limit); | |
| 57 buckets[fdiv_remainder(sample, bucket_count)]++; | |
| 58 } | |
| 59 | |
| 60 for (T i = 0; i < bucket_count; i++) { | |
| 61 // Expect the result to be within 3 standard deviations of the mean. | |
| 62 EXPECT_NEAR(buckets[i], samples / bucket_count, | |
| 63 3 * sqrt(samples / bucket_count)); | |
| 64 } | |
| 65 } | |
| 66 | |
| 67 TEST(RandomNumberGeneratorTest, BucketTestSignedChar) { | |
| 68 Random prng(7297352569824ull); | |
| 69 UniformBucketTest<signed char>(64, 640000, &prng); | |
| 70 UniformBucketTest<signed char>(11, 440000, &prng); | |
| 71 UniformBucketTest<signed char>(3, 270000, &prng); | |
| 72 } | |
| 73 | |
| 74 TEST(RandomNumberGeneratorTest, BucketTestUnsignedChar) { | |
| 75 Random prng(7297352569824ull); | |
| 76 UniformBucketTest<unsigned char>(64, 640000, &prng); | |
| 77 UniformBucketTest<unsigned char>(11, 440000, &prng); | |
| 78 UniformBucketTest<unsigned char>(3, 270000, &prng); | |
| 79 } | |
| 80 | |
| 81 TEST(RandomNumberGeneratorTest, BucketTestSignedShort) { | |
| 82 Random prng(7297352569824ull); | |
| 83 UniformBucketTest<int16_t>(64, 640000, &prng); | |
| 84 UniformBucketTest<int16_t>(11, 440000, &prng); | |
| 85 UniformBucketTest<int16_t>(3, 270000, &prng); | |
| 86 } | |
| 87 | |
| 88 TEST(RandomNumberGeneratorTest, BucketTestUnsignedShort) { | |
| 89 Random prng(7297352569824ull); | |
| 90 UniformBucketTest<uint16_t>(64, 640000, &prng); | |
| 91 UniformBucketTest<uint16_t>(11, 440000, &prng); | |
| 92 UniformBucketTest<uint16_t>(3, 270000, &prng); | |
| 93 } | |
| 94 | |
| 95 TEST(RandomNumberGeneratorTest, BucketTestSignedInt) { | |
| 96 Random prng(7297352569824ull); | |
| 97 UniformBucketTest<signed int>(64, 640000, &prng); | |
| 98 UniformBucketTest<signed int>(11, 440000, &prng); | |
| 99 UniformBucketTest<signed int>(3, 270000, &prng); | |
| 100 } | |
| 101 | |
| 102 TEST(RandomNumberGeneratorTest, BucketTestUnsignedInt) { | |
| 103 Random prng(7297352569824ull); | |
| 104 UniformBucketTest<unsigned int>(64, 640000, &prng); | |
| 105 UniformBucketTest<unsigned int>(11, 440000, &prng); | |
| 106 UniformBucketTest<unsigned int>(3, 270000, &prng); | |
| 107 } | |
| 108 | |
| 109 // The range of the random numbers is divided into bucket_count intervals | |
| 110 // of consecutive numbers. Check that approximately equally many numbers | |
| 111 // from each inteval are generated. | |
| 112 void BucketTestSignedInterval(unsigned int bucket_count, | |
| 113 unsigned int samples, | |
| 114 int32_t low, | |
| 115 int32_t high, | |
| 116 int sigma_level, | |
| 117 Random* prng) { | |
| 118 std::vector<unsigned int> buckets(bucket_count, 0); | |
| 119 | |
| 120 ASSERT_GE(high, low); | |
| 121 ASSERT_GE(bucket_count, 2u); | |
| 122 uint32_t interval = unsigned_difference<int32_t>(high, low) + 1; | |
| 123 uint32_t numbers_per_bucket; | |
| 124 if (interval == 0) { | |
| 125 // The computation high - low + 1 should be 2^32 but overflowed | |
| 126 // Hence, bucket_count must be a power of 2 | |
| 127 ASSERT_EQ(bucket_count & (bucket_count - 1), 0u); | |
| 128 numbers_per_bucket = (0x80000000u / bucket_count) * 2; | |
| 129 } else { | |
| 130 ASSERT_EQ(interval % bucket_count, 0u); | |
| 131 numbers_per_bucket = interval / bucket_count; | |
| 132 } | |
| 133 | |
| 134 for (unsigned int i = 0; i < samples; i++) { | |
| 135 int32_t sample = prng->Rand(low, high); | |
| 136 EXPECT_LE(low, sample); | |
| 137 EXPECT_GE(high, sample); | |
| 138 buckets[unsigned_difference<int32_t>(sample, low) / numbers_per_bucket]++; | |
| 139 } | |
| 140 | |
| 141 for (unsigned int i = 0; i < bucket_count; i++) { | |
| 142 // Expect the result to be within 3 standard deviations of the mean, | |
| 143 // or more generally, within sigma_level standard deviations of the mean. | |
| 144 double mean = static_cast<double>(samples) / bucket_count; | |
| 145 EXPECT_NEAR(buckets[i], mean, sigma_level * sqrt(mean)); | |
| 146 } | |
| 147 } | |
| 148 | |
| 149 // The range of the random numbers is divided into bucket_count intervals | |
| 150 // of consecutive numbers. Check that approximately equally many numbers | |
| 151 // from each inteval are generated. | |
| 152 void BucketTestUnsignedInterval(unsigned int bucket_count, | |
| 153 unsigned int samples, | |
| 154 uint32_t low, | |
| 155 uint32_t high, | |
| 156 int sigma_level, | |
| 157 Random* prng) { | |
| 158 std::vector<unsigned int> buckets(bucket_count, 0); | |
| 159 | |
| 160 ASSERT_GE(high, low); | |
| 161 ASSERT_GE(bucket_count, 2u); | |
| 162 uint32_t interval = high - low + 1; | |
| 163 uint32_t numbers_per_bucket; | |
| 164 if (interval == 0) { | |
| 165 // The computation high - low + 1 should be 2^32 but overflowed | |
| 166 // Hence, bucket_count must be a power of 2 | |
| 167 ASSERT_EQ(bucket_count & (bucket_count - 1), 0u); | |
| 168 numbers_per_bucket = (0x80000000u / bucket_count) * 2; | |
| 169 } else { | |
| 170 ASSERT_EQ(interval % bucket_count, 0u); | |
| 171 numbers_per_bucket = interval / bucket_count; | |
| 172 } | |
| 173 | |
| 174 for (unsigned int i = 0; i < samples; i++) { | |
| 175 uint32_t sample = prng->Rand(low, high); | |
| 176 EXPECT_LE(low, sample); | |
| 177 EXPECT_GE(high, sample); | |
| 178 buckets[(sample - low) / numbers_per_bucket]++; | |
| 179 } | |
| 180 | |
| 181 for (unsigned int i = 0; i < bucket_count; i++) { | |
| 182 // Expect the result to be within 3 standard deviations of the mean, | |
| 183 // or more generally, within sigma_level standard deviations of the mean. | |
| 184 double mean = static_cast<double>(samples) / bucket_count; | |
| 185 EXPECT_NEAR(buckets[i], mean, sigma_level * sqrt(mean)); | |
| 186 } | |
| 187 } | |
| 188 | |
| 189 TEST(RandomNumberGeneratorTest, UniformUnsignedInterval) { | |
| 190 Random prng(299792458ull); | |
| 191 BucketTestUnsignedInterval(2, 100000, 0, 1, 3, &prng); | |
| 192 BucketTestUnsignedInterval(7, 100000, 1, 14, 3, &prng); | |
| 193 BucketTestUnsignedInterval(11, 100000, 1000, 1010, 3, &prng); | |
| 194 BucketTestUnsignedInterval(100, 100000, 0, 99, 3, &prng); | |
| 195 BucketTestUnsignedInterval(2, 100000, 0, 4294967295, 3, &prng); | |
| 196 BucketTestUnsignedInterval(17, 100000, 455, 2147484110, 3, &prng); | |
| 197 // 99.7% of all samples will be within 3 standard deviations of the mean, | |
| 198 // but since we test 1000 buckets we allow an interval of 4 sigma. | |
| 199 BucketTestUnsignedInterval(1000, 1000000, 0, 2147483999, 4, &prng); | |
| 200 } | |
| 201 | |
| 202 // Disabled for UBSan: https://bugs.chromium.org/p/webrtc/issues/detail?id=5491 | |
| 203 #ifdef UNDEFINED_SANITIZER | |
| 204 #define MAYBE_UniformSignedInterval DISABLED_UniformSignedInterval | |
| 205 #else | |
| 206 #define MAYBE_UniformSignedInterval UniformSignedInterval | |
| 207 #endif | |
| 208 TEST(RandomNumberGeneratorTest, MAYBE_UniformSignedInterval) { | |
| 209 Random prng(66260695729ull); | |
| 210 BucketTestSignedInterval(2, 100000, 0, 1, 3, &prng); | |
| 211 BucketTestSignedInterval(7, 100000, -2, 4, 3, &prng); | |
| 212 BucketTestSignedInterval(11, 100000, 1000, 1010, 3, &prng); | |
| 213 BucketTestSignedInterval(100, 100000, 0, 99, 3, &prng); | |
| 214 BucketTestSignedInterval(2, 100000, std::numeric_limits<int32_t>::min(), | |
| 215 std::numeric_limits<int32_t>::max(), 3, &prng); | |
| 216 BucketTestSignedInterval(17, 100000, -1073741826, 1073741829, 3, &prng); | |
| 217 // 99.7% of all samples will be within 3 standard deviations of the mean, | |
| 218 // but since we test 1000 buckets we allow an interval of 4 sigma. | |
| 219 BucketTestSignedInterval(1000, 1000000, -352, 2147483647, 4, &prng); | |
| 220 } | |
| 221 | |
| 222 // The range of the random numbers is divided into bucket_count intervals | |
| 223 // of consecutive numbers. Check that approximately equally many numbers | |
| 224 // from each inteval are generated. | |
| 225 void BucketTestFloat(unsigned int bucket_count, | |
| 226 unsigned int samples, | |
| 227 int sigma_level, | |
| 228 Random* prng) { | |
| 229 ASSERT_GE(bucket_count, 2u); | |
| 230 std::vector<unsigned int> buckets(bucket_count, 0); | |
| 231 | |
| 232 for (unsigned int i = 0; i < samples; i++) { | |
| 233 uint32_t sample = bucket_count * prng->Rand<float>(); | |
| 234 EXPECT_LE(0u, sample); | |
| 235 EXPECT_GE(bucket_count - 1, sample); | |
| 236 buckets[sample]++; | |
| 237 } | |
| 238 | |
| 239 for (unsigned int i = 0; i < bucket_count; i++) { | |
| 240 // Expect the result to be within 3 standard deviations of the mean, | |
| 241 // or more generally, within sigma_level standard deviations of the mean. | |
| 242 double mean = static_cast<double>(samples) / bucket_count; | |
| 243 EXPECT_NEAR(buckets[i], mean, sigma_level * sqrt(mean)); | |
| 244 } | |
| 245 } | |
| 246 | |
| 247 TEST(RandomNumberGeneratorTest, UniformFloatInterval) { | |
| 248 Random prng(1380648813ull); | |
| 249 BucketTestFloat(100, 100000, 3, &prng); | |
| 250 // 99.7% of all samples will be within 3 standard deviations of the mean, | |
| 251 // but since we test 1000 buckets we allow an interval of 4 sigma. | |
| 252 // BucketTestSignedInterval(1000, 1000000, -352, 2147483647, 4, &prng); | |
| 253 } | |
| 254 | |
| 255 TEST(RandomNumberGeneratorTest, SignedHasSameBitPattern) { | |
| 256 Random prng_signed(66738480ull), prng_unsigned(66738480ull); | |
| 257 | |
| 258 for (int i = 0; i < 1000; i++) { | |
| 259 signed int s = prng_signed.Rand<signed int>(); | |
| 260 unsigned int u = prng_unsigned.Rand<unsigned int>(); | |
| 261 EXPECT_EQ(u, static_cast<unsigned int>(s)); | |
| 262 } | |
| 263 | |
| 264 for (int i = 0; i < 1000; i++) { | |
| 265 int16_t s = prng_signed.Rand<int16_t>(); | |
| 266 uint16_t u = prng_unsigned.Rand<uint16_t>(); | |
| 267 EXPECT_EQ(u, static_cast<uint16_t>(s)); | |
| 268 } | |
| 269 | |
| 270 for (int i = 0; i < 1000; i++) { | |
| 271 signed char s = prng_signed.Rand<signed char>(); | |
| 272 unsigned char u = prng_unsigned.Rand<unsigned char>(); | |
| 273 EXPECT_EQ(u, static_cast<unsigned char>(s)); | |
| 274 } | |
| 275 } | |
| 276 | |
| 277 TEST(RandomNumberGeneratorTest, Gaussian) { | |
| 278 const int kN = 100000; | |
| 279 const int kBuckets = 100; | |
| 280 const double kMean = 49; | |
| 281 const double kStddev = 10; | |
| 282 | |
| 283 Random prng(1256637061); | |
| 284 | |
| 285 std::vector<unsigned int> buckets(kBuckets, 0); | |
| 286 for (int i = 0; i < kN; i++) { | |
| 287 int index = prng.Gaussian(kMean, kStddev) + 0.5; | |
| 288 if (index >= 0 && index < kBuckets) { | |
| 289 buckets[index]++; | |
| 290 } | |
| 291 } | |
| 292 | |
| 293 const double kPi = 3.14159265358979323846; | |
| 294 const double kScale = 1 / (kStddev * sqrt(2.0 * kPi)); | |
| 295 const double kDiv = -2.0 * kStddev * kStddev; | |
| 296 for (int n = 0; n < kBuckets; ++n) { | |
| 297 // Use Simpsons rule to estimate the probability that a random gaussian | |
| 298 // sample is in the interval [n-0.5, n+0.5]. | |
| 299 double f_left = kScale * exp((n - kMean - 0.5) * (n - kMean - 0.5) / kDiv); | |
| 300 double f_mid = kScale * exp((n - kMean) * (n - kMean) / kDiv); | |
| 301 double f_right = kScale * exp((n - kMean + 0.5) * (n - kMean + 0.5) / kDiv); | |
| 302 double normal_dist = (f_left + 4 * f_mid + f_right) / 6; | |
| 303 // Expect the number of samples to be within 3 standard deviations | |
| 304 // (rounded up) of the expected number of samples in the bucket. | |
| 305 EXPECT_NEAR(buckets[n], kN * normal_dist, 3 * sqrt(kN * normal_dist) + 1); | |
| 306 } | |
| 307 } | |
| 308 | |
| 309 } // namespace webrtc | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2877023002:
Move webrtc/{base => rtc_base} (Closed)
