random/internal/pool_urbg.h

0001 // Copyright 2017 The Abseil Authors.
0002 //
0003 // Licensed under the Apache License, Version 2.0 (the "License");
0004 // you may not use this file except in compliance with the License.
0005 // You may obtain a copy of the License at
0006 //
0007 //      https://www.apache.org/licenses/LICENSE-2.0
0008 //
0009 // Unless required by applicable law or agreed to in writing, software
0010 // distributed under the License is distributed on an "AS IS" BASIS,
0011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0012 // See the License for the specific language governing permissions and
0013 // limitations under the License.
0014
0015 #ifndef ABSL_RANDOM_INTERNAL_POOL_URBG_H_
0016 #define ABSL_RANDOM_INTERNAL_POOL_URBG_H_
0017
0018 #include <cinttypes>
0019 #include <limits>
0020
0021 #include "absl/random/internal/traits.h"
0022 #include "absl/types/span.h"
0023
0024 namespace absl {
0025 ABSL_NAMESPACE_BEGIN
0026 namespace random_internal {
0027
0028 // RandenPool is a thread-safe random number generator [random.req.urbg] that
0029 // uses an underlying pool of Randen generators to generate values.  Each thread
0030 // has affinity to one instance of the underlying pool generators.  Concurrent
0031 // access is guarded by a spin-lock.
0032 template <typename T>
0033 class RandenPool {
0034  public:
0035   using result_type = T;
0036   static_assert(std::is_unsigned<result_type>::value,
0037                 "RandenPool template argument must be a built-in unsigned "
0038                 "integer type");
0039
0040   static constexpr result_type(min)() {
0041     return (std::numeric_limits<result_type>::min)();
0042   }
0043
0044   static constexpr result_type(max)() {
0045     return (std::numeric_limits<result_type>::max)();
0046   }
0047
0048   RandenPool() {}
0049
0050   // Returns a single value.
0051   inline result_type operator()() { return Generate(); }
0052
0053   // Fill data with random values.
0054   static void Fill(absl::Span<result_type> data);
0055
0056  protected:
0057   // Generate returns a single value.
0058   static result_type Generate();
0059 };
0060
0061 extern template class RandenPool<uint8_t>;
0062 extern template class RandenPool<uint16_t>;
0063 extern template class RandenPool<uint32_t>;
0064 extern template class RandenPool<uint64_t>;
0065
0066 // PoolURBG uses an underlying pool of random generators to implement a
0067 // thread-compatible [random.req.urbg] interface with an internal cache of
0068 // values.
0069 template <typename T, size_t kBufferSize>
0070 class PoolURBG {
0071   // Inheritance to access the protected static members of RandenPool.
0072   using unsigned_type = typename make_unsigned_bits<T>::type;
0073   using PoolType = RandenPool<unsigned_type>;
0074   using SpanType = absl::Span<unsigned_type>;
0075
0076   static constexpr size_t kInitialBuffer = kBufferSize + 1;
0077   static constexpr size_t kHalfBuffer = kBufferSize / 2;
0078
0079  public:
0080   using result_type = T;
0081
0082   static_assert(std::is_unsigned<result_type>::value,
0083                 "PoolURBG must be parameterized by an unsigned integer type");
0084
0085   static_assert(kBufferSize > 1,
0086                 "PoolURBG must be parameterized by a buffer-size > 1");
0087
0088   static_assert(kBufferSize <= 256,
0089                 "PoolURBG must be parameterized by a buffer-size <= 256");
0090
0091   static constexpr result_type(min)() {
0092     return (std::numeric_limits<result_type>::min)();
0093   }
0094
0095   static constexpr result_type(max)() {
0096     return (std::numeric_limits<result_type>::max)();
0097   }
0098
0099   PoolURBG() : next_(kInitialBuffer) {}
0100
0101   // copy-constructor does not copy cache.
0102   PoolURBG(const PoolURBG&) : next_(kInitialBuffer) {}
0103   const PoolURBG& operator=(const PoolURBG&) {
0104     next_ = kInitialBuffer;
0105     return *this;
0106   }
0107
0108   // move-constructor does move cache.
0109   PoolURBG(PoolURBG&&) = default;
0110   PoolURBG& operator=(PoolURBG&&) = default;
0111
0112   inline result_type operator()() {
0113     if (next_ >= kBufferSize) {
0114       next_ = (kBufferSize > 2 && next_ > kBufferSize) ? kHalfBuffer : 0;
0115       PoolType::Fill(SpanType(reinterpret_cast<unsigned_type*>(state_ + next_),
0116                               kBufferSize - next_));
0117     }
0118     return state_[next_++];
0119   }
0120
0121  private:
0122   // Buffer size.
0123   size_t next_;  // index within state_
0124   result_type state_[kBufferSize];
0125 };
0126
0127 }  // namespace random_internal
0128 ABSL_NAMESPACE_END
0129 }  // namespace absl
0130
0131 #endif  // ABSL_RANDOM_INTERNAL_POOL_URBG_H_