• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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_GENERATE_REAL_H_
16 #define ABSL_RANDOM_INTERNAL_GENERATE_REAL_H_
17 
18 // This file contains some implementation details which are used by one or more
19 // of the absl random number distributions.
20 
21 #include <cstdint>
22 #include <cstring>
23 #include <limits>
24 #include <type_traits>
25 
26 #include "absl/meta/type_traits.h"
27 #include "absl/numeric/bits.h"
28 #include "absl/random/internal/fastmath.h"
29 #include "absl/random/internal/traits.h"
30 
31 namespace absl {
32 ABSL_NAMESPACE_BEGIN
33 namespace random_internal {
34 
35 // Tristate tag types controlling the output of GenerateRealFromBits.
36 struct GeneratePositiveTag {};
37 struct GenerateNegativeTag {};
38 struct GenerateSignedTag {};
39 
40 // GenerateRealFromBits generates a single real value from a single 64-bit
41 // `bits` with template fields controlling the output.
42 //
43 // The `SignedTag` parameter controls whether positive, negative,
44 // or either signed/unsigned may be returned.
45 //   When SignedTag == GeneratePositiveTag, range is U(0, 1)
46 //   When SignedTag == GenerateNegativeTag, range is U(-1, 0)
47 //   When SignedTag == GenerateSignedTag, range is U(-1, 1)
48 //
49 // When the `IncludeZero` parameter is true, the function may return 0 for some
50 // inputs, otherwise it never returns 0.
51 //
52 // When a value in U(0,1) is required, use:
53 //   Uniform64ToReal<double, PositiveValueT, true>;
54 //
55 // When a value in U(-1,1) is required, use:
56 //   Uniform64ToReal<double, SignedValueT, false>;
57 //
58 //   This generates more distinct values than the mathematical equivalent
59 //   `U(0, 1) * 2.0 - 1.0`.
60 //
61 // Scaling the result by powers of 2 (and avoiding a multiply) is also possible:
62 //   GenerateRealFromBits<double>(..., -1);  => U(0, 0.5)
63 //   GenerateRealFromBits<double>(..., 1);   => U(0, 2)
64 //
65 template <typename RealType,  // Real type, either float or double.
66           typename SignedTag = GeneratePositiveTag,  // Whether a positive,
67                                                      // negative, or signed
68                                                      // value is generated.
69           bool IncludeZero = true>
70 inline RealType GenerateRealFromBits(uint64_t bits, int exp_bias = 0) {
71   using real_type = RealType;
72   using uint_type = absl::conditional_t<std::is_same<real_type, float>::value,
73                                         uint32_t, uint64_t>;
74 
75   static_assert(
76       (std::is_same<double, real_type>::value ||
77        std::is_same<float, real_type>::value),
78       "GenerateRealFromBits must be parameterized by either float or double.");
79 
80   static_assert(sizeof(uint_type) == sizeof(real_type),
81                 "Mismatched unsinged and real types.");
82 
83   static_assert((std::numeric_limits<real_type>::is_iec559 &&
84                  std::numeric_limits<real_type>::radix == 2),
85                 "RealType representation is not IEEE 754 binary.");
86 
87   static_assert((std::is_same<SignedTag, GeneratePositiveTag>::value ||
88                  std::is_same<SignedTag, GenerateNegativeTag>::value ||
89                  std::is_same<SignedTag, GenerateSignedTag>::value),
90                 "");
91 
92   static constexpr int kExp = std::numeric_limits<real_type>::digits - 1;
93   static constexpr uint_type kMask = (static_cast<uint_type>(1) << kExp) - 1u;
94   static constexpr int kUintBits = sizeof(uint_type) * 8;
95 
96   int exp = exp_bias + int{std::numeric_limits<real_type>::max_exponent - 2};
97 
98   // Determine the sign bit.
99   // Depending on the SignedTag, this may use the left-most bit
100   // or it may be a constant value.
101   uint_type sign = std::is_same<SignedTag, GenerateNegativeTag>::value
102                        ? (static_cast<uint_type>(1) << (kUintBits - 1))
103                        : 0;
104   if (std::is_same<SignedTag, GenerateSignedTag>::value) {
105     if (std::is_same<uint_type, uint64_t>::value) {
106       sign = bits & uint64_t{0x8000000000000000};
107     }
108     if (std::is_same<uint_type, uint32_t>::value) {
109       const uint64_t tmp = bits & uint64_t{0x8000000000000000};
110       sign = static_cast<uint32_t>(tmp >> 32);
111     }
112     // adjust the bits and the exponent to account for removing
113     // the leading bit.
114     bits = bits & uint64_t{0x7FFFFFFFFFFFFFFF};
115     exp++;
116   }
117   if (IncludeZero) {
118     if (bits == 0u) return 0;
119   }
120 
121   // Number of leading zeros is mapped to the exponent: 2^-clz
122   // bits is 0..01xxxxxx. After shifting, we're left with 1xxx...0..0
123   int clz = countl_zero(bits);
124   bits <<= (IncludeZero ? clz : (clz & 63));  // remove 0-bits.
125   exp -= clz;                                 // set the exponent.
126   bits >>= (63 - kExp);
127 
128   // Construct the 32-bit or 64-bit IEEE 754 floating-point value from
129   // the individual fields: sign, exp, mantissa(bits).
130   uint_type val = sign | (static_cast<uint_type>(exp) << kExp) |
131                   (static_cast<uint_type>(bits) & kMask);
132 
133   // bit_cast to the output-type
134   real_type result;
135   memcpy(static_cast<void*>(&result), static_cast<const void*>(&val),
136          sizeof(result));
137   return result;
138 }
139 
140 }  // namespace random_internal
141 ABSL_NAMESPACE_END
142 }  // namespace absl
143 
144 #endif  // ABSL_RANDOM_INTERNAL_GENERATE_REAL_H_
145