1 // Copyright 2017 The Abseil Authors. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #ifndef ABSL_RANDOM_INTERNAL_POOL_URBG_H_ 16 #define ABSL_RANDOM_INTERNAL_POOL_URBG_H_ 17 18 #include <cinttypes> 19 #include <limits> 20 21 #include "absl/random/internal/traits.h" 22 #include "absl/types/span.h" 23 24 namespace absl { 25 ABSL_NAMESPACE_BEGIN 26 namespace random_internal { 27 28 // RandenPool is a thread-safe random number generator [random.req.urbg] that 29 // uses an underlying pool of Randen generators to generate values. Each thread 30 // has affinity to one instance of the underlying pool generators. Concurrent 31 // access is guarded by a spin-lock. 32 template <typename T> 33 class RandenPool { 34 public: 35 using result_type = T; 36 static_assert(std::is_unsigned<result_type>::value, 37 "RandenPool template argument must be a built-in unsigned " 38 "integer type"); 39 result_type(min)40 static constexpr result_type(min)() { 41 return (std::numeric_limits<result_type>::min)(); 42 } 43 result_type(max)44 static constexpr result_type(max)() { 45 return (std::numeric_limits<result_type>::max)(); 46 } 47 RandenPool()48 RandenPool() {} 49 50 // Returns a single value. operator()51 inline result_type operator()() { return Generate(); } 52 53 // Fill data with random values. 54 static void Fill(absl::Span<result_type> data); 55 56 protected: 57 // Generate returns a single value. 58 static result_type Generate(); 59 }; 60 61 extern template class RandenPool<uint8_t>; 62 extern template class RandenPool<uint16_t>; 63 extern template class RandenPool<uint32_t>; 64 extern template class RandenPool<uint64_t>; 65 66 // PoolURBG uses an underlying pool of random generators to implement a 67 // thread-compatible [random.req.urbg] interface with an internal cache of 68 // values. 69 template <typename T, size_t kBufferSize> 70 class PoolURBG { 71 // Inheritance to access the protected static members of RandenPool. 72 using unsigned_type = typename make_unsigned_bits<T>::type; 73 using PoolType = RandenPool<unsigned_type>; 74 using SpanType = absl::Span<unsigned_type>; 75 76 static constexpr size_t kInitialBuffer = kBufferSize + 1; 77 static constexpr size_t kHalfBuffer = kBufferSize / 2; 78 79 public: 80 using result_type = T; 81 82 static_assert(std::is_unsigned<result_type>::value, 83 "PoolURBG must be parameterized by an unsigned integer type"); 84 85 static_assert(kBufferSize > 1, 86 "PoolURBG must be parameterized by a buffer-size > 1"); 87 88 static_assert(kBufferSize <= 256, 89 "PoolURBG must be parameterized by a buffer-size <= 256"); 90 result_type(min)91 static constexpr result_type(min)() { 92 return (std::numeric_limits<result_type>::min)(); 93 } 94 result_type(max)95 static constexpr result_type(max)() { 96 return (std::numeric_limits<result_type>::max)(); 97 } 98 PoolURBG()99 PoolURBG() : next_(kInitialBuffer) {} 100 101 // copy-constructor does not copy cache. PoolURBG(const PoolURBG &)102 PoolURBG(const PoolURBG&) : next_(kInitialBuffer) {} 103 const PoolURBG& operator=(const PoolURBG&) { 104 next_ = kInitialBuffer; 105 return *this; 106 } 107 108 // move-constructor does move cache. 109 PoolURBG(PoolURBG&&) = default; 110 PoolURBG& operator=(PoolURBG&&) = default; 111 operator()112 inline result_type operator()() { 113 if (next_ >= kBufferSize) { 114 next_ = (kBufferSize > 2 && next_ > kBufferSize) ? kHalfBuffer : 0; 115 PoolType::Fill(SpanType(reinterpret_cast<unsigned_type*>(state_ + next_), 116 kBufferSize - next_)); 117 } 118 return state_[next_++]; 119 } 120 121 private: 122 // Buffer size. 123 size_t next_; // index within state_ 124 result_type state_[kBufferSize]; 125 }; 126 127 } // namespace random_internal 128 ABSL_NAMESPACE_END 129 } // namespace absl 130 131 #endif // ABSL_RANDOM_INTERNAL_POOL_URBG_H_ 132