diff options
28 files changed, 739 insertions, 370 deletions
diff --git a/absl/base/BUILD.bazel b/absl/base/BUILD.bazel index d74bac631a61..ffeca630706e 100644 --- a/absl/base/BUILD.bazel +++ b/absl/base/BUILD.bazel @@ -558,6 +558,31 @@ cc_test( ) cc_library( + name = "exponential_biased", + srcs = ["internal/exponential_biased.cc"], + hdrs = ["internal/exponential_biased.h"], + linkopts = ABSL_DEFAULT_LINKOPTS, + visibility = [ + "//absl:__subpackages__", + ], + deps = [":core_headers"], +) + +cc_test( + name = "exponential_biased_test", + size = "small", + srcs = ["internal/exponential_biased_test.cc"], + copts = ABSL_TEST_COPTS, + linkopts = ABSL_DEFAULT_LINKOPTS, + visibility = ["//visibility:private"], + deps = [ + ":exponential_biased", + "//absl/strings", + "@com_google_googletest//:gtest_main", + ], +) + +cc_library( name = "scoped_set_env", testonly = 1, srcs = ["internal/scoped_set_env.cc"], diff --git a/absl/base/CMakeLists.txt b/absl/base/CMakeLists.txt index 79ee5b93ed71..2698213c566d 100644 --- a/absl/base/CMakeLists.txt +++ b/absl/base/CMakeLists.txt @@ -505,6 +505,32 @@ absl_cc_test( absl_cc_library( NAME + exponential_biased + SRCS + "internal/exponential_biased.cc" + HDRS + "internal/exponential_biased.h" + COPTS + ${ABSL_DEFAULT_COPTS} + DEPS + absl::core_headers +) + +absl_cc_test( + NAME + exponential_biased_test + SRCS + "internal/exponential_biased_test.cc" + COPTS + ${ABSL_TEST_COPTS} + DEPS + absl::exponential_biased + absl::strings + gmock_main +) + +absl_cc_library( + NAME scoped_set_env SRCS "internal/scoped_set_env.cc" diff --git a/absl/base/config.h b/absl/base/config.h index 039b73d81f70..24851fa33ce4 100644 --- a/absl/base/config.h +++ b/absl/base/config.h @@ -307,7 +307,7 @@ // ABSL_HAVE_SEMAPHORE_H // -// Checks whether the platform supports the <semaphore.h> header and sem_open(3) +// Checks whether the platform supports the <semaphore.h> header and sem_init(3) // family of functions as standardized in POSIX.1-2001. // // Note: While Apple provides <semaphore.h> for both iOS and macOS, it is diff --git a/absl/base/internal/exponential_biased.cc b/absl/base/internal/exponential_biased.cc new file mode 100644 index 000000000000..d7ffd184e968 --- /dev/null +++ b/absl/base/internal/exponential_biased.cc @@ -0,0 +1,84 @@ +// Copyright 2019 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "absl/base/internal/exponential_biased.h" + +#include <stdint.h> + +#include <atomic> +#include <cmath> +#include <limits> + +#include "absl/base/attributes.h" +#include "absl/base/optimization.h" + +namespace absl { +namespace base_internal { + +// The algorithm generates a random number between 0 and 1 and applies the +// inverse cumulative distribution function for an exponential. Specifically: +// Let m be the inverse of the sample period, then the probability +// distribution function is m*exp(-mx) so the CDF is +// p = 1 - exp(-mx), so +// q = 1 - p = exp(-mx) +// log_e(q) = -mx +// -log_e(q)/m = x +// log_2(q) * (-log_e(2) * 1/m) = x +// In the code, q is actually in the range 1 to 2**26, hence the -26 below +int64_t ExponentialBiased::Get(int64_t mean) { + if (ABSL_PREDICT_FALSE(!initialized_)) { + Initialize(); + } + + uint64_t rng = NextRandom(rng_); + rng_ = rng; + + // Take the top 26 bits as the random number + // (This plus the 1<<58 sampling bound give a max possible step of + // 5194297183973780480 bytes.) + // The uint32_t cast is to prevent a (hard-to-reproduce) NAN + // under piii debug for some binaries. + double q = static_cast<uint32_t>(rng >> (kPrngNumBits - 26)) + 1.0; + // Put the computed p-value through the CDF of a geometric. + double interval = (std::log2(q) - 26) * (-std::log(2.0) * mean); + // Very large values of interval overflow int64_t. To avoid that, we will cheat + // and clamp any huge values to (int64_t max)/2. This is a potential source of + // bias, but the mean would need to be such a large value that it's not likely + // to come up. For example, with a mean of 1e18, the probability of hitting + // this condition is about 1/1000. For a mean of 1e17, standard calculators + // claim that this event won't happen. + if (interval > static_cast<double>(std::numeric_limits<int64_t>::max() / 2)) { + return std::numeric_limits<int64_t>::max() / 2; + } + + return static_cast<int64_t>(interval); +} + +void ExponentialBiased::Initialize() { + // We don't get well distributed numbers from `this` so we call NextRandom() a + // bunch to mush the bits around. We use a global_rand to handle the case + // where the same thread (by memory address) gets created and destroyed + // repeatedly. + ABSL_CONST_INIT static std::atomic<uint32_t> global_rand(0); + uint64_t r = reinterpret_cast<uint64_t>(this) + + global_rand.fetch_add(1, std::memory_order_relaxed); + for (int i = 0; i < 20; ++i) { + r = NextRandom(r); + } + rng_ = r; + initialized_ = true; +} + +} // namespace base_internal +} // namespace absl diff --git a/absl/base/internal/exponential_biased.h b/absl/base/internal/exponential_biased.h new file mode 100644 index 000000000000..cac2d8ad84ff --- /dev/null +++ b/absl/base/internal/exponential_biased.h @@ -0,0 +1,77 @@ +// Copyright 2019 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#ifndef ABSL_BASE_INTERNAL_EXPONENTIAL_BIASED_H_ +#define ABSL_BASE_INTERNAL_EXPONENTIAL_BIASED_H_ + +#include <stdint.h> + +namespace absl { +namespace base_internal { + +// ExponentialBiased provides a small and fast random number generator for a +// rounded exponential distribution. This generator doesn't requires very little +// state doesn't impose synchronization overhead, which makes it useful in some +// specialized scenarios. +// +// For the generated variable X, X ~ floor(Exponential(1/mean)). The floor +// operation introduces a small amount of bias, but the distribution is useful +// to generate a wait time. That is, if an operation is supposed to happen on +// average to 1/mean events, then the generated variable X will describe how +// many events to skip before performing the operation and computing a new X. +// +// The mathematically precise distribution to use for integer wait times is a +// Geometric distribution, but a Geometric distribution takes slightly more time +// to compute and when the mean is large (say, 100+), the Geometric distribution +// is hard to distinguish from the result of ExponentialBiased. +// +// This class is thread-compatible. +class ExponentialBiased { + public: + // The number of bits set by NextRandom. + static constexpr int kPrngNumBits = 48; + + // Generates the floor of an exponentially distributed random variable by + // rounding the value down to the nearest integer. The result will be in the + // range [0, int64_t max / 2]. + int64_t Get(int64_t mean); + + // Computes a random number in the range [0, 1<<(kPrngNumBits+1) - 1] + // + // This is public to enable testing. + static uint64_t NextRandom(uint64_t rnd); + + private: + void Initialize(); + + uint64_t rng_{0}; + bool initialized_{false}; +}; + +// Returns the next prng value. +// pRNG is: aX+b mod c with a = 0x5DEECE66D, b = 0xB, c = 1<<48 +// This is the lrand64 generator. +inline uint64_t ExponentialBiased::NextRandom(uint64_t rnd) { + const uint64_t prng_mult = uint64_t{0x5DEECE66D}; + const uint64_t prng_add = 0xB; + const uint64_t prng_mod_power = 48; + const uint64_t prng_mod_mask = + ~((~static_cast<uint64_t>(0)) << prng_mod_power); + return (prng_mult * rnd + prng_add) & prng_mod_mask; +} + +} // namespace base_internal +} // namespace absl + +#endif // ABSL_BASE_INTERNAL_EXPONENTIAL_BIASED_H_ diff --git a/absl/base/internal/exponential_biased_test.cc b/absl/base/internal/exponential_biased_test.cc new file mode 100644 index 000000000000..09b511d14e70 --- /dev/null +++ b/absl/base/internal/exponential_biased_test.cc @@ -0,0 +1,168 @@ +// Copyright 2019 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "absl/base/internal/exponential_biased.h" + +#include <stddef.h> + +#include <cmath> +#include <cstdint> +#include <vector> + +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include "absl/strings/str_cat.h" + +using ::testing::Ge; + +namespace absl { +namespace base_internal { + +MATCHER_P2(IsBetween, a, b, + absl::StrCat(std::string(negation ? "isn't" : "is"), " between ", a, + " and ", b)) { + return a <= arg && arg <= b; +} + +// Tests of the quality of the random numbers generated +// This uses the Anderson Darling test for uniformity. +// See "Evaluating the Anderson-Darling Distribution" by Marsaglia +// for details. + +// Short cut version of ADinf(z), z>0 (from Marsaglia) +// This returns the p-value for Anderson Darling statistic in +// the limit as n-> infinity. For finite n, apply the error fix below. +double AndersonDarlingInf(double z) { + if (z < 2) { + return exp(-1.2337141 / z) / sqrt(z) * + (2.00012 + + (0.247105 - + (0.0649821 - (0.0347962 - (0.011672 - 0.00168691 * z) * z) * z) * + z) * + z); + } + return exp( + -exp(1.0776 - + (2.30695 - + (0.43424 - (0.082433 - (0.008056 - 0.0003146 * z) * z) * z) * z) * + z)); +} + +// Corrects the approximation error in AndersonDarlingInf for small values of n +// Add this to AndersonDarlingInf to get a better approximation +// (from Marsaglia) +double AndersonDarlingErrFix(int n, double x) { + if (x > 0.8) { + return (-130.2137 + + (745.2337 - + (1705.091 - (1950.646 - (1116.360 - 255.7844 * x) * x) * x) * x) * + x) / + n; + } + double cutoff = 0.01265 + 0.1757 / n; + if (x < cutoff) { + double t = x / cutoff; + t = sqrt(t) * (1 - t) * (49 * t - 102); + return t * (0.0037 / (n * n) + 0.00078 / n + 0.00006) / n; + } else { + double t = (x - cutoff) / (0.8 - cutoff); + t = -0.00022633 + + (6.54034 - (14.6538 - (14.458 - (8.259 - 1.91864 * t) * t) * t) * t) * + t; + return t * (0.04213 + 0.01365 / n) / n; + } +} + +// Returns the AndersonDarling p-value given n and the value of the statistic +double AndersonDarlingPValue(int n, double z) { + double ad = AndersonDarlingInf(z); + double errfix = AndersonDarlingErrFix(n, ad); + return ad + errfix; +} + +double AndersonDarlingStatistic(const std::vector<double>& random_sample) { + int n = random_sample.size(); + double ad_sum = 0; + for (int i = 0; i < n; i++) { + ad_sum += (2 * i + 1) * + std::log(random_sample[i] * (1 - random_sample[n - 1 - i])); + } + double ad_statistic = -n - 1 / static_cast<double>(n) * ad_sum; + return ad_statistic; +} + +// Tests if the array of doubles is uniformly distributed. +// Returns the p-value of the Anderson Darling Statistic +// for the given set of sorted random doubles +// See "Evaluating the Anderson-Darling Distribution" by +// Marsaglia and Marsaglia for details. +double AndersonDarlingTest(const std::vector<double>& random_sample) { + double ad_statistic = AndersonDarlingStatistic(random_sample); + double p = AndersonDarlingPValue(random_sample.size(), ad_statistic); + return p; +} + +// Testing that NextRandom generates uniform random numbers. Applies the +// Anderson-Darling test for uniformity +TEST(ExponentialBiasedTest, TestNextRandom) { + for (auto n : std::vector<int>({ + 10, // Check short-range correlation + 100, 1000, + 10000 // Make sure there's no systemic error + })) { + uint64_t x = 1; + // This assumes that the prng returns 48 bit numbers + uint64_t max_prng_value = static_cast<uint64_t>(1) << 48; + // Initialize. + for (int i = 1; i <= 20; i++) { + x = ExponentialBiased::NextRandom(x); + } + std::vector<uint64_t> int_random_sample(n); + // Collect samples + for (int i = 0; i < n; i++) { + int_random_sample[i] = x; + x = ExponentialBiased::NextRandom(x); + } + // First sort them... + std::sort(int_random_sample.begin(), int_random_sample.end()); + std::vector<double> random_sample(n); + // Convert them to uniform randoms (in the range [0,1]) + for (int i = 0; i < n; i++) { + random_sample[i] = + static_cast<double>(int_random_sample[i]) / max_prng_value; + } + // Now compute the Anderson-Darling statistic + double ad_pvalue = AndersonDarlingTest(random_sample); + EXPECT_GT(std::min(ad_pvalue, 1 - ad_pvalue), 0.0001) + << "prng is not uniform: n = " << n << " p = " << ad_pvalue; + } +} + +// The generator needs to be available as a thread_local and as a static +// variable. +TEST(ExponentialBiasedTest, InitializationModes) { + ABSL_CONST_INIT static ExponentialBiased eb_static; + EXPECT_THAT(eb_static.Get(2), Ge(0)); + +#if ABSL_HAVE_THREAD_LOCAL + thread_local ExponentialBiased eb_thread; + EXPECT_THAT(eb_thread.Get(2), Ge(0)); +#endif + + ExponentialBiased eb_stack; + EXPECT_THAT(eb_stack.Get(2), Ge(0)); +} + +} // namespace base_internal +} // namespace absl diff --git a/absl/base/optimization.h b/absl/base/optimization.h index 0dcbef32a3c5..646523b34612 100644 --- a/absl/base/optimization.h +++ b/absl/base/optimization.h @@ -172,7 +172,7 @@ #if ABSL_HAVE_BUILTIN(__builtin_expect) || \ (defined(__GNUC__) && !defined(__clang__)) #define ABSL_PREDICT_FALSE(x) (__builtin_expect(x, 0)) -#define ABSL_PREDICT_TRUE(x) (__builtin_expect(!!(x), 1)) +#define ABSL_PREDICT_TRUE(x) (__builtin_expect(false || (x), true)) #else #define ABSL_PREDICT_FALSE(x) (x) #define ABSL_PREDICT_TRUE(x) (x) diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index 0894bb207c67..e60979b2a54f 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel @@ -493,6 +493,7 @@ cc_library( ":have_sse", "//absl/base", "//absl/base:core_headers", + "//absl/base:exponential_biased", "//absl/debugging:stacktrace", "//absl/memory", "//absl/synchronization", diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index 933c7a8c48a4..aa33659b322a 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt @@ -538,6 +538,7 @@ absl_cc_library( ${ABSL_DEFAULT_COPTS} DEPS absl::base + absl::exponential_biased absl::have_sse absl::synchronization ) diff --git a/absl/container/flat_hash_map.h b/absl/container/flat_hash_map.h index 5c16ac88fbb8..283f24396764 100644 --- a/absl/container/flat_hash_map.h +++ b/absl/container/flat_hash_map.h @@ -401,7 +401,7 @@ class flat_hash_map : public absl::container_internal::raw_hash_map< // for the past-the-end iterator, which is invalidated. // // `swap()` requires that the flat hash map's hashing and key equivalence - // functions be Swappable, and are exchaged using unqualified calls to + // functions be Swappable, and are exchanged using unqualified calls to // non-member `swap()`. If the map's allocator has // `std::allocator_traits<allocator_type>::propagate_on_container_swap::value` // set to `true`, the allocators are also exchanged using an unqualified call diff --git a/absl/container/internal/hashtablez_sampler.cc b/absl/container/internal/hashtablez_sampler.cc index 054e89817815..0a7ef61c8fe5 100644 --- a/absl/container/internal/hashtablez_sampler.cc +++ b/absl/container/internal/hashtablez_sampler.cc @@ -21,6 +21,7 @@ #include <limits> #include "absl/base/attributes.h" +#include "absl/base/internal/exponential_biased.h" #include "absl/container/internal/have_sse.h" #include "absl/debugging/stacktrace.h" #include "absl/memory/memory.h" @@ -37,77 +38,13 @@ ABSL_CONST_INIT std::atomic<bool> g_hashtablez_enabled{ ABSL_CONST_INIT std::atomic<int32_t> g_hashtablez_sample_parameter{1 << 10}; ABSL_CONST_INIT std::atomic<int32_t> g_hashtablez_max_samples{1 << 20}; -// Returns the next pseudo-random value. -// pRNG is: aX+b mod c with a = 0x5DEECE66D, b = 0xB, c = 1<<48 -// This is the lrand64 generator. -uint64_t NextRandom(uint64_t rnd) { - const uint64_t prng_mult = uint64_t{0x5DEECE66D}; - const uint64_t prng_add = 0xB; - const uint64_t prng_mod_power = 48; - const uint64_t prng_mod_mask = ~(~uint64_t{0} << prng_mod_power); - return (prng_mult * rnd + prng_add) & prng_mod_mask; -} - -// Generates a geometric variable with the specified mean. -// This is done by generating a random number between 0 and 1 and applying -// the inverse cumulative distribution function for an exponential. -// Specifically: Let m be the inverse of the sample period, then -// the probability distribution function is m*exp(-mx) so the CDF is -// p = 1 - exp(-mx), so -// q = 1 - p = exp(-mx) -// log_e(q) = -mx -// -log_e(q)/m = x -// log_2(q) * (-log_e(2) * 1/m) = x -// In the code, q is actually in the range 1 to 2**26, hence the -26 below -// -int64_t GetGeometricVariable(int64_t mean) { #if ABSL_HAVE_THREAD_LOCAL - thread_local -#else // ABSL_HAVE_THREAD_LOCAL - // SampleSlow and hence GetGeometricVariable is guarded by a single mutex when - // there are not thread locals. Thus, a single global rng is acceptable for - // that case. - static -#endif // ABSL_HAVE_THREAD_LOCAL - uint64_t rng = []() { - // We don't get well distributed numbers from this so we call - // NextRandom() a bunch to mush the bits around. We use a global_rand - // to handle the case where the same thread (by memory address) gets - // created and destroyed repeatedly. - ABSL_CONST_INIT static std::atomic<uint32_t> global_rand(0); - uint64_t r = reinterpret_cast<uint64_t>(&rng) + - global_rand.fetch_add(1, std::memory_order_relaxed); - for (int i = 0; i < 20; ++i) { - r = NextRandom(r); - } - return r; - }(); - - rng = NextRandom(rng); - - // Take the top 26 bits as the random number - // (This plus the 1<<58 sampling bound give a max possible step of - // 5194297183973780480 bytes.) - const uint64_t prng_mod_power = 48; // Number of bits in prng - // The uint32_t cast is to prevent a (hard-to-reproduce) NAN - // under piii debug for some binaries. - double q = static_cast<uint32_t>(rng >> (prng_mod_power - 26)) + 1.0; - // Put the computed p-value through the CDF of a geometric. - double interval = (log2(q) - 26) * (-std::log(2.0) * mean); - - // Very large values of interval overflow int64_t. If we happen to - // hit such improbable condition, we simply cheat and clamp interval - // to largest supported value. - if (interval > static_cast<double>(std::numeric_limits<int64_t>::max() / 2)) { - return std::numeric_limits<int64_t>::max() / 2; - } - - // Small values of interval are equivalent to just sampling next time. - if (interval < 1) { - return 1; - } - return static_cast<int64_t>(interval); -} +thread_local absl::base_internal::ExponentialBiased + g_exponential_biased_generator; +#else +ABSL_CONST_INIT static absl::base_internal::ExponentialBiased + g_exponential_biased_generator; +#endif } // namespace @@ -253,8 +190,12 @@ HashtablezInfo* SampleSlow(int64_t* next_sample) { } bool first = *next_sample < 0; - *next_sample = GetGeometricVariable( + *next_sample = g_exponential_biased_generator.Get( g_hashtablez_sample_parameter.load(std::memory_order_relaxed)); + // Small values of interval are equivalent to just sampling next time. + if (*next_sample < 1) { + *next_sample = 1; + } // g_hashtablez_enabled can be dynamically flipped, we need to set a threshold // low enough that we will start sampling in a reasonable time, so we just use diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 42b3c4681133..9992ba4b8ac0 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h @@ -614,13 +614,17 @@ class raw_hash_set { iterator() {} // PRECONDITION: not an end() iterator. - reference operator*() const { return PolicyTraits::element(slot_); } + reference operator*() const { + /* To be enabled: assert_is_full(); */ + return PolicyTraits::element(slot_); + } // PRECONDITION: not an end() iterator. pointer operator->() const { return &operator*(); } // PRECONDITION: not an end() iterator. iterator& operator++() { + /* To be enabled: assert_is_full(); */ ++ctrl_; ++slot_; skip_empty_or_deleted(); @@ -634,6 +638,8 @@ class raw_hash_set { } friend bool operator==(const iterator& a, const iterator& b) { + /* To be enabled: a.assert_is_valid(); */ + /* To be enabled: b.assert_is_valid(); */ return a.ctrl_ == b.ctrl_; } friend bool operator!=(const iterator& a, const iterator& b) { @@ -644,6 +650,11 @@ class raw_hash_set { iterator(ctrl_t* ctrl) : ctrl_(ctrl) {} // for end() iterator(ctrl_t* ctrl, slot_type* slot) : ctrl_(ctrl), slot_(slot) {} + void assert_is_full() const { assert(IsFull(*ctrl_)); } + void assert_is_valid() const { + assert(!ctrl_ || IsFull(*ctrl_) || *ctrl_ == kSentinel); + } + void skip_empty_or_deleted() { while (IsEmptyOrDeleted(*ctrl_)) { // ctrl is not necessarily aligned to Group::kWidth. It is also likely @@ -1155,7 +1166,7 @@ class raw_hash_set { // This overload is necessary because otherwise erase<K>(const K&) would be // a better match if non-const iterator is passed as an argument. void erase(iterator it) { - assert(it != end()); + it.assert_is_full(); PolicyTraits::destroy(&alloc_ref(), it.slot_); erase_meta_only(it); } @@ -1172,12 +1183,14 @@ class raw_hash_set { template <typename H, typename E> void merge(raw_hash_set<Policy, H, E, Alloc>& src) { // NOLINT assert(this != &src); - for (auto it = src.begin(), e = src.end(); it != e; ++it) { + for (auto it = src.begin(), e = src.end(); it != e;) { + auto next = std::next(it); if (PolicyTraits::apply(InsertSlot<false>{*this, std::move(*it.slot_)}, PolicyTraits::element(it.slot_)) .second) { src.erase_meta_only(it); } + it = next; } } @@ -1187,6 +1200,7 @@ class raw_hash_set { } node_type extract(const_iterator position) { + position.inner_.assert_is_full(); auto node = CommonAccess::Transfer<node_type>(alloc_ref(), position.inner_.slot_); erase_meta_only(position); diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index ed4ca8c88d3b..33cfa72ce7ab 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc @@ -1837,7 +1837,7 @@ TEST(TableDeathTest, EraseOfEndAsserts) { IntTable t; // Extra simple "regexp" as regexp support is highly varied across platforms. - constexpr char kDeathMsg[] = "it != end"; + constexpr char kDeathMsg[] = "IsFull"; EXPECT_DEATH_IF_SUPPORTED(t.erase(t.end()), kDeathMsg); } diff --git a/absl/copts/AbseilConfigureCopts.cmake b/absl/copts/AbseilConfigureCopts.cmake index b430873c5e07..b442646948a2 100644 --- a/absl/copts/AbseilConfigureCopts.cmake +++ b/absl/copts/AbseilConfigureCopts.cmake @@ -5,10 +5,29 @@ set(ABSL_LSAN_LINKOPTS "") set(ABSL_HAVE_LSAN OFF) set(ABSL_DEFAULT_LINKOPTS "") +if("${CMAKE_SYSTEM_PROCESSOR}" STREQUAL "x86_64") + if (MSVC) + set(ABSL_RANDOM_RANDEN_COPTS "${ABSL_RANDOM_HWAES_MSVC_X64_FLAGS}") + else() + set(ABSL_RANDOM_RANDEN_COPTS "${ABSL_RANDOM_HWAES_X64_FLAGS}") + endif() +elseif("${CMAKE_SYSTEM_PROCESSOR}" STREQUAL "arm") + if ("${CMAKE_SIZEOF_VOID_P}" STREQUAL "8") + set(ABSL_RANDOM_RANDEN_COPTS "${ABSL_RANDOM_HWAES_ARM64_FLAGS}") + elseif("${CMAKE_SIZEOF_VOID_P}" STREQUAL "4") + set(ABSL_RANDOM_RANDEN_COPTS "${ABSL_RANDOM_HWAES_ARM32_FLAGS}") + else() + message(WARNING "Value of CMAKE_SIZEOF_VOID_P (${CMAKE_SIZEOF_VOID_P}) is not supported.") + endif() +else() + message(WARNING "Value of CMAKE_SYSTEM_PROCESSOR (${CMAKE_SYSTEM_PROCESSOR}) is unknown and cannot be used to set ABSL_RANDOM_RANDEN_COPTS") + set(ABSL_RANDOM_RANDEN_COPTS "") +endif() + + if("${CMAKE_CXX_COMPILER_ID}" STREQUAL "GNU") set(ABSL_DEFAULT_COPTS "${ABSL_GCC_FLAGS}") set(ABSL_TEST_COPTS "${ABSL_GCC_FLAGS};${ABSL_GCC_TEST_FLAGS}") - set(ABSL_RANDOM_RANDEN_COPTS "${ABSL_RANDOM_HWAES_X64_FLAGS}") elseif("${CMAKE_CXX_COMPILER_ID}" MATCHES "Clang") # MATCHES so we get both Clang and AppleClang if(MSVC) @@ -16,11 +35,9 @@ elseif("${CMAKE_CXX_COMPILER_ID}" MATCHES "Clang") set(ABSL_DEFAULT_COPTS "${ABSL_CLANG_CL_FLAGS}") set(ABSL_TEST_COPTS "${ABSL_CLANG_CL_FLAGS};${ABSL_CLANG_CL_TEST_FLAGS}") set(ABSL_DEFAULT_LINKOPTS "${ABSL_MSVC_LINKOPTS}") - set(ABSL_RANDOM_RANDEN_COPTS "${ABSL_RANDOM_HWAES_MSVC_X64_FLAGS}") else() set(ABSL_DEFAULT_COPTS "${ABSL_LLVM_FLAGS}") set(ABSL_TEST_COPTS "${ABSL_LLVM_FLAGS};${ABSL_LLVM_TEST_FLAGS}") - set(ABSL_RANDOM_RANDEN_COPTS "${ABSL_RANDOM_HWAES_X64_FLAGS}") if("${CMAKE_CXX_COMPILER_ID}" STREQUAL "Clang") # AppleClang doesn't have lsan # https://developer.apple.com/documentation/code_diagnostics @@ -34,12 +51,10 @@ elseif("${CMAKE_CXX_COMPILER_ID}" STREQUAL "MSVC") set(ABSL_DEFAULT_COPTS "${ABSL_MSVC_FLAGS}") set(ABSL_TEST_COPTS "${ABSL_MSVC_FLAGS};${ABSL_MSVC_TEST_FLAGS}") set(ABSL_DEFAULT_LINKOPTS "${ABSL_MSVC_LINKOPTS}") - set(ABSL_RANDOM_RANDEN_COPTS "${ABSL_RANDOM_HWAES_MSVC_X64_FLAGS}") else() message(WARNING "Unknown compiler: ${CMAKE_CXX_COMPILER}. Building with no default flags") set(ABSL_DEFAULT_COPTS "") set(ABSL_TEST_COPTS "") - set(ABSL_RANDOM_RANDEN_COPTS "") endif() if("${CMAKE_CXX_STANDARD}" EQUAL 98) diff --git a/absl/random/BUILD.bazel b/absl/random/BUILD.bazel index 828f1348bacb..c3520df8dccb 100644 --- a/absl/random/BUILD.bazel +++ b/absl/random/BUILD.bazel @@ -69,10 +69,10 @@ cc_library( "//absl/base:base_internal", "//absl/base:core_headers", "//absl/meta:type_traits", - "//absl/random/internal:distribution_impl", "//absl/random/internal:distributions", "//absl/random/internal:fast_uniform_bits", "//absl/random/internal:fastmath", + "//absl/random/internal:generate_real", "//absl/random/internal:iostream_state_saver", "//absl/random/internal:traits", "//absl/random/internal:uniform_helper", diff --git a/absl/random/CMakeLists.txt b/absl/random/CMakeLists.txt index 19dd2cabf57a..289854ffd40d 100644 --- a/absl/random/CMakeLists.txt +++ b/absl/random/CMakeLists.txt @@ -58,7 +58,7 @@ absl_cc_library( DEPS absl::base_internal absl::core_headers - absl::random_internal_distribution_impl + absl::random_internal_generate_real absl::random_internal_distributions absl::random_internal_fast_uniform_bits absl::random_internal_fastmath @@ -543,19 +543,18 @@ absl_cc_library( # Internal-only target, do not depend on directly. absl_cc_library( NAME - random_internal_distribution_impl + random_internal_generate_real HDRS - "internal/distribution_impl.h" + "internal/generate_real.h" COPTS ${ABSL_DEFAULT_COPTS} LINKOPTS ${ABSL_DEFAULT_LINKOPTS} DEPS absl::bits - absl::config - absl::int128 absl::random_internal_fastmath absl::random_internal_traits + absl::type_traits ) # Internal-only target, do not depend on directly. @@ -767,9 +766,9 @@ absl_cc_test( # Internal-only target, do not depend on directly. absl_cc_test( NAME - random_internal_distribution_impl_test + random_internal_generate_real_test SRCS - "internal/distribution_impl_test.cc" + "internal/generate_real_test.cc" COPTS ${ABSL_TEST_COPTS} LINKOPTS @@ -777,8 +776,7 @@ absl_cc_test( DEPS absl::bits absl::flags - absl::int128 - absl::random_internal_distribution_impl + absl::random_internal_generate_real gtest_main ) @@ -1029,7 +1027,6 @@ absl_cc_library( ${ABSL_DEFAULT_LINKOPTS} DEPS absl::core_headers - absl::random_internal_distribution_impl absl::random_internal_fast_uniform_bits absl::random_internal_iostream_state_saver absl::random_internal_traits diff --git a/absl/random/beta_distribution.h b/absl/random/beta_distribution.h index e29894f2037f..b09b02f0dde5 100644 --- a/absl/random/beta_distribution.h +++ b/absl/random/beta_distribution.h @@ -22,9 +22,10 @@ #include <ostream> #include <type_traits> -#include "absl/random/internal/distribution_impl.h" +#include "absl/meta/type_traits.h" #include "absl/random/internal/fast_uniform_bits.h" #include "absl/random/internal/fastmath.h" +#include "absl/random/internal/generate_real.h" #include "absl/random/internal/iostream_state_saver.h" namespace absl { @@ -275,15 +276,21 @@ typename beta_distribution<RealType>::result_type beta_distribution<RealType>::AlgorithmJoehnk( URBG& g, // NOLINT(runtime/references) const param_type& p) { + using random_internal::GeneratePositiveTag; + using random_internal::GenerateRealFromBits; + using real_type = + absl::conditional_t<std::is_same<RealType, float>::value, float, double>; + // Based on Joehnk, M. D. Erzeugung von betaverteilten und gammaverteilten // Zufallszahlen. Metrika 8.1 (1964): 5-15. // This method is described in Knuth, Vol 2 (Third Edition), pp 134. - using RandU64ToReal = typename random_internal::RandU64ToReal<result_type>; - using random_internal::PositiveValueT; + result_type u, v, x, y, z; for (;;) { - u = RandU64ToReal::template Value<PositiveValueT, false>(fast_u64_(g)); - v = RandU64ToReal::template Value<PositiveValueT, false>(fast_u64_(g)); + u = GenerateRealFromBits<real_type, GeneratePositiveTag, false>( + fast_u64_(g)); + v = GenerateRealFromBits<real_type, GeneratePositiveTag, false>( + fast_u64_(g)); // Direct method. std::pow is slow for float, so rely on the optimizer to // remove the std::pow() path for that case. @@ -327,12 +334,14 @@ typename beta_distribution<RealType>::result_type beta_distribution<RealType>::AlgorithmCheng( URBG& g, // NOLINT(runtime/references) const param_type& p) { + using random_internal::GeneratePositiveTag; + using random_internal::GenerateRealFromBits; + using real_type = + absl::conditional_t<std::is_same<RealType, float>::value, float, double>; + // Based on Cheng, Russell CH. Generating beta variates with nonintegral // shape parameters. Communications of the ACM 21.4 (1978): 317-322. // (https://dl.acm.org/citation.cfm?id=359482). - using RandU64ToReal = typename random_internal::RandU64ToReal<result_type>; - using random_internal::PositiveValueT; - static constexpr result_type kLogFour = result_type(1.3862943611198906188344642429163531361); // log(4) static constexpr result_type kS = @@ -341,8 +350,10 @@ beta_distribution<RealType>::AlgorithmCheng( const bool use_algorithm_ba = (p.method_ == param_type::CHENG_BA); result_type u1, u2, v, w, z, r, s, t, bw_inv, lhs; for (;;) { - u1 = RandU64ToReal::template Value<PositiveValueT, false>(fast_u64_(g)); - u2 = RandU64ToReal::template Value<PositiveValueT, false>(fast_u64_(g)); + u1 = GenerateRealFromBits<real_type, GeneratePositiveTag, false>( + fast_u64_(g)); + u2 = GenerateRealFromBits<real_type, GeneratePositiveTag, false>( + fast_u64_(g)); v = p.y_ * std::log(u1 / (1 - u1)); w = p.a_ * std::exp(v); bw_inv = result_type(1) / (p.b_ + w); diff --git a/absl/random/beta_distribution_test.cc b/absl/random/beta_distribution_test.cc index 966ad08b5c91..d0111b3e3a83 100644 --- a/absl/random/beta_distribution_test.cc +++ b/absl/random/beta_distribution_test.cc @@ -92,7 +92,7 @@ TYPED_TEST(BetaDistributionInterfaceTest, SerializeTest) { for (TypeParam alpha : kValues) { for (TypeParam beta : kValues) { ABSL_INTERNAL_LOG( - INFO, absl::StrFormat("Smoke test for Beta(%f, %f)", alpha, beta)); + INFO, absl::StrFormat("Smoke test for Beta(%a, %a)", alpha, beta)); param_type param(alpha, beta); absl::beta_distribution<TypeParam> before(alpha, beta); diff --git a/absl/random/exponential_distribution.h b/absl/random/exponential_distribution.h index c8af197575c1..24abf57e99d6 100644 --- a/absl/random/exponential_distribution.h +++ b/absl/random/exponential_distribution.h @@ -21,8 +21,9 @@ #include <limits> #include <type_traits> -#include "absl/random/internal/distribution_impl.h" +#include "absl/meta/type_traits.h" #include "absl/random/internal/fast_uniform_bits.h" +#include "absl/random/internal/generate_real.h" #include "absl/random/internal/iostream_state_saver.h" namespace absl { @@ -118,9 +119,14 @@ typename exponential_distribution<RealType>::result_type exponential_distribution<RealType>::operator()( URBG& g, // NOLINT(runtime/references) const param_type& p) { - using random_internal::NegativeValueT; - const result_type u = random_internal::RandU64ToReal< - result_type>::template Value<NegativeValueT, false>(fast_u64_(g)); + using random_internal::GenerateNegativeTag; + using random_internal::GenerateRealFromBits; + using real_type = + absl::conditional_t<std::is_same<RealType, float>::value, float, double>; + + const result_type u = GenerateRealFromBits<real_type, GenerateNegativeTag, + false>(fast_u64_(g)); // U(-1, 0) + // log1p(-x) is mathematically equivalent to log(1 - x) but has more // accuracy for x near zero. return p.neg_inv_lambda_ * std::log1p(u); diff --git a/absl/random/gaussian_distribution.h b/absl/random/gaussian_distribution.h index 1d1347bce0a0..c299e9441c46 100644 --- a/absl/random/gaussian_distribution.h +++ b/absl/random/gaussian_distribution.h @@ -28,8 +28,8 @@ #include <limits> #include <type_traits> -#include "absl/random/internal/distribution_impl.h" #include "absl/random/internal/fast_uniform_bits.h" +#include "absl/random/internal/generate_real.h" #include "absl/random/internal/iostream_state_saver.h" namespace absl { @@ -207,12 +207,18 @@ namespace random_internal { template <typename URBG> inline double gaussian_distribution_base::zignor_fallback(URBG& g, bool neg) { + using random_internal::GeneratePositiveTag; + using random_internal::GenerateRealFromBits; + // This fallback path happens approximately 0.05% of the time. double x, y; do { // kRInv = 1/r, U(0, 1) - x = kRInv * std::log(RandU64ToDouble<PositiveValueT, false>(fast_u64_(g))); - y = -std::log(RandU64ToDouble<PositiveValueT, false>(fast_u64_(g))); + x = kRInv * + std::log(GenerateRealFromBits<double, GeneratePositiveTag, false>( + fast_u64_(g))); + y = -std::log( + GenerateRealFromBits<double, GeneratePositiveTag, false>(fast_u64_(g))); } while ((y + y) < (x * x)); return neg ? (x - kR) : (kR - x); } @@ -220,6 +226,10 @@ inline double gaussian_distribution_base::zignor_fallback(URBG& g, bool neg) { template <typename URBG> inline double gaussian_distribution_base::zignor( URBG& g) { // NOLINT(runtime/references) + using random_internal::GeneratePositiveTag; + using random_internal::GenerateRealFromBits; + using random_internal::GenerateSignedTag; + while (true) { // We use a single uint64_t to generate both a double and a strip. // These bits are unused when the generated double is > 1/2^5. @@ -227,7 +237,8 @@ inline double gaussian_distribution_base::zignor( // values (those smaller than 1/2^5, which all end up on the left tail). uint64_t bits = fast_u64_(g); int i = static_cast<int>(bits & kMask); // pick a random strip - double j = RandU64ToDouble<SignedValueT, false>(bits); // U(-1, 1) + double j = GenerateRealFromBits<double, GenerateSignedTag, false>( + bits); // U(-1, 1) const double x = j * zg_.x[i]; // Retangular box. Handles >97% of all cases. @@ -244,7 +255,8 @@ inline double gaussian_distribution_base::zignor( } // i > 0: Wedge samples using precomputed values. - double v = RandU64ToDouble<PositiveValueT, false>(fast_u64_(g)); // U(0, 1) + double v = GenerateRealFromBits<double, GeneratePositiveTag, false>( + fast_u64_(g)); // U(0, 1) if ((zg_.f[i + 1] + v * (zg_.f[i] - zg_.f[i + 1])) < std::exp(-0.5 * x * x)) { return x; diff --git a/absl/random/internal/BUILD.bazel b/absl/random/internal/BUILD.bazel index ec58cecd43e9..91388d19f3c5 100644 --- a/absl/random/internal/BUILD.bazel +++ b/absl/random/internal/BUILD.bazel @@ -175,9 +175,9 @@ cc_library( ) cc_library( - name = "distribution_impl", + name = "generate_real", hdrs = [ - "distribution_impl.h", + "generate_real.h", ], copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, @@ -185,8 +185,7 @@ cc_library( ":fastmath", ":traits", "//absl/base:bits", - "//absl/base:config", - "//absl/numeric:int128", + "//absl/meta:type_traits", ], ) @@ -398,16 +397,17 @@ cc_test( ) cc_test( - name = "distribution_impl_test", + name = "generate_real_test", size = "small", - srcs = ["distribution_impl_test.cc"], + srcs = [ + "generate_real_test.cc", + ], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ - ":distribution_impl", + ":generate_real", "//absl/base:bits", "//absl/flags:flag", - "//absl/numeric:int128", "@com_google_googletest//:gtest_main", ], ) diff --git a/absl/random/internal/distribution_impl.h b/absl/random/internal/distribution_impl.h deleted file mode 100644 index 49b3e1a6e33d..000000000000 --- a/absl/random/internal/distribution_impl.h +++ /dev/null @@ -1,194 +0,0 @@ -// Copyright 2017 The Abseil Authors. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// https://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -#ifndef ABSL_RANDOM_INTERNAL_DISTRIBUTION_IMPL_H_ -#define ABSL_RANDOM_INTERNAL_DISTRIBUTION_IMPL_H_ - -// This file contains some implementation details which are used by one or more -// of the absl random number distributions. - -#include <cfloat> -#include <cstddef> -#include <cstdint> -#include <cstring> -#include <limits> -#include <type_traits> - -#if (defined(_WIN32) || defined(_WIN64)) && defined(_M_IA64) -#include <intrin.h> // NOLINT(build/include_order) -#pragma intrinsic(_umul128) -#define ABSL_INTERNAL_USE_UMUL128 1 -#endif - -#include "absl/base/config.h" -#include "absl/base/internal/bits.h" -#include "absl/numeric/int128.h" -#include "absl/random/internal/fastmath.h" -#include "absl/random/internal/traits.h" - -namespace absl { -namespace random_internal { - -// Creates a double from `bits`, with the template fields controlling the -// output. -// -// RandU64To is both more efficient and generates more unique values in the -// result interval than known implementations of std::generate_canonical(). -// -// The `Signed` parameter controls whether positive, negative, or both are -// returned (thus affecting the output interval). -// When Signed == SignedValueT, range is U(-1, 1) -// When Signed == NegativeValueT, range is U(-1, 0) -// When Signed == PositiveValueT, range is U(0, 1) -// -// When the `IncludeZero` parameter is true, the function may return 0 for some -// inputs, otherwise it never returns 0. -// -// The `ExponentBias` parameter determines the scale of the output range by -// adjusting the exponent. -// -// When a value in U(0,1) is required, use: -// RandU64ToDouble<PositiveValueT, true, 0>(); -// -// When a value in U(-1,1) is required, use: -// RandU64ToDouble<SignedValueT, false, 0>() => U(-1, 1) -// This generates more distinct values than the mathematically equivalent -// expression `U(0, 1) * 2.0 - 1.0`, and is preferable. -// -// Scaling the result by powers of 2 (and avoiding a multiply) is also possible: -// RandU64ToDouble<PositiveValueT, false, 1>(); => U(0, 2) -// RandU64ToDouble<PositiveValueT, false, -1>(); => U(0, 0.5) -// - -// Tristate types controlling the output. -struct PositiveValueT {}; -struct NegativeValueT {}; -struct SignedValueT {}; - -// RandU64ToDouble is the double-result variant of RandU64To, described above. -template <typename Signed, bool IncludeZero, int ExponentBias = 0> -inline double RandU64ToDouble(uint64_t bits) { - static_assert(std::is_same<Signed, PositiveValueT>::value || - std::is_same<Signed, NegativeValueT>::value || - std::is_same<Signed, SignedValueT>::value, - ""); - - // Maybe use the left-most bit for a sign bit. - uint64_t sign = std::is_same<Signed, NegativeValueT>::value - ? 0x8000000000000000ull - : 0; // Sign bits. - - if (std::is_same<Signed, SignedValueT>::value) { - sign = bits & 0x8000000000000000ull; - bits = bits & 0x7FFFFFFFFFFFFFFFull; - } - if (IncludeZero) { - if (bits == 0u) return 0; - } - - // Number of leading zeros is mapped to the exponent: 2^-clz - int clz = base_internal::CountLeadingZeros64(bits); - // Shift number left to erase leading zeros. - bits <<= IncludeZero ? clz : (clz & 63); - - // Shift number right to remove bits that overflow double mantissa. The - // direction of the shift depends on `clz`. - bits >>= (64 - DBL_MANT_DIG); - - // Compute IEEE 754 double exponent. - // In the Signed case, bits is a 63-bit number with a 0 msb. Adjust the - // exponent to account for that. - const uint64_t exp = - (std::is_same<Signed, SignedValueT>::value ? 1023U : 1022U) + - static_cast<uint64_t>(ExponentBias - clz); - constexpr int kExp = DBL_MANT_DIG - 1; - // Construct IEEE 754 double from exponent and mantissa. - const uint64_t val = sign | (exp << kExp) | (bits & ((1ULL << kExp) - 1U)); - - double res; - static_assert(sizeof(res) == sizeof(val), "double is not 64 bit"); - // Memcpy value from "val" to "res" to avoid aliasing problems. Assumes that - // endian-ness is same for double and uint64_t. - std::memcpy(&res, &val, sizeof(res)); - - return res; -} - -// RandU64ToFloat is the float-result variant of RandU64To, described above. -template <typename Signed, bool IncludeZero, int ExponentBias = 0> -inline float RandU64ToFloat(uint64_t bits) { - static_assert(std::is_same<Signed, PositiveValueT>::value || - std::is_same<Signed, NegativeValueT>::value || - std::is_same<Signed, SignedValueT>::value, - ""); - - // Maybe use the left-most bit for a sign bit. - uint64_t sign = std::is_same<Signed, NegativeValueT>::value - ? 0x80000000ul - : 0; // Sign bits. - - if (std::is_same<Signed, SignedValueT>::value) { - uint64_t a = bits & 0x8000000000000000ull; - sign = static_cast<uint32_t>(a >> 32); - bits = bits & 0x7FFFFFFFFFFFFFFFull; - } - if (IncludeZero) { - if (bits == 0u) return 0; - } - - // Number of leading zeros is mapped to the exponent: 2^-clz - int clz = base_internal::CountLeadingZeros64(bits); - // Shift number left to erase leading zeros. - bits <<= IncludeZero ? clz : (clz & 63); - // Shift number right to remove bits that overflow double mantissa. The - // direction of the shift depends on `clz`. - bits >>= (64 - FLT_MANT_DIG); - - // Construct IEEE 754 float exponent. - // In the Signed case, bits is a 63-bit number with a 0 msb. Adjust the - // exponent to account for that. - const uint32_t exp = - (std::is_same<Signed, SignedValueT>::value ? 127U : 126U) + - static_cast<uint32_t>(ExponentBias - clz); - constexpr int kExp = FLT_MANT_DIG - 1; - const uint32_t val = sign | (exp << kExp) | (bits & ((1U << kExp) - 1U)); - - float res; - static_assert(sizeof(res) == sizeof(val), "float is not 32 bit"); - // Assumes that endian-ness is same for float and uint32_t. - std::memcpy(&res, &val, sizeof(res)); - - return res; -} - -template <typename Result> -struct RandU64ToReal { - template <typename Signed, bool IncludeZero, int ExponentBias = 0> - static inline Result Value(uint64_t bits) { - return RandU64ToDouble<Signed, IncludeZero, ExponentBias>(bits); - } -}; - -template <> -struct RandU64ToReal<float> { - template <typename Signed, bool IncludeZero, int ExponentBias = 0> - static inline float Value(uint64_t bits) { - return RandU64ToFloat<Signed, IncludeZero, ExponentBias>(bits); - } -}; - -} // namespace random_internal -} // namespace absl - -#endif // ABSL_RANDOM_INTERNAL_DISTRIBUTION_IMPL_H_ diff --git a/absl/random/internal/generate_real.h b/absl/random/internal/generate_real.h new file mode 100644 index 000000000000..246d863e56e4 --- /dev/null +++ b/absl/random/internal/generate_real.h @@ -0,0 +1,144 @@ +// Copyright 2017 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#ifndef ABSL_RANDOM_INTERNAL_GENERATE_REAL_H_ +#define ABSL_RANDOM_INTERNAL_GENERATE_REAL_H_ + +// This file contains some implementation details which are used by one or more +// of the absl random number distributions. + +#include <cstdint> +#include <cstring> +#include <limits> +#include <type_traits> + +#include "absl/base/internal/bits.h" +#include "absl/meta/type_traits.h" +#include "absl/random/internal/fastmath.h" +#include "absl/random/internal/traits.h" + +namespace absl { +namespace random_internal { + +// Tristate tag types controlling the output of GenerateRealFromBits. +struct GeneratePositiveTag {}; +struct GenerateNegativeTag {}; +struct GenerateSignedTag {}; + +// GenerateRealFromBits generates a single real value from a single 64-bit +// `bits` with template fields controlling the output. +// +// The `SignedTag` parameter controls whether positive, negative, +// or either signed/unsigned may be returned. +// When SignedTag == GeneratePositiveTag, range is U(0, 1) +// When SignedTag == GenerateNegativeTag, range is U(-1, 0) +// When SignedTag == GenerateSignedTag, range is U(-1, 1) +// +// When the `IncludeZero` parameter is true, the function may return 0 for some +// inputs, otherwise it never returns 0. +// +// When a value in U(0,1) is required, use: +// Uniform64ToReal<double, PositiveValueT, true>; +// +// When a value in U(-1,1) is required, use: +// Uniform64ToReal<double, SignedValueT, false>; +// +// This generates more distinct values than the mathematical equivalent +// `U(0, 1) * 2.0 - 1.0`. +// +// Scaling the result by powers of 2 (and avoiding a multiply) is also possible: +// GenerateRealFromBits<double>(..., -1); => U(0, 0.5) +// GenerateRealFromBits<double>(..., 1); => U(0, 2) +// +template <typename RealType, // Real type, either float or double. + typename SignedTag = GeneratePositiveTag, // Whether a positive, + // negative, or signed + // value is generated. + bool IncludeZero = true> +inline RealType GenerateRealFromBits(uint64_t bits, int exp_bias = 0) { + using real_type = RealType; + using uint_type = absl::conditional_t<std::is_same<real_type, float>::value, + uint32_t, uint64_t>; + + static_assert( + (std::is_same<double, real_type>::value || + std::is_same<float, real_type>::value), + "GenerateRealFromBits must be parameterized by either float or double."); + + static_assert(sizeof(uint_type) == sizeof(real_type), + "Mismatched unsinged and real types."); + + static_assert((std::numeric_limits<real_type>::is_iec559 && + std::numeric_limits<real_type>::radix == 2), + "RealType representation is not IEEE 754 binary."); + + static_assert((std::is_same<SignedTag, GeneratePositiveTag>::value || + std::is_same<SignedTag, GenerateNegativeTag>::value || + std::is_same<SignedTag, GenerateSignedTag>::value), + ""); + + static constexpr int kExp = std::numeric_limits<real_type>::digits - 1; + static constexpr uint_type kMask = (static_cast<uint_type>(1) << kExp) - 1u; + static constexpr int kUintBits = sizeof(uint_type) * 8; + + int exp = exp_bias + int{std::numeric_limits<real_type>::max_exponent - 2}; + + // Determine the sign bit. + // Depending on the SignedTag, this may use the left-most bit + // or it may be a constant value. + uint_type sign = std::is_same<SignedTag, GenerateNegativeTag>::value + ? (static_cast<uint_type>(1) << (kUintBits - 1)) + : 0; + if (std::is_same<SignedTag, GenerateSignedTag>::value) { + if (std::is_same<uint_type, uint64_t>::value) { + sign = bits & uint64_t{0x8000000000000000}; + } + if (std::is_same<uint_type, uint32_t>::value) { + const uint64_t tmp = bits & uint64_t{0x8000000000000000}; + sign = static_cast<uint32_t>(tmp >> 32); + } + // adjust the bits and the exponent to account for removing + // the leading bit. + bits = bits & uint64_t{0x7FFFFFFFFFFFFFFF}; + exp++; + } + if (IncludeZero) { + if (bits == 0u) return 0; + } + + // Number of leading zeros is mapped to the exponent: 2^-clz + // bits is 0..01xxxxxx. After shifting, we're left with 1xxx...0..0 + int clz = base_internal::CountLeadingZeros64(bits); + bits <<= (IncludeZero ? clz : (clz & 63)); // remove 0-bits. + exp -= clz; // set the exponent. + bits >>= (63 - kExp); + + // Construct the 32-bit or 64-bit IEEE 754 floating-point value from + // the individual fields: sign, exp, mantissa(bits). + uint_type val = + (std::is_same<SignedTag, GeneratePositiveTag>::value ? 0u : sign) | + (static_cast<uint_type>(exp) << kExp) | + (static_cast<uint_type>(bits) & kMask); + + // bit_cast to the output-type + real_type result; + memcpy(static_cast<void*>(&result), static_cast<const void*>(&val), + sizeof(result)); + return result; +} + +} // namespace random_internal +} // namespace absl + +#endif // ABSL_RANDOM_INTERNAL_GENERATE_REAL_H_ diff --git a/absl/random/internal/distribution_impl_test.cc b/absl/random/internal/generate_real_test.cc index fcc169046d7e..aa02f0c2c1b9 100644 --- a/absl/random/internal/distribution_impl_test.cc +++ b/absl/random/internal/generate_real_test.cc @@ -12,57 +12,74 @@ // See the License for the specific language governing permissions and // limitations under the License. -#include "absl/random/internal/distribution_impl.h" +#include "absl/random/internal/generate_real.h" + +#include <cfloat> +#include <cstddef> +#include <cstdint> +#include <string> #include "gtest/gtest.h" #include "absl/base/internal/bits.h" #include "absl/flags/flag.h" -#include "absl/numeric/int128.h" ABSL_FLAG(int64_t, absl_random_test_trials, 50000, "Number of trials for the probability tests."); -using absl::random_internal::NegativeValueT; -using absl::random_internal::PositiveValueT; -using absl::random_internal::RandU64ToDouble; -using absl::random_internal::RandU64ToFloat; -using absl::random_internal::SignedValueT; +using absl::random_internal::GenerateNegativeTag; +using absl::random_internal::GeneratePositiveTag; +using absl::random_internal::GenerateRealFromBits; +using absl::random_internal::GenerateSignedTag; namespace { -TEST(DistributionImplTest, U64ToFloat_Positive_NoZero_Test) { +TEST(GenerateRealTest, U64ToFloat_Positive_NoZero_Test) { auto ToFloat = [](uint64_t a) { - return RandU64ToFloat<PositiveValueT, false>(a); + return GenerateRealFromBits<float, GeneratePositiveTag, false>(a); }; EXPECT_EQ(ToFloat(0x0000000000000000), 2.710505431e-20f); EXPECT_EQ(ToFloat(0x0000000000000001), 5.421010862e-20f); EXPECT_EQ(ToFloat(0x8000000000000000), 0.5); + EXPECT_EQ(ToFloat(0x8000000000000001), 0.5); EXPECT_EQ(ToFloat(0xFFFFFFFFFFFFFFFF), 0.9999999404f); } -TEST(DistributionImplTest, U64ToFloat_Positive_Zero_Test) { +TEST(GenerateRealTest, U64ToFloat_Positive_Zero_Test) { auto ToFloat = [](uint64_t a) { - return RandU64ToFloat<PositiveValueT, true>(a); + return GenerateRealFromBits<float, GeneratePositiveTag, true>(a); }; EXPECT_EQ(ToFloat(0x0000000000000000), 0.0); EXPECT_EQ(ToFloat(0x0000000000000001), 5.421010862e-20f); EXPECT_EQ(ToFloat(0x8000000000000000), 0.5); + EXPECT_EQ(ToFloat(0x8000000000000001), 0.5); EXPECT_EQ(ToFloat(0xFFFFFFFFFFFFFFFF), 0.9999999404f); } -TEST(DistributionImplTest, U64ToFloat_Negative_NoZero_Test) { +TEST(GenerateRealTest, U64ToFloat_Negative_NoZero_Test) { auto ToFloat = [](uint64_t a) { - return RandU64ToFloat<NegativeValueT, false>(a); + return GenerateRealFromBits<float, GenerateNegativeTag, false>(a); }; EXPECT_EQ(ToFloat(0x0000000000000000), -2.710505431e-20f); EXPECT_EQ(ToFloat(0x0000000000000001), -5.421010862e-20f); EXPECT_EQ(ToFloat(0x8000000000000000), -0.5); + EXPECT_EQ(ToFloat(0x8000000000000001), -0.5); EXPECT_EQ(ToFloat(0xFFFFFFFFFFFFFFFF), -0.9999999404f); } -TEST(DistributionImplTest, U64ToFloat_Signed_NoZero_Test) { +TEST(GenerateRealTest, U64ToFloat_Negative_Zero_Test) { auto ToFloat = [](uint64_t a) { - return RandU64ToFloat<SignedValueT, false>(a); + return GenerateRealFromBits<float, GenerateNegativeTag, true>(a); + }; + EXPECT_EQ(ToFloat(0x0000000000000000), 0.0); + EXPECT_EQ(ToFloat(0x0000000000000001), -5.421010862e-20f); + EXPECT_EQ(ToFloat(0x8000000000000000), -0.5); + EXPECT_EQ(ToFloat(0x8000000000000001), -0.5); + EXPECT_EQ(ToFloat(0xFFFFFFFFFFFFFFFF), -0.9999999404f); +} + +TEST(GenerateRealTest, U64ToFloat_Signed_NoZero_Test) { + auto ToFloat = [](uint64_t a) { + return GenerateRealFromBits<float, GenerateSignedTag, false>(a); }; EXPECT_EQ(ToFloat(0x0000000000000000), 5.421010862e-20f); EXPECT_EQ(ToFloat(0x0000000000000001), 1.084202172e-19f); @@ -72,9 +89,9 @@ TEST(DistributionImplTest, U64ToFloat_Signed_NoZero_Test) { EXPECT_EQ(ToFloat(0xFFFFFFFFFFFFFFFF), -0.9999999404f); } -TEST(DistributionImplTest, U64ToFloat_Signed_Zero_Test) { +TEST(GenerateRealTest, U64ToFloat_Signed_Zero_Test) { auto ToFloat = [](uint64_t a) { - return RandU64ToFloat<SignedValueT, true>(a); + return GenerateRealFromBits<float, GenerateSignedTag, true>(a); }; EXPECT_EQ(ToFloat(0x0000000000000000), 0); EXPECT_EQ(ToFloat(0x0000000000000001), 1.084202172e-19f); @@ -84,9 +101,9 @@ TEST(DistributionImplTest, U64ToFloat_Signed_Zero_Test) { EXPECT_EQ(ToFloat(0xFFFFFFFFFFFFFFFF), -0.9999999404f); } -TEST(DistributionImplTest, U64ToFloat_Signed_Bias_Test) { +TEST(GenerateRealTest, U64ToFloat_Signed_Bias_Test) { auto ToFloat = [](uint64_t a) { - return RandU64ToFloat<SignedValueT, true, 1>(a); + return GenerateRealFromBits<float, GenerateSignedTag, true>(a, 1); }; EXPECT_EQ(ToFloat(0x0000000000000000), 0); EXPECT_EQ(ToFloat(0x0000000000000001), 2 * 1.084202172e-19f); @@ -96,9 +113,9 @@ TEST(DistributionImplTest, U64ToFloat_Signed_Bias_Test) { EXPECT_EQ(ToFloat(0xFFFFFFFFFFFFFFFF), 2 * -0.9999999404f); } -TEST(DistributionImplTest, U64ToFloatTest) { +TEST(GenerateRealTest, U64ToFloatTest) { auto ToFloat = [](uint64_t a) -> float { - return RandU64ToFloat<PositiveValueT, true>(a); + return GenerateRealFromBits<float, GeneratePositiveTag, true>(a); }; EXPECT_EQ(ToFloat(0x0000000000000000), 0.0f); @@ -150,44 +167,60 @@ TEST(DistributionImplTest, U64ToFloatTest) { } } -TEST(DistributionImplTest, U64ToDouble_Positive_NoZero_Test) { +TEST(GenerateRealTest, U64ToDouble_Positive_NoZero_Test) { auto ToDouble = [](uint64_t a) { - return RandU64ToDouble<PositiveValueT, false>(a); + return GenerateRealFromBits<double, GeneratePositiveTag, false>(a); }; EXPECT_EQ(ToDouble(0x0000000000000000), 2.710505431213761085e-20); EXPECT_EQ(ToDouble(0x0000000000000001), 5.42101086242752217004e-20); EXPECT_EQ(ToDouble(0x0000000000000002), 1.084202172485504434e-19); EXPECT_EQ(ToDouble(0x8000000000000000), 0.5); + EXPECT_EQ(ToDouble(0x8000000000000001), 0.5); EXPECT_EQ(ToDouble(0xFFFFFFFFFFFFFFFF), 0.999999999999999888978); } -TEST(DistributionImplTest, U64ToDouble_Positive_Zero_Test) { +TEST(GenerateRealTest, U64ToDouble_Positive_Zero_Test) { auto ToDouble = [](uint64_t a) { - return RandU64ToDouble<PositiveValueT, true>(a); + return GenerateRealFromBits<double, GeneratePositiveTag, true>(a); }; EXPECT_EQ(ToDouble(0x0000000000000000), 0.0); EXPECT_EQ(ToDouble(0x0000000000000001), 5.42101086242752217004e-20); EXPECT_EQ(ToDouble(0x8000000000000000), 0.5); + EXPECT_EQ(ToDouble(0x8000000000000001), 0.5); EXPECT_EQ(ToDouble(0xFFFFFFFFFFFFFFFF), 0.999999999999999888978); } -TEST(DistributionImplTest, U64ToDouble_Negative_NoZero_Test) { +TEST(GenerateRealTest, U64ToDouble_Negative_NoZero_Test) { auto ToDouble = [](uint64_t a) { - return RandU64ToDouble<NegativeValueT, false>(a); + return GenerateRealFromBits<double, GenerateNegativeTag, false>(a); }; EXPECT_EQ(ToDouble(0x0000000000000000), -2.710505431213761085e-20); EXPECT_EQ(ToDouble(0x0000000000000001), -5.42101086242752217004e-20); EXPECT_EQ(ToDouble(0x0000000000000002), -1.084202172485504434e-19); EXPECT_EQ(ToDouble(0x8000000000000000), -0.5); + EXPECT_EQ(ToDouble(0x8000000000000001), -0.5); + EXPECT_EQ(ToDouble(0xFFFFFFFFFFFFFFFF), -0.999999999999999888978); +} + +TEST(GenerateRealTest, U64ToDouble_Negative_Zero_Test) { + auto ToDouble = [](uint64_t a) { + return GenerateRealFromBits<double, GenerateNegativeTag, true>(a); + }; + + EXPECT_EQ(ToDouble(0x0000000000000000), 0.0); + EXPECT_EQ(ToDouble(0x0000000000000001), -5.42101086242752217004e-20); + EXPECT_EQ(ToDouble(0x0000000000000002), -1.084202172485504434e-19); + EXPECT_EQ(ToDouble(0x8000000000000000), -0.5); + EXPECT_EQ(ToDouble(0x8000000000000001), -0.5); EXPECT_EQ(ToDouble(0xFFFFFFFFFFFFFFFF), -0.999999999999999888978); } -TEST(DistributionImplTest, U64ToDouble_Signed_NoZero_Test) { +TEST(GenerateRealTest, U64ToDouble_Signed_NoZero_Test) { auto ToDouble = [](uint64_t a) { - return RandU64ToDouble<SignedValueT, false>(a); + return GenerateRealFromBits<double, GenerateSignedTag, false>(a); }; EXPECT_EQ(ToDouble(0x0000000000000000), 5.42101086242752217004e-20); @@ -198,9 +231,9 @@ TEST(DistributionImplTest, U64ToDouble_Signed_NoZero_Test) { EXPECT_EQ(ToDouble(0xFFFFFFFFFFFFFFFF), -0.999999999999999888978); } -TEST(DistributionImplTest, U64ToDouble_Signed_Zero_Test) { +TEST(GenerateRealTest, U64ToDouble_Signed_Zero_Test) { auto ToDouble = [](uint64_t a) { - return RandU64ToDouble<SignedValueT, true>(a); + return GenerateRealFromBits<double, GenerateSignedTag, true>(a); }; EXPECT_EQ(ToDouble(0x0000000000000000), 0); EXPECT_EQ(ToDouble(0x0000000000000001), 1.084202172485504434e-19); @@ -210,9 +243,9 @@ TEST(DistributionImplTest, U64ToDouble_Signed_Zero_Test) { EXPECT_EQ(ToDouble(0xFFFFFFFFFFFFFFFF), -0.999999999999999888978); } -TEST(DistributionImplTest, U64ToDouble_Signed_Bias_Test) { +TEST(GenerateRealTest, U64ToDouble_GenerateSignedTag_Bias_Test) { auto ToDouble = [](uint64_t a) { - return RandU64ToDouble<SignedValueT, true, -1>(a); + return GenerateRealFromBits<double, GenerateSignedTag, true>(a, -1); }; EXPECT_EQ(ToDouble(0x0000000000000000), 0); EXPECT_EQ(ToDouble(0x0000000000000001), 1.084202172485504434e-19 / 2); @@ -222,9 +255,9 @@ TEST(DistributionImplTest, U64ToDouble_Signed_Bias_Test) { EXPECT_EQ(ToDouble(0xFFFFFFFFFFFFFFFF), -0.999999999999999888978 / 2); } -TEST(DistributionImplTest, U64ToDoubleTest) { +TEST(GenerateRealTest, U64ToDoubleTest) { auto ToDouble = [](uint64_t a) { - return RandU64ToDouble<PositiveValueT, true>(a); + return GenerateRealFromBits<double, GeneratePositiveTag, true>(a); }; EXPECT_EQ(ToDouble(0x0000000000000000), 0.0); @@ -296,9 +329,9 @@ TEST(DistributionImplTest, U64ToDoubleTest) { } } -TEST(DistributionImplTest, U64ToDoubleSignedTest) { +TEST(GenerateRealTest, U64ToDoubleSignedTest) { auto ToDouble = [](uint64_t a) { - return RandU64ToDouble<SignedValueT, false>(a); + return GenerateRealFromBits<double, GenerateSignedTag, false>(a); }; EXPECT_EQ(ToDouble(0x0000000000000000), 5.42101086242752217004e-20); @@ -379,10 +412,10 @@ TEST(DistributionImplTest, U64ToDoubleSignedTest) { } } -TEST(DistributionImplTest, ExhaustiveFloat) { +TEST(GenerateRealTest, ExhaustiveFloat) { using absl::base_internal::CountLeadingZeros64; auto ToFloat = [](uint64_t a) { - return RandU64ToFloat<PositiveValueT, true>(a); + return GenerateRealFromBits<float, GeneratePositiveTag, true>(a); }; // Rely on RandU64ToFloat generating values from greatest to least when diff --git a/absl/random/log_uniform_int_distribution.h b/absl/random/log_uniform_int_distribution.h index ac43416ee573..956a69070ccd 100644 --- a/absl/random/log_uniform_int_distribution.h +++ b/absl/random/log_uniform_int_distribution.h @@ -23,8 +23,8 @@ #include <ostream> #include <type_traits> -#include "absl/random/internal/distribution_impl.h" #include "absl/random/internal/fastmath.h" +#include "absl/random/internal/generate_real.h" #include "absl/random/internal/iostream_state_saver.h" #include "absl/random/internal/traits.h" #include "absl/random/uniform_int_distribution.h" diff --git a/absl/random/poisson_distribution.h b/absl/random/poisson_distribution.h index 7750b1c9ba59..23a953ff253c 100644 --- a/absl/random/poisson_distribution.h +++ b/absl/random/poisson_distribution.h @@ -22,9 +22,9 @@ #include <ostream> #include <type_traits> -#include "absl/random/internal/distribution_impl.h" #include "absl/random/internal/fast_uniform_bits.h" #include "absl/random/internal/fastmath.h" +#include "absl/random/internal/generate_real.h" #include "absl/random/internal/iostream_state_saver.h" namespace absl { @@ -164,9 +164,9 @@ typename poisson_distribution<IntType>::result_type poisson_distribution<IntType>::operator()( URBG& g, // NOLINT(runtime/references) const param_type& p) { - using random_internal::PositiveValueT; - using random_internal::RandU64ToDouble; - using random_internal::SignedValueT; + using random_internal::GeneratePositiveTag; + using random_internal::GenerateRealFromBits; + using random_internal::GenerateSignedTag; if (p.split_ != 0) { // Use Knuth's algorithm with range splitting to avoid floating-point @@ -186,7 +186,8 @@ poisson_distribution<IntType>::operator()( for (int split = p.split_; split > 0; --split) { double r = 1.0; do { - r *= RandU64ToDouble<PositiveValueT, true>(fast_u64_(g)); + r *= GenerateRealFromBits<double, GeneratePositiveTag, true>( + fast_u64_(g)); // U(-1, 0) ++n; } while (r > p.emu_); --n; @@ -205,10 +206,11 @@ poisson_distribution<IntType>::operator()( // and k = max(f). const double a = p.mean_ + 0.5; for (;;) { - const double u = - RandU64ToDouble<PositiveValueT, false>(fast_u64_(g)); // (0, 1) - const double v = - RandU64ToDouble<SignedValueT, false>(fast_u64_(g)); // (-1, 1) + const double u = GenerateRealFromBits<double, GeneratePositiveTag, false>( + fast_u64_(g)); // U(0, 1) + const double v = GenerateRealFromBits<double, GenerateSignedTag, false>( + fast_u64_(g)); // U(-1, 1) + const double x = std::floor(p.s_ * v / u + a); if (x < 0) continue; // f(negative) = 0 const double rhs = x * p.lmu_; diff --git a/absl/random/uniform_int_distribution.h b/absl/random/uniform_int_distribution.h index 02aa376555e6..dc8ba8c1e2a2 100644 --- a/absl/random/uniform_int_distribution.h +++ b/absl/random/uniform_int_distribution.h @@ -34,7 +34,6 @@ #include <type_traits> #include "absl/base/optimization.h" -#include "absl/random/internal/distribution_impl.h" #include "absl/random/internal/fast_uniform_bits.h" #include "absl/random/internal/iostream_state_saver.h" #include "absl/random/internal/traits.h" diff --git a/absl/random/uniform_real_distribution.h b/absl/random/uniform_real_distribution.h index 336abb3907bf..bf2ed2c5ad36 100644 --- a/absl/random/uniform_real_distribution.h +++ b/absl/random/uniform_real_distribution.h @@ -39,8 +39,9 @@ #include <limits> #include <type_traits> -#include "absl/random/internal/distribution_impl.h" +#include "absl/meta/type_traits.h" #include "absl/random/internal/fast_uniform_bits.h" +#include "absl/random/internal/generate_real.h" #include "absl/random/internal/iostream_state_saver.h" namespace absl { @@ -76,6 +77,7 @@ class uniform_real_distribution { // is not possible, so value generation cannot use the full range of the // real type. assert(range_ <= (std::numeric_limits<result_type>::max)()); + assert(std::isfinite(range_)); } result_type a() const { return lo_; } @@ -151,10 +153,15 @@ template <typename URBG> typename uniform_real_distribution<RealType>::result_type uniform_real_distribution<RealType>::operator()( URBG& gen, const param_type& p) { // NOLINT(runtime/references) - using random_internal::PositiveValueT; + using random_internal::GeneratePositiveTag; + using random_internal::GenerateRealFromBits; + using real_type = + absl::conditional_t<std::is_same<RealType, float>::value, float, double>; + while (true) { - const result_type sample = random_internal::RandU64ToReal< - result_type>::template Value<PositiveValueT, true>(fast_u64_(gen)); + const result_type sample = + GenerateRealFromBits<real_type, GeneratePositiveTag, true>( + fast_u64_(gen)); const result_type res = p.a() + (sample * p.range_); if (res < p.b() || p.range_ <= 0 || !std::isfinite(p.range_)) { return res; |