iOS/Pods/Realm/include/core/realm/util/random.hpp

   1 /*************************************************************************
   2  *
   3  * REALM CONFIDENTIAL
   4  * __________________
   5  *
   6  *  [2011] - [2016] Realm Inc
   7  *  All Rights Reserved.
   8  *
   9  * NOTICE:  All information contained herein is, and remains
  10  * the property of Realm Incorporated and its suppliers,
  11  * if any.  The intellectual and technical concepts contained
  12  * herein are proprietary to Realm Incorporated
  13  * and its suppliers and may be covered by U.S. and Foreign Patents,
  14  * patents in process, and are protected by trade secret or copyright law.
  15  * Dissemination of this information or reproduction of this material
  16  * is strictly forbidden unless prior written permission is obtained
  17  * from Realm Incorporated.
  18  *
  19  **************************************************************************/
  20
  21 #ifndef REALM_UTIL_RANDOM_HPP
  22 #define REALM_UTIL_RANDOM_HPP
  23
  24 #include <stddef.h>
  25 #include <limits>
  26 #include <array>
  27 #include <random>
  28 #include <algorithm>
  29 #include <functional>
  30
  31 namespace realm {
  32 namespace util {
  33
  34 /// Perform a nondeterministc seeding of the specified pseudo random number
  35 /// generator.
  36 ///
  37 /// \tparam Engine A type that satisfies UniformRandomBitGenerator as defined by
  38 /// the C++ standard.
  39 ///
  40 /// \tparam state_size The number of words of type Engine::result_type that make
  41 /// up the engine state.
  42 ///
  43 /// Thread-safe.
  44 ///
  45 /// FIXME: Move this to core repo, as it is generally useful.
  46 template<class Engine, size_t state_size = Engine::state_size>
  47 void seed_prng_nondeterministically(Engine&);
  48
  49
  50
  51
  52 // Implementation
  53
  54 } // namespace util
  55
  56 namespace _impl {
  57
  58 void get_extra_seed_entropy(unsigned int& extra_entropy_1, unsigned int& extra_entropy_2,
  59                             unsigned int& extra_entropy_3);
  60
  61 } // namespace _impl
  62
  63 namespace util {
  64
  65 template<class Engine, size_t state_size> void seed_prng_nondeterministically(Engine& engine)
  66 {
  67     // This implementation was informed and inspired by
  68     // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0205r0.html.
  69     //
  70     // The number of bits of entropy needed is `state_size *
  71     // std::numeric_limits<typename Engine::result_type>::digits` (assuming that
  72     // the engine uses all available bits in each word).
  73     //
  74     // Each invocation of `std::random_device::operator()` gives us
  75     // `std::numeric_limits<unsigned int>::digits` bits (assuming maximum
  76     // entropy). Note that `std::random_device::result_type` must be `unsigned
  77     // int`, `std::random_device::min()` must return zero, and
  78     // `std::random_device::max()` must return `std::numeric_limits<unsigned
  79     // int>::max()`.
  80     //
  81     // Ideally, we could have used `std::random_device::entropy()` as the actual
  82     // number of bits of entropy produced per invocation of
  83     // `std::random_device::operator()`, however, it is incorrectly implemented
  84     // on many platform. Also, it is supposed to return zero when
  85     // `std::random_device` is just a PRNG, but that would leave us with no way
  86     // to continue.
  87     //
  88     // When the actual entropy from `std::random_device` is less than maximum,
  89     // the seeding will be less than optimal. For example, if the actual entropy
  90     // is only half of the maximum, then the seeding will only produce half the
  91     // entrpy that it ought to, but that will generally still be a good seeding.
  92     //
  93     // For the (assumed) rare cases where `std::random_device` is a PRGN that is
  94     // not nondeterministically seeded, we include a bit of extra entropy taken
  95     // from such places as the current time and the ID of the executing process
  96     // (when available).
  97
  98     constexpr long seed_bits_needed = state_size *
  99         long(std::numeric_limits<typename Engine::result_type>::digits);
 100     constexpr int seed_bits_per_device_invocation =
 101         std::numeric_limits<unsigned int>::digits;
 102     constexpr size_t seed_words_needed =
 103         size_t((seed_bits_needed + (seed_bits_per_device_invocation - 1)) /
 104                seed_bits_per_device_invocation); // Rounding up
 105     constexpr int num_extra = 3;
 106     std::array<std::random_device::result_type, seed_words_needed+num_extra> seed_values;
 107     std::random_device rnddev;
 108     std::generate(seed_values.begin(), seed_values.end()-num_extra, std::ref(rnddev));
 109
 110     unsigned int extra_entropy[3];
 111     _impl::get_extra_seed_entropy(extra_entropy[0], extra_entropy[1], extra_entropy[2]);
 112     static_assert(num_extra == sizeof extra_entropy / sizeof extra_entropy[0], "Mismatch");
 113     std::copy(extra_entropy, extra_entropy+num_extra, seed_values.end()-num_extra);
 114
 115     std::seed_seq seed_seq(seed_values.begin(), seed_values.end());
 116     engine.seed(seed_seq);
 117 }
 118
 119 } // namespace util
 120 } // namespace realm
 121
 122 #endif // REALM_UTIL_RANDOM_HPP