Movatterモバイル変換

[0]ホーム
URL:

Google Git
Sign in
chromium /chromium /src /refs/heads/main /. /base /rand_util.cc
blob: 9fc55773d72e044d2fd59f6ca13c4b643f7d73eb [file] [log] [blame]
Avi Drissmane4622aa2022-09-08 20:36:06[diff] [blame]1// Copyright 2011 The Chromium Authors
mark@chromium.org05f9b682008-09-29 22:18:01[diff] [blame]2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include"base/rand_util.h"
6
avi9b6f42932015-12-26 22:15:14[diff] [blame]7#include<limits.h>
mark@chromium.org05f9b682008-09-29 22:18:01[diff] [blame]8#include<math.h>
tfarina32089922015-05-18 22:14:09[diff] [blame]9#include<stdint.h>
mark@chromium.org94a0f312008-09-30 14:26:33[diff] [blame]10
John Chen87cc25c2018-04-20 22:49:49[diff] [blame]11#include<algorithm>
Olivier Li Shing Tat-Dupuis9e5e7d92024-02-13 14:42:10[diff] [blame]12#include<atomic>
John Chen87cc25c2018-04-20 22:49:49[diff] [blame]13#include<limits>
14
Anand Ravib793ffb32025-02-25 22:56:54[diff] [blame]15#include"base/check.h"
Hans Wennborgc3cffa62020-04-27 10:09:12[diff] [blame]16#include"base/check_op.h"
Peter Kastinga253f752025-01-31 18:57:26[diff] [blame]17#include"base/containers/span.h"
Peter Kastingf18c8ca2023-10-04 16:31:51[diff] [blame]18#include"base/time/time.h"
mark@chromium.org05f9b682008-09-29 22:18:01[diff] [blame]19
mark@chromium.org05f9b682008-09-29 22:18:01[diff] [blame]20namespace base{
21
François Doray87e35a82023-05-05 14:44:28[diff] [blame]22namespace{
23
Olivier Li Shing Tat-Dupuis9e5e7d92024-02-13 14:42:10[diff] [blame]24// A MetricSubsampler instance is not thread-safe. However, the global
25// sampling state may be read concurrently with writing it via testing
26// scopers, hence the need to use atomics. All operations use
27// memory_order_relaxed because there are no dependent memory accesses.
28std::atomic<bool> g_subsampling_always_sample=false;
29std::atomic<bool> g_subsampling_never_sample=false;
François Doray87e35a82023-05-05 14:44:28[diff] [blame]30
Anthony Vallée-Duboisecfdb382025-02-04 20:07:40[diff] [blame]31MetricsSubSampler*GetSharedSubsampler(){
32static thread_localMetricsSubSampler g_shared_subsampler;
33return&g_shared_subsampler;
34}
35
François Doray87e35a82023-05-05 14:44:28[diff] [blame]36}// namespace
37
John Mellorafab972d2017-09-26 16:28:19[diff] [blame]38uint64_tRandUint64(){
39uint64_t number;
danakj95305d272024-05-09 20:38:44[diff] [blame]40RandBytes(base::byte_span_from_ref(number));
John Mellorafab972d2017-09-26 16:28:19[diff] [blame]41return number;
42}
43
mark@chromium.org05f9b682008-09-29 22:18:01[diff] [blame]44intRandInt(int min,int max){
kushi.p@gmail.comd7a93ad2011-04-22 13:13:07[diff] [blame]45 DCHECK_LE(min, max);
mark@chromium.org05f9b682008-09-29 22:18:01[diff] [blame]46
Peter Kasting28b51cf2022-06-28 15:02:43[diff] [blame]47uint64_t range=static_cast<uint64_t>(max)-static_cast<uint64_t>(min)+1;
John Chen87cc25c2018-04-20 22:49:49[diff] [blame]48// |range| is at most UINT_MAX + 1, so the result of RandGenerator(range)
49// is at most UINT_MAX. Hence it's safe to cast it from uint64_t to int64_t.
50int result=
51static_cast<int>(min+static_cast<int64_t>(base::RandGenerator(range)));
kushi.p@gmail.come1be56d2011-05-04 01:29:38[diff] [blame]52 DCHECK_GE(result, min);
53 DCHECK_LE(result, max);
mark@chromium.org05f9b682008-09-29 22:18:01[diff] [blame]54return result;
55}
56
57doubleRandDouble(){
joi@chromium.orgedafd4c2011-05-10 17:18:53[diff] [blame]58returnBitsToOpenEndedUnitInterval(base::RandUint64());
59}
60
Avery Musbacheff342b2022-10-06 18:36:07[diff] [blame]61floatRandFloat(){
62returnBitsToOpenEndedUnitIntervalF(base::RandUint64());
63}
64
Peter Kastingb2dc55042025-01-16 16:30:54[diff] [blame]65boolRandBool(){
66uint8_t number;
67RandBytes(span_from_ref(number));
68return number&1;
69}
70
Peter Kastingf18c8ca2023-10-04 16:31:51[diff] [blame]71TimeDeltaRandTimeDelta(TimeDelta start,TimeDelta limit){
72// We must have a finite, non-empty, non-reversed interval.
73 CHECK_LT(start, limit);
74 CHECK(!start.is_min());
75 CHECK(!limit.is_max());
76
77constint64_t range=(limit- start).InMicroseconds();
78// Because of the `CHECK_LT()` above, range > 0, so this cast is safe.
79constuint64_t delta_us= base::RandGenerator(static_cast<uint64_t>(range));
80// ...and because `range` fit in an `int64_t`, so will `delta_us`.
81return start+Microseconds(static_cast<int64_t>(delta_us));
82}
83
84TimeDeltaRandTimeDeltaUpTo(TimeDelta limit){
85returnRandTimeDelta(TimeDelta(), limit);
86}
87
Nico Weber0a3852a72015-10-29 20:42:58[diff] [blame]88doubleBitsToOpenEndedUnitInterval(uint64_t bits){
mark@chromium.org94a0f312008-09-30 14:26:33[diff] [blame]89// We try to get maximum precision by masking out as many bits as will fit
90// in the target type's mantissa, and raising it to an appropriate power to
91// produce output in the range [0, 1). For IEEE 754 doubles, the mantissa
Avery Musbach92a30e382022-09-08 23:30:41[diff] [blame]92// is expected to accommodate 53 bits (including the implied bit).
avi4ec0dff2015-11-24 14:26:24[diff] [blame]93static_assert(std::numeric_limits<double>::radix==2,
94"otherwise use scalbn");
Avery Musbach92a30e382022-09-08 23:30:41[diff] [blame]95constexprint kBits= std::numeric_limits<double>::digits;
96return ldexp(bits&((UINT64_C(1)<< kBits)-1u),-kBits);
mark@chromium.org05f9b682008-09-29 22:18:01[diff] [blame]97}
98
Avery Musbacheff342b2022-10-06 18:36:07[diff] [blame]99floatBitsToOpenEndedUnitIntervalF(uint64_t bits){
100// We try to get maximum precision by masking out as many bits as will fit
101// in the target type's mantissa, and raising it to an appropriate power to
102// produce output in the range [0, 1). For IEEE 754 floats, the mantissa is
103// expected to accommodate 12 bits (including the implied bit).
104static_assert(std::numeric_limits<float>::radix==2,"otherwise use scalbn");
105constexprint kBits= std::numeric_limits<float>::digits;
106return ldexpf(bits&((UINT64_C(1)<< kBits)-1u),-kBits);
107}
108
Nico Weber0a3852a72015-10-29 20:42:58[diff] [blame]109uint64_tRandGenerator(uint64_t range){
dilmah@chromium.org0173b962011-08-24 19:58:36[diff] [blame]110 DCHECK_GT(range,0u);
joi@chromium.orgaf2e192b2011-05-30 17:39:09[diff] [blame]111// We must discard random results above this number, as they would
112// make the random generator non-uniform (consider e.g. if
dilmah@chromium.org0173b962011-08-24 19:58:36[diff] [blame]113// MAX_UINT64 was 7 and |range| was 5, then a result of 1 would be twice
114// as likely as a result of 3 or 4).
Nico Weber0a3852a72015-10-29 20:42:58[diff] [blame]115uint64_t max_acceptable_value=
116(std::numeric_limits<uint64_t>::max()/ range)* range-1;
joi@chromium.orgaf2e192b2011-05-30 17:39:09[diff] [blame]117
Nico Weber0a3852a72015-10-29 20:42:58[diff] [blame]118uint64_t value;
joi@chromium.orgaf2e192b2011-05-30 17:39:09[diff] [blame]119do{
120 value= base::RandUint64();
dilmah@chromium.org0173b962011-08-24 19:58:36[diff] [blame]121}while(value> max_acceptable_value);
joi@chromium.orgaf2e192b2011-05-30 17:39:09[diff] [blame]122
dilmah@chromium.org0173b962011-08-24 19:58:36[diff] [blame]123return value% range;
isherman@chromium.orga74dcae2010-08-30 21:07:05[diff] [blame]124}
125
qsr@google.com51a01812011-05-05 08:46:11[diff] [blame]126std::stringRandBytesAsString(size_t length){
Daniel Cheng589602312024-02-09 17:50:51[diff] [blame]127 std::string result(length,'\0');
danakj95305d272024-05-09 20:38:44[diff] [blame]128RandBytes(as_writable_byte_span(result));
abarth@chromium.org29548d82011-04-29 21:03:54[diff] [blame]129return result;
130}
131
Tom Sepez230a75c62023-11-13 23:27:16[diff] [blame]132std::vector<uint8_t>RandBytesAsVector(size_t length){
133 std::vector<uint8_t> result(length);
danakj95305d272024-05-09 20:38:44[diff] [blame]134RandBytes(result);
Tom Sepez230a75c62023-11-13 23:27:16[diff] [blame]135return result;
136}
137
Benoit Lize7532d4af2021-08-24 11:34:04[diff] [blame]138InsecureRandomGenerator::InsecureRandomGenerator(){
Benoit Lize73de21b2021-07-02 08:17:56[diff] [blame]139 a_= base::RandUint64();
140 b_= base::RandUint64();
Benoit Lize73de21b2021-07-02 08:17:56[diff] [blame]141}
142
Benoit Lize7532d4af2021-08-24 11:34:04[diff] [blame]143voidInsecureRandomGenerator::ReseedForTesting(uint64_t seed){
Benoit Lize73de21b2021-07-02 08:17:56[diff] [blame]144 a_= seed;
145 b_= seed;
Benoit Lize73de21b2021-07-02 08:17:56[diff] [blame]146}
147
Anthony Vallée-Dubois13bd8f62025-01-21 17:10:32[diff] [blame]148uint64_tInsecureRandomGenerator::RandUint64()const{
Benoit Lize73de21b2021-07-02 08:17:56[diff] [blame]149// Using XorShift128+, which is simple and widely used. See
150// https://en.wikipedia.org/wiki/Xorshift#xorshift+ for details.
151uint64_t t= a_;
152constuint64_t s= b_;
153
154 a_= s;
155 t^= t<<23;
156 t^= t>>17;
157 t^= s^(s>>26);
158 b_= t;
159
160return t+ s;
161}
162
Anthony Vallée-Dubois13bd8f62025-01-21 17:10:32[diff] [blame]163uint32_tInsecureRandomGenerator::RandUint32()const{
Benoit Lize73de21b2021-07-02 08:17:56[diff] [blame]164// The generator usually returns an uint64_t, truncate it.
165//
166// It is noted in this paper (https://arxiv.org/abs/1810.05313) that the
167// lowest 32 bits fail some statistical tests from the Big Crush
168// suite. Use the higher ones instead.
169returnthis->RandUint64()>>32;
170}
171
Anthony Vallée-Dubois13bd8f62025-01-21 17:10:32[diff] [blame]172doubleInsecureRandomGenerator::RandDouble()const{
Benoit Lized6377142021-07-05 10:17:16[diff] [blame]173uint64_t x=RandUint64();
174// From https://vigna.di.unimi.it/xorshift/.
175// 53 bits of mantissa, hence the "hexadecimal exponent" 1p-53.
176return(x>>11)*0x1.0p-53;
177}
178
Benoit Lizeee4fe1e42022-06-29 19:13:48[diff] [blame]179MetricsSubSampler::MetricsSubSampler()=default;
Anthony Vallée-Dubois13bd8f62025-01-21 17:10:32[diff] [blame]180boolMetricsSubSampler::ShouldSample(double probability)const{
Olivier Li Shing Tat-Dupuis9e5e7d92024-02-13 14:42:10[diff] [blame]181if(g_subsampling_always_sample.load(std::memory_order_relaxed)){
Olivier Lief2b23c2024-01-29 20:58:56[diff] [blame]182returntrue;
183}
Olivier Li Shing Tat-Dupuis9e5e7d92024-02-13 14:42:10[diff] [blame]184if(g_subsampling_never_sample.load(std::memory_order_relaxed)){
Olivier Lief2b23c2024-01-29 20:58:56[diff] [blame]185returnfalse;
186}
187
Anand Ravib793ffb32025-02-25 22:56:54[diff] [blame]188 DCHECK(probability>=0&& probability<=1);
Olivier Lief2b23c2024-01-29 20:58:56[diff] [blame]189return generator_.RandDouble()< probability;
François Doray87e35a82023-05-05 14:44:28[diff] [blame]190}
191
Anthony Vallée-Duboisecfdb382025-02-04 20:07:40[diff] [blame]192voidMetricsSubSampler::Reseed(){
193 generator_=InsecureRandomGenerator();
194}
195
Olivier Lief2b23c2024-01-29 20:58:56[diff] [blame]196MetricsSubSampler::ScopedAlwaysSampleForTesting::
197ScopedAlwaysSampleForTesting(){
Olivier Li Shing Tat-Dupuis9e5e7d92024-02-13 14:42:10[diff] [blame]198 DCHECK(!g_subsampling_always_sample.load(std::memory_order_relaxed));
199 DCHECK(!g_subsampling_never_sample.load(std::memory_order_relaxed));
200 g_subsampling_always_sample.store(true, std::memory_order_relaxed);
François Doray87e35a82023-05-05 14:44:28[diff] [blame]201}
202
Olivier Lief2b23c2024-01-29 20:58:56[diff] [blame]203MetricsSubSampler::ScopedAlwaysSampleForTesting::
204~ScopedAlwaysSampleForTesting(){
Olivier Li Shing Tat-Dupuis9e5e7d92024-02-13 14:42:10[diff] [blame]205 DCHECK(g_subsampling_always_sample.load(std::memory_order_relaxed));
206 DCHECK(!g_subsampling_never_sample.load(std::memory_order_relaxed));
207 g_subsampling_always_sample.store(false, std::memory_order_relaxed);
Olivier Lief2b23c2024-01-29 20:58:56[diff] [blame]208}
209
210MetricsSubSampler::ScopedNeverSampleForTesting::ScopedNeverSampleForTesting(){
Olivier Li Shing Tat-Dupuis9e5e7d92024-02-13 14:42:10[diff] [blame]211 DCHECK(!g_subsampling_always_sample.load(std::memory_order_relaxed));
212 DCHECK(!g_subsampling_never_sample.load(std::memory_order_relaxed));
213 g_subsampling_never_sample.store(true, std::memory_order_relaxed);
Olivier Lief2b23c2024-01-29 20:58:56[diff] [blame]214}
215
216MetricsSubSampler::ScopedNeverSampleForTesting::~ScopedNeverSampleForTesting(){
217 DCHECK(!g_subsampling_always_sample);
218 DCHECK(g_subsampling_never_sample);
Olivier Li Shing Tat-Dupuis9e5e7d92024-02-13 14:42:10[diff] [blame]219 g_subsampling_never_sample.store(false, std::memory_order_relaxed);
Benoit Lizeee4fe1e42022-06-29 19:13:48[diff] [blame]220}
221
Anthony Vallée-Duboisecfdb382025-02-04 20:07:40[diff] [blame]222boolShouldRecordSubsampledMetric(double probability){
223returnGetSharedSubsampler()->ShouldSample(probability);
224}
225
226voidReseedSharedMetricsSubsampler(){
227GetSharedSubsampler()->Reseed();
228}
229
mark@chromium.org05f9b682008-09-29 22:18:01[diff] [blame]230}// namespace base
[8]ページ先頭
©2009-2025 Movatter.jp