base/rand_util.h

   1 // Copyright 2012 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 #ifndef BASE_RAND_UTIL_H_
   6 #define BASE_RAND_UTIL_H_
   7
   8 #include <stddef.h>
   9 #include <stdint.h>
  10
  11 #include <algorithm>
  12 #include <string>
  13
  14 #include "base/base_export.h"
  15 #include "base/compiler_specific.h"
  16 #include "base/gtest_prod_util.h"
  17 #include "build/build_config.h"
  18
  19 #if !BUILDFLAG(IS_NACL)
  20 #include "third_party/boringssl/src/include/openssl/rand.h"
  21 #endif
  22
  23 namespace base {
  24
  25 namespace internal {
  26
  27 #if BUILDFLAG(IS_ANDROID)
  28 // Sets the implementation of RandBytes according to the corresponding
  29 // base::Feature. Thread safe: allows to switch while RandBytes() is in use.
  30 void ConfigureRandBytesFieldTrial();
  31 #endif
  32
  33 #if !BUILDFLAG(IS_NACL)
  34 void ConfigureBoringSSLBackedRandBytesFieldTrial();
  35 #endif
  36
  37 // Returns a random double in range [0, 1). For use in allocator shim to avoid
  38 // infinite recursion. Thread-safe.
  39 BASE_EXPORT double RandDoubleAvoidAllocation();
  40
  41 }  // namespace internal
  42
  43 // Returns a random number in range [0, UINT64_MAX]. Thread-safe.
  44 BASE_EXPORT uint64_t RandUint64();
  45
  46 // Returns a random number between min and max (inclusive). Thread-safe.
  47 BASE_EXPORT int RandInt(int min, int max);
  48
  49 // Returns a random number in range [0, range).  Thread-safe.
  50 BASE_EXPORT uint64_t RandGenerator(uint64_t range);
  51
  52 // Returns a random double in range [0, 1). Thread-safe.
  53 BASE_EXPORT double RandDouble();
  54
  55 // Returns a random float in range [0, 1). Thread-safe.
  56 BASE_EXPORT float RandFloat();
  57
  58 // Given input |bits|, convert with maximum precision to a double in
  59 // the range [0, 1). Thread-safe.
  60 BASE_EXPORT double BitsToOpenEndedUnitInterval(uint64_t bits);
  61
  62 // Given input `bits`, convert with maximum precision to a float in the range
  63 // [0, 1). Thread-safe.
  64 BASE_EXPORT float BitsToOpenEndedUnitIntervalF(uint64_t bits);
  65
  66 // Fills |output_length| bytes of |output| with random data. Thread-safe.
  67 //
  68 // Although implementations are required to use a cryptographically secure
  69 // random number source, code outside of base/ that relies on this should use
  70 // crypto::RandBytes instead to ensure the requirement is easily discoverable.
  71 BASE_EXPORT void RandBytes(void* output, size_t output_length);
  72
  73 // Fills a string of length |length| with random data and returns it.
  74 // |length| should be nonzero. Thread-safe.
  75 //
  76 // Note that this is a variation of |RandBytes| with a different return type.
  77 // The returned string is likely not ASCII/UTF-8. Use with care.
  78 //
  79 // Although implementations are required to use a cryptographically secure
  80 // random number source, code outside of base/ that relies on this should use
  81 // crypto::RandBytes instead to ensure the requirement is easily discoverable.
  82 BASE_EXPORT std::string RandBytesAsString(size_t length);
  83
  84 // An STL UniformRandomBitGenerator backed by RandUint64.
  85 class RandomBitGenerator {
  86  public:
  87   using result_type = uint64_t;
  88   static constexpr result_type min() { return 0; }
  89   static constexpr result_type max() { return UINT64_MAX; }
  90   result_type operator()() const { return RandUint64(); }
  91
  92   RandomBitGenerator() = default;
  93   ~RandomBitGenerator() = default;
  94 };
  95
  96 #if !BUILDFLAG(IS_NACL)
  97 class NonAllocatingRandomBitGenerator {
  98  public:
  99   using result_type = uint64_t;
 100   static constexpr result_type min() { return 0; }
 101   static constexpr result_type max() { return UINT64_MAX; }
 102   result_type operator()() const {
 103     uint64_t result;
 104     RAND_get_system_entropy_for_custom_prng(reinterpret_cast<uint8_t*>(&result),
 105                                             sizeof(result));
 106     return result;
 107   }
 108
 109   NonAllocatingRandomBitGenerator() = default;
 110   ~NonAllocatingRandomBitGenerator() = default;
 111 };
 112 #endif
 113
 114 // Shuffles [first, last) randomly. Thread-safe.
 115 template <typename Itr>
 116 void RandomShuffle(Itr first, Itr last) {
 117   std::shuffle(first, last, RandomBitGenerator());
 118 }
 119
 120 #if BUILDFLAG(IS_POSIX)
 121 BASE_EXPORT int GetUrandomFD();
 122 #endif
 123
 124 class MetricsSubSampler;
 125
 126 // Fast, insecure pseudo-random number generator.
 127 //
 128 // WARNING: This is not the generator you are looking for. This has significant
 129 // caveats:
 130 //   - It is non-cryptographic, so easy to miuse
 131 //   - It is neither fork() nor clone()-safe.
 132 //   - Synchronization is up to the client.
 133 //
 134 // Always prefer base::Rand*() above, unless you have a use case where its
 135 // overhead is too high, or system calls are disallowed.
 136 //
 137 // Performance: As of 2021, rough overhead on Linux on a desktop machine of
 138 // base::RandUint64() is ~800ns per call (it performs a system call). On Windows
 139 // it is lower. On the same machine, this generator's cost is ~2ns per call,
 140 // regardless of platform.
 141 //
 142 // This is different from |Rand*()| above as it is guaranteed to never make a
 143 // system call to generate a new number, except to seed it.  This should *never*
 144 // be used for cryptographic applications, and is not thread-safe.
 145 //
 146 // It is seeded using base::RandUint64() in the constructor, meaning that it
 147 // doesn't need to be seeded. It can be re-seeded though, with
 148 // ReseedForTesting(). Its period is long enough that it should not need to be
 149 // re-seeded during use.
 150 //
 151 // Uses the XorShift128+ generator under the hood.
 152 class BASE_EXPORT InsecureRandomGenerator {
 153  public:
 154   // Never use outside testing, not enough entropy.
 155   void ReseedForTesting(uint64_t seed);
 156
 157   uint32_t RandUint32();
 158   uint64_t RandUint64();
 159   // In [0, 1).
 160   double RandDouble();
 161
 162  private:
 163   InsecureRandomGenerator();
 164   // State.
 165   uint64_t a_ = 0, b_ = 0;
 166
 167   // Before adding a new friend class, make sure that the overhead of
 168   // base::Rand*() is too high, using something more representative than a
 169   // microbenchmark.
 170
 171   // Uses the generator to sub-sample metrics.
 172   friend class MetricsSubSampler;
 173
 174   FRIEND_TEST_ALL_PREFIXES(RandUtilTest,
 175                            InsecureRandomGeneratorProducesBothValuesOfAllBits);
 176   FRIEND_TEST_ALL_PREFIXES(RandUtilTest, InsecureRandomGeneratorChiSquared);
 177   FRIEND_TEST_ALL_PREFIXES(RandUtilTest, InsecureRandomGeneratorRandDouble);
 178   FRIEND_TEST_ALL_PREFIXES(RandUtilPerfTest, InsecureRandomRandUint64);
 179 };
 180
 181 class BASE_EXPORT MetricsSubSampler {
 182  public:
 183   MetricsSubSampler();
 184   bool ShouldSample(double probability);
 185
 186  private:
 187   InsecureRandomGenerator generator_;
 188 };
 189
 190 }  // namespace base
 191
 192 #endif  // BASE_RAND_UTIL_H_