base/rand_util.cc

   1 // Copyright 2011 The Chromium Authors
   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
   7 #include <limits.h>
   8 #include <math.h>
   9 #include <stdint.h>
  10
  11 #include <algorithm>
  12 #include <limits>
  13
  14 #include "base/check_op.h"
  15 #include "base/strings/string_util.h"
  16 #include "base/time/time.h"
  17
  18 namespace base {
  19
  20 namespace {
  21
  22 bool g_subsampling_enabled = true;
  23
  24 }  // namespace
  25
  26 uint64_t RandUint64() {
  27   uint64_t number;
  28   RandBytes(&number, sizeof(number));
  29   return number;
  30 }
  31
  32 int RandInt(int min, int max) {
  33   DCHECK_LE(min, max);
  34
  35   uint64_t range = static_cast<uint64_t>(max) - static_cast<uint64_t>(min) + 1;
  36   // |range| is at most UINT_MAX + 1, so the result of RandGenerator(range)
  37   // is at most UINT_MAX.  Hence it's safe to cast it from uint64_t to int64_t.
  38   int result =
  39       static_cast<int>(min + static_cast<int64_t>(base::RandGenerator(range)));
  40   DCHECK_GE(result, min);
  41   DCHECK_LE(result, max);
  42   return result;
  43 }
  44
  45 double RandDouble() {
  46   return BitsToOpenEndedUnitInterval(base::RandUint64());
  47 }
  48
  49 float RandFloat() {
  50   return BitsToOpenEndedUnitIntervalF(base::RandUint64());
  51 }
  52
  53 TimeDelta RandTimeDelta(TimeDelta start, TimeDelta limit) {
  54   // We must have a finite, non-empty, non-reversed interval.
  55   CHECK_LT(start, limit);
  56   CHECK(!start.is_min());
  57   CHECK(!limit.is_max());
  58
  59   const int64_t range = (limit - start).InMicroseconds();
  60   // Because of the `CHECK_LT()` above, range > 0, so this cast is safe.
  61   const uint64_t delta_us = base::RandGenerator(static_cast<uint64_t>(range));
  62   // ...and because `range` fit in an `int64_t`, so will `delta_us`.
  63   return start + Microseconds(static_cast<int64_t>(delta_us));
  64 }
  65
  66 TimeDelta RandTimeDeltaUpTo(TimeDelta limit) {
  67   return RandTimeDelta(TimeDelta(), limit);
  68 }
  69
  70 double BitsToOpenEndedUnitInterval(uint64_t bits) {
  71   // We try to get maximum precision by masking out as many bits as will fit
  72   // in the target type's mantissa, and raising it to an appropriate power to
  73   // produce output in the range [0, 1).  For IEEE 754 doubles, the mantissa
  74   // is expected to accommodate 53 bits (including the implied bit).
  75   static_assert(std::numeric_limits<double>::radix == 2,
  76                 "otherwise use scalbn");
  77   constexpr int kBits = std::numeric_limits<double>::digits;
  78   return ldexp(bits & ((UINT64_C(1) << kBits) - 1u), -kBits);
  79 }
  80
  81 float BitsToOpenEndedUnitIntervalF(uint64_t bits) {
  82   // We try to get maximum precision by masking out as many bits as will fit
  83   // in the target type's mantissa, and raising it to an appropriate power to
  84   // produce output in the range [0, 1).  For IEEE 754 floats, the mantissa is
  85   // expected to accommodate 12 bits (including the implied bit).
  86   static_assert(std::numeric_limits<float>::radix == 2, "otherwise use scalbn");
  87   constexpr int kBits = std::numeric_limits<float>::digits;
  88   return ldexpf(bits & ((UINT64_C(1) << kBits) - 1u), -kBits);
  89 }
  90
  91 uint64_t RandGenerator(uint64_t range) {
  92   DCHECK_GT(range, 0u);
  93   // We must discard random results above this number, as they would
  94   // make the random generator non-uniform (consider e.g. if
  95   // MAX_UINT64 was 7 and |range| was 5, then a result of 1 would be twice
  96   // as likely as a result of 3 or 4).
  97   uint64_t max_acceptable_value =
  98       (std::numeric_limits<uint64_t>::max() / range) * range - 1;
  99
 100   uint64_t value;
 101   do {
 102     value = base::RandUint64();
 103   } while (value > max_acceptable_value);
 104
 105   return value % range;
 106 }
 107
 108 std::string RandBytesAsString(size_t length) {
 109   DCHECK_GT(length, 0u);
 110   std::string result;
 111   RandBytes(WriteInto(&result, length + 1), length);
 112   return result;
 113 }
 114
 115 InsecureRandomGenerator::InsecureRandomGenerator() {
 116   a_ = base::RandUint64();
 117   b_ = base::RandUint64();
 118 }
 119
 120 void InsecureRandomGenerator::ReseedForTesting(uint64_t seed) {
 121   a_ = seed;
 122   b_ = seed;
 123 }
 124
 125 uint64_t InsecureRandomGenerator::RandUint64() {
 126   // Using XorShift128+, which is simple and widely used. See
 127   // https://en.wikipedia.org/wiki/Xorshift#xorshift+ for details.
 128   uint64_t t = a_;
 129   const uint64_t s = b_;
 130
 131   a_ = s;
 132   t ^= t << 23;
 133   t ^= t >> 17;
 134   t ^= s ^ (s >> 26);
 135   b_ = t;
 136
 137   return t + s;
 138 }
 139
 140 uint32_t InsecureRandomGenerator::RandUint32() {
 141   // The generator usually returns an uint64_t, truncate it.
 142   //
 143   // It is noted in this paper (https://arxiv.org/abs/1810.05313) that the
 144   // lowest 32 bits fail some statistical tests from the Big Crush
 145   // suite. Use the higher ones instead.
 146   return this->RandUint64() >> 32;
 147 }
 148
 149 double InsecureRandomGenerator::RandDouble() {
 150   uint64_t x = RandUint64();
 151   // From https://vigna.di.unimi.it/xorshift/.
 152   // 53 bits of mantissa, hence the "hexadecimal exponent" 1p-53.
 153   return (x >> 11) * 0x1.0p-53;
 154 }
 155
 156 MetricsSubSampler::MetricsSubSampler() = default;
 157 bool MetricsSubSampler::ShouldSample(double probability) {
 158   return !g_subsampling_enabled || generator_.RandDouble() < probability;
 159 }
 160
 161 MetricsSubSampler::ScopedDisableForTesting::ScopedDisableForTesting() {
 162   DCHECK(g_subsampling_enabled);
 163   g_subsampling_enabled = false;
 164 }
 165
 166 MetricsSubSampler::ScopedDisableForTesting::~ScopedDisableForTesting() {
 167   DCHECK(!g_subsampling_enabled);
 168   g_subsampling_enabled = true;
 169 }
 170
 171 }  // namespace base