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_FAST_UNIFORM_BITS_H_
16 #define ABSL_RANDOM_INTERNAL_FAST_UNIFORM_BITS_H_
17 
18 #include <cstddef>
19 #include <cstdint>
20 #include <limits>
21 #include <type_traits>
22 
23 #include "absl/base/config.h"
24 #include "absl/meta/type_traits.h"
25 #include "absl/random/internal/traits.h"
26 
27 namespace absl {
28 ABSL_NAMESPACE_BEGIN
29 namespace random_internal {
30 // Returns true if the input value is zero or a power of two. Useful for
31 // determining if the range of output values in a URBG
32 template <typename UIntType>
IsPowerOfTwoOrZero(UIntType n)33 constexpr bool IsPowerOfTwoOrZero(UIntType n) {
34   return (n == 0) || ((n & (n - 1)) == 0);
35 }
36 
37 // Computes the length of the range of values producible by the URBG, or returns
38 // zero if that would encompass the entire range of representable values in
39 // URBG::result_type.
40 template <typename URBG>
RangeSize()41 constexpr typename URBG::result_type RangeSize() {
42   using result_type = typename URBG::result_type;
43   static_assert((URBG::max)() != (URBG::min)(), "URBG range cannot be 0.");
44   return ((URBG::max)() == (std::numeric_limits<result_type>::max)() &&
45           (URBG::min)() == std::numeric_limits<result_type>::lowest())
46              ? result_type{0}
47              : ((URBG::max)() - (URBG::min)() + result_type{1});
48 }
49 
50 // Computes the floor of the log. (i.e., std::floor(std::log2(N));
51 template <typename UIntType>
IntegerLog2(UIntType n)52 constexpr UIntType IntegerLog2(UIntType n) {
53   return (n <= 1) ? 0 : 1 + IntegerLog2(n >> 1);
54 }
55 
56 // Returns the number of bits of randomness returned through
57 // `PowerOfTwoVariate(urbg)`.
58 template <typename URBG>
NumBits()59 constexpr size_t NumBits() {
60   return RangeSize<URBG>() == 0
61              ? std::numeric_limits<typename URBG::result_type>::digits
62              : IntegerLog2(RangeSize<URBG>());
63 }
64 
65 // Given a shift value `n`, constructs a mask with exactly the low `n` bits set.
66 // If `n == 0`, all bits are set.
67 template <typename UIntType>
MaskFromShift(size_t n)68 constexpr UIntType MaskFromShift(size_t n) {
69   return ((n % std::numeric_limits<UIntType>::digits) == 0)
70              ? ~UIntType{0}
71              : (UIntType{1} << n) - UIntType{1};
72 }
73 
74 // Tags used to dispatch FastUniformBits::generate to the simple or more complex
75 // entropy extraction algorithm.
76 struct SimplifiedLoopTag {};
77 struct RejectionLoopTag {};
78 
79 // FastUniformBits implements a fast path to acquire uniform independent bits
80 // from a type which conforms to the [rand.req.urbg] concept.
81 // Parameterized by:
82 //  `UIntType`: the result (output) type
83 //
84 // The std::independent_bits_engine [rand.adapt.ibits] adaptor can be
85 // instantiated from an existing generator through a copy or a move. It does
86 // not, however, facilitate the production of pseudorandom bits from an un-owned
87 // generator that will outlive the std::independent_bits_engine instance.
88 template <typename UIntType = uint64_t>
89 class FastUniformBits {
90  public:
91   using result_type = UIntType;
92 
result_type(min)93   static constexpr result_type(min)() { return 0; }
result_type(max)94   static constexpr result_type(max)() {
95     return (std::numeric_limits<result_type>::max)();
96   }
97 
98   template <typename URBG>
99   result_type operator()(URBG& g);  // NOLINT(runtime/references)
100 
101  private:
102   static_assert(IsUnsigned<UIntType>::value,
103                 "Class-template FastUniformBits<> must be parameterized using "
104                 "an unsigned type.");
105 
106   // Generate() generates a random value, dispatched on whether
107   // the underlying URBG must use rejection sampling to generate a value,
108   // or whether a simplified loop will suffice.
109   template <typename URBG>
110   result_type Generate(URBG& g,  // NOLINT(runtime/references)
111                        SimplifiedLoopTag);
112 
113   template <typename URBG>
114   result_type Generate(URBG& g,  // NOLINT(runtime/references)
115                        RejectionLoopTag);
116 };
117 
118 template <typename UIntType>
119 template <typename URBG>
120 typename FastUniformBits<UIntType>::result_type
operator()121 FastUniformBits<UIntType>::operator()(URBG& g) {  // NOLINT(runtime/references)
122   // kRangeMask is the mask used when sampling variates from the URBG when the
123   // width of the URBG range is not a power of 2.
124   // Y = (2 ^ kRange) - 1
125   static_assert((URBG::max)() > (URBG::min)(),
126                 "URBG::max and URBG::min may not be equal.");
127 
128   using tag = absl::conditional_t<IsPowerOfTwoOrZero(RangeSize<URBG>()),
129                                   SimplifiedLoopTag, RejectionLoopTag>;
130   return Generate(g, tag{});
131 }
132 
133 template <typename UIntType>
134 template <typename URBG>
135 typename FastUniformBits<UIntType>::result_type
Generate(URBG & g,SimplifiedLoopTag)136 FastUniformBits<UIntType>::Generate(URBG& g,  // NOLINT(runtime/references)
137                                     SimplifiedLoopTag) {
138   // The simplified version of FastUniformBits works only on URBGs that have
139   // a range that is a power of 2. In this case we simply loop and shift without
140   // attempting to balance the bits across calls.
141   static_assert(IsPowerOfTwoOrZero(RangeSize<URBG>()),
142                 "incorrect Generate tag for URBG instance");
143 
144   static constexpr size_t kResultBits =
145       std::numeric_limits<result_type>::digits;
146   static constexpr size_t kUrbgBits = NumBits<URBG>();
147   static constexpr size_t kIters =
148       (kResultBits / kUrbgBits) + (kResultBits % kUrbgBits != 0);
149   static constexpr size_t kShift = (kIters == 1) ? 0 : kUrbgBits;
150   static constexpr auto kMin = (URBG::min)();
151 
152   result_type r = static_cast<result_type>(g() - kMin);
153   for (size_t n = 1; n < kIters; ++n) {
154     r = static_cast<result_type>(r << kShift) +
155         static_cast<result_type>(g() - kMin);
156   }
157   return r;
158 }
159 
160 template <typename UIntType>
161 template <typename URBG>
162 typename FastUniformBits<UIntType>::result_type
Generate(URBG & g,RejectionLoopTag)163 FastUniformBits<UIntType>::Generate(URBG& g,  // NOLINT(runtime/references)
164                                     RejectionLoopTag) {
165   static_assert(!IsPowerOfTwoOrZero(RangeSize<URBG>()),
166                 "incorrect Generate tag for URBG instance");
167   using urbg_result_type = typename URBG::result_type;
168 
169   // See [rand.adapt.ibits] for more details on the constants calculated below.
170   //
171   // It is preferable to use roughly the same number of bits from each generator
172   // call, however this is only possible when the number of bits provided by the
173   // URBG is a divisor of the number of bits in `result_type`. In all other
174   // cases, the number of bits used cannot always be the same, but it can be
175   // guaranteed to be off by at most 1. Thus we run two loops, one with a
176   // smaller bit-width size (`kSmallWidth`) and one with a larger width size
177   // (satisfying `kLargeWidth == kSmallWidth + 1`). The loops are run
178   // `kSmallIters` and `kLargeIters` times respectively such
179   // that
180   //
181   //    `kResultBits == kSmallIters * kSmallBits
182   //                    + kLargeIters * kLargeBits`
183   //
184   // where `kResultBits` is the total number of bits in `result_type`.
185   //
186   static constexpr size_t kResultBits =
187       std::numeric_limits<result_type>::digits;                      // w
188   static constexpr urbg_result_type kUrbgRange = RangeSize<URBG>();  // R
189   static constexpr size_t kUrbgBits = NumBits<URBG>();               // m
190 
191   // compute the initial estimate of the bits used.
192   // [rand.adapt.ibits] 2 (c)
193   static constexpr size_t kA =  // ceil(w/m)
194       (kResultBits / kUrbgBits) + ((kResultBits % kUrbgBits) != 0);  // n'
195 
196   static constexpr size_t kABits = kResultBits / kA;  // w0'
197   static constexpr urbg_result_type kARejection =
198       ((kUrbgRange >> kABits) << kABits);  // y0'
199 
200   // refine the selection to reduce the rejection frequency.
201   static constexpr size_t kTotalIters =
202       ((kUrbgRange - kARejection) <= (kARejection / kA)) ? kA : (kA + 1);  // n
203 
204   // [rand.adapt.ibits] 2 (b)
205   static constexpr size_t kSmallIters =
206       kTotalIters - (kResultBits % kTotalIters);                   // n0
207   static constexpr size_t kSmallBits = kResultBits / kTotalIters;  // w0
208   static constexpr urbg_result_type kSmallRejection =
209       ((kUrbgRange >> kSmallBits) << kSmallBits);  // y0
210 
211   static constexpr size_t kLargeBits = kSmallBits + 1;  // w0+1
212   static constexpr urbg_result_type kLargeRejection =
213       ((kUrbgRange >> kLargeBits) << kLargeBits);  // y1
214 
215   //
216   // Because `kLargeBits == kSmallBits + 1`, it follows that
217   //
218   //     `kResultBits == kSmallIters * kSmallBits + kLargeIters`
219   //
220   // and therefore
221   //
222   //     `kLargeIters == kTotalWidth % kSmallWidth`
223   //
224   // Intuitively, each iteration with the large width accounts for one unit
225   // of the remainder when `kTotalWidth` is divided by `kSmallWidth`. As
226   // mentioned above, if the URBG width is a divisor of `kTotalWidth`, then
227   // there would be no need for any large iterations (i.e., one loop would
228   // suffice), and indeed, in this case, `kLargeIters` would be zero.
229   static_assert(kResultBits == kSmallIters * kSmallBits +
230                                    (kTotalIters - kSmallIters) * kLargeBits,
231                 "Error in looping constant calculations.");
232 
233   // The small shift is essentially small bits, but due to the potential
234   // of generating a smaller result_type from a larger urbg type, the actual
235   // shift might be 0.
236   static constexpr size_t kSmallShift = kSmallBits % kResultBits;
237   static constexpr auto kSmallMask =
238       MaskFromShift<urbg_result_type>(kSmallShift);
239   static constexpr size_t kLargeShift = kLargeBits % kResultBits;
240   static constexpr auto kLargeMask =
241       MaskFromShift<urbg_result_type>(kLargeShift);
242 
243   static constexpr auto kMin = (URBG::min)();
244 
245   result_type s = 0;
246   for (size_t n = 0; n < kSmallIters; ++n) {
247     urbg_result_type v;
248     do {
249       v = g() - kMin;
250     } while (v >= kSmallRejection);
251 
252     s = (s << kSmallShift) + static_cast<result_type>(v & kSmallMask);
253   }
254 
255   for (size_t n = kSmallIters; n < kTotalIters; ++n) {
256     urbg_result_type v;
257     do {
258       v = g() - kMin;
259     } while (v >= kLargeRejection);
260 
261     s = (s << kLargeShift) + static_cast<result_type>(v & kLargeMask);
262   }
263   return s;
264 }
265 
266 }  // namespace random_internal
267 ABSL_NAMESPACE_END
268 }  // namespace absl
269 
270 #endif  // ABSL_RANDOM_INTERNAL_FAST_UNIFORM_BITS_H_
271