diff options
Diffstat (limited to 'absl/random/internal')
49 files changed, 918 insertions, 718 deletions
diff --git a/absl/random/internal/BUILD.bazel b/absl/random/internal/BUILD.bazel index fd5471a6..d7ad4efe 100644 --- a/absl/random/internal/BUILD.bazel +++ b/absl/random/internal/BUILD.bazel @@ -1,3 +1,21 @@ +# +# 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. +# + +load("@rules_cc//cc:defs.bzl", "cc_binary", "cc_library", "cc_test") + # Internal-only implementation classes for Abseil Random load( "//absl:copts/configure_copts.bzl", @@ -33,24 +51,21 @@ cc_library( visibility = [ "//absl/random:__pkg__", ], + deps = ["//absl/base:config"], ) cc_library( name = "distributions", - hdrs = [ - "distributions.h", - ], + hdrs = ["distributions.h"], copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ ":distribution_caller", - ":fast_uniform_bits", - ":fastmath", ":traits", ":uniform_helper", + "//absl/base", "//absl/meta:type_traits", "//absl/strings", - "//absl/types:span", ], ) @@ -64,6 +79,7 @@ cc_library( visibility = [ "//absl/random:__pkg__", ], + deps = ["//absl/base:config"], ) cc_library( @@ -75,11 +91,14 @@ cc_library( "seed_material.h", ], copts = ABSL_DEFAULT_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, + linkopts = ABSL_DEFAULT_LINKOPTS + select({ + "//absl:windows": ["-DEFAULTLIB:bcrypt.lib"], + "//conditions:default": [], + }), deps = [ ":fast_uniform_bits", - "//absl/base", "//absl/base:core_headers", + "//absl/base:raw_logging_internal", "//absl/strings", "//absl/types:optional", "//absl/types:span", @@ -107,6 +126,7 @@ cc_library( "//absl/base:config", "//absl/base:core_headers", "//absl/base:endian", + "//absl/base:raw_logging_internal", "//absl/random:seed_gen_exception", "//absl/types:span", ], @@ -120,6 +140,7 @@ cc_library( ], copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, + deps = ["//absl/base:config"], ) cc_library( @@ -130,6 +151,7 @@ cc_library( ], copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, + deps = ["//absl/base:config"], ) cc_library( @@ -160,9 +182,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, @@ -170,8 +192,7 @@ cc_library( ":fastmath", ":traits", "//absl/base:bits", - "//absl/base:config", - "//absl/numeric:int128", + "//absl/meta:type_traits", ], ) @@ -186,6 +207,19 @@ cc_library( ) cc_library( + name = "wide_multiply", + hdrs = ["wide_multiply.h"], + copts = ABSL_DEFAULT_COPTS, + linkopts = ABSL_DEFAULT_LINKOPTS, + deps = [ + ":traits", + "//absl/base:bits", + "//absl/base:config", + "//absl/numeric:int128", + ], +) + +cc_library( name = "nonsecure_base", hdrs = ["nonsecure_base.h"], copts = ABSL_DEFAULT_COPTS, @@ -239,6 +273,7 @@ cc_library( "randen-keys.inc", "platform.h", ], + deps = ["//absl/base:config"], ) cc_library( @@ -255,7 +290,7 @@ cc_library( ":platform", ":randen_hwaes", ":randen_slow", - "//absl/base", + "//absl/base:raw_logging_internal", ], ) @@ -267,6 +302,8 @@ cc_library( linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ ":platform", + "//absl/base:config", + "//absl/base:core_headers", ], ) @@ -286,6 +323,7 @@ cc_library( deps = [ ":platform", ":randen_hwaes_impl", + "//absl/base:config", ], ) @@ -305,7 +343,11 @@ cc_library( # anyway and thus there wouldn't be any gain from using it as a module. features = ["-header_modules"], linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [":platform"], + deps = [ + ":platform", + "//absl/base:config", + "//absl/base:core_headers", + ], ) cc_binary( @@ -334,8 +376,9 @@ cc_library( copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ - "//absl/base", + "//absl/base:config", "//absl/base:core_headers", + "//absl/base:raw_logging_internal", "//absl/strings", "//absl/strings:str_format", "//absl/types:span", @@ -367,16 +410,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", ], ) @@ -459,6 +503,29 @@ cc_test( ], ) +cc_library( + name = "mocking_bit_gen_base", + hdrs = ["mocking_bit_gen_base.h"], + linkopts = ABSL_DEFAULT_LINKOPTS, + deps = [ + "//absl/random", + "//absl/strings", + ], +) + +cc_library( + name = "mock_overload_set", + testonly = 1, + hdrs = ["mock_overload_set.h"], + visibility = [ + "//absl/random:__pkg__", + ], + deps = [ + "//absl/random:mocking_bit_gen", + "@com_google_googletest//:gtest", + ], +) + cc_test( name = "nonsecure_base_test", size = "small", @@ -531,7 +598,7 @@ cc_test( deps = [ ":explicit_seed_seq", ":randen_engine", - "//absl/base", + "//absl/base:raw_logging_internal", "//absl/strings", "//absl/time", "@com_google_googletest//:gtest_main", @@ -574,12 +641,26 @@ cc_test( ":platform", ":randen_hwaes", ":randen_hwaes_impl", # build_cleaner: keep - "//absl/base", + "//absl/base:raw_logging_internal", "//absl/strings:str_format", "@com_google_googletest//:gtest", ], ) +cc_test( + name = "wide_multiply_test", + size = "small", + srcs = ["wide_multiply_test.cc"], + copts = ABSL_TEST_COPTS, + linkopts = ABSL_DEFAULT_LINKOPTS, + deps = [ + ":wide_multiply", + "//absl/base:bits", + "//absl/numeric:int128", + "@com_google_googletest//:gtest_main", + ], +) + cc_library( name = "nanobenchmark", srcs = ["nanobenchmark.cc"], @@ -588,7 +669,8 @@ cc_library( deps = [ ":platform", ":randen_engine", - "//absl/base", + "//absl/base:core_headers", + "//absl/base:raw_logging_internal", ], ) @@ -598,11 +680,6 @@ cc_library( copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ - ":distribution_impl", - ":fast_uniform_bits", - ":iostream_state_saver", - ":traits", - "//absl/base:core_headers", "//absl/meta:type_traits", ], ) @@ -620,7 +697,7 @@ cc_test( ], deps = [ ":nanobenchmark", - "//absl/base", + "//absl/base:raw_logging_internal", "//absl/strings", ], ) @@ -641,7 +718,7 @@ cc_test( ":randen_hwaes", ":randen_hwaes_impl", ":randen_slow", - "//absl/base", + "//absl/base:raw_logging_internal", "//absl/strings", ], ) diff --git a/absl/random/internal/chi_square.cc b/absl/random/internal/chi_square.cc index 45671a3e..640d48ce 100644 --- a/absl/random/internal/chi_square.cc +++ b/absl/random/internal/chi_square.cc @@ -19,7 +19,7 @@ #include "absl/random/internal/distribution_test_util.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { namespace { @@ -228,5 +228,5 @@ double ChiSquarePValue(double chi_square, int dof) { } } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl diff --git a/absl/random/internal/chi_square.h b/absl/random/internal/chi_square.h index 002b4c95..07f4fbe5 100644 --- a/absl/random/internal/chi_square.h +++ b/absl/random/internal/chi_square.h @@ -26,8 +26,10 @@ #include <cassert> +#include "absl/base/config.h" + namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { constexpr const char kChiSquared[] = "chi-squared"; @@ -81,7 +83,7 @@ double ChiSquareValue(int dof, double p); double ChiSquarePValue(double chi_square, int dof); } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_RANDOM_INTERNAL_CHI_SQUARE_H_ diff --git a/absl/random/internal/distribution_caller.h b/absl/random/internal/distribution_caller.h index dd06c985..02603cf8 100644 --- a/absl/random/internal/distribution_caller.h +++ b/absl/random/internal/distribution_caller.h @@ -19,8 +19,10 @@ #include <utility> +#include "absl/base/config.h" + namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { // DistributionCaller provides an opportunity to overload the general @@ -52,7 +54,7 @@ struct DistributionCaller { }; } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_RANDOM_INTERNAL_DISTRIBUTION_CALLER_H_ diff --git a/absl/random/internal/distribution_impl.h b/absl/random/internal/distribution_impl.h deleted file mode 100644 index a8e5d61e..00000000 --- a/absl/random/internal/distribution_impl.h +++ /dev/null @@ -1,262 +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 { -inline namespace lts_2019_08_08 { -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); - } -}; - -inline uint128 MultiplyU64ToU128(uint64_t a, uint64_t b) { -#if defined(ABSL_HAVE_INTRINSIC_INT128) - return uint128(static_cast<__uint128_t>(a) * b); -#elif defined(ABSL_INTERNAL_USE_UMUL128) - // uint64_t * uint64_t => uint128 multiply using imul intrinsic on MSVC. - uint64_t high = 0; - const uint64_t low = _umul128(a, b, &high); - return absl::MakeUint128(high, low); -#else - // uint128(a) * uint128(b) in emulated mode computes a full 128-bit x 128-bit - // multiply. However there are many cases where that is not necessary, and it - // is only necessary to support a 64-bit x 64-bit = 128-bit multiply. This is - // for those cases. - const uint64_t a00 = static_cast<uint32_t>(a); - const uint64_t a32 = a >> 32; - const uint64_t b00 = static_cast<uint32_t>(b); - const uint64_t b32 = b >> 32; - - const uint64_t c00 = a00 * b00; - const uint64_t c32a = a00 * b32; - const uint64_t c32b = a32 * b00; - const uint64_t c64 = a32 * b32; - - const uint32_t carry = - static_cast<uint32_t>(((c00 >> 32) + static_cast<uint32_t>(c32a) + - static_cast<uint32_t>(c32b)) >> - 32); - - return absl::MakeUint128(c64 + (c32a >> 32) + (c32b >> 32) + carry, - c00 + (c32a << 32) + (c32b << 32)); -#endif -} - -// wide_multiply<T> multiplies two N-bit values to a 2N-bit result. -template <typename UIntType> -struct wide_multiply { - static constexpr size_t kN = std::numeric_limits<UIntType>::digits; - using input_type = UIntType; - using result_type = typename random_internal::unsigned_bits<kN * 2>::type; - - static result_type multiply(input_type a, input_type b) { - return static_cast<result_type>(a) * b; - } - - static input_type hi(result_type r) { return r >> kN; } - static input_type lo(result_type r) { return r; } - - static_assert(std::is_unsigned<UIntType>::value, - "Class-template wide_multiply<> argument must be unsigned."); -}; - -#ifndef ABSL_HAVE_INTRINSIC_INT128 -template <> -struct wide_multiply<uint64_t> { - using input_type = uint64_t; - using result_type = uint128; - - static result_type multiply(uint64_t a, uint64_t b) { - return MultiplyU64ToU128(a, b); - } - - static uint64_t hi(result_type r) { return Uint128High64(r); } - static uint64_t lo(result_type r) { return Uint128Low64(r); } -}; -#endif - -} // namespace random_internal -} // inline namespace lts_2019_08_08 -} // namespace absl - -#endif // ABSL_RANDOM_INTERNAL_DISTRIBUTION_IMPL_H_ diff --git a/absl/random/internal/distribution_test_util.cc b/absl/random/internal/distribution_test_util.cc index 4fb4149d..e9005658 100644 --- a/absl/random/internal/distribution_test_util.cc +++ b/absl/random/internal/distribution_test_util.cc @@ -25,7 +25,7 @@ #include "absl/strings/str_format.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { namespace { @@ -414,5 +414,5 @@ double MaxErrorTolerance(double acceptance_probability) { } } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl diff --git a/absl/random/internal/distribution_test_util.h b/absl/random/internal/distribution_test_util.h index 56dc86ac..6d94cf6c 100644 --- a/absl/random/internal/distribution_test_util.h +++ b/absl/random/internal/distribution_test_util.h @@ -26,7 +26,7 @@ // non-test code. namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { // http://webspace.ship.edu/pgmarr/Geo441/Lectures/Lec%205%20-%20Normality%20Testing.pdf @@ -107,7 +107,7 @@ double BetaIncomplete(double x, double p, double q); double BetaIncompleteInv(double p, double q, double alpha); } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_RANDOM_INTERNAL_DISTRIBUTION_TEST_UTIL_H_ diff --git a/absl/random/internal/distributions.h b/absl/random/internal/distributions.h index 98d4f313..d7e3c016 100644 --- a/absl/random/internal/distributions.h +++ b/absl/random/internal/distributions.h @@ -23,40 +23,8 @@ #include "absl/random/internal/uniform_helper.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { -template <typename D> -struct DistributionFormatTraits; - -// UniformImpl implements the core logic of the Uniform<T> call, which is to -// select the correct distribution type, compute the bounds based on the -// interval tag, and then generate a value. -template <typename NumType, typename TagType, typename URBG> -NumType UniformImpl(TagType tag, - URBG& urbg, // NOLINT(runtime/references) - NumType lo, NumType hi) { - static_assert( - std::is_arithmetic<NumType>::value, - "absl::Uniform<T>() must use an integer or real parameter type."); - - using distribution_t = - typename std::conditional<std::is_integral<NumType>::value, - absl::uniform_int_distribution<NumType>, - absl::uniform_real_distribution<NumType>>::type; - using format_t = random_internal::DistributionFormatTraits<distribution_t>; - - auto a = random_internal::uniform_lower_bound<NumType>(tag, lo, hi); - auto b = random_internal::uniform_upper_bound<NumType>(tag, lo, hi); - // TODO(lar): it doesn't make a lot of sense to ask for a random number in an - // empty range. Right now we just return a boundary--even though that - // boundary is not an acceptable value! Is there something better we can do - // here? - - using gen_t = absl::decay_t<URBG>; - if (a > b) return a; - return DistributionCaller<gen_t>::template Call<distribution_t, format_t>( - &urbg, a, b); -} // In the absence of an explicitly provided return-type, the template // "uniform_inferred_return_t<A, B>" is used to derive a suitable type, based on @@ -78,7 +46,7 @@ using uniform_inferred_return_t = is_widening_convertible<A, B>::value, B, A>::type>; } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_RANDOM_INTERNAL_DISTRIBUTIONS_H_ diff --git a/absl/random/internal/explicit_seed_seq.h b/absl/random/internal/explicit_seed_seq.h index 66c35f2e..6a743eaf 100644 --- a/absl/random/internal/explicit_seed_seq.h +++ b/absl/random/internal/explicit_seed_seq.h @@ -22,8 +22,10 @@ #include <iterator> #include <vector> +#include "absl/base/config.h" + namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { // This class conforms to the C++ Standard "Seed Sequence" concept @@ -83,7 +85,7 @@ class ExplicitSeedSeq { }; } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_RANDOM_INTERNAL_EXPLICIT_SEED_SEQ_H_ diff --git a/absl/random/internal/fast_uniform_bits.h b/absl/random/internal/fast_uniform_bits.h index 5aa9de01..f13c8729 100644 --- a/absl/random/internal/fast_uniform_bits.h +++ b/absl/random/internal/fast_uniform_bits.h @@ -20,8 +20,10 @@ #include <limits> #include <type_traits> +#include "absl/base/config.h" + namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { // Returns true if the input value is zero or a power of two. Useful for // determining if the range of output values in a URBG @@ -256,7 +258,7 @@ FastUniformBits<UIntType>::Generate(URBG& g, // NOLINT(runtime/references) } } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_RANDOM_INTERNAL_FAST_UNIFORM_BITS_H_ diff --git a/absl/random/internal/fast_uniform_bits_test.cc b/absl/random/internal/fast_uniform_bits_test.cc index 35c96226..f5b837e5 100644 --- a/absl/random/internal/fast_uniform_bits_test.cc +++ b/absl/random/internal/fast_uniform_bits_test.cc @@ -19,7 +19,7 @@ #include "gtest/gtest.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { namespace { @@ -270,5 +270,5 @@ TEST(FastUniformBitsTest, URBG32bitRegression) { } // namespace } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl diff --git a/absl/random/internal/fastmath.h b/absl/random/internal/fastmath.h index 1dc2cd7b..6baeb5a7 100644 --- a/absl/random/internal/fastmath.h +++ b/absl/random/internal/fastmath.h @@ -25,7 +25,7 @@ #include "absl/base/internal/bits.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { // Returns the position of the first bit set. @@ -68,7 +68,7 @@ inline constexpr uint64_t rotr(uint64_t value, uint8_t bits) { } } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_RANDOM_INTERNAL_FASTMATH_H_ diff --git a/absl/random/internal/gaussian_distribution_gentables.cc b/absl/random/internal/gaussian_distribution_gentables.cc index 6f9a28be..a2bf0394 100644 --- a/absl/random/internal/gaussian_distribution_gentables.cc +++ b/absl/random/internal/gaussian_distribution_gentables.cc @@ -27,7 +27,7 @@ #include "absl/base/macros.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { namespace { @@ -136,7 +136,7 @@ void TableGenerator::Print(std::ostream* os) { } } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl int main(int, char**) { diff --git a/absl/random/internal/generate_real.h b/absl/random/internal/generate_real.h new file mode 100644 index 00000000..20f6d208 --- /dev/null +++ b/absl/random/internal/generate_real.h @@ -0,0 +1,146 @@ +// 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 { +ABSL_NAMESPACE_BEGIN +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 +ABSL_NAMESPACE_END +} // 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 09e7a318..aa02f0c2 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(GenerateRealTest, U64ToFloat_Negative_Zero_Test) { + auto ToFloat = [](uint64_t 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(DistributionImplTest, U64ToFloat_Signed_NoZero_Test) { +TEST(GenerateRealTest, U64ToFloat_Signed_NoZero_Test) { auto ToFloat = [](uint64_t a) { - return RandU64ToFloat<SignedValueT, false>(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 @@ -461,46 +494,4 @@ TEST(DistributionImplTest, ExhaustiveFloat) { } } -TEST(DistributionImplTest, MultiplyU64ToU128Test) { - using absl::random_internal::MultiplyU64ToU128; - constexpr uint64_t k1 = 1; - constexpr uint64_t kMax = ~static_cast<uint64_t>(0); - - EXPECT_EQ(absl::uint128(0), MultiplyU64ToU128(0, 0)); - - // Max uint64 - EXPECT_EQ(MultiplyU64ToU128(kMax, kMax), - absl::MakeUint128(0xfffffffffffffffe, 0x0000000000000001)); - EXPECT_EQ(absl::MakeUint128(0, kMax), MultiplyU64ToU128(kMax, 1)); - EXPECT_EQ(absl::MakeUint128(0, kMax), MultiplyU64ToU128(1, kMax)); - for (int i = 0; i < 64; ++i) { - EXPECT_EQ(absl::MakeUint128(0, kMax) << i, - MultiplyU64ToU128(kMax, k1 << i)); - EXPECT_EQ(absl::MakeUint128(0, kMax) << i, - MultiplyU64ToU128(k1 << i, kMax)); - } - - // 1-bit x 1-bit. - for (int i = 0; i < 64; ++i) { - for (int j = 0; j < 64; ++j) { - EXPECT_EQ(absl::MakeUint128(0, 1) << (i + j), - MultiplyU64ToU128(k1 << i, k1 << j)); - EXPECT_EQ(absl::MakeUint128(0, 1) << (i + j), - MultiplyU64ToU128(k1 << i, k1 << j)); - } - } - - // Verified multiplies - EXPECT_EQ(MultiplyU64ToU128(0xffffeeeeddddcccc, 0xbbbbaaaa99998888), - absl::MakeUint128(0xbbbb9e2692c5dddc, 0xc28f7531048d2c60)); - EXPECT_EQ(MultiplyU64ToU128(0x0123456789abcdef, 0xfedcba9876543210), - absl::MakeUint128(0x0121fa00ad77d742, 0x2236d88fe5618cf0)); - EXPECT_EQ(MultiplyU64ToU128(0x0123456789abcdef, 0xfdb97531eca86420), - absl::MakeUint128(0x0120ae99d26725fc, 0xce197f0ecac319e0)); - EXPECT_EQ(MultiplyU64ToU128(0x97a87f4f261ba3f2, 0xfedcba9876543210), - absl::MakeUint128(0x96fbf1a8ae78d0ba, 0x5a6dd4b71f278320)); - EXPECT_EQ(MultiplyU64ToU128(0xfedcba9876543210, 0xfdb97531eca86420), - absl::MakeUint128(0xfc98c6981a413e22, 0x342d0bbf48948200)); -} - } // namespace diff --git a/absl/random/internal/iostream_state_saver.h b/absl/random/internal/iostream_state_saver.h index b9adca86..7378829a 100644 --- a/absl/random/internal/iostream_state_saver.h +++ b/absl/random/internal/iostream_state_saver.h @@ -24,7 +24,7 @@ #include "absl/numeric/int128.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { // The null_state_saver does nothing. @@ -239,7 +239,7 @@ inline FloatType read_floating_point(IStream& is) { } } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_RANDOM_INTERNAL_IOSTREAM_STATE_SAVER_H_ diff --git a/absl/random/internal/iostream_state_saver_test.cc b/absl/random/internal/iostream_state_saver_test.cc index 2ecbaac1..7bb8ad95 100644 --- a/absl/random/internal/iostream_state_saver_test.cc +++ b/absl/random/internal/iostream_state_saver_test.cc @@ -196,8 +196,8 @@ TEST(IOStreamStateSaver, RoundTripFloats) { EXPECT_EQ(-d, StreamRoundTrip<double>(-d)); // Avoid undefined behavior (overflow/underflow). - if (d <= std::numeric_limits<int64_t>::max() && - d >= std::numeric_limits<int64_t>::lowest()) { + if (f <= static_cast<float>(std::numeric_limits<int64_t>::max()) && + f >= static_cast<float>(std::numeric_limits<int64_t>::lowest())) { int64_t x = static_cast<int64_t>(f); EXPECT_EQ(x, StreamRoundTrip<int64_t>(x)); } @@ -264,14 +264,15 @@ TEST(IOStreamStateSaver, RoundTripDoubles) { } // Avoid undefined behavior (overflow/underflow). - if (d <= std::numeric_limits<int64_t>::max() && - d >= std::numeric_limits<int64_t>::lowest()) { + if (d <= static_cast<double>(std::numeric_limits<int64_t>::max()) && + d >= static_cast<double>(std::numeric_limits<int64_t>::lowest())) { int64_t x = static_cast<int64_t>(d); EXPECT_EQ(x, StreamRoundTrip<int64_t>(x)); } } } +#if !defined(__EMSCRIPTEN__) TEST(IOStreamStateSaver, RoundTripLongDoubles) { // Technically, C++ only guarantees that long double is at least as large as a // double. Practically it varies from 64-bits to 128-bits. @@ -349,6 +350,7 @@ TEST(IOStreamStateSaver, RoundTripLongDoubles) { } } } +#endif // !defined(__EMSCRIPTEN__) TEST(StrToDTest, DoubleMin) { const char kV[] = "2.22507385850720138e-308"; diff --git a/absl/random/internal/mock_overload_set.h b/absl/random/internal/mock_overload_set.h new file mode 100644 index 00000000..c2a30d89 --- /dev/null +++ b/absl/random/internal/mock_overload_set.h @@ -0,0 +1,91 @@ +// +// 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_RANDOM_INTERNAL_MOCK_OVERLOAD_SET_H_ +#define ABSL_RANDOM_INTERNAL_MOCK_OVERLOAD_SET_H_ + +#include <type_traits> + +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include "absl/random/mocking_bit_gen.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace random_internal { + +template <typename DistrT, typename Fn> +struct MockSingleOverload; + +// MockSingleOverload +// +// MockSingleOverload hooks in to gMock's `ON_CALL` and `EXPECT_CALL` macros. +// EXPECT_CALL(mock_single_overload, Call(...))` will expand to a call to +// `mock_single_overload.gmock_Call(...)`. Because expectations are stored on +// the MockingBitGen (an argument passed inside `Call(...)`), this forwards to +// arguments to Mocking::Register. +template <typename DistrT, typename Ret, typename... Args> +struct MockSingleOverload<DistrT, Ret(MockingBitGen&, Args...)> { + static_assert(std::is_same<typename DistrT::result_type, Ret>::value, + "Overload signature must have return type matching the " + "distributions result type."); + auto gmock_Call( + absl::MockingBitGen& gen, // NOLINT(google-runtime-references) + const ::testing::Matcher<Args>&... args) + -> decltype(gen.Register<DistrT, Args...>(args...)) { + return gen.Register<DistrT, Args...>(args...); + } +}; + +template <typename DistrT, typename Ret, typename Arg, typename... Args> +struct MockSingleOverload<DistrT, Ret(Arg, MockingBitGen&, Args...)> { + static_assert(std::is_same<typename DistrT::result_type, Ret>::value, + "Overload signature must have return type matching the " + "distributions result type."); + auto gmock_Call( + const ::testing::Matcher<Arg>& arg, + absl::MockingBitGen& gen, // NOLINT(google-runtime-references) + const ::testing::Matcher<Args>&... args) + -> decltype(gen.Register<DistrT, Arg, Args...>(arg, args...)) { + return gen.Register<DistrT, Arg, Args...>(arg, args...); + } +}; + +// MockOverloadSet +// +// MockOverloadSet takes a distribution and a collection of signatures and +// performs overload resolution amongst all the overloads. This makes +// `EXPECT_CALL(mock_overload_set, Call(...))` expand and do overload resolution +// correctly. +template <typename DistrT, typename... Signatures> +struct MockOverloadSet; + +template <typename DistrT, typename Sig> +struct MockOverloadSet<DistrT, Sig> : public MockSingleOverload<DistrT, Sig> { + using MockSingleOverload<DistrT, Sig>::gmock_Call; +}; + +template <typename DistrT, typename FirstSig, typename... Rest> +struct MockOverloadSet<DistrT, FirstSig, Rest...> + : public MockSingleOverload<DistrT, FirstSig>, + public MockOverloadSet<DistrT, Rest...> { + using MockSingleOverload<DistrT, FirstSig>::gmock_Call; + using MockOverloadSet<DistrT, Rest...>::gmock_Call; +}; + +} // namespace random_internal +ABSL_NAMESPACE_END +} // namespace absl +#endif // ABSL_RANDOM_INTERNAL_MOCK_OVERLOAD_SET_H_ diff --git a/absl/random/internal/mocking_bit_gen_base.h b/absl/random/internal/mocking_bit_gen_base.h new file mode 100644 index 00000000..eeeae9d2 --- /dev/null +++ b/absl/random/internal/mocking_bit_gen_base.h @@ -0,0 +1,120 @@ +// +// Copyright 2018 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_MOCKING_BIT_GEN_BASE_H_ +#define ABSL_RANDOM_INTERNAL_MOCKING_BIT_GEN_BASE_H_ + +#include <atomic> +#include <deque> +#include <string> +#include <typeinfo> + +#include "absl/random/random.h" +#include "absl/strings/str_cat.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace random_internal { + +// MockingBitGenExpectationFormatter is invoked to format unsatisfied mocks +// and remaining results into a description string. +template <typename DistrT, typename FormatT> +struct MockingBitGenExpectationFormatter { + std::string operator()(absl::string_view args) { + return absl::StrCat(FormatT::FunctionName(), "(", args, ")"); + } +}; + +// MockingBitGenCallFormatter is invoked to format each distribution call +// into a description string for the mock log. +template <typename DistrT, typename FormatT> +struct MockingBitGenCallFormatter { + std::string operator()(const DistrT& dist, + const typename DistrT::result_type& result) { + return absl::StrCat( + FormatT::FunctionName(), "(", FormatT::FormatArgs(dist), ") => {", + FormatT::FormatResults(absl::MakeSpan(&result, 1)), "}"); + } +}; + +class MockingBitGenBase { + template <typename> + friend struct DistributionCaller; + using generator_type = absl::BitGen; + + public: + // URBG interface + using result_type = generator_type::result_type; + static constexpr result_type(min)() { return (generator_type::min)(); } + static constexpr result_type(max)() { return (generator_type::max)(); } + result_type operator()() { return gen_(); } + + MockingBitGenBase() : gen_(), observed_call_log_() {} + virtual ~MockingBitGenBase() = default; + + protected: + const std::deque<std::string>& observed_call_log() { + return observed_call_log_; + } + + // CallImpl is the type-erased virtual dispatch. + // The type of dist is always distribution<T>, + // The type of result is always distribution<T>::result_type. + virtual bool CallImpl(const std::type_info& distr_type, void* dist_args, + void* result) = 0; + + template <typename DistrT, typename ArgTupleT> + static const std::type_info& GetTypeId() { + return typeid(std::pair<absl::decay_t<DistrT>, absl::decay_t<ArgTupleT>>); + } + + // Call the generating distribution function. + // Invoked by DistributionCaller<>::Call<DistT, FormatT>. + // DistT is the distribution type. + // FormatT is the distribution formatter traits type. + template <typename DistrT, typename FormatT, typename... Args> + typename DistrT::result_type Call(Args&&... args) { + using distr_result_type = typename DistrT::result_type; + using ArgTupleT = std::tuple<absl::decay_t<Args>...>; + + ArgTupleT arg_tuple(std::forward<Args>(args)...); + auto dist = absl::make_from_tuple<DistrT>(arg_tuple); + + distr_result_type result{}; + bool found_match = + CallImpl(GetTypeId<DistrT, ArgTupleT>(), &arg_tuple, &result); + + if (!found_match) { + result = dist(gen_); + } + + // TODO(asoffer): Forwarding the args through means we no longer need to + // extract them from the from the distribution in formatter traits. We can + // just StrJoin them. + observed_call_log_.push_back( + MockingBitGenCallFormatter<DistrT, FormatT>{}(dist, result)); + return result; + } + + private: + generator_type gen_; + std::deque<std::string> observed_call_log_; +}; // namespace random_internal + +} // namespace random_internal +ABSL_NAMESPACE_END +} // namespace absl + +#endif // ABSL_RANDOM_INTERNAL_MOCKING_BIT_GEN_BASE_H_ diff --git a/absl/random/internal/named_generator.cc b/absl/random/internal/named_generator.cc deleted file mode 100644 index b168a25b..00000000 --- a/absl/random/internal/named_generator.cc +++ /dev/null @@ -1,30 +0,0 @@ -// Copyright 2018 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 <cstddef> -#include <iostream> - -#include "absl/random/random.h" - -// This program is used in integration tests. - -int main() { - auto seed_seq = absl::MakeTaggedSeedSeq("TEST_GENERATOR", std::cerr); - absl::BitGen rng(seed_seq); - constexpr size_t kSequenceLength = 8; - for (size_t i = 0; i < kSequenceLength; i++) { - std::cout << rng() << "\n"; - } - return 0; -} diff --git a/absl/random/internal/nanobenchmark.cc b/absl/random/internal/nanobenchmark.cc index 4d26469b..8fee77fc 100644 --- a/absl/random/internal/nanobenchmark.cc +++ b/absl/random/internal/nanobenchmark.cc @@ -27,6 +27,7 @@ #include <utility> #include <vector> +#include "absl/base/attributes.h" #include "absl/base/internal/raw_logging.h" #include "absl/random/internal/platform.h" #include "absl/random/internal/randen_engine.h" @@ -59,15 +60,6 @@ #include <time.h> // NOLINT #endif -// ABSL_HAVE_ATTRIBUTE -#if !defined(ABSL_HAVE_ATTRIBUTE) -#ifdef __has_attribute -#define ABSL_HAVE_ATTRIBUTE(x) __has_attribute(x) -#else -#define ABSL_HAVE_ATTRIBUTE(x) 0 -#endif -#endif - // ABSL_RANDOM_INTERNAL_ATTRIBUTE_NEVER_INLINE prevents inlining of the method. #if ABSL_HAVE_ATTRIBUTE(noinline) || (defined(__GNUC__) && !defined(__clang__)) #define ABSL_RANDOM_INTERNAL_ATTRIBUTE_NEVER_INLINE __attribute__((noinline)) @@ -78,7 +70,7 @@ #endif namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal_nanobenchmark { namespace { @@ -808,5 +800,5 @@ size_t Measure(const Func func, const void* arg, const FuncInput* inputs, } } // namespace random_internal_nanobenchmark -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl diff --git a/absl/random/internal/nanobenchmark.h b/absl/random/internal/nanobenchmark.h index 424d2ba2..a5097ba2 100644 --- a/absl/random/internal/nanobenchmark.h +++ b/absl/random/internal/nanobenchmark.h @@ -50,8 +50,10 @@ #include <stddef.h> #include <stdint.h> +#include "absl/base/config.h" + namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal_nanobenchmark { // Input influencing the function being measured (e.g. number of bytes to copy). @@ -164,7 +166,7 @@ static inline size_t MeasureClosure(const Closure& closure, } } // namespace random_internal_nanobenchmark -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_RANDOM_INTERNAL_NANOBENCHMARK_H_ diff --git a/absl/random/internal/nanobenchmark_test.cc b/absl/random/internal/nanobenchmark_test.cc index f96e0f5d..ab824ef5 100644 --- a/absl/random/internal/nanobenchmark_test.cc +++ b/absl/random/internal/nanobenchmark_test.cc @@ -18,7 +18,7 @@ #include "absl/strings/numbers.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal_nanobenchmark { namespace { @@ -68,7 +68,7 @@ void RunAll(const int argc, char* argv[]) { } // namespace } // namespace random_internal_nanobenchmark -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl int main(int argc, char* argv[]) { diff --git a/absl/random/internal/nonsecure_base.h b/absl/random/internal/nonsecure_base.h index c8af51cf..730fa2ea 100644 --- a/absl/random/internal/nonsecure_base.h +++ b/absl/random/internal/nonsecure_base.h @@ -33,7 +33,7 @@ #include "absl/types/span.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { // Each instance of NonsecureURBGBase<URBG> will be seeded by variates produced @@ -144,7 +144,7 @@ class NonsecureURBGBase { }; } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_RANDOM_INTERNAL_NONSECURE_BASE_H_ diff --git a/absl/random/internal/nonsecure_base_test.cc b/absl/random/internal/nonsecure_base_test.cc index d9de9901..698027fc 100644 --- a/absl/random/internal/nonsecure_base_test.cc +++ b/absl/random/internal/nonsecure_base_test.cc @@ -154,9 +154,10 @@ TEST(NonsecureURBGBase, CompatibleWithDistributionUtils) { TEST(NonsecureURBGBase, CompatibleWithStdDistributions) { ExampleNonsecureURBG rbg; - std::uniform_int_distribution<uint32_t>(0, 100)(rbg); - std::uniform_real_distribution<float>()(rbg); - std::bernoulli_distribution(0.2)(rbg); + // Cast to void to suppress [[nodiscard]] warnings + static_cast<void>(std::uniform_int_distribution<uint32_t>(0, 100)(rbg)); + static_cast<void>(std::uniform_real_distribution<float>()(rbg)); + static_cast<void>(std::bernoulli_distribution(0.2)(rbg)); } TEST(NonsecureURBGBase, ConsecutiveDefaultInstancesYieldUniqueVariates) { diff --git a/absl/random/internal/pcg_engine.h b/absl/random/internal/pcg_engine.h index 607ac34b..53c23fe1 100644 --- a/absl/random/internal/pcg_engine.h +++ b/absl/random/internal/pcg_engine.h @@ -24,7 +24,7 @@ #include "absl/random/internal/iostream_state_saver.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { // pcg_engine is a simplified implementation of Melissa O'Neil's PCG engine in @@ -301,7 +301,7 @@ using pcg32_2018_engine = pcg_engine< random_internal::pcg_xsh_rr_64_32>; } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_RANDOM_INTERNAL_PCG_ENGINE_H_ diff --git a/absl/random/internal/platform.h b/absl/random/internal/platform.h index a5a42cbb..bbdb4e62 100644 --- a/absl/random/internal/platform.h +++ b/absl/random/internal/platform.h @@ -162,7 +162,8 @@ // iOS does not support dispatch, even on x86, since applications // should be bundled as fat binaries, with a different build tailored for // each specific supported platform/architecture. -#if defined(__APPLE__) && (TARGET_OS_IPHONE || TARGET_OS_IPHONE_SIMULATOR) +#if (defined(TARGET_OS_IPHONE) && TARGET_OS_IPHONE) || \ + (defined(TARGET_OS_IPHONE_SIMULATOR) && TARGET_OS_IPHONE_SIMULATOR) #undef ABSL_RANDOM_INTERNAL_AES_DISPATCH #define ABSL_RANDOM_INTERNAL_AES_DISPATCH 0 #endif diff --git a/absl/random/internal/pool_urbg.cc b/absl/random/internal/pool_urbg.cc index 304d9b16..5bee5307 100644 --- a/absl/random/internal/pool_urbg.cc +++ b/absl/random/internal/pool_urbg.cc @@ -37,7 +37,7 @@ using absl::base_internal::SpinLock; using absl::base_internal::SpinLockHolder; namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { namespace { @@ -60,13 +60,13 @@ class RandenPoolEntry { } // Copy bytes into out. - void Fill(uint8_t* out, size_t bytes) LOCKS_EXCLUDED(mu_); + void Fill(uint8_t* out, size_t bytes) ABSL_LOCKS_EXCLUDED(mu_); // Returns random bits from the buffer in units of T. template <typename T> - inline T Generate() LOCKS_EXCLUDED(mu_); + inline T Generate() ABSL_LOCKS_EXCLUDED(mu_); - inline void MaybeRefill() EXCLUSIVE_LOCKS_REQUIRED(mu_) { + inline void MaybeRefill() ABSL_EXCLUSIVE_LOCKS_REQUIRED(mu_) { if (next_ >= kState) { next_ = kCapacity; impl_.Generate(state_); @@ -75,10 +75,10 @@ class RandenPoolEntry { private: // Randen URBG state. - uint32_t state_[kState] GUARDED_BY(mu_); // First to satisfy alignment. + uint32_t state_[kState] ABSL_GUARDED_BY(mu_); // First to satisfy alignment. SpinLock mu_; const Randen impl_; - size_t next_ GUARDED_BY(mu_); + size_t next_ ABSL_GUARDED_BY(mu_); }; template <> @@ -250,5 +250,5 @@ template class RandenPool<uint32_t>; template class RandenPool<uint64_t>; } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl diff --git a/absl/random/internal/pool_urbg.h b/absl/random/internal/pool_urbg.h index eac75e2c..05721929 100644 --- a/absl/random/internal/pool_urbg.h +++ b/absl/random/internal/pool_urbg.h @@ -22,7 +22,7 @@ #include "absl/types/span.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { // RandenPool is a thread-safe random number generator [random.req.urbg] that @@ -125,7 +125,7 @@ class PoolURBG { }; } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_RANDOM_INTERNAL_POOL_URBG_H_ diff --git a/absl/random/internal/randen.cc b/absl/random/internal/randen.cc index 3b087605..78a1e00c 100644 --- a/absl/random/internal/randen.cc +++ b/absl/random/internal/randen.cc @@ -41,7 +41,7 @@ // structured/low-entropy counters to digits of Pi. namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { namespace { @@ -87,5 +87,5 @@ Randen::Randen() { } } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl diff --git a/absl/random/internal/randen.h b/absl/random/internal/randen.h index ef375f90..c2834aaf 100644 --- a/absl/random/internal/randen.h +++ b/absl/random/internal/randen.h @@ -23,7 +23,7 @@ #include "absl/random/internal/randen_traits.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { // RANDen = RANDom generator or beetroots in Swiss German. @@ -96,7 +96,7 @@ class Randen { }; } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_RANDOM_INTERNAL_RANDEN_H_ diff --git a/absl/random/internal/randen_detect.cc b/absl/random/internal/randen_detect.cc index 610ae319..d63230c2 100644 --- a/absl/random/internal/randen_detect.cc +++ b/absl/random/internal/randen_detect.cc @@ -95,7 +95,7 @@ static uint32_t GetAuxval(uint32_t hwcap_type) { #endif namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { // The default return at the end of the function might be unreachable depending @@ -217,5 +217,5 @@ bool CPUSupportsRandenHwAes() { #endif } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl diff --git a/absl/random/internal/randen_detect.h b/absl/random/internal/randen_detect.h index cb777550..f283f432 100644 --- a/absl/random/internal/randen_detect.h +++ b/absl/random/internal/randen_detect.h @@ -15,8 +15,10 @@ #ifndef ABSL_RANDOM_INTERNAL_RANDEN_DETECT_H_ #define ABSL_RANDOM_INTERNAL_RANDEN_DETECT_H_ +#include "absl/base/config.h" + namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { // Returns whether the current CPU supports RandenHwAes implementation. @@ -25,7 +27,7 @@ namespace random_internal { bool CPUSupportsRandenHwAes(); } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_RANDOM_INTERNAL_RANDEN_DETECT_H_ diff --git a/absl/random/internal/randen_engine.h b/absl/random/internal/randen_engine.h index e721559e..6b337313 100644 --- a/absl/random/internal/randen_engine.h +++ b/absl/random/internal/randen_engine.h @@ -28,7 +28,7 @@ #include "absl/random/internal/randen.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { // Deterministic pseudorandom byte generator with backtracking resistance @@ -224,7 +224,7 @@ class alignas(16) randen_engine { }; } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_RANDOM_INTERNAL_RANDEN_ENGINE_H_ diff --git a/absl/random/internal/randen_hwaes.cc b/absl/random/internal/randen_hwaes.cc index d7eed8b2..e23844f1 100644 --- a/absl/random/internal/randen_hwaes.cc +++ b/absl/random/internal/randen_hwaes.cc @@ -22,39 +22,9 @@ #include <cstdint> #include <cstring> +#include "absl/base/attributes.h" #include "absl/random/internal/platform.h" -// ABSL_HAVE_ATTRIBUTE -#if !defined(ABSL_HAVE_ATTRIBUTE) -#ifdef __has_attribute -#define ABSL_HAVE_ATTRIBUTE(x) __has_attribute(x) -#else -#define ABSL_HAVE_ATTRIBUTE(x) 0 -#endif -#endif - -#if ABSL_HAVE_ATTRIBUTE(always_inline) || \ - (defined(__GNUC__) && !defined(__clang__)) -#define ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE \ - __attribute__((always_inline)) -#elif defined(_MSC_VER) -// We can achieve something similar to attribute((always_inline)) with MSVC by -// using the __forceinline keyword, however this is not perfect. MSVC is -// much less aggressive about inlining, and even with the __forceinline keyword. -#define ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE __forceinline -#else -#define ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE -#endif - -// ABSL_ATTRIBUTE_FLATTEN enables much more aggressive inlining within -// the indicated function. -#undef ABSL_ATTRIBUTE_FLATTEN -#if ABSL_HAVE_ATTRIBUTE(flatten) || (defined(__GNUC__) && !defined(__clang__)) -#define ABSL_ATTRIBUTE_FLATTEN __attribute__((flatten)) -#else -#define ABSL_ATTRIBUTE_FLATTEN -#endif - // ABSL_RANDEN_HWAES_IMPL indicates whether this file will contain // a hardware accelerated implementation of randen, or whether it // will contain stubs that exit the process. @@ -105,7 +75,7 @@ #include <cstdlib> namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { // No accelerated implementation. @@ -137,7 +107,7 @@ void RandenHwAes::Generate(const void*, void*) { } } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #else // defined(ABSL_RANDEN_HWAES_IMPL) @@ -148,18 +118,6 @@ void RandenHwAes::Generate(const void*, void*) { #include "absl/random/internal/randen_traits.h" -// ABSL_FUNCTION_ALIGN32 defines a 32-byte alignment attribute -// for the functions in this file. -// -// NOTE: Determine whether we actually have any wins from ALIGN32 -// using microbenchmarks. If not, remove. -#undef ABSL_FUNCTION_ALIGN32 -#if ABSL_HAVE_ATTRIBUTE(aligned) || (defined(__GNUC__) && !defined(__clang__)) -#define ABSL_FUNCTION_ALIGN32 __attribute__((aligned(32))) -#else -#define ABSL_FUNCTION_ALIGN32 -#endif - // TARGET_CRYPTO defines a crypto attribute for each architecture. // // NOTE: Evaluate whether we should eliminate ABSL_TARGET_CRYPTO. @@ -193,8 +151,7 @@ using Vector128 = __vector unsigned long long; // NOLINT(runtime/int) namespace { -inline ABSL_TARGET_CRYPTO ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE Vector128 -ReverseBytes(const Vector128& v) { +inline ABSL_TARGET_CRYPTO Vector128 ReverseBytes(const Vector128& v) { // Reverses the bytes of the vector. const __vector unsigned char perm = {15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0}; @@ -204,26 +161,23 @@ ReverseBytes(const Vector128& v) { // WARNING: these load/store in native byte order. It is OK to load and then // store an unchanged vector, but interpreting the bits as a number or input // to AES will have undefined results. -inline ABSL_TARGET_CRYPTO ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE Vector128 -Vector128Load(const void* ABSL_RANDOM_INTERNAL_RESTRICT from) { +inline ABSL_TARGET_CRYPTO Vector128 Vector128Load(const void* from) { return vec_vsx_ld(0, reinterpret_cast<const Vector128*>(from)); } -inline ABSL_TARGET_CRYPTO ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE void -Vector128Store(const Vector128& v, void* ABSL_RANDOM_INTERNAL_RESTRICT to) { +inline ABSL_TARGET_CRYPTO void Vector128Store(const Vector128& v, void* to) { vec_vsx_st(v, 0, reinterpret_cast<Vector128*>(to)); } // One round of AES. "round_key" is a public constant for breaking the // symmetry of AES (ensures previously equal columns differ afterwards). -inline ABSL_TARGET_CRYPTO ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE Vector128 -AesRound(const Vector128& state, const Vector128& round_key) { +inline ABSL_TARGET_CRYPTO Vector128 AesRound(const Vector128& state, + const Vector128& round_key) { return Vector128(__builtin_crypto_vcipher(state, round_key)); } // Enables native loads in the round loop by pre-swapping. -inline ABSL_TARGET_CRYPTO ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE void -SwapEndian(uint64_t* ABSL_RANDOM_INTERNAL_RESTRICT state) { +inline ABSL_TARGET_CRYPTO void SwapEndian(uint64_t* state) { using absl::random_internal::RandenTraits; constexpr size_t kLanes = 2; constexpr size_t kFeistelBlocks = RandenTraits::kFeistelBlocks; @@ -275,20 +229,18 @@ using Vector128 = uint8x16_t; namespace { -inline ABSL_TARGET_CRYPTO ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE Vector128 -Vector128Load(const void* ABSL_RANDOM_INTERNAL_RESTRICT from) { +inline ABSL_TARGET_CRYPTO Vector128 Vector128Load(const void* from) { return vld1q_u8(reinterpret_cast<const uint8_t*>(from)); } -inline ABSL_TARGET_CRYPTO ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE void -Vector128Store(const Vector128& v, void* ABSL_RANDOM_INTERNAL_RESTRICT to) { +inline ABSL_TARGET_CRYPTO void Vector128Store(const Vector128& v, void* to) { vst1q_u8(reinterpret_cast<uint8_t*>(to), v); } // One round of AES. "round_key" is a public constant for breaking the // symmetry of AES (ensures previously equal columns differ afterwards). -inline ABSL_TARGET_CRYPTO ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE Vector128 -AesRound(const Vector128& state, const Vector128& round_key) { +inline ABSL_TARGET_CRYPTO Vector128 AesRound(const Vector128& state, + const Vector128& round_key) { // It is important to always use the full round function - omitting the // final MixColumns reduces security [https://eprint.iacr.org/2010/041.pdf] // and does not help because we never decrypt. @@ -299,8 +251,7 @@ AesRound(const Vector128& state, const Vector128& round_key) { return vaesmcq_u8(vaeseq_u8(state, uint8x16_t{})) ^ round_key; } -inline ABSL_TARGET_CRYPTO ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE void -SwapEndian(uint64_t* ABSL_RANDOM_INTERNAL_RESTRICT) {} +inline ABSL_TARGET_CRYPTO void SwapEndian(uint64_t*) {} } // namespace @@ -315,16 +266,11 @@ namespace { class Vector128 { public: // Convert from/to intrinsics. - inline ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE explicit Vector128( - const __m128i& Vector128) - : data_(Vector128) {} + inline explicit Vector128(const __m128i& Vector128) : data_(Vector128) {} - inline ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE __m128i data() const { - return data_; - } + inline __m128i data() const { return data_; } - inline ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE Vector128& operator^=( - const Vector128& other) { + inline Vector128& operator^=(const Vector128& other) { data_ = _mm_xor_si128(data_, other.data()); return *this; } @@ -333,29 +279,25 @@ class Vector128 { __m128i data_; }; -inline ABSL_TARGET_CRYPTO ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE Vector128 -Vector128Load(const void* ABSL_RANDOM_INTERNAL_RESTRICT from) { +inline ABSL_TARGET_CRYPTO Vector128 Vector128Load(const void* from) { return Vector128(_mm_load_si128(reinterpret_cast<const __m128i*>(from))); } -inline ABSL_TARGET_CRYPTO ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE void -Vector128Store(const Vector128& v, void* ABSL_RANDOM_INTERNAL_RESTRICT to) { - _mm_store_si128(reinterpret_cast<__m128i * ABSL_RANDOM_INTERNAL_RESTRICT>(to), - v.data()); +inline ABSL_TARGET_CRYPTO void Vector128Store(const Vector128& v, void* to) { + _mm_store_si128(reinterpret_cast<__m128i*>(to), v.data()); } // One round of AES. "round_key" is a public constant for breaking the // symmetry of AES (ensures previously equal columns differ afterwards). -inline ABSL_TARGET_CRYPTO ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE Vector128 -AesRound(const Vector128& state, const Vector128& round_key) { +inline ABSL_TARGET_CRYPTO Vector128 AesRound(const Vector128& state, + const Vector128& round_key) { // It is important to always use the full round function - omitting the // final MixColumns reduces security [https://eprint.iacr.org/2010/041.pdf] // and does not help because we never decrypt. return Vector128(_mm_aesenc_si128(state.data(), round_key.data())); } -inline ABSL_TARGET_CRYPTO ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE void -SwapEndian(uint64_t* ABSL_RANDOM_INTERNAL_RESTRICT) {} +inline ABSL_TARGET_CRYPTO void SwapEndian(uint64_t*) {} } // namespace @@ -452,8 +394,7 @@ constexpr size_t kLanes = 2; // Block shuffles applies a shuffle to the entire state between AES rounds. // Improved odd-even shuffle from "New criterion for diffusion property". -inline ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE ABSL_TARGET_CRYPTO void -BlockShuffle(uint64_t* ABSL_RANDOM_INTERNAL_RESTRICT state) { +inline ABSL_TARGET_CRYPTO void BlockShuffle(uint64_t* state) { static_assert(kFeistelBlocks == 16, "Expecting 16 FeistelBlocks."); constexpr size_t shuffle[kFeistelBlocks] = {7, 2, 13, 4, 11, 8, 3, 6, @@ -501,10 +442,8 @@ BlockShuffle(uint64_t* ABSL_RANDOM_INTERNAL_RESTRICT state) { // per 16 bytes (vs. 10 for AES-CTR). Computing eight round functions in // parallel hides the 7-cycle AESNI latency on HSW. Note that the Feistel // XORs are 'free' (included in the second AES instruction). -inline ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE ABSL_TARGET_CRYPTO const - u64x2* - FeistelRound(uint64_t* ABSL_RANDOM_INTERNAL_RESTRICT state, - const u64x2* ABSL_RANDOM_INTERNAL_RESTRICT keys) { +inline ABSL_TARGET_CRYPTO const u64x2* FeistelRound( + uint64_t* state, const u64x2* ABSL_RANDOM_INTERNAL_RESTRICT keys) { static_assert(kFeistelBlocks == 16, "Expecting 16 FeistelBlocks."); // MSVC does a horrible job at unrolling loops. @@ -563,9 +502,8 @@ inline ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE ABSL_TARGET_CRYPTO const // Indistinguishable from ideal by chosen-ciphertext adversaries using less than // 2^64 queries if the round function is a PRF. This is similar to the b=8 case // of Simpira v2, but more efficient than its generic construction for b=16. -inline ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE ABSL_TARGET_CRYPTO void -Permute(const void* ABSL_RANDOM_INTERNAL_RESTRICT keys, - uint64_t* ABSL_RANDOM_INTERNAL_RESTRICT state) { +inline ABSL_TARGET_CRYPTO void Permute( + const void* ABSL_RANDOM_INTERNAL_RESTRICT keys, uint64_t* state) { const u64x2* ABSL_RANDOM_INTERNAL_RESTRICT keys128 = static_cast<const u64x2*>(keys); @@ -582,25 +520,22 @@ Permute(const void* ABSL_RANDOM_INTERNAL_RESTRICT keys, } // namespace namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { bool HasRandenHwAesImplementation() { return true; } -const void* ABSL_TARGET_CRYPTO ABSL_FUNCTION_ALIGN32 ABSL_ATTRIBUTE_FLATTEN -RandenHwAes::GetKeys() { +const void* ABSL_TARGET_CRYPTO RandenHwAes::GetKeys() { // Round keys for one AES per Feistel round and branch. // The canonical implementation uses first digits of Pi. return round_keys; } // NOLINTNEXTLINE -void ABSL_TARGET_CRYPTO ABSL_FUNCTION_ALIGN32 ABSL_ATTRIBUTE_FLATTEN -RandenHwAes::Absorb(const void* seed_void, void* state_void) { - uint64_t* ABSL_RANDOM_INTERNAL_RESTRICT state = - reinterpret_cast<uint64_t*>(state_void); - const uint64_t* ABSL_RANDOM_INTERNAL_RESTRICT seed = - reinterpret_cast<const uint64_t*>(seed_void); +void ABSL_TARGET_CRYPTO RandenHwAes::Absorb(const void* seed_void, + void* state_void) { + auto* state = static_cast<uint64_t*>(state_void); + const auto* seed = static_cast<const uint64_t*>(seed_void); constexpr size_t kCapacityBlocks = kCapacityBytes / sizeof(Vector128); constexpr size_t kStateBlocks = kStateBytes / sizeof(Vector128); @@ -672,12 +607,11 @@ RandenHwAes::Absorb(const void* seed_void, void* state_void) { } // NOLINTNEXTLINE -void ABSL_TARGET_CRYPTO ABSL_FUNCTION_ALIGN32 ABSL_ATTRIBUTE_FLATTEN -RandenHwAes::Generate(const void* keys, void* state_void) { +void ABSL_TARGET_CRYPTO RandenHwAes::Generate(const void* keys, + void* state_void) { static_assert(kCapacityBytes == sizeof(Vector128), "Capacity mismatch"); - uint64_t* ABSL_RANDOM_INTERNAL_RESTRICT state = - reinterpret_cast<uint64_t*>(state_void); + auto* state = static_cast<uint64_t*>(state_void); const Vector128 prev_inner = Vector128Load(state); @@ -698,7 +632,7 @@ RandenHwAes::Generate(const void* keys, void* state_void) { #endif } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // (ABSL_RANDEN_HWAES_IMPL) diff --git a/absl/random/internal/randen_hwaes.h b/absl/random/internal/randen_hwaes.h index 848bcead..bce36b52 100644 --- a/absl/random/internal/randen_hwaes.h +++ b/absl/random/internal/randen_hwaes.h @@ -15,13 +15,15 @@ #ifndef ABSL_RANDOM_INTERNAL_RANDEN_HWAES_H_ #define ABSL_RANDOM_INTERNAL_RANDEN_HWAES_H_ +#include "absl/base/config.h" + // HERMETIC NOTE: The randen_hwaes target must not introduce duplicate // symbols from arbitrary system and other headers, since it may be built // with different flags from other targets, using different levels of // optimization, potentially introducing ODR violations. namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { // RANDen = RANDom generator or beetroots in Swiss German. @@ -42,7 +44,7 @@ class RandenHwAes { bool HasRandenHwAesImplementation(); } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_RANDOM_INTERNAL_RANDEN_HWAES_H_ diff --git a/absl/random/internal/randen_slow.cc b/absl/random/internal/randen_slow.cc index e2d44f88..8d074582 100644 --- a/absl/random/internal/randen_slow.cc +++ b/absl/random/internal/randen_slow.cc @@ -18,17 +18,9 @@ #include <cstdint> #include <cstring> +#include "absl/base/attributes.h" #include "absl/random/internal/platform.h" -// ABSL_HAVE_ATTRIBUTE -#if !defined(ABSL_HAVE_ATTRIBUTE) -#ifdef __has_attribute -#define ABSL_HAVE_ATTRIBUTE(x) __has_attribute(x) -#else -#define ABSL_HAVE_ATTRIBUTE(x) 0 -#endif -#endif - #if ABSL_HAVE_ATTRIBUTE(always_inline) || \ (defined(__GNUC__) && !defined(__clang__)) #define ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE \ @@ -470,7 +462,7 @@ inline ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE void Permute( } // namespace namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { const void* RandenSlow::GetKeys() { @@ -510,5 +502,5 @@ void RandenSlow::Generate(const void* keys, void* state_void) { } } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl diff --git a/absl/random/internal/randen_slow.h b/absl/random/internal/randen_slow.h index 2133b370..72f92b54 100644 --- a/absl/random/internal/randen_slow.h +++ b/absl/random/internal/randen_slow.h @@ -17,8 +17,10 @@ #include <cstddef> +#include "absl/base/config.h" + namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { // RANDen = RANDom generator or beetroots in Swiss German. @@ -39,7 +41,7 @@ class RandenSlow { }; } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_RANDOM_INTERNAL_RANDEN_SLOW_H_ diff --git a/absl/random/internal/randen_traits.h b/absl/random/internal/randen_traits.h index d2562586..2b8bbe73 100644 --- a/absl/random/internal/randen_traits.h +++ b/absl/random/internal/randen_traits.h @@ -22,8 +22,10 @@ #include <cstddef> +#include "absl/base/config.h" + namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { // RANDen = RANDom generator or beetroots in Swiss German. @@ -55,7 +57,7 @@ struct RandenTraits { }; } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_RANDOM_INTERNAL_RANDEN_TRAITS_H_ diff --git a/absl/random/internal/salted_seed_seq.h b/absl/random/internal/salted_seed_seq.h index 08bf369e..5953a090 100644 --- a/absl/random/internal/salted_seed_seq.h +++ b/absl/random/internal/salted_seed_seq.h @@ -30,7 +30,7 @@ #include "absl/types/span.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { // This class conforms to the C++ Standard "Seed Sequence" concept @@ -161,7 +161,7 @@ SaltedSeedSeq<typename std::decay<SSeq>::type> MakeSaltedSeedSeq(SSeq&& seq) { } } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_RANDOM_INTERNAL_SALTED_SEED_SEQ_H_ diff --git a/absl/random/internal/seed_material.cc b/absl/random/internal/seed_material.cc index dae7007f..4d38a574 100644 --- a/absl/random/internal/seed_material.cc +++ b/absl/random/internal/seed_material.cc @@ -45,6 +45,9 @@ #define ABSL_RANDOM_USE_BCRYPT 1 #pragma comment(lib, "bcrypt.lib") +#elif defined(__Fuchsia__) +#include <zircon/syscalls.h> + #endif #if defined(ABSL_RANDOM_USE_BCRYPT) @@ -58,7 +61,7 @@ #endif namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { namespace { @@ -108,6 +111,15 @@ bool ReadSeedMaterialFromOSEntropyImpl(absl::Span<uint32_t> values) { return true; } +#elif defined(__Fuchsia__) + +bool ReadSeedMaterialFromOSEntropyImpl(absl::Span<uint32_t> values) { + auto buffer = reinterpret_cast<uint8_t*>(values.data()); + size_t buffer_size = sizeof(uint32_t) * values.size(); + zx_cprng_draw(buffer, buffer_size); + return true; +} + #else // On *nix, read entropy from /dev/urandom. @@ -203,5 +215,5 @@ absl::optional<uint32_t> GetSaltMaterial() { } } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl diff --git a/absl/random/internal/seed_material.h b/absl/random/internal/seed_material.h index 41387fe3..4be10e92 100644 --- a/absl/random/internal/seed_material.h +++ b/absl/random/internal/seed_material.h @@ -27,7 +27,7 @@ #include "absl/types/span.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { // Returns the number of 32-bit blocks needed to contain the given number of @@ -98,7 +98,7 @@ void MixIntoSeedMaterial(absl::Span<const uint32_t> sequence, absl::optional<uint32_t> GetSaltMaterial(); } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_RANDOM_INTERNAL_SEED_MATERIAL_H_ diff --git a/absl/random/internal/seed_salting_sequence_generator.cc b/absl/random/internal/seed_salting_sequence_generator.cc deleted file mode 100644 index 31fdcfe1..00000000 --- a/absl/random/internal/seed_salting_sequence_generator.cc +++ /dev/null @@ -1,30 +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. - -#include <iostream> -#include <random> - -#include "absl/random/random.h" - -// This program is used in integration tests. - -int main() { - std::seed_seq seed_seq{1234}; - absl::BitGen rng(seed_seq); - constexpr size_t kSequenceLength = 8; - for (size_t i = 0; i < kSequenceLength; i++) { - std::cout << rng() << "\n"; - } - return 0; -} diff --git a/absl/random/internal/seed_salting_sequence_generator_empty_sequence.cc b/absl/random/internal/seed_salting_sequence_generator_empty_sequence.cc deleted file mode 100644 index 8797e2e7..00000000 --- a/absl/random/internal/seed_salting_sequence_generator_empty_sequence.cc +++ /dev/null @@ -1,30 +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. - -#include <iostream> -#include <random> - -#include "absl/random/random.h" - -// This program is used in integration tests. - -int main() { - std::seed_seq seed_seq{}; - absl::BitGen rng(seed_seq); - constexpr size_t kSequenceLength = 8; - for (size_t i = 0; i < kSequenceLength; i++) { - std::cout << rng() << "\n"; - } - return 0; -} diff --git a/absl/random/internal/sequence_urbg.h b/absl/random/internal/sequence_urbg.h index cec0bf9b..bc96a12c 100644 --- a/absl/random/internal/sequence_urbg.h +++ b/absl/random/internal/sequence_urbg.h @@ -21,8 +21,10 @@ #include <type_traits> #include <vector> +#include "absl/base/config.h" + namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { // `sequence_urbg` is a simple random number generator which meets the @@ -52,7 +54,7 @@ class sequence_urbg { }; } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_RANDOM_INTERNAL_SEQUENCE_URBG_H_ diff --git a/absl/random/internal/traits.h b/absl/random/internal/traits.h index 9f7d126c..75772bd9 100644 --- a/absl/random/internal/traits.h +++ b/absl/random/internal/traits.h @@ -22,7 +22,7 @@ #include "absl/base/config.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace random_internal { // random_internal::is_widening_convertible<A, B> @@ -95,7 +95,7 @@ struct make_unsigned_bits { }; } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_RANDOM_INTERNAL_TRAITS_H_ diff --git a/absl/random/internal/uniform_helper.h b/absl/random/internal/uniform_helper.h index 6af053ef..663107cb 100644 --- a/absl/random/internal/uniform_helper.h +++ b/absl/random/internal/uniform_helper.h @@ -22,7 +22,7 @@ #include "absl/meta/type_traits.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN template <typename IntType> class uniform_int_distribution; @@ -31,15 +31,33 @@ class uniform_real_distribution; // Interval tag types which specify whether the interval is open or closed // on either boundary. + namespace random_internal { -struct IntervalClosedClosedT {}; -struct IntervalClosedOpenT {}; -struct IntervalOpenClosedT {}; -struct IntervalOpenOpenT {}; +template <typename T> +struct TagTypeCompare {}; + +template <typename T> +constexpr bool operator==(TagTypeCompare<T>, TagTypeCompare<T>) { + // Tags are mono-states. They always compare equal. + return true; +} +template <typename T> +constexpr bool operator!=(TagTypeCompare<T>, TagTypeCompare<T>) { + return false; +} + } // namespace random_internal -namespace random_internal { +struct IntervalClosedClosedTag + : public random_internal::TagTypeCompare<IntervalClosedClosedTag> {}; +struct IntervalClosedOpenTag + : public random_internal::TagTypeCompare<IntervalClosedOpenTag> {}; +struct IntervalOpenClosedTag + : public random_internal::TagTypeCompare<IntervalOpenClosedTag> {}; +struct IntervalOpenOpenTag + : public random_internal::TagTypeCompare<IntervalOpenOpenTag> {}; +namespace random_internal { // The functions // uniform_lower_bound(tag, a, b) // and @@ -60,8 +78,8 @@ template <typename IntType, typename Tag> typename absl::enable_if_t< absl::conjunction< std::is_integral<IntType>, - absl::disjunction<std::is_same<Tag, IntervalOpenClosedT>, - std::is_same<Tag, IntervalOpenOpenT>>>::value, + absl::disjunction<std::is_same<Tag, IntervalOpenClosedTag>, + std::is_same<Tag, IntervalOpenOpenTag>>>::value, IntType> uniform_lower_bound(Tag, IntType a, IntType) { return a + 1; @@ -71,8 +89,8 @@ template <typename FloatType, typename Tag> typename absl::enable_if_t< absl::conjunction< std::is_floating_point<FloatType>, - absl::disjunction<std::is_same<Tag, IntervalOpenClosedT>, - std::is_same<Tag, IntervalOpenOpenT>>>::value, + absl::disjunction<std::is_same<Tag, IntervalOpenClosedTag>, + std::is_same<Tag, IntervalOpenOpenTag>>>::value, FloatType> uniform_lower_bound(Tag, FloatType a, FloatType b) { return std::nextafter(a, b); @@ -80,8 +98,8 @@ uniform_lower_bound(Tag, FloatType a, FloatType b) { template <typename NumType, typename Tag> typename absl::enable_if_t< - absl::disjunction<std::is_same<Tag, IntervalClosedClosedT>, - std::is_same<Tag, IntervalClosedOpenT>>::value, + absl::disjunction<std::is_same<Tag, IntervalClosedClosedTag>, + std::is_same<Tag, IntervalClosedOpenTag>>::value, NumType> uniform_lower_bound(Tag, NumType a, NumType) { return a; @@ -91,8 +109,8 @@ template <typename IntType, typename Tag> typename absl::enable_if_t< absl::conjunction< std::is_integral<IntType>, - absl::disjunction<std::is_same<Tag, IntervalClosedOpenT>, - std::is_same<Tag, IntervalOpenOpenT>>>::value, + absl::disjunction<std::is_same<Tag, IntervalClosedOpenTag>, + std::is_same<Tag, IntervalOpenOpenTag>>>::value, IntType> uniform_upper_bound(Tag, IntType, IntType b) { return b - 1; @@ -102,8 +120,8 @@ template <typename FloatType, typename Tag> typename absl::enable_if_t< absl::conjunction< std::is_floating_point<FloatType>, - absl::disjunction<std::is_same<Tag, IntervalClosedOpenT>, - std::is_same<Tag, IntervalOpenOpenT>>>::value, + absl::disjunction<std::is_same<Tag, IntervalClosedOpenTag>, + std::is_same<Tag, IntervalOpenOpenTag>>>::value, FloatType> uniform_upper_bound(Tag, FloatType, FloatType b) { return b; @@ -113,8 +131,8 @@ template <typename IntType, typename Tag> typename absl::enable_if_t< absl::conjunction< std::is_integral<IntType>, - absl::disjunction<std::is_same<Tag, IntervalClosedClosedT>, - std::is_same<Tag, IntervalOpenClosedT>>>::value, + absl::disjunction<std::is_same<Tag, IntervalClosedClosedTag>, + std::is_same<Tag, IntervalOpenClosedTag>>>::value, IntType> uniform_upper_bound(Tag, IntType, IntType b) { return b; @@ -124,8 +142,8 @@ template <typename FloatType, typename Tag> typename absl::enable_if_t< absl::conjunction< std::is_floating_point<FloatType>, - absl::disjunction<std::is_same<Tag, IntervalClosedClosedT>, - std::is_same<Tag, IntervalOpenClosedT>>>::value, + absl::disjunction<std::is_same<Tag, IntervalClosedClosedTag>, + std::is_same<Tag, IntervalOpenClosedTag>>>::value, FloatType> uniform_upper_bound(Tag, FloatType, FloatType b) { return std::nextafter(b, (std::numeric_limits<FloatType>::max)()); @@ -137,16 +155,26 @@ using UniformDistribution = absl::uniform_int_distribution<NumType>, absl::uniform_real_distribution<NumType>>::type; -template <typename TagType, typename NumType> +template <typename NumType> struct UniformDistributionWrapper : public UniformDistribution<NumType> { - explicit UniformDistributionWrapper(NumType lo, NumType hi) + template <typename TagType> + explicit UniformDistributionWrapper(TagType, NumType lo, NumType hi) : UniformDistribution<NumType>( uniform_lower_bound<NumType>(TagType{}, lo, hi), uniform_upper_bound<NumType>(TagType{}, lo, hi)) {} + + explicit UniformDistributionWrapper(NumType lo, NumType hi) + : UniformDistribution<NumType>( + uniform_lower_bound<NumType>(IntervalClosedOpenTag(), lo, hi), + uniform_upper_bound<NumType>(IntervalClosedOpenTag(), lo, hi)) {} + + explicit UniformDistributionWrapper() + : UniformDistribution<NumType>(std::numeric_limits<NumType>::lowest(), + (std::numeric_limits<NumType>::max)()) {} }; } // namespace random_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_RANDOM_INTERNAL_UNIFORM_HELPER_H_ diff --git a/absl/random/internal/wide_multiply.h b/absl/random/internal/wide_multiply.h new file mode 100644 index 00000000..6e4cf1be --- /dev/null +++ b/absl/random/internal/wide_multiply.h @@ -0,0 +1,111 @@ +// 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_WIDE_MULTIPLY_H_ +#define ABSL_RANDOM_INTERNAL_WIDE_MULTIPLY_H_ + +#include <cstdint> +#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/traits.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace random_internal { + +// Helper object to multiply two 64-bit values to a 128-bit value. +// MultiplyU64ToU128 multiplies two 64-bit values to a 128-bit value. +// If an intrinsic is available, it is used, otherwise use native 32-bit +// multiplies to construct the result. +inline uint128 MultiplyU64ToU128(uint64_t a, uint64_t b) { +#if defined(ABSL_HAVE_INTRINSIC_INT128) + return uint128(static_cast<__uint128_t>(a) * b); +#elif defined(ABSL_INTERNAL_USE_UMUL128) + // uint64_t * uint64_t => uint128 multiply using imul intrinsic on MSVC. + uint64_t high = 0; + const uint64_t low = _umul128(a, b, &high); + return absl::MakeUint128(high, low); +#else + // uint128(a) * uint128(b) in emulated mode computes a full 128-bit x 128-bit + // multiply. However there are many cases where that is not necessary, and it + // is only necessary to support a 64-bit x 64-bit = 128-bit multiply. This is + // for those cases. + const uint64_t a00 = static_cast<uint32_t>(a); + const uint64_t a32 = a >> 32; + const uint64_t b00 = static_cast<uint32_t>(b); + const uint64_t b32 = b >> 32; + + const uint64_t c00 = a00 * b00; + const uint64_t c32a = a00 * b32; + const uint64_t c32b = a32 * b00; + const uint64_t c64 = a32 * b32; + + const uint32_t carry = + static_cast<uint32_t>(((c00 >> 32) + static_cast<uint32_t>(c32a) + + static_cast<uint32_t>(c32b)) >> + 32); + + return absl::MakeUint128(c64 + (c32a >> 32) + (c32b >> 32) + carry, + c00 + (c32a << 32) + (c32b << 32)); +#endif +} + +// wide_multiply<T> multiplies two N-bit values to a 2N-bit result. +template <typename UIntType> +struct wide_multiply { + static constexpr size_t kN = std::numeric_limits<UIntType>::digits; + using input_type = UIntType; + using result_type = typename random_internal::unsigned_bits<kN * 2>::type; + + static result_type multiply(input_type a, input_type b) { + return static_cast<result_type>(a) * b; + } + + static input_type hi(result_type r) { return r >> kN; } + static input_type lo(result_type r) { return r; } + + static_assert(std::is_unsigned<UIntType>::value, + "Class-template wide_multiply<> argument must be unsigned."); +}; + +#ifndef ABSL_HAVE_INTRINSIC_INT128 +template <> +struct wide_multiply<uint64_t> { + using input_type = uint64_t; + using result_type = uint128; + + static result_type multiply(uint64_t a, uint64_t b) { + return MultiplyU64ToU128(a, b); + } + + static uint64_t hi(result_type r) { return Uint128High64(r); } + static uint64_t lo(result_type r) { return Uint128Low64(r); } +}; +#endif + +} // namespace random_internal +ABSL_NAMESPACE_END +} // namespace absl + +#endif // ABSL_RANDOM_INTERNAL_WIDE_MULTIPLY_H_ diff --git a/absl/random/internal/wide_multiply_test.cc b/absl/random/internal/wide_multiply_test.cc new file mode 100644 index 00000000..922603f2 --- /dev/null +++ b/absl/random/internal/wide_multiply_test.cc @@ -0,0 +1,66 @@ +// 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. + +#include "absl/random/internal/wide_multiply.h" + +#include "gtest/gtest.h" +#include "absl/base/internal/bits.h" +#include "absl/numeric/int128.h" + +using absl::random_internal::MultiplyU64ToU128; + +namespace { + +TEST(WideMultiplyTest, MultiplyU64ToU128Test) { + constexpr uint64_t k1 = 1; + constexpr uint64_t kMax = ~static_cast<uint64_t>(0); + + EXPECT_EQ(absl::uint128(0), MultiplyU64ToU128(0, 0)); + + // Max uint64 + EXPECT_EQ(MultiplyU64ToU128(kMax, kMax), + absl::MakeUint128(0xfffffffffffffffe, 0x0000000000000001)); + EXPECT_EQ(absl::MakeUint128(0, kMax), MultiplyU64ToU128(kMax, 1)); + EXPECT_EQ(absl::MakeUint128(0, kMax), MultiplyU64ToU128(1, kMax)); + for (int i = 0; i < 64; ++i) { + EXPECT_EQ(absl::MakeUint128(0, kMax) << i, + MultiplyU64ToU128(kMax, k1 << i)); + EXPECT_EQ(absl::MakeUint128(0, kMax) << i, + MultiplyU64ToU128(k1 << i, kMax)); + } + + // 1-bit x 1-bit. + for (int i = 0; i < 64; ++i) { + for (int j = 0; j < 64; ++j) { + EXPECT_EQ(absl::MakeUint128(0, 1) << (i + j), + MultiplyU64ToU128(k1 << i, k1 << j)); + EXPECT_EQ(absl::MakeUint128(0, 1) << (i + j), + MultiplyU64ToU128(k1 << i, k1 << j)); + } + } + + // Verified multiplies + EXPECT_EQ(MultiplyU64ToU128(0xffffeeeeddddcccc, 0xbbbbaaaa99998888), + absl::MakeUint128(0xbbbb9e2692c5dddc, 0xc28f7531048d2c60)); + EXPECT_EQ(MultiplyU64ToU128(0x0123456789abcdef, 0xfedcba9876543210), + absl::MakeUint128(0x0121fa00ad77d742, 0x2236d88fe5618cf0)); + EXPECT_EQ(MultiplyU64ToU128(0x0123456789abcdef, 0xfdb97531eca86420), + absl::MakeUint128(0x0120ae99d26725fc, 0xce197f0ecac319e0)); + EXPECT_EQ(MultiplyU64ToU128(0x97a87f4f261ba3f2, 0xfedcba9876543210), + absl::MakeUint128(0x96fbf1a8ae78d0ba, 0x5a6dd4b71f278320)); + EXPECT_EQ(MultiplyU64ToU128(0xfedcba9876543210, 0xfdb97531eca86420), + absl::MakeUint128(0xfc98c6981a413e22, 0x342d0bbf48948200)); +} + +} // namespace |