/*
- * Copyright 2014 Facebook, Inc.
+ * Copyright 2017 Facebook, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* limitations under the License.
*/
-#ifndef FOLLY_BASE_RANDOM_H_
-#define FOLLY_BASE_RANDOM_H_
+#pragma once
+#define FOLLY_RANDOM_H_
-#include <stdint.h>
+#include <array>
+#include <cstdint>
+#include <random>
+#include <type_traits>
+
+#include <folly/Portability.h>
+#include <folly/Traits.h>
+
+#if FOLLY_HAVE_EXTRANDOM_SFMT19937
+#include <ext/random>
+#endif
namespace folly {
+/**
+ * A PRNG with one instance per thread. This PRNG uses a mersenne twister random
+ * number generator and is seeded from /dev/urandom. It should not be used for
+ * anything which requires security, only for statistical randomness.
+ *
+ * An instance of this class represents the current threads PRNG. This means
+ * copying an instance of this class across threads will result in corruption
+ *
+ * Most users will use the Random class which implicitly creates this class.
+ * However, if you are worried about performance, you can memoize the TLS
+ * lookups that get the per thread state by manually using this class:
+ *
+ * ThreadLocalPRNG rng;
+ * for (...) {
+ * Random::rand32(rng);
+ * }
+ */
+class ThreadLocalPRNG {
+ public:
+ typedef uint32_t result_type;
+
+ uint32_t operator()() {
+ // Using a static method allows the compiler to avoid allocating stack space
+ // for this class.
+ return getImpl(local_);
+ }
+
+ static constexpr result_type min() {
+ return std::numeric_limits<result_type>::min();
+ }
+ static constexpr result_type max() {
+ return std::numeric_limits<result_type>::max();
+ }
+ friend class Random;
+
+ ThreadLocalPRNG();
+
+ class LocalInstancePRNG;
+
+ private:
+ static result_type getImpl(LocalInstancePRNG* local);
+ LocalInstancePRNG* local_;
+};
+
+
+class Random {
+
+ private:
+ template <class RNG>
+ using ValidRNG = typename std::enable_if<
+ std::is_unsigned<typename std::result_of<RNG&()>::type>::value,
+ RNG>::type;
+
+ public:
+ // Default generator type.
+#if FOLLY_HAVE_EXTRANDOM_SFMT19937
+ typedef __gnu_cxx::sfmt19937 DefaultGenerator;
+#else
+ typedef std::mt19937 DefaultGenerator;
+#endif
+
+ /**
+ * Get secure random bytes. (On Linux and OSX, this means /dev/urandom).
+ */
+ static void secureRandom(void* data, size_t len);
+
+ /**
+ * Shortcut to get a secure random value of integral type.
+ */
+ template <class T>
+ static typename std::enable_if<
+ std::is_integral<T>::value && !std::is_same<T,bool>::value,
+ T>::type
+ secureRandom() {
+ T val;
+ secureRandom(&val, sizeof(val));
+ return val;
+ }
+
+ /**
+ * (Re-)Seed an existing RNG with a good seed.
+ *
+ * Note that you should usually use ThreadLocalPRNG unless you need
+ * reproducibility (such as during a test), in which case you'd want
+ * to create a RNG with a good seed in production, and seed it yourself
+ * in test.
+ */
+ template <class RNG = DefaultGenerator, class /* EnableIf */ = ValidRNG<RNG>>
+ static void seed(RNG& rng);
+
+ /**
+ * Create a new RNG, seeded with a good seed.
+ *
+ * Note that you should usually use ThreadLocalPRNG unless you need
+ * reproducibility (such as during a test), in which case you'd want
+ * to create a RNG with a good seed in production, and seed it yourself
+ * in test.
+ */
+ template <class RNG = DefaultGenerator, class /* EnableIf */ = ValidRNG<RNG>>
+ static RNG create();
+
+ /**
+ * Returns a random uint32_t
+ */
+ static uint32_t rand32() {
+ return rand32(ThreadLocalPRNG());
+ }
+
+ /**
+ * Returns a random uint32_t given a specific RNG
+ */
+ template <class RNG, class /* EnableIf */ = ValidRNG<RNG>>
+ static uint32_t rand32(RNG&& rng) {
+ return rng();
+ }
+
+ /**
+ * Returns a random uint32_t in [0, max). If max == 0, returns 0.
+ */
+ static uint32_t rand32(uint32_t max) {
+ return rand32(0, max, ThreadLocalPRNG());
+ }
+
+ /**
+ * Returns a random uint32_t in [0, max) given a specific RNG.
+ * If max == 0, returns 0.
+ */
+ template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
+ static uint32_t rand32(uint32_t max, RNG&& rng) {
+ return rand32(0, max, rng);
+ }
+
+ /**
+ * Returns a random uint32_t in [min, max). If min == max, returns 0.
+ */
+ static uint32_t rand32(uint32_t min, uint32_t max) {
+ return rand32(min, max, ThreadLocalPRNG());
+ }
+
+ /**
+ * Returns a random uint32_t in [min, max) given a specific RNG.
+ * If min == max, returns 0.
+ */
+ template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
+ static uint32_t rand32(uint32_t min, uint32_t max, RNG&& rng) {
+ if (min == max) {
+ return 0;
+ }
+ return std::uniform_int_distribution<uint32_t>(min, max - 1)(rng);
+ }
+
+ /**
+ * Returns a random uint64_t
+ */
+ static uint64_t rand64() {
+ return rand64(ThreadLocalPRNG());
+ }
+
+ /**
+ * Returns a random uint64_t
+ */
+ template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
+ static uint64_t rand64(RNG&& rng) {
+ return ((uint64_t)rng() << 32) | rng();
+ }
+
+ /**
+ * Returns a random uint64_t in [0, max). If max == 0, returns 0.
+ */
+ static uint64_t rand64(uint64_t max) {
+ return rand64(0, max, ThreadLocalPRNG());
+ }
+
+ /**
+ * Returns a random uint64_t in [0, max). If max == 0, returns 0.
+ */
+ template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
+ static uint64_t rand64(uint64_t max, RNG&& rng) {
+ return rand64(0, max, rng);
+ }
+
+ /**
+ * Returns a random uint64_t in [min, max). If min == max, returns 0.
+ */
+ static uint64_t rand64(uint64_t min, uint64_t max) {
+ return rand64(min, max, ThreadLocalPRNG());
+ }
+
+ /**
+ * Returns a random uint64_t in [min, max). If min == max, returns 0.
+ */
+ template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
+ static uint64_t rand64(uint64_t min, uint64_t max, RNG&& rng) {
+ if (min == max) {
+ return 0;
+ }
+ return std::uniform_int_distribution<uint64_t>(min, max - 1)(rng);
+ }
+
+ /**
+ * Returns true 1/n of the time. If n == 0, always returns false
+ */
+ static bool oneIn(uint32_t n) {
+ return oneIn(n, ThreadLocalPRNG());
+ }
+
+ /**
+ * Returns true 1/n of the time. If n == 0, always returns false
+ */
+ template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
+ static bool oneIn(uint32_t n, RNG&& rng) {
+ if (n == 0) {
+ return false;
+ }
+ return rand32(0, n, rng) == 0;
+ }
+
+ /**
+ * Returns a double in [0, 1)
+ */
+ static double randDouble01() {
+ return randDouble01(ThreadLocalPRNG());
+ }
+
+ /**
+ * Returns a double in [0, 1)
+ */
+ template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
+ static double randDouble01(RNG&& rng) {
+ return std::generate_canonical<double, std::numeric_limits<double>::digits>(
+ rng);
+ }
+
+ /**
+ * Returns a double in [min, max), if min == max, returns 0.
+ */
+ static double randDouble(double min, double max) {
+ return randDouble(min, max, ThreadLocalPRNG());
+ }
+
+ /**
+ * Returns a double in [min, max), if min == max, returns 0.
+ */
+ template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
+ static double randDouble(double min, double max, RNG&& rng) {
+ if (std::fabs(max - min) < std::numeric_limits<double>::epsilon()) {
+ return 0;
+ }
+ return std::uniform_real_distribution<double>(min, max)(rng);
+ }
+
+};
+
/*
* Return a good seed for a random number generator.
+ * Note that this is a legacy function, as it returns a 32-bit value, which
+ * is too small to be useful as a "real" RNG seed. Use the functions in class
+ * Random instead.
*/
-uint32_t randomNumberSeed();
+inline uint32_t randomNumberSeed() {
+ return Random::rand32();
+}
}
-#endif
+#include <folly/Random-inl.h>