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
|
// 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 <limits.h>
#include <math.h>
#include <stdint.h>
#include <algorithm>
#include <limits>
#include "base/check_op.h"
#include "base/strings/string_util.h"
#include "base/time/time.h"
namespace base {
namespace {
bool g_subsampling_enabled = true;
} // namespace
uint64_t RandUint64() {
uint64_t number;
RandBytes(&number, sizeof(number));
return number;
}
int RandInt(int min, int max) {
DCHECK_LE(min, max);
uint64_t range = static_cast<uint64_t>(max) - static_cast<uint64_t>(min) + 1;
// |range| is at most UINT_MAX + 1, so the result of RandGenerator(range)
// is at most UINT_MAX. Hence it's safe to cast it from uint64_t to int64_t.
int result =
static_cast<int>(min + static_cast<int64_t>(base::RandGenerator(range)));
DCHECK_GE(result, min);
DCHECK_LE(result, max);
return result;
}
double RandDouble() {
return BitsToOpenEndedUnitInterval(base::RandUint64());
}
float RandFloat() {
return BitsToOpenEndedUnitIntervalF(base::RandUint64());
}
TimeDelta RandTimeDelta(TimeDelta start, TimeDelta limit) {
// We must have a finite, non-empty, non-reversed interval.
CHECK_LT(start, limit);
CHECK(!start.is_min());
CHECK(!limit.is_max());
const int64_t range = (limit - start).InMicroseconds();
// Because of the `CHECK_LT()` above, range > 0, so this cast is safe.
const uint64_t delta_us = base::RandGenerator(static_cast<uint64_t>(range));
// ...and because `range` fit in an `int64_t`, so will `delta_us`.
return start + Microseconds(static_cast<int64_t>(delta_us));
}
TimeDelta RandTimeDeltaUpTo(TimeDelta limit) {
return RandTimeDelta(TimeDelta(), limit);
}
double BitsToOpenEndedUnitInterval(uint64_t bits) {
// We try to get maximum precision by masking out as many bits as will fit
// in the target type's mantissa, and raising it to an appropriate power to
// produce output in the range [0, 1). For IEEE 754 doubles, the mantissa
// is expected to accommodate 53 bits (including the implied bit).
static_assert(std::numeric_limits<double>::radix == 2,
"otherwise use scalbn");
constexpr int kBits = std::numeric_limits<double>::digits;
return ldexp(bits & ((UINT64_C(1) << kBits) - 1u), -kBits);
}
float BitsToOpenEndedUnitIntervalF(uint64_t bits) {
// We try to get maximum precision by masking out as many bits as will fit
// in the target type's mantissa, and raising it to an appropriate power to
// produce output in the range [0, 1). For IEEE 754 floats, the mantissa is
// expected to accommodate 12 bits (including the implied bit).
static_assert(std::numeric_limits<float>::radix == 2, "otherwise use scalbn");
constexpr int kBits = std::numeric_limits<float>::digits;
return ldexpf(bits & ((UINT64_C(1) << kBits) - 1u), -kBits);
}
uint64_t RandGenerator(uint64_t range) {
DCHECK_GT(range, 0u);
// We must discard random results above this number, as they would
// make the random generator non-uniform (consider e.g. if
// MAX_UINT64 was 7 and |range| was 5, then a result of 1 would be twice
// as likely as a result of 3 or 4).
uint64_t max_acceptable_value =
(std::numeric_limits<uint64_t>::max() / range) * range - 1;
uint64_t value;
do {
value = base::RandUint64();
} while (value > max_acceptable_value);
return value % range;
}
std::string RandBytesAsString(size_t length) {
DCHECK_GT(length, 0u);
std::string result;
RandBytes(WriteInto(&result, length + 1), length);
return result;
}
InsecureRandomGenerator::InsecureRandomGenerator() {
a_ = base::RandUint64();
b_ = base::RandUint64();
}
void InsecureRandomGenerator::ReseedForTesting(uint64_t seed) {
a_ = seed;
b_ = seed;
}
uint64_t InsecureRandomGenerator::RandUint64() {
// Using XorShift128+, which is simple and widely used. See
// https://en.wikipedia.org/wiki/Xorshift#xorshift+ for details.
uint64_t t = a_;
const uint64_t s = b_;
a_ = s;
t ^= t << 23;
t ^= t >> 17;
t ^= s ^ (s >> 26);
b_ = t;
return t + s;
}
uint32_t InsecureRandomGenerator::RandUint32() {
// The generator usually returns an uint64_t, truncate it.
//
// It is noted in this paper (https://arxiv.org/abs/1810.05313) that the
// lowest 32 bits fail some statistical tests from the Big Crush
// suite. Use the higher ones instead.
return this->RandUint64() >> 32;
}
double InsecureRandomGenerator::RandDouble() {
uint64_t x = RandUint64();
// From https://vigna.di.unimi.it/xorshift/.
// 53 bits of mantissa, hence the "hexadecimal exponent" 1p-53.
return (x >> 11) * 0x1.0p-53;
}
MetricsSubSampler::MetricsSubSampler() = default;
bool MetricsSubSampler::ShouldSample(double probability) {
return !g_subsampling_enabled || generator_.RandDouble() < probability;
}
MetricsSubSampler::ScopedDisableForTesting::ScopedDisableForTesting() {
DCHECK(g_subsampling_enabled);
g_subsampling_enabled = false;
}
MetricsSubSampler::ScopedDisableForTesting::~ScopedDisableForTesting() {
DCHECK(!g_subsampling_enabled);
g_subsampling_enabled = true;
}
} // namespace base
|
