1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369
|
// Copyright 2011 The Chromium Authors
// 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 <stddef.h>
#include <stdint.h>
#include <algorithm>
#include <cmath>
#include <limits>
#include <memory>
#include <vector>
#include "base/logging.h"
#include "base/time/time.h"
#include "testing/gtest/include/gtest/gtest.h"
namespace base {
namespace {
const int kIntMin = std::numeric_limits<int>::min();
const int kIntMax = std::numeric_limits<int>::max();
} // namespace
TEST(RandUtilTest, RandInt) {
EXPECT_EQ(base::RandInt(0, 0), 0);
EXPECT_EQ(base::RandInt(kIntMin, kIntMin), kIntMin);
EXPECT_EQ(base::RandInt(kIntMax, kIntMax), kIntMax);
// Check that the DCHECKS in RandInt() don't fire due to internal overflow.
// There was a 50% chance of that happening, so calling it 40 times means
// the chances of this passing by accident are tiny (9e-13).
for (int i = 0; i < 40; ++i)
base::RandInt(kIntMin, kIntMax);
}
TEST(RandUtilTest, RandDouble) {
// Force 64-bit precision, making sure we're not in a 80-bit FPU register.
volatile double number = base::RandDouble();
EXPECT_GT(1.0, number);
EXPECT_LE(0.0, number);
}
TEST(RandUtilTest, RandFloat) {
// Force 32-bit precision, making sure we're not in an 80-bit FPU register.
volatile float number = base::RandFloat();
EXPECT_GT(1.f, number);
EXPECT_LE(0.f, number);
}
TEST(RandUtilTest, RandTimeDelta) {
{
const auto delta =
base::RandTimeDelta(-base::Seconds(2), -base::Seconds(1));
EXPECT_GE(delta, -base::Seconds(2));
EXPECT_LT(delta, -base::Seconds(1));
}
{
const auto delta = base::RandTimeDelta(-base::Seconds(2), base::Seconds(2));
EXPECT_GE(delta, -base::Seconds(2));
EXPECT_LT(delta, base::Seconds(2));
}
{
const auto delta = base::RandTimeDelta(base::Seconds(1), base::Seconds(2));
EXPECT_GE(delta, base::Seconds(1));
EXPECT_LT(delta, base::Seconds(2));
}
}
TEST(RandUtilTest, RandTimeDeltaUpTo) {
const auto delta = base::RandTimeDeltaUpTo(base::Seconds(2));
EXPECT_FALSE(delta.is_negative());
EXPECT_LT(delta, base::Seconds(2));
}
TEST(RandUtilTest, BitsToOpenEndedUnitInterval) {
// Force 64-bit precision, making sure we're not in an 80-bit FPU register.
volatile double all_zeros = BitsToOpenEndedUnitInterval(0x0);
EXPECT_EQ(0.0, all_zeros);
// Force 64-bit precision, making sure we're not in an 80-bit FPU register.
volatile double smallest_nonzero = BitsToOpenEndedUnitInterval(0x1);
EXPECT_LT(0.0, smallest_nonzero);
for (uint64_t i = 0x2; i < 0x10; ++i) {
// Force 64-bit precision, making sure we're not in an 80-bit FPU register.
volatile double number = BitsToOpenEndedUnitInterval(i);
EXPECT_EQ(i * smallest_nonzero, number);
}
// Force 64-bit precision, making sure we're not in an 80-bit FPU register.
volatile double all_ones = BitsToOpenEndedUnitInterval(UINT64_MAX);
EXPECT_GT(1.0, all_ones);
}
TEST(RandUtilTest, BitsToOpenEndedUnitIntervalF) {
// Force 32-bit precision, making sure we're not in an 80-bit FPU register.
volatile float all_zeros = BitsToOpenEndedUnitIntervalF(0x0);
EXPECT_EQ(0.f, all_zeros);
// Force 32-bit precision, making sure we're not in an 80-bit FPU register.
volatile float smallest_nonzero = BitsToOpenEndedUnitIntervalF(0x1);
EXPECT_LT(0.f, smallest_nonzero);
for (uint64_t i = 0x2; i < 0x10; ++i) {
// Force 32-bit precision, making sure we're not in an 80-bit FPU register.
volatile float number = BitsToOpenEndedUnitIntervalF(i);
EXPECT_EQ(i * smallest_nonzero, number);
}
// Force 32-bit precision, making sure we're not in an 80-bit FPU register.
volatile float all_ones = BitsToOpenEndedUnitIntervalF(UINT64_MAX);
EXPECT_GT(1.f, all_ones);
}
TEST(RandUtilTest, RandBytes) {
const size_t buffer_size = 50;
char buffer[buffer_size];
memset(buffer, 0, buffer_size);
base::RandBytes(buffer, buffer_size);
std::sort(buffer, buffer + buffer_size);
// Probability of occurrence of less than 25 unique bytes in 50 random bytes
// is below 10^-25.
EXPECT_GT(std::unique(buffer, buffer + buffer_size) - buffer, 25);
}
// Verify that calling base::RandBytes with an empty buffer doesn't fail.
TEST(RandUtilTest, RandBytes0) {
base::RandBytes(nullptr, 0);
}
TEST(RandUtilTest, RandBytesAsString) {
std::string random_string = base::RandBytesAsString(1);
EXPECT_EQ(1U, random_string.size());
random_string = base::RandBytesAsString(145);
EXPECT_EQ(145U, random_string.size());
char accumulator = 0;
for (auto i : random_string)
accumulator |= i;
// In theory this test can fail, but it won't before the universe dies of
// heat death.
EXPECT_NE(0, accumulator);
}
// Make sure that it is still appropriate to use RandGenerator in conjunction
// with std::random_shuffle().
TEST(RandUtilTest, RandGeneratorForRandomShuffle) {
EXPECT_EQ(base::RandGenerator(1), 0U);
EXPECT_LE(std::numeric_limits<ptrdiff_t>::max(),
std::numeric_limits<int64_t>::max());
}
TEST(RandUtilTest, RandGeneratorIsUniform) {
// Verify that RandGenerator has a uniform distribution. This is a
// regression test that consistently failed when RandGenerator was
// implemented this way:
//
// return base::RandUint64() % max;
//
// A degenerate case for such an implementation is e.g. a top of
// range that is 2/3rds of the way to MAX_UINT64, in which case the
// bottom half of the range would be twice as likely to occur as the
// top half. A bit of calculus care of jar@ shows that the largest
// measurable delta is when the top of the range is 3/4ths of the
// way, so that's what we use in the test.
constexpr uint64_t kTopOfRange =
(std::numeric_limits<uint64_t>::max() / 4ULL) * 3ULL;
constexpr double kExpectedAverage = static_cast<double>(kTopOfRange / 2);
constexpr double kAllowedVariance = kExpectedAverage / 50.0; // +/- 2%
constexpr int kMinAttempts = 1000;
constexpr int kMaxAttempts = 1000000;
double cumulative_average = 0.0;
int count = 0;
while (count < kMaxAttempts) {
uint64_t value = base::RandGenerator(kTopOfRange);
cumulative_average = (count * cumulative_average + value) / (count + 1);
// Don't quit too quickly for things to start converging, or we may have
// a false positive.
if (count > kMinAttempts &&
kExpectedAverage - kAllowedVariance < cumulative_average &&
cumulative_average < kExpectedAverage + kAllowedVariance) {
break;
}
++count;
}
ASSERT_LT(count, kMaxAttempts) << "Expected average was " << kExpectedAverage
<< ", average ended at " << cumulative_average;
}
TEST(RandUtilTest, RandUint64ProducesBothValuesOfAllBits) {
// This tests to see that our underlying random generator is good
// enough, for some value of good enough.
uint64_t kAllZeros = 0ULL;
uint64_t kAllOnes = ~kAllZeros;
uint64_t found_ones = kAllZeros;
uint64_t found_zeros = kAllOnes;
for (size_t i = 0; i < 1000; ++i) {
uint64_t value = base::RandUint64();
found_ones |= value;
found_zeros &= value;
if (found_zeros == kAllZeros && found_ones == kAllOnes)
return;
}
FAIL() << "Didn't achieve all bit values in maximum number of tries.";
}
TEST(RandUtilTest, RandBytesLonger) {
// Fuchsia can only retrieve 256 bytes of entropy at a time, so make sure we
// handle longer requests than that.
std::string random_string0 = base::RandBytesAsString(255);
EXPECT_EQ(255u, random_string0.size());
std::string random_string1 = base::RandBytesAsString(1023);
EXPECT_EQ(1023u, random_string1.size());
std::string random_string2 = base::RandBytesAsString(4097);
EXPECT_EQ(4097u, random_string2.size());
}
// Benchmark test for RandBytes(). Disabled since it's intentionally slow and
// does not test anything that isn't already tested by the existing RandBytes()
// tests.
TEST(RandUtilTest, DISABLED_RandBytesPerf) {
// Benchmark the performance of |kTestIterations| of RandBytes() using a
// buffer size of |kTestBufferSize|.
const int kTestIterations = 10;
const size_t kTestBufferSize = 1 * 1024 * 1024;
std::unique_ptr<uint8_t[]> buffer(new uint8_t[kTestBufferSize]);
const base::TimeTicks now = base::TimeTicks::Now();
for (int i = 0; i < kTestIterations; ++i)
base::RandBytes(buffer.get(), kTestBufferSize);
const base::TimeTicks end = base::TimeTicks::Now();
LOG(INFO) << "RandBytes(" << kTestBufferSize
<< ") took: " << (end - now).InMicroseconds() << "µs";
}
TEST(RandUtilTest, InsecureRandomGeneratorProducesBothValuesOfAllBits) {
// This tests to see that our underlying random generator is good
// enough, for some value of good enough.
uint64_t kAllZeros = 0ULL;
uint64_t kAllOnes = ~kAllZeros;
uint64_t found_ones = kAllZeros;
uint64_t found_zeros = kAllOnes;
InsecureRandomGenerator generator;
for (size_t i = 0; i < 1000; ++i) {
uint64_t value = generator.RandUint64();
found_ones |= value;
found_zeros &= value;
if (found_zeros == kAllZeros && found_ones == kAllOnes)
return;
}
FAIL() << "Didn't achieve all bit values in maximum number of tries.";
}
namespace {
constexpr double kXp1Percent = -2.33;
constexpr double kXp99Percent = 2.33;
double ChiSquaredCriticalValue(double nu, double x_p) {
// From "The Art Of Computer Programming" (TAOCP), Volume 2, Section 3.3.1,
// Table 1. This is the asymptotic value for nu > 30, up to O(1 / sqrt(nu)).
return nu + sqrt(2. * nu) * x_p + 2. / 3. * (x_p * x_p) - 2. / 3.;
}
int ExtractBits(uint64_t value, int from_bit, int num_bits) {
return (value >> from_bit) & ((1 << num_bits) - 1);
}
// Performs a Chi-Squared test on a subset of |num_bits| extracted starting from
// |from_bit| in the generated value.
//
// See TAOCP, Volume 2, Section 3.3.1, and
// https://en.wikipedia.org/wiki/Pearson%27s_chi-squared_test for details.
//
// This is only one of the many, many random number generator test we could do,
// but they are cumbersome, as they are typically very slow, and expected to
// fail from time to time, due to their probabilistic nature.
//
// The generator we use has however been vetted with the BigCrush test suite
// from Marsaglia, so this should suffice as a smoke test that our
// implementation is wrong.
bool ChiSquaredTest(InsecureRandomGenerator& gen,
size_t n,
int from_bit,
int num_bits) {
const int range = 1 << num_bits;
CHECK_EQ(static_cast<int>(n % range), 0) << "Makes computations simpler";
std::vector<size_t> samples(range, 0);
// Count how many samples pf each value are found. All buckets should be
// almost equal if the generator is suitably uniformly random.
for (size_t i = 0; i < n; i++) {
int sample = ExtractBits(gen.RandUint64(), from_bit, num_bits);
samples[sample] += 1;
}
// Compute the Chi-Squared statistic, which is:
// \Sum_{k=0}^{range-1} \frac{(count - expected)^2}{expected}
double chi_squared = 0.;
double expected_count = n / range;
for (size_t sample_count : samples) {
double deviation = sample_count - expected_count;
chi_squared += (deviation * deviation) / expected_count;
}
// The generator should produce numbers that are not too far of (chi_squared
// lower than a given quantile), but not too close to the ideal distribution
// either (chi_squared is too low).
//
// See The Art Of Computer Programming, Volume 2, Section 3.3.1 for details.
return chi_squared > ChiSquaredCriticalValue(range - 1, kXp1Percent) &&
chi_squared < ChiSquaredCriticalValue(range - 1, kXp99Percent);
}
} // namespace
TEST(RandUtilTest, InsecureRandomGeneratorChiSquared) {
constexpr int kIterations = 50;
// Specifically test the low bits, which are usually weaker in random number
// generators. We don't use them for the 32 bit number generation, but let's
// make sure they are still suitable.
for (int start_bit : {1, 2, 3, 8, 12, 20, 32, 48, 54}) {
int pass_count = 0;
for (int i = 0; i < kIterations; i++) {
size_t samples = 1 << 16;
InsecureRandomGenerator gen;
// Fix the seed to make the test non-flaky.
gen.ReseedForTesting(kIterations + 1);
bool pass = ChiSquaredTest(gen, samples, start_bit, 8);
pass_count += pass;
}
// We exclude 1% on each side, so we expect 98% of tests to pass, meaning 98
// * kIterations / 100. However this is asymptotic, so add a bit of leeway.
int expected_pass_count = (kIterations * 98) / 100;
EXPECT_GE(pass_count, expected_pass_count - ((kIterations * 2) / 100))
<< "For start_bit = " << start_bit;
}
}
TEST(RandUtilTest, InsecureRandomGeneratorRandDouble) {
InsecureRandomGenerator gen;
for (int i = 0; i < 1000; i++) {
volatile double x = gen.RandDouble();
EXPECT_GE(x, 0.);
EXPECT_LT(x, 1.);
}
}
} // namespace base
|