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