diff options
Diffstat (limited to 'absl/random')
49 files changed, 1130 insertions, 845 deletions
diff --git a/absl/random/BUILD.bazel b/absl/random/BUILD.bazel index 66ffcbc7..08ecd197 100644 --- a/absl/random/BUILD.bazel +++ b/absl/random/BUILD.bazel @@ -16,7 +16,6 @@ # ABSL random-number generation libraries. -load("@rules_cc//cc:defs.bzl", "cc_binary", "cc_library", "cc_test") load( "//absl:copts/configure_copts.bzl", "ABSL_DEFAULT_COPTS", @@ -101,8 +100,7 @@ cc_library( linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ ":seed_gen_exception", - "//absl/container:inlined_vector", - "//absl/random/internal:nonsecure_base", + "//absl/base:config", "//absl/random/internal:pool_urbg", "//absl/random/internal:salted_seed_seq", "//absl/random/internal:seed_material", @@ -129,6 +127,7 @@ cc_library( name = "mock_distributions", testonly = 1, hdrs = ["mock_distributions.h"], + linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ ":distributions", ":mocking_bit_gen", @@ -184,6 +183,9 @@ cc_test( copts = ABSL_TEST_COPTS, flaky = 1, linkopts = ABSL_DEFAULT_LINKOPTS, + tags = [ + "no_test_wasm", + ], deps = [ ":distributions", ":random", @@ -236,6 +238,9 @@ cc_test( ], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, + tags = [ + "no_test_wasm", # Does not converge on WASM. + ], deps = [ ":distributions", ":random", @@ -430,6 +435,9 @@ cc_test( srcs = ["mocking_bit_gen_test.cc"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, + tags = [ + "no_test_wasm", + ], deps = [ ":bit_gen_ref", ":mock_distributions", @@ -445,6 +453,9 @@ cc_test( srcs = ["mock_distributions_test.cc"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, + tags = [ + "no_test_wasm", + ], deps = [ ":mock_distributions", ":mocking_bit_gen", @@ -459,6 +470,9 @@ cc_test( srcs = ["examples_test.cc"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, + tags = [ + "no_test_wasm", + ], deps = [ ":random", "@com_google_googletest//:gtest_main", diff --git a/absl/random/CMakeLists.txt b/absl/random/CMakeLists.txt index 3009a034..d04c7081 100644 --- a/absl/random/CMakeLists.txt +++ b/absl/random/CMakeLists.txt @@ -62,8 +62,8 @@ absl_cc_test( absl::random_random absl::random_internal_sequence_urbg absl::fast_type_id - gmock - gtest_main + GTest::gmock + GTest::gtest_main ) # Internal-only target, do not depend on directly. @@ -119,8 +119,9 @@ absl_cc_library( absl::type_traits absl::utility absl::variant - gmock - gtest + GTest::gmock + GTest::gtest + PUBLIC TESTONLY ) @@ -136,8 +137,8 @@ absl_cc_test( DEPS absl::random_mocking_bit_gen absl::random_random - gmock - gtest_main + GTest::gmock + GTest::gtest_main ) absl_cc_test( @@ -153,8 +154,8 @@ absl_cc_test( absl::random_bit_gen_ref absl::random_mocking_bit_gen absl::random_random - gmock - gtest_main + GTest::gmock + GTest::gtest_main ) absl_cc_library( @@ -222,8 +223,8 @@ absl_cc_library( LINKOPTS ${ABSL_DEFAULT_LINKOPTS} DEPS + absl::config absl::inlined_vector - absl::random_internal_nonsecure_base absl::random_internal_pool_urbg absl::random_internal_salted_seed_seq absl::random_internal_seed_material @@ -245,8 +246,8 @@ absl_cc_test( absl::random_random absl::random_internal_sequence_urbg absl::random_internal_pcg_engine - gmock - gtest_main + GTest::gmock + GTest::gtest_main ) absl_cc_test( @@ -268,8 +269,8 @@ absl_cc_test( absl::raw_logging_internal absl::strings absl::str_format - gmock - gtest_main + GTest::gmock + GTest::gtest_main ) absl_cc_test( @@ -285,8 +286,8 @@ absl_cc_test( absl::random_distributions absl::random_random absl::random_internal_distribution_test_util - gmock - gtest_main + GTest::gmock + GTest::gtest_main ) absl_cc_test( @@ -301,8 +302,8 @@ absl_cc_test( absl::random_distributions absl::random_random absl::raw_logging_internal - gmock - gtest_main + GTest::gmock + GTest::gtest_main ) absl_cc_test( @@ -322,8 +323,8 @@ absl_cc_test( absl::raw_logging_internal absl::strings absl::str_format - gmock - gtest_main + GTest::gmock + GTest::gtest_main ) absl_cc_test( @@ -343,8 +344,8 @@ absl_cc_test( absl::random_random absl::raw_logging_internal absl::strings - gmock - gtest_main + GTest::gmock + GTest::gtest_main ) absl_cc_test( @@ -367,8 +368,8 @@ absl_cc_test( absl::raw_logging_internal absl::strings absl::str_format - gmock - gtest_main + GTest::gmock + GTest::gtest_main ) absl_cc_test( @@ -391,8 +392,8 @@ absl_cc_test( absl::raw_logging_internal absl::strings absl::str_format - gmock - gtest_main + GTest::gmock + GTest::gtest_main ) absl_cc_test( @@ -414,8 +415,8 @@ absl_cc_test( absl::raw_logging_internal absl::strings absl::str_format - gmock - gtest_main + GTest::gmock + GTest::gtest_main ) absl_cc_test( @@ -435,8 +436,8 @@ absl_cc_test( absl::random_random absl::raw_logging_internal absl::strings - gmock - gtest_main + GTest::gmock + GTest::gtest_main ) absl_cc_test( @@ -456,8 +457,8 @@ absl_cc_test( absl::random_internal_sequence_urbg absl::random_random absl::strings - gmock - gtest_main + GTest::gmock + GTest::gtest_main ) absl_cc_test( @@ -477,8 +478,8 @@ absl_cc_test( absl::random_random absl::raw_logging_internal absl::strings - gmock - gtest_main + GTest::gmock + GTest::gtest_main ) absl_cc_test( @@ -492,7 +493,7 @@ absl_cc_test( ${ABSL_DEFAULT_LINKOPTS} DEPS absl::random_random - gtest_main + GTest::gtest_main ) absl_cc_test( @@ -508,8 +509,8 @@ absl_cc_test( absl::random_seed_sequences absl::random_internal_nonsecure_base absl::random_random - gmock - gtest_main + GTest::gmock + GTest::gtest_main ) # Internal-only target, do not depend on directly. @@ -726,7 +727,7 @@ absl_cc_library( ${ABSL_DEFAULT_LINKOPTS} DEPS absl::core_headers - absl::optional + absl::inlined_vector absl::random_internal_pool_urbg absl::random_internal_salted_seed_seq absl::random_internal_seed_material @@ -894,7 +895,7 @@ absl_cc_test( ${ABSL_DEFAULT_LINKOPTS} DEPS absl::random_internal_traits - gtest_main + GTest::gtest_main ) # Internal-only target, do not depend on directly. @@ -911,7 +912,7 @@ absl_cc_test( absl::bits absl::flags absl::random_internal_generate_real - gtest_main + GTest::gtest_main ) # Internal-only target, do not depend on directly. @@ -926,7 +927,7 @@ absl_cc_test( ${ABSL_DEFAULT_LINKOPTS} DEPS absl::random_internal_distribution_test_util - gtest_main + GTest::gtest_main ) # Internal-only target, do not depend on directly. @@ -941,7 +942,7 @@ absl_cc_test( ${ABSL_DEFAULT_LINKOPTS} DEPS absl::random_internal_fastmath - gtest_main + GTest::gtest_main ) # Internal-only target, do not depend on directly. @@ -957,8 +958,8 @@ absl_cc_test( DEPS absl::random_internal_explicit_seed_seq absl::random_seed_sequences - gmock - gtest_main + GTest::gmock + GTest::gtest_main ) # Internal-only target, do not depend on directly. @@ -973,8 +974,8 @@ absl_cc_test( ${ABSL_DEFAULT_LINKOPTS} DEPS absl::random_internal_salted_seed_seq - gmock - gtest_main + GTest::gmock + GTest::gtest_main ) # Internal-only target, do not depend on directly. @@ -990,7 +991,7 @@ absl_cc_test( DEPS absl::core_headers absl::random_internal_distribution_test_util - gtest_main + GTest::gtest_main ) # Internal-only target, do not depend on directly. @@ -1005,7 +1006,7 @@ absl_cc_test( ${ABSL_DEFAULT_LINKOPTS} DEPS absl::random_internal_fast_uniform_bits - gtest_main + GTest::gtest_main ) # Internal-only target, do not depend on directly. @@ -1024,7 +1025,7 @@ absl_cc_test( absl::random_distributions absl::random_seed_sequences absl::strings - gtest_main + GTest::gtest_main ) # Internal-only target, do not depend on directly. @@ -1039,8 +1040,8 @@ absl_cc_test( ${ABSL_DEFAULT_LINKOPTS} DEPS absl::random_internal_seed_material - gmock - gtest_main + GTest::gmock + GTest::gtest_main ) # Internal-only target, do not depend on directly. @@ -1057,7 +1058,7 @@ absl_cc_test( absl::random_internal_pool_urbg absl::span absl::type_traits - gtest_main + GTest::gtest_main ) # Internal-only target, do not depend on directly. @@ -1074,8 +1075,8 @@ absl_cc_test( absl::random_internal_explicit_seed_seq absl::random_internal_pcg_engine absl::time - gmock - gtest_main + GTest::gmock + GTest::gtest_main ) # Internal-only target, do not depend on directly. @@ -1094,8 +1095,8 @@ absl_cc_test( absl::raw_logging_internal absl::strings absl::time - gmock - gtest_main + GTest::gmock + GTest::gtest_main ) # Internal-only target, do not depend on directly. @@ -1111,7 +1112,7 @@ absl_cc_test( DEPS absl::random_internal_randen absl::type_traits - gtest_main + GTest::gtest_main ) # Internal-only target, do not depend on directly. @@ -1127,7 +1128,7 @@ absl_cc_test( DEPS absl::endian absl::random_internal_randen_slow - gtest_main + GTest::gtest_main ) # Internal-only target, do not depend on directly. @@ -1146,8 +1147,8 @@ absl_cc_test( absl::random_internal_randen_hwaes_impl absl::raw_logging_internal absl::str_format - gmock - gtest + GTest::gmock + GTest::gtest ) # Internal-only target, do not depend on directly. @@ -1178,7 +1179,7 @@ absl_cc_test( ${ABSL_DEFAULT_LINKOPTS} DEPS absl::random_internal_uniform_helper - gtest_main + GTest::gtest_main ) # Internal-only target, do not depend on directly. @@ -1193,7 +1194,7 @@ absl_cc_test( ${ABSL_DEFAULT_LINKOPTS} DEPS absl::random_internal_iostream_state_saver - gtest_main + GTest::gtest_main ) # Internal-only target, do not depend on directly. @@ -1210,5 +1211,6 @@ absl_cc_test( absl::random_internal_wide_multiply absl::bits absl::int128 - gtest_main + GTest::gmock + GTest::gtest_main ) diff --git a/absl/random/bernoulli_distribution.h b/absl/random/bernoulli_distribution.h index 25bd0d5c..d81b6ae6 100644 --- a/absl/random/bernoulli_distribution.h +++ b/absl/random/bernoulli_distribution.h @@ -138,16 +138,16 @@ bool bernoulli_distribution::Generate(double p, // 64 bits. // // Second, `c` is constructed by first casting explicitly to a signed - // integer and then converting implicitly to an unsigned integer of the same + // integer and then casting explicitly to an unsigned integer of the same // size. This is done because the hardware conversion instructions produce // signed integers from double; if taken as a uint64_t the conversion would // be wrong for doubles greater than 2^63 (not relevant in this use-case). // If converted directly to an unsigned integer, the compiler would end up // emitting code to handle such large values that are not relevant due to // the known bounds on `c`. To avoid these extra instructions this - // implementation converts first to the signed type and then use the - // implicit conversion to unsigned (which is a no-op). - const uint64_t c = static_cast<int64_t>(p * kP32); + // implementation converts first to the signed type and then convert to + // unsigned (which is a no-op). + const uint64_t c = static_cast<uint64_t>(static_cast<int64_t>(p * kP32)); const uint32_t v = fast_u32(g); // FAST PATH: this path fails with probability 1/2^32. Note that simply // returning v <= c would approximate P very well (up to an absolute error diff --git a/absl/random/beta_distribution_test.cc b/absl/random/beta_distribution_test.cc index 44cdfdd0..c16fbb4f 100644 --- a/absl/random/beta_distribution_test.cc +++ b/absl/random/beta_distribution_test.cc @@ -15,6 +15,7 @@ #include "absl/random/beta_distribution.h" #include <algorithm> +#include <cfloat> #include <cstddef> #include <cstdint> #include <iterator> @@ -44,16 +45,26 @@ namespace { template <typename IntType> class BetaDistributionInterfaceTest : public ::testing::Test {}; -// double-double arithmetic is not supported well by either GCC or Clang; see -// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99048, -// https://bugs.llvm.org/show_bug.cgi?id=49131, and -// https://bugs.llvm.org/show_bug.cgi?id=49132. Don't bother running these tests -// with double doubles until compiler support is better. -using RealTypes = - std::conditional<absl::numeric_internal::IsDoubleDouble(), - ::testing::Types<float, double>, - ::testing::Types<float, double, long double>>::type; -TYPED_TEST_CASE(BetaDistributionInterfaceTest, RealTypes); +constexpr bool ShouldExerciseLongDoubleTests() { + // long double arithmetic is not supported well by either GCC or Clang on + // most platforms specifically not when implemented in terms of double-double; + // see https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99048, + // https://bugs.llvm.org/show_bug.cgi?id=49131, and + // https://bugs.llvm.org/show_bug.cgi?id=49132. + // So a conservative choice here is to disable long-double tests pretty much + // everywhere except on x64 but only if long double is not implemented as + // double-double. +#if defined(__i686__) && defined(__x86_64__) + return !absl::numeric_internal::IsDoubleDouble(); +#else + return false; +#endif +} + +using RealTypes = std::conditional<ShouldExerciseLongDoubleTests(), + ::testing::Types<float, double, long double>, + ::testing::Types<float, double>>::type; +TYPED_TEST_SUITE(BetaDistributionInterfaceTest, RealTypes); TYPED_TEST(BetaDistributionInterfaceTest, SerializeTest) { // The threshold for whether std::exp(1/a) is finite. @@ -430,13 +441,13 @@ std::string ParamName( return absl::StrReplaceAll(name, {{"+", "_"}, {"-", "_"}, {".", "_"}}); } -INSTANTIATE_TEST_CASE_P( +INSTANTIATE_TEST_SUITE_P( TestSampleStatisticsCombinations, BetaDistributionTest, ::testing::Combine(::testing::Values(0.1, 0.2, 0.9, 1.1, 2.5, 10.0, 123.4), ::testing::Values(0.1, 0.2, 0.9, 1.1, 2.5, 10.0, 123.4)), ParamName); -INSTANTIATE_TEST_CASE_P( +INSTANTIATE_TEST_SUITE_P( TestSampleStatistics_SelectedPairs, BetaDistributionTest, ::testing::Values(std::make_pair(0.5, 1000), std::make_pair(1000, 0.5), std::make_pair(900, 1000), std::make_pair(10000, 20000), @@ -558,6 +569,14 @@ TEST(BetaDistributionTest, StabilityTest) { // dependencies of the distribution change, such as RandU64ToDouble, then this // is also likely to change. TEST(BetaDistributionTest, AlgorithmBounds) { +#if (defined(__i386__) || defined(_M_IX86)) && FLT_EVAL_METHOD != 0 + // We're using an x87-compatible FPU, and intermediate operations are + // performed with 80-bit floats. This produces slightly different results from + // what we expect below. + GTEST_SKIP() + << "Skipping the test because we detected x87 floating-point semantics"; +#endif + { absl::random_internal::sequence_urbg urbg( {0x7fbe76c8b4395800ull, 0x8000000000000000ull}); diff --git a/absl/random/bit_gen_ref.h b/absl/random/bit_gen_ref.h index 9555460f..e475221a 100644 --- a/absl/random/bit_gen_ref.h +++ b/absl/random/bit_gen_ref.h @@ -24,6 +24,10 @@ #ifndef ABSL_RANDOM_BIT_GEN_REF_H_ #define ABSL_RANDOM_BIT_GEN_REF_H_ +#include <limits> +#include <type_traits> +#include <utility> + #include "absl/base/internal/fast_type_id.h" #include "absl/base/macros.h" #include "absl/meta/type_traits.h" diff --git a/absl/random/discrete_distribution_test.cc b/absl/random/discrete_distribution_test.cc index 6d007006..415b14cc 100644 --- a/absl/random/discrete_distribution_test.cc +++ b/absl/random/discrete_distribution_test.cc @@ -99,6 +99,7 @@ TYPED_TEST(DiscreteDistributionTypeTest, Constructor) { } TEST(DiscreteDistributionTest, InitDiscreteDistribution) { + using testing::_; using testing::Pair; { @@ -111,8 +112,8 @@ TEST(DiscreteDistributionTest, InitDiscreteDistribution) { // Each bucket is p=1/3, so bucket 0 will send half it's traffic // to bucket 2, while the rest will retain all of their traffic. EXPECT_THAT(q, testing::ElementsAre(Pair(0.5, 2), // - Pair(1.0, 1), // - Pair(1.0, 2))); + Pair(1.0, _), // + Pair(1.0, _))); } { @@ -135,7 +136,7 @@ TEST(DiscreteDistributionTest, InitDiscreteDistribution) { EXPECT_THAT(q, testing::ElementsAre(Pair(b0, 3), // Pair(b1, 3), // - Pair(1.0, 2), // + Pair(1.0, _), // Pair(b3, 2), // Pair(b1, 3))); } diff --git a/absl/random/distributions.h b/absl/random/distributions.h index 31c79694..37fc3aa7 100644 --- a/absl/random/distributions.h +++ b/absl/random/distributions.h @@ -373,7 +373,7 @@ RealType Gaussian(URBG&& urbg, // NOLINT(runtime/references) template <typename IntType, typename URBG> IntType LogUniform(URBG&& urbg, // NOLINT(runtime/references) IntType lo, IntType hi, IntType base = 2) { - static_assert(std::is_integral<IntType>::value, + static_assert(random_internal::IsIntegral<IntType>::value, "Template-argument 'IntType' must be an integral type, in " "absl::LogUniform<IntType, URBG>(...)"); @@ -403,7 +403,7 @@ IntType LogUniform(URBG&& urbg, // NOLINT(runtime/references) template <typename IntType, typename URBG> IntType Poisson(URBG&& urbg, // NOLINT(runtime/references) double mean = 1.0) { - static_assert(std::is_integral<IntType>::value, + static_assert(random_internal::IsIntegral<IntType>::value, "Template-argument 'IntType' must be an integral type, in " "absl::Poisson<IntType, URBG>(...)"); @@ -435,7 +435,7 @@ template <typename IntType, typename URBG> IntType Zipf(URBG&& urbg, // NOLINT(runtime/references) IntType hi = (std::numeric_limits<IntType>::max)(), double q = 2.0, double v = 1.0) { - static_assert(std::is_integral<IntType>::value, + static_assert(random_internal::IsIntegral<IntType>::value, "Template-argument 'IntType' must be an integral type, in " "absl::Zipf<IntType, URBG>(...)"); diff --git a/absl/random/distributions_test.cc b/absl/random/distributions_test.cc index 5866a072..5321a11c 100644 --- a/absl/random/distributions_test.cc +++ b/absl/random/distributions_test.cc @@ -14,6 +14,7 @@ #include "absl/random/distributions.h" +#include <cfloat> #include <cmath> #include <cstdint> #include <random> @@ -219,11 +220,21 @@ TEST_F(RandomDistributionsTest, UniformNoBounds) { absl::Uniform<uint16_t>(gen); absl::Uniform<uint32_t>(gen); absl::Uniform<uint64_t>(gen); + absl::Uniform<absl::uint128>(gen); } TEST_F(RandomDistributionsTest, UniformNonsenseRanges) { // The ranges used in this test are undefined behavior. // The results are arbitrary and subject to future changes. + +#if (defined(__i386__) || defined(_M_IX86)) && FLT_EVAL_METHOD != 0 + // We're using an x87-compatible FPU, and intermediate operations can be + // performed with 80-bit floats. This produces slightly different results from + // what we expect below. + GTEST_SKIP() + << "Skipping the test because we detected x87 floating-point semantics"; +#endif + absl::InsecureBitGen gen; // <uint> diff --git a/absl/random/exponential_distribution_test.cc b/absl/random/exponential_distribution_test.cc index af11d61c..3c44d9ec 100644 --- a/absl/random/exponential_distribution_test.cc +++ b/absl/random/exponential_distribution_test.cc @@ -15,6 +15,7 @@ #include "absl/random/exponential_distribution.h" #include <algorithm> +#include <cfloat> #include <cmath> #include <cstddef> #include <cstdint> @@ -57,7 +58,7 @@ using RealTypes = std::conditional<absl::numeric_internal::IsDoubleDouble(), ::testing::Types<float, double>, ::testing::Types<float, double, long double>>::type; -TYPED_TEST_CASE(ExponentialDistributionTypedTest, RealTypes); +TYPED_TEST_SUITE(ExponentialDistributionTypedTest, RealTypes); TYPED_TEST(ExponentialDistributionTypedTest, SerializeTest) { using param_type = @@ -342,8 +343,8 @@ std::string ParamName(const ::testing::TestParamInfo<Param>& info) { return absl::StrReplaceAll(name, {{"+", "_"}, {"-", "_"}, {".", "_"}}); } -INSTANTIATE_TEST_CASE_P(All, ExponentialDistributionTests, - ::testing::ValuesIn(GenParams()), ParamName); +INSTANTIATE_TEST_SUITE_P(All, ExponentialDistributionTests, + ::testing::ValuesIn(GenParams()), ParamName); // NOTE: absl::exponential_distribution is not guaranteed to be stable. TEST(ExponentialDistributionTest, StabilityTest) { @@ -384,6 +385,15 @@ TEST(ExponentialDistributionTest, StabilityTest) { TEST(ExponentialDistributionTest, AlgorithmBounds) { // Relies on absl::uniform_real_distribution, so some of these comments // reference that. + +#if (defined(__i386__) || defined(_M_IX86)) && FLT_EVAL_METHOD != 0 + // We're using an x87-compatible FPU, and intermediate operations can be + // performed with 80-bit floats. This produces slightly different results from + // what we expect below. + GTEST_SKIP() + << "Skipping the test because we detected x87 floating-point semantics"; +#endif + absl::exponential_distribution<double> dist; { diff --git a/absl/random/gaussian_distribution_test.cc b/absl/random/gaussian_distribution_test.cc index c0bac2b0..4584ac92 100644 --- a/absl/random/gaussian_distribution_test.cc +++ b/absl/random/gaussian_distribution_test.cc @@ -54,7 +54,7 @@ using RealTypes = std::conditional<absl::numeric_internal::IsDoubleDouble(), ::testing::Types<float, double>, ::testing::Types<float, double, long double>>::type; -TYPED_TEST_CASE(GaussianDistributionInterfaceTest, RealTypes); +TYPED_TEST_SUITE(GaussianDistributionInterfaceTest, RealTypes); TYPED_TEST(GaussianDistributionInterfaceTest, SerializeTest) { using param_type = diff --git a/absl/random/generators_test.cc b/absl/random/generators_test.cc index 41725f13..14fd24e9 100644 --- a/absl/random/generators_test.cc +++ b/absl/random/generators_test.cc @@ -107,6 +107,8 @@ void TestPoisson(URBG* gen) { absl::Poisson<int64_t>(*gen); absl::Poisson<uint64_t>(*gen); absl::Poisson<uint64_t>(URBG()); + absl::Poisson<absl::int128>(*gen); + absl::Poisson<absl::uint128>(*gen); } template <typename URBG> @@ -126,6 +128,8 @@ void TestZipf(URBG* gen) { absl::Zipf<int64_t>(*gen, 1 << 10); absl::Zipf<uint64_t>(*gen, 1 << 10); absl::Zipf<uint64_t>(URBG(), 1 << 10); + absl::Zipf<absl::int128>(*gen, 1 << 10); + absl::Zipf<absl::uint128>(*gen, 1 << 10); } template <typename URBG> @@ -146,6 +150,8 @@ void TestLogNormal(URBG* gen) { absl::LogUniform<int64_t>(*gen, 0, 1 << 10); absl::LogUniform<uint64_t>(*gen, 0, 1 << 10); absl::LogUniform<uint64_t>(URBG(), 0, 1 << 10); + absl::LogUniform<absl::int128>(*gen, 0, 1 << 10); + absl::LogUniform<absl::uint128>(*gen, 0, 1 << 10); } template <typename URBG> diff --git a/absl/random/internal/BUILD.bazel b/absl/random/internal/BUILD.bazel index 612b1505..fd5b6195 100644 --- a/absl/random/internal/BUILD.bazel +++ b/absl/random/internal/BUILD.bazel @@ -14,8 +14,6 @@ # 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", @@ -37,7 +35,11 @@ cc_library( hdrs = ["traits.h"], copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, - deps = ["//absl/base:config"], + deps = [ + "//absl/base:config", + "//absl/numeric:bits", + "//absl/numeric:int128", + ], ) cc_library( @@ -60,6 +62,7 @@ cc_library( copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ + ":traits", "//absl/base:config", "//absl/meta:type_traits", ], @@ -82,6 +85,7 @@ cc_library( deps = [ ":fast_uniform_bits", "//absl/base:core_headers", + "//absl/base:dynamic_annotations", "//absl/base:raw_logging_internal", "//absl/strings", "//absl/types:optional", @@ -218,8 +222,8 @@ cc_library( ":salted_seed_seq", ":seed_material", "//absl/base:core_headers", + "//absl/container:inlined_vector", "//absl/meta:type_traits", - "//absl/types:optional", "//absl/types:span", ], ) @@ -296,6 +300,8 @@ cc_library( ":platform", "//absl/base:config", "//absl/base:core_headers", + "//absl/base:endian", + "//absl/numeric:int128", ], ) @@ -336,6 +342,7 @@ cc_library( ":platform", "//absl/base:config", "//absl/base:core_headers", + "//absl/numeric:int128", ], ) @@ -495,6 +502,7 @@ cc_test( cc_library( name = "mock_helpers", hdrs = ["mock_helpers.h"], + linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ "//absl/base:fast_type_id", "//absl/types:optional", @@ -505,6 +513,7 @@ cc_library( name = "mock_overload_set", testonly = 1, hdrs = ["mock_overload_set.h"], + linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ ":mock_helpers", "//absl/random:mocking_bit_gen", @@ -622,7 +631,7 @@ cc_test( name = "randen_hwaes_test", size = "small", srcs = ["randen_hwaes_test.cc"], - copts = ABSL_TEST_COPTS, + copts = ABSL_TEST_COPTS + ABSL_RANDOM_RANDEN_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, tags = ABSL_RANDOM_NONPORTABLE_TAGS, deps = [ @@ -672,6 +681,7 @@ cc_library( ":traits", "//absl/base:config", "//absl/meta:type_traits", + "//absl/numeric:int128", ], ) @@ -685,6 +695,7 @@ cc_test( "benchmark", "no_test_ios_x86_64", "no_test_loonix", # Crashing. + "no_test_wasm", ], deps = [ ":nanobenchmark", @@ -717,7 +728,6 @@ cc_test( cc_test( name = "iostream_state_saver_test", - size = "small", srcs = ["iostream_state_saver_test.cc"], linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ diff --git a/absl/random/internal/chi_square.cc b/absl/random/internal/chi_square.cc index 640d48ce..fbe01732 100644 --- a/absl/random/internal/chi_square.cc +++ b/absl/random/internal/chi_square.cc @@ -125,7 +125,8 @@ double ChiSquareValue(int dof, double p) { const double variance = 2.0 / (9 * dof); // Cannot use this method if the variance is 0. if (variance != 0) { - return std::pow(z * std::sqrt(variance) + mean, 3.0) * dof; + double term = z * std::sqrt(variance) + mean; + return dof * (term * term * term); } } diff --git a/absl/random/internal/distribution_caller.h b/absl/random/internal/distribution_caller.h index fc81b787..0f162a4e 100644 --- a/absl/random/internal/distribution_caller.h +++ b/absl/random/internal/distribution_caller.h @@ -18,6 +18,7 @@ #define ABSL_RANDOM_INTERNAL_DISTRIBUTION_CALLER_H_ #include <utility> +#include <type_traits> #include "absl/base/config.h" #include "absl/base/internal/fast_type_id.h" @@ -32,6 +33,8 @@ namespace random_internal { // to intercept such calls. template <typename URBG> struct DistributionCaller { + static_assert(!std::is_pointer<URBG>::value, + "You must pass a reference, not a pointer."); // SFINAE to detect whether the URBG type includes a member matching // bool InvokeMock(base_internal::FastTypeIdType, void*, void*). // diff --git a/absl/random/internal/explicit_seed_seq.h b/absl/random/internal/explicit_seed_seq.h index e3aa31a1..25f79153 100644 --- a/absl/random/internal/explicit_seed_seq.h +++ b/absl/random/internal/explicit_seed_seq.h @@ -74,7 +74,7 @@ class ExplicitSeedSeq { template <typename OutIterator> void generate(OutIterator begin, OutIterator end) { for (size_t index = 0; begin != end; begin++) { - *begin = state_.empty() ? 0 : little_endian::FromHost32(state_[index++]); + *begin = state_.empty() ? 0 : state_[index++]; if (index >= state_.size()) { index = 0; } diff --git a/absl/random/internal/explicit_seed_seq_test.cc b/absl/random/internal/explicit_seed_seq_test.cc index a55ad739..e36d5fa0 100644 --- a/absl/random/internal/explicit_seed_seq_test.cc +++ b/absl/random/internal/explicit_seed_seq_test.cc @@ -24,6 +24,8 @@ namespace { +using ::absl::random_internal::ExplicitSeedSeq; + template <typename Sseq> bool ConformsToInterface() { // Check that the SeedSequence can be default-constructed. @@ -64,14 +66,14 @@ TEST(SeedSequences, CheckInterfaces) { EXPECT_TRUE(ConformsToInterface<std::seed_seq>()); // Abseil classes - EXPECT_TRUE(ConformsToInterface<absl::random_internal::ExplicitSeedSeq>()); + EXPECT_TRUE(ConformsToInterface<ExplicitSeedSeq>()); } TEST(ExplicitSeedSeq, DefaultConstructorGeneratesZeros) { const size_t kNumBlocks = 128; uint32_t outputs[kNumBlocks]; - absl::random_internal::ExplicitSeedSeq seq; + ExplicitSeedSeq seq; seq.generate(outputs, &outputs[kNumBlocks]); for (uint32_t& seed : outputs) { @@ -87,8 +89,7 @@ TEST(ExplicitSeeqSeq, SeedMaterialIsForwardedIdentically) { for (uint32_t& seed : seed_material) { seed = urandom(); } - absl::random_internal::ExplicitSeedSeq seq(seed_material, - &seed_material[kNumBlocks]); + ExplicitSeedSeq seq(seed_material, &seed_material[kNumBlocks]); // Check that output is same as seed-material provided to constructor. { @@ -133,17 +134,14 @@ TEST(ExplicitSeedSeq, CopyAndMoveConstructors) { for (uint32_t& entry : entropy) { entry = urandom(); } - absl::random_internal::ExplicitSeedSeq seq_from_entropy(std::begin(entropy), - std::end(entropy)); + ExplicitSeedSeq seq_from_entropy(std::begin(entropy), std::end(entropy)); // Copy constructor. { - absl::random_internal::ExplicitSeedSeq seq_copy(seq_from_entropy); + ExplicitSeedSeq seq_copy(seq_from_entropy); EXPECT_EQ(seq_copy.size(), seq_from_entropy.size()); - std::vector<uint32_t> seeds_1; - seeds_1.resize(1000, 0); - std::vector<uint32_t> seeds_2; - seeds_2.resize(1000, 1); + std::vector<uint32_t> seeds_1(1000, 0); + std::vector<uint32_t> seeds_2(1000, 1); seq_from_entropy.generate(seeds_1.begin(), seeds_1.end()); seq_copy.generate(seeds_2.begin(), seeds_2.end()); @@ -155,13 +153,10 @@ TEST(ExplicitSeedSeq, CopyAndMoveConstructors) { for (uint32_t& entry : entropy) { entry = urandom(); } - absl::random_internal::ExplicitSeedSeq another_seq(std::begin(entropy), - std::end(entropy)); + ExplicitSeedSeq another_seq(std::begin(entropy), std::end(entropy)); - std::vector<uint32_t> seeds_1; - seeds_1.resize(1000, 0); - std::vector<uint32_t> seeds_2; - seeds_2.resize(1000, 0); + std::vector<uint32_t> seeds_1(1000, 0); + std::vector<uint32_t> seeds_2(1000, 0); seq_from_entropy.generate(seeds_1.begin(), seeds_1.end()); another_seq.generate(seeds_2.begin(), seeds_2.end()); @@ -170,7 +165,15 @@ TEST(ExplicitSeedSeq, CopyAndMoveConstructors) { EXPECT_THAT(seeds_1, Not(Pointwise(Eq(), seeds_2))); // Apply the assignment-operator. + // GCC 12 has a false-positive -Wstringop-overflow warning here. +#if ABSL_INTERNAL_HAVE_MIN_GNUC_VERSION(12, 0) +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wstringop-overflow" +#endif another_seq = seq_from_entropy; +#if ABSL_INTERNAL_HAVE_MIN_GNUC_VERSION(12, 0) +#pragma GCC diagnostic pop +#endif // Re-generate seeds. seq_from_entropy.generate(seeds_1.begin(), seeds_1.end()); @@ -182,15 +185,13 @@ TEST(ExplicitSeedSeq, CopyAndMoveConstructors) { // Move constructor. { // Get seeds from seed-sequence constructed from entropy. - std::vector<uint32_t> seeds_1; - seeds_1.resize(1000, 0); + std::vector<uint32_t> seeds_1(1000, 0); seq_from_entropy.generate(seeds_1.begin(), seeds_1.end()); // Apply move-constructor move the sequence to another instance. absl::random_internal::ExplicitSeedSeq moved_seq( std::move(seq_from_entropy)); - std::vector<uint32_t> seeds_2; - seeds_2.resize(1000, 1); + std::vector<uint32_t> seeds_2(1000, 1); moved_seq.generate(seeds_2.begin(), seeds_2.end()); // Verify that seeds produced by moved-instance are the same as original. EXPECT_THAT(seeds_1, Pointwise(Eq(), seeds_2)); @@ -202,3 +203,35 @@ TEST(ExplicitSeedSeq, CopyAndMoveConstructors) { EXPECT_THAT(seeds_1, Each(Eq(0))); } } + +TEST(ExplicitSeedSeq, StdURBGGoldenTests) { + // Verify that for std::- URBG instances the results are stable across + // platforms (these should have deterministic output). + { + ExplicitSeedSeq seed_sequence{12, 34, 56}; + std::minstd_rand rng(seed_sequence); + + std::minstd_rand::result_type values[4] = {rng(), rng(), rng(), rng()}; + EXPECT_THAT(values, + testing::ElementsAre(579252, 43785881, 464353103, 1501811174)); + } + + { + ExplicitSeedSeq seed_sequence{12, 34, 56}; + std::mt19937 rng(seed_sequence); + + std::mt19937::result_type values[4] = {rng(), rng(), rng(), rng()}; + EXPECT_THAT(values, testing::ElementsAre(138416803, 151130212, 33817739, + 138416803)); + } + + { + ExplicitSeedSeq seed_sequence{12, 34, 56}; + std::mt19937_64 rng(seed_sequence); + + std::mt19937_64::result_type values[4] = {rng(), rng(), rng(), rng()}; + EXPECT_THAT(values, + testing::ElementsAre(19738651785169348, 1464811352364190456, + 18054685302720800, 19738651785169348)); + } +} diff --git a/absl/random/internal/fast_uniform_bits.h b/absl/random/internal/fast_uniform_bits.h index 425aaf7d..f3a5c00f 100644 --- a/absl/random/internal/fast_uniform_bits.h +++ b/absl/random/internal/fast_uniform_bits.h @@ -22,6 +22,7 @@ #include "absl/base/config.h" #include "absl/meta/type_traits.h" +#include "absl/random/internal/traits.h" namespace absl { ABSL_NAMESPACE_BEGIN @@ -98,7 +99,7 @@ class FastUniformBits { result_type operator()(URBG& g); // NOLINT(runtime/references) private: - static_assert(std::is_unsigned<UIntType>::value, + static_assert(IsUnsigned<UIntType>::value, "Class-template FastUniformBits<> must be parameterized using " "an unsigned type."); diff --git a/absl/random/internal/generate_real.h b/absl/random/internal/generate_real.h index 4f62873d..b569450c 100644 --- a/absl/random/internal/generate_real.h +++ b/absl/random/internal/generate_real.h @@ -50,10 +50,10 @@ struct GenerateSignedTag {}; // inputs, otherwise it never returns 0. // // When a value in U(0,1) is required, use: -// Uniform64ToReal<double, PositiveValueT, true>; +// GenerateRealFromBits<double, PositiveValueT, true>; // // When a value in U(-1,1) is required, use: -// Uniform64ToReal<double, SignedValueT, false>; +// GenerateRealFromBits<double, SignedValueT, false>; // // This generates more distinct values than the mathematical equivalent // `U(0, 1) * 2.0 - 1.0`. @@ -127,10 +127,8 @@ inline RealType GenerateRealFromBits(uint64_t bits, int exp_bias = 0) { // 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); + uint_type val = sign | (static_cast<uint_type>(exp) << kExp) | + (static_cast<uint_type>(bits) & kMask); // bit_cast to the output-type real_type result; diff --git a/absl/random/internal/mock_helpers.h b/absl/random/internal/mock_helpers.h index 9d6ab21e..882b0518 100644 --- a/absl/random/internal/mock_helpers.h +++ b/absl/random/internal/mock_helpers.h @@ -18,6 +18,7 @@ #include <tuple> #include <type_traits> +#include <utility> #include "absl/base/internal/fast_type_id.h" #include "absl/types/optional.h" diff --git a/absl/random/internal/nonsecure_base.h b/absl/random/internal/nonsecure_base.h index 730fa2ea..c7d7fa4b 100644 --- a/absl/random/internal/nonsecure_base.h +++ b/absl/random/internal/nonsecure_base.h @@ -17,28 +17,82 @@ #include <algorithm> #include <cstdint> -#include <iostream> #include <iterator> -#include <random> -#include <string> #include <type_traits> +#include <utility> #include <vector> #include "absl/base/macros.h" +#include "absl/container/inlined_vector.h" #include "absl/meta/type_traits.h" #include "absl/random/internal/pool_urbg.h" #include "absl/random/internal/salted_seed_seq.h" #include "absl/random/internal/seed_material.h" -#include "absl/types/optional.h" #include "absl/types/span.h" namespace absl { ABSL_NAMESPACE_BEGIN namespace random_internal { +// RandenPoolSeedSeq is a custom seed sequence type where generate() fills the +// provided buffer via the RandenPool entropy source. +class RandenPoolSeedSeq { + private: + struct ContiguousTag {}; + struct BufferTag {}; + + // Generate random unsigned values directly into the buffer. + template <typename Contiguous> + void generate_impl(ContiguousTag, Contiguous begin, Contiguous end) { + const size_t n = std::distance(begin, end); + auto* a = &(*begin); + RandenPool<uint8_t>::Fill( + absl::MakeSpan(reinterpret_cast<uint8_t*>(a), sizeof(*a) * n)); + } + + // Construct a buffer of size n and fill it with values, then copy + // those values into the seed iterators. + template <typename RandomAccessIterator> + void generate_impl(BufferTag, RandomAccessIterator begin, + RandomAccessIterator end) { + const size_t n = std::distance(begin, end); + absl::InlinedVector<uint32_t, 8> data(n, 0); + RandenPool<uint32_t>::Fill(absl::MakeSpan(data.begin(), data.end())); + std::copy(std::begin(data), std::end(data), begin); + } + + public: + using result_type = uint32_t; + + size_t size() { return 0; } + + template <typename OutIterator> + void param(OutIterator) const {} + + template <typename RandomAccessIterator> + void generate(RandomAccessIterator begin, RandomAccessIterator end) { + // RandomAccessIterator must be assignable from uint32_t + if (begin != end) { + using U = typename std::iterator_traits<RandomAccessIterator>::value_type; + // ContiguousTag indicates the common case of a known contiguous buffer, + // which allows directly filling the buffer. In C++20, + // std::contiguous_iterator_tag provides a mechanism for testing this + // capability, however until Abseil's support requirements allow us to + // assume C++20, limit checks to a few common cases. + using TagType = absl::conditional_t< + (std::is_pointer<RandomAccessIterator>::value || + std::is_same<RandomAccessIterator, + typename std::vector<U>::iterator>::value), + ContiguousTag, BufferTag>; + + generate_impl(TagType{}, begin, end); + } + } +}; + // Each instance of NonsecureURBGBase<URBG> will be seeded by variates produced // by a thread-unique URBG-instance. -template <typename URBG> +template <typename URBG, typename Seeder = RandenPoolSeedSeq> class NonsecureURBGBase { public: using result_type = typename URBG::result_type; @@ -85,49 +139,6 @@ class NonsecureURBGBase { } private: - // Seeder is a custom seed sequence type where generate() fills the provided - // buffer via the RandenPool entropy source. - struct Seeder { - using result_type = uint32_t; - - size_t size() { return 0; } - - template <typename OutIterator> - void param(OutIterator) const {} - - template <typename RandomAccessIterator> - void generate(RandomAccessIterator begin, RandomAccessIterator end) { - if (begin != end) { - // begin, end must be random access iterators assignable from uint32_t. - generate_impl( - std::integral_constant<bool, sizeof(*begin) == sizeof(uint32_t)>{}, - begin, end); - } - } - - // Commonly, generate is invoked with a pointer to a buffer which - // can be cast to a uint32_t. - template <typename RandomAccessIterator> - void generate_impl(std::integral_constant<bool, true>, - RandomAccessIterator begin, RandomAccessIterator end) { - auto buffer = absl::MakeSpan(begin, end); - auto target = absl::MakeSpan(reinterpret_cast<uint32_t*>(buffer.data()), - buffer.size()); - RandenPool<uint32_t>::Fill(target); - } - - // The non-uint32_t case should be uncommon, and involves an extra copy, - // filling the uint32_t buffer and then mixing into the output. - template <typename RandomAccessIterator> - void generate_impl(std::integral_constant<bool, false>, - RandomAccessIterator begin, RandomAccessIterator end) { - const size_t n = std::distance(begin, end); - absl::InlinedVector<uint32_t, 8> data(n, 0); - RandenPool<uint32_t>::Fill(absl::MakeSpan(data.begin(), data.end())); - std::copy(std::begin(data), std::end(data), begin); - } - }; - static URBG ConstructURBG() { Seeder seeder; return URBG(seeder); diff --git a/absl/random/internal/nonsecure_base_test.cc b/absl/random/internal/nonsecure_base_test.cc index 698027fc..3502243e 100644 --- a/absl/random/internal/nonsecure_base_test.cc +++ b/absl/random/internal/nonsecure_base_test.cc @@ -15,6 +15,7 @@ #include "absl/random/internal/nonsecure_base.h" #include <algorithm> +#include <cstdint> #include <iostream> #include <memory> #include <random> @@ -192,54 +193,35 @@ TEST(NonsecureURBGBase, EqualSeedSequencesYieldEqualVariates) { } } -// This is a PRNG-compatible type specifically designed to test -// that NonsecureURBGBase::Seeder can correctly handle iterators -// to arbitrary non-uint32_t size types. -template <typename T> -struct SeederTestEngine { - using result_type = T; +TEST(RandenPoolSeedSeqTest, SeederWorksForU32) { + absl::random_internal::RandenPoolSeedSeq seeder; - static constexpr result_type(min)() { - return (std::numeric_limits<result_type>::min)(); - } - static constexpr result_type(max)() { - return (std::numeric_limits<result_type>::max)(); - } - - template <class SeedSequence, - typename = typename absl::enable_if_t< - !std::is_same<SeedSequence, SeederTestEngine>::value>> - explicit SeederTestEngine(SeedSequence&& seq) { - seed(seq); - } - - SeederTestEngine(const SeederTestEngine&) = default; - SeederTestEngine& operator=(const SeederTestEngine&) = default; - SeederTestEngine(SeederTestEngine&&) = default; - SeederTestEngine& operator=(SeederTestEngine&&) = default; + uint32_t state[2] = {0, 0}; + seeder.generate(std::begin(state), std::end(state)); + EXPECT_FALSE(state[0] == 0 && state[1] == 0); +} - result_type operator()() { return state[0]; } +TEST(RandenPoolSeedSeqTest, SeederWorksForU64) { + absl::random_internal::RandenPoolSeedSeq seeder; - template <class SeedSequence> - void seed(SeedSequence&& seq) { - std::fill(std::begin(state), std::end(state), T(0)); - seq.generate(std::begin(state), std::end(state)); - } + uint64_t state[2] = {0, 0}; + seeder.generate(std::begin(state), std::end(state)); + EXPECT_FALSE(state[0] == 0 && state[1] == 0); + EXPECT_FALSE((state[0] >> 32) == 0 && (state[1] >> 32) == 0); +} - T state[2]; -}; +TEST(RandenPoolSeedSeqTest, SeederWorksForS32) { + absl::random_internal::RandenPoolSeedSeq seeder; -TEST(NonsecureURBGBase, SeederWorksForU32) { - using U32 = - absl::random_internal::NonsecureURBGBase<SeederTestEngine<uint32_t>>; - U32 x; - EXPECT_NE(0, x()); + int32_t state[2] = {0, 0}; + seeder.generate(std::begin(state), std::end(state)); + EXPECT_FALSE(state[0] == 0 && state[1] == 0); } -TEST(NonsecureURBGBase, SeederWorksForU64) { - using U64 = - absl::random_internal::NonsecureURBGBase<SeederTestEngine<uint64_t>>; +TEST(RandenPoolSeedSeqTest, SeederWorksForVector) { + absl::random_internal::RandenPoolSeedSeq seeder; - U64 x; - EXPECT_NE(0, x()); + std::vector<uint32_t> state(2); + seeder.generate(std::begin(state), std::end(state)); + EXPECT_FALSE(state[0] == 0 && state[1] == 0); } diff --git a/absl/random/internal/pcg_engine.h b/absl/random/internal/pcg_engine.h index 8efaf2e0..4ab44c94 100644 --- a/absl/random/internal/pcg_engine.h +++ b/absl/random/internal/pcg_engine.h @@ -262,7 +262,7 @@ struct pcg_xsl_rr_128_64 { uint64_t rotate = h >> 58u; uint64_t s = Uint128Low64(state) ^ h; #endif - return rotr(s, rotate); + return rotr(s, static_cast<int>(rotate)); } }; diff --git a/absl/random/internal/pool_urbg.cc b/absl/random/internal/pool_urbg.cc index 5bee5307..725100a4 100644 --- a/absl/random/internal/pool_urbg.cc +++ b/absl/random/internal/pool_urbg.cc @@ -194,11 +194,10 @@ RandenPoolEntry* PoolAlignedAlloc() { // Not all the platforms that we build for have std::aligned_alloc, however // since we never free these objects, we can over allocate and munge the // pointers to the correct alignment. - void* memory = std::malloc(sizeof(RandenPoolEntry) + kAlignment); - auto x = reinterpret_cast<intptr_t>(memory); + intptr_t x = reinterpret_cast<intptr_t>( + new char[sizeof(RandenPoolEntry) + kAlignment]); auto y = x % kAlignment; - void* aligned = - (y == 0) ? memory : reinterpret_cast<void*>(x + kAlignment - y); + void* aligned = reinterpret_cast<void*>(y == 0 ? x : (x + kAlignment - y)); return new (aligned) RandenPoolEntry(); } diff --git a/absl/random/internal/randen.h b/absl/random/internal/randen.h index 9a3840b8..9ff4a7a5 100644 --- a/absl/random/internal/randen.h +++ b/absl/random/internal/randen.h @@ -43,10 +43,8 @@ class Randen { // Generate updates the randen sponge. The outer portion of the sponge // (kCapacityBytes .. kStateBytes) may be consumed as PRNG state. - template <typename T, size_t N> - void Generate(T (&state)[N]) const { - static_assert(N * sizeof(T) == kStateBytes, - "Randen::Generate() requires kStateBytes of state"); + // REQUIRES: state points to kStateBytes of state. + inline void Generate(void* state) const { #if ABSL_RANDOM_INTERNAL_AES_DISPATCH // HW AES Dispatch. if (has_crypto_) { @@ -65,13 +63,9 @@ class Randen { // Absorb incorporates additional seed material into the randen sponge. After // absorb returns, Generate must be called before the state may be consumed. - template <typename S, size_t M, typename T, size_t N> - void Absorb(const S (&seed)[M], T (&state)[N]) const { - static_assert(M * sizeof(S) == RandenTraits::kSeedBytes, - "Randen::Absorb() requires kSeedBytes of seed"); - - static_assert(N * sizeof(T) == RandenTraits::kStateBytes, - "Randen::Absorb() requires kStateBytes of state"); + // REQUIRES: seed points to kSeedBytes of seed. + // REQUIRES: state points to kStateBytes of state. + inline void Absorb(const void* seed, void* state) const { #if ABSL_RANDOM_INTERNAL_AES_DISPATCH // HW AES Dispatch. if (has_crypto_) { diff --git a/absl/random/internal/randen_detect.cc b/absl/random/internal/randen_detect.cc index bbe7b965..6dababa3 100644 --- a/absl/random/internal/randen_detect.cc +++ b/absl/random/internal/randen_detect.cc @@ -24,6 +24,11 @@ #include "absl/random/internal/platform.h" +#if !defined(__UCLIBC__) && defined(__GLIBC__) && \ + (__GLIBC__ > 2 || (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 16)) +#define ABSL_HAVE_GETAUXVAL +#endif + #if defined(ABSL_ARCH_X86_64) #define ABSL_INTERNAL_USE_X86_CPUID #elif defined(ABSL_ARCH_PPC) || defined(ABSL_ARCH_ARM) || \ @@ -31,7 +36,7 @@ #if defined(__ANDROID__) #define ABSL_INTERNAL_USE_ANDROID_GETAUXVAL #define ABSL_INTERNAL_USE_GETAUXVAL -#elif defined(__linux__) +#elif defined(__linux__) && defined(ABSL_HAVE_GETAUXVAL) #define ABSL_INTERNAL_USE_LINUX_GETAUXVAL #define ABSL_INTERNAL_USE_GETAUXVAL #endif @@ -40,7 +45,6 @@ #if defined(ABSL_INTERNAL_USE_X86_CPUID) #if defined(_WIN32) || defined(_WIN64) #include <intrin.h> // NOLINT(build/include_order) -#pragma intrinsic(__cpuid) #else // MSVC-equivalent __cpuid intrinsic function. static void __cpuid(int cpu_info[4], int info_type) { diff --git a/absl/random/internal/randen_engine.h b/absl/random/internal/randen_engine.h index 92bb8905..b4708664 100644 --- a/absl/random/internal/randen_engine.h +++ b/absl/random/internal/randen_engine.h @@ -42,7 +42,7 @@ namespace random_internal { // 'Strong' (well-distributed, unpredictable, backtracking-resistant) random // generator, faster in some benchmarks than std::mt19937_64 and pcg64_c32. template <typename T> -class alignas(16) randen_engine { +class alignas(8) randen_engine { public: // C++11 URBG interface: using result_type = T; @@ -58,7 +58,8 @@ class alignas(16) randen_engine { return (std::numeric_limits<result_type>::max)(); } - explicit randen_engine(result_type seed_value = 0) { seed(seed_value); } + randen_engine() : randen_engine(0) {} + explicit randen_engine(result_type seed_value) { seed(seed_value); } template <class SeedSequence, typename = typename absl::enable_if_t< @@ -67,17 +68,27 @@ class alignas(16) randen_engine { seed(seq); } - randen_engine(const randen_engine&) = default; + // alignment requirements dictate custom copy and move constructors. + randen_engine(const randen_engine& other) + : next_(other.next_), impl_(other.impl_) { + std::memcpy(state(), other.state(), kStateSizeT * sizeof(result_type)); + } + randen_engine& operator=(const randen_engine& other) { + next_ = other.next_; + impl_ = other.impl_; + std::memcpy(state(), other.state(), kStateSizeT * sizeof(result_type)); + return *this; + } // Returns random bits from the buffer in units of result_type. result_type operator()() { // Refill the buffer if needed (unlikely). + auto* begin = state(); if (next_ >= kStateSizeT) { next_ = kCapacityT; - impl_.Generate(state_); + impl_.Generate(begin); } - - return little_endian::ToHost(state_[next_++]); + return little_endian::ToHost(begin[next_++]); } template <class SeedSequence> @@ -92,9 +103,10 @@ class alignas(16) randen_engine { void seed(result_type seed_value = 0) { next_ = kStateSizeT; // Zeroes the inner state and fills the outer state with seed_value to - // mimics behaviour of reseed - std::fill(std::begin(state_), std::begin(state_) + kCapacityT, 0); - std::fill(std::begin(state_) + kCapacityT, std::end(state_), seed_value); + // mimic the behaviour of reseed + auto* begin = state(); + std::fill(begin, begin + kCapacityT, 0); + std::fill(begin + kCapacityT, begin + kStateSizeT, seed_value); } // Inserts entropy into (part of) the state. Calling this periodically with @@ -105,7 +117,6 @@ class alignas(16) randen_engine { using sequence_result_type = typename SeedSequence::result_type; static_assert(sizeof(sequence_result_type) == 4, "SeedSequence::result_type must be 32-bit"); - constexpr size_t kBufferSize = Randen::kSeedBytes / sizeof(sequence_result_type); alignas(16) sequence_result_type buffer[kBufferSize]; @@ -119,8 +130,15 @@ class alignas(16) randen_engine { if (entropy_size < kBufferSize) { // ... and only request that many values, or 256-bits, when unspecified. const size_t requested_entropy = (entropy_size == 0) ? 8u : entropy_size; - std::fill(std::begin(buffer) + requested_entropy, std::end(buffer), 0); - seq.generate(std::begin(buffer), std::begin(buffer) + requested_entropy); + std::fill(buffer + requested_entropy, buffer + kBufferSize, 0); + seq.generate(buffer, buffer + requested_entropy); +#ifdef ABSL_IS_BIG_ENDIAN + // Randen expects the seed buffer to be in Little Endian; reverse it on + // Big Endian platforms. + for (sequence_result_type& e : buffer) { + e = absl::little_endian::FromHost(e); + } +#endif // The Randen paper suggests preferentially initializing even-numbered // 128-bit vectors of the randen state (there are 16 such vectors). // The seed data is merged into the state offset by 128-bits, which @@ -139,9 +157,9 @@ class alignas(16) randen_engine { std::swap(buffer[--dst], buffer[--src]); } } else { - seq.generate(std::begin(buffer), std::end(buffer)); + seq.generate(buffer, buffer + kBufferSize); } - impl_.Absorb(buffer, state_); + impl_.Absorb(buffer, state()); // Generate will be called when operator() is called next_ = kStateSizeT; @@ -152,9 +170,10 @@ class alignas(16) randen_engine { count -= step; constexpr uint64_t kRateT = kStateSizeT - kCapacityT; + auto* begin = state(); while (count > 0) { next_ = kCapacityT; - impl_.Generate(state_); + impl_.Generate(*reinterpret_cast<result_type(*)[kStateSizeT]>(begin)); step = std::min<uint64_t>(kRateT, count); count -= step; } @@ -162,9 +181,9 @@ class alignas(16) randen_engine { } bool operator==(const randen_engine& other) const { + const auto* begin = state(); return next_ == other.next_ && - std::equal(std::begin(state_), std::end(state_), - std::begin(other.state_)); + std::equal(begin, begin + kStateSizeT, other.state()); } bool operator!=(const randen_engine& other) const { @@ -178,11 +197,12 @@ class alignas(16) randen_engine { using numeric_type = typename random_internal::stream_format_type<result_type>::type; auto saver = random_internal::make_ostream_state_saver(os); - for (const auto& elem : engine.state_) { + auto* it = engine.state(); + for (auto* end = it + kStateSizeT; it < end; ++it) { // In the case that `elem` is `uint8_t`, it must be cast to something // larger so that it prints as an integer rather than a character. For // simplicity, apply the cast all circumstances. - os << static_cast<numeric_type>(little_endian::FromHost(elem)) + os << static_cast<numeric_type>(little_endian::FromHost(*it)) << os.fill(); } os << engine.next_; @@ -208,7 +228,7 @@ class alignas(16) randen_engine { if (is.fail()) { return is; } - std::memcpy(engine.state_, state, sizeof(engine.state_)); + std::memcpy(engine.state(), state, sizeof(state)); engine.next_ = next; return is; } @@ -219,9 +239,21 @@ class alignas(16) randen_engine { static constexpr size_t kCapacityT = Randen::kCapacityBytes / sizeof(result_type); - // First kCapacityT are `inner', the others are accessible random bits. - alignas(16) result_type state_[kStateSizeT]; - size_t next_; // index within state_ + // Returns the state array pointer, which is aligned to 16 bytes. + // The first kCapacityT are the `inner' sponge; the remainder are available. + result_type* state() { + return reinterpret_cast<result_type*>( + (reinterpret_cast<uintptr_t>(&raw_state_) & 0xf) ? (raw_state_ + 8) + : raw_state_); + } + const result_type* state() const { + return const_cast<randen_engine*>(this)->state(); + } + + // raw state array, manually aligned in state(). This overallocates + // by 8 bytes since C++ does not guarantee extended heap alignment. + alignas(8) char raw_state_[Randen::kStateBytes + 8]; + size_t next_; // index within state() Randen impl_; }; diff --git a/absl/random/internal/randen_hwaes.cc b/absl/random/internal/randen_hwaes.cc index b5a3f90a..fee6677c 100644 --- a/absl/random/internal/randen_hwaes.cc +++ b/absl/random/internal/randen_hwaes.cc @@ -23,49 +23,20 @@ #include <cstring> #include "absl/base/attributes.h" +#include "absl/numeric/int128.h" #include "absl/random/internal/platform.h" #include "absl/random/internal/randen_traits.h" // 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. -#if defined(ABSL_ARCH_X86_64) || defined(ABSL_ARCH_X86_32) -// The platform.h directives are sufficient to indicate whether -// we should build accelerated implementations for x86. -#if (ABSL_HAVE_ACCELERATED_AES || ABSL_RANDOM_INTERNAL_AES_DISPATCH) -#define ABSL_RANDEN_HWAES_IMPL 1 -#endif -#elif defined(ABSL_ARCH_PPC) -// The platform.h directives are sufficient to indicate whether -// we should build accelerated implementations for PPC. -// -// NOTE: This has mostly been tested on 64-bit Power variants, -// and not embedded cpus such as powerpc32-8540 #if ABSL_HAVE_ACCELERATED_AES +// The following plaforms have implemented RandenHwAes. +#if defined(ABSL_ARCH_X86_64) || defined(ABSL_ARCH_X86_32) || \ + defined(ABSL_ARCH_PPC) || defined(ABSL_ARCH_ARM) || \ + defined(ABSL_ARCH_AARCH64) #define ABSL_RANDEN_HWAES_IMPL 1 #endif -#elif defined(ABSL_ARCH_ARM) || defined(ABSL_ARCH_AARCH64) -// ARM is somewhat more complicated. We might support crypto natively... -#if ABSL_HAVE_ACCELERATED_AES || \ - (defined(__ARM_NEON) && defined(__ARM_FEATURE_CRYPTO)) -#define ABSL_RANDEN_HWAES_IMPL 1 - -#elif ABSL_RANDOM_INTERNAL_AES_DISPATCH && !defined(__APPLE__) && \ - (defined(__GNUC__) && __GNUC__ > 4 || __GNUC__ == 4 && __GNUC_MINOR__ > 9) -// ...or, on GCC, we can use an ASM directive to -// instruct the assember to allow crypto instructions. -#define ABSL_RANDEN_HWAES_IMPL 1 -#define ABSL_RANDEN_HWAES_IMPL_CRYPTO_DIRECTIVE 1 -#endif -#else -// HWAES is unsupported by these architectures / platforms: -// __myriad2__ -// __mips__ -// -// Other architectures / platforms are unknown. -// -// See the Abseil documentation on supported macros at: -// https://abseil.io/docs/cpp/platforms/macros #endif #if !defined(ABSL_RANDEN_HWAES_IMPL) @@ -120,11 +91,6 @@ namespace { using absl::random_internal::RandenTraits; -// Randen operates on 128-bit vectors. -struct alignas(16) u64x2 { - uint64_t data[2]; -}; - } // namespace // TARGET_CRYPTO defines a crypto attribute for each architecture. @@ -186,7 +152,7 @@ inline ABSL_TARGET_CRYPTO Vector128 AesRound(const Vector128& state, } // Enables native loads in the round loop by pre-swapping. -inline ABSL_TARGET_CRYPTO void SwapEndian(u64x2* state) { +inline ABSL_TARGET_CRYPTO void SwapEndian(absl::uint128* state) { for (uint32_t block = 0; block < RandenTraits::kFeistelBlocks; ++block) { Vector128Store(ReverseBytes(Vector128Load(state + block)), state + block); } @@ -196,22 +162,6 @@ inline ABSL_TARGET_CRYPTO void SwapEndian(u64x2* state) { #elif defined(ABSL_ARCH_ARM) || defined(ABSL_ARCH_AARCH64) -// This asm directive will cause the file to be compiled with crypto extensions -// whether or not the cpu-architecture supports it. -#if ABSL_RANDEN_HWAES_IMPL_CRYPTO_DIRECTIVE -asm(".arch_extension crypto\n"); - -// Override missing defines. -#if !defined(__ARM_NEON) -#define __ARM_NEON 1 -#endif - -#if !defined(__ARM_FEATURE_CRYPTO) -#define __ARM_FEATURE_CRYPTO 1 -#endif - -#endif - // Rely on the ARM NEON+Crypto advanced simd types, defined in <arm_neon.h>. // uint8x16_t is the user alias for underlying __simd128_uint8_t type. // http://infocenter.arm.com/help/topic/com.arm.doc.ihi0073a/IHI0073A_arm_neon_intrinsics_ref.pdf @@ -261,7 +211,7 @@ inline ABSL_TARGET_CRYPTO void SwapEndian(void*) {} #elif defined(ABSL_ARCH_X86_64) || defined(ABSL_ARCH_X86_32) // On x86 we rely on the aesni instructions -#include <wmmintrin.h> +#include <immintrin.h> namespace { @@ -270,7 +220,7 @@ namespace { class Vector128 { public: // Convert from/to intrinsics. - inline explicit Vector128(const __m128i& Vector128) : data_(Vector128) {} + inline explicit Vector128(const __m128i& v) : data_(v) {} inline __m128i data() const { return data_; } @@ -327,7 +277,7 @@ namespace { // Block shuffles applies a shuffle to the entire state between AES rounds. // Improved odd-even shuffle from "New criterion for diffusion property". -inline ABSL_TARGET_CRYPTO void BlockShuffle(u64x2* state) { +inline ABSL_TARGET_CRYPTO void BlockShuffle(absl::uint128* state) { static_assert(RandenTraits::kFeistelBlocks == 16, "Expecting 16 FeistelBlocks."); @@ -374,8 +324,9 @@ inline ABSL_TARGET_CRYPTO void BlockShuffle(u64x2* 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_TARGET_CRYPTO const u64x2* FeistelRound( - u64x2* state, const u64x2* ABSL_RANDOM_INTERNAL_RESTRICT keys) { +inline ABSL_TARGET_CRYPTO const absl::uint128* FeistelRound( + absl::uint128* state, + const absl::uint128* ABSL_RANDOM_INTERNAL_RESTRICT keys) { static_assert(RandenTraits::kFeistelBlocks == 16, "Expecting 16 FeistelBlocks."); @@ -436,7 +387,8 @@ inline ABSL_TARGET_CRYPTO const u64x2* FeistelRound( // 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_TARGET_CRYPTO void Permute( - u64x2* state, const u64x2* ABSL_RANDOM_INTERNAL_RESTRICT keys) { + absl::uint128* state, + const absl::uint128* ABSL_RANDOM_INTERNAL_RESTRICT keys) { // (Successfully unrolled; the first iteration jumps into the second half) #ifdef __clang__ #pragma clang loop unroll_count(2) @@ -473,10 +425,11 @@ void ABSL_TARGET_CRYPTO RandenHwAes::Absorb(const void* seed_void, static_assert(RandenTraits::kStateBytes / sizeof(Vector128) == 16, "Unexpected Randen kStateBlocks"); - auto* state = - reinterpret_cast<u64x2 * ABSL_RANDOM_INTERNAL_RESTRICT>(state_void); + auto* state = reinterpret_cast<absl::uint128 * ABSL_RANDOM_INTERNAL_RESTRICT>( + state_void); const auto* seed = - reinterpret_cast<const u64x2 * ABSL_RANDOM_INTERNAL_RESTRICT>(seed_void); + reinterpret_cast<const absl::uint128 * ABSL_RANDOM_INTERNAL_RESTRICT>( + seed_void); Vector128 b1 = Vector128Load(state + 1); b1 ^= Vector128Load(seed + 0); @@ -545,8 +498,8 @@ void ABSL_TARGET_CRYPTO RandenHwAes::Generate(const void* keys_void, static_assert(RandenTraits::kCapacityBytes == sizeof(Vector128), "Capacity mismatch"); - auto* state = reinterpret_cast<u64x2*>(state_void); - const auto* keys = reinterpret_cast<const u64x2*>(keys_void); + auto* state = reinterpret_cast<absl::uint128*>(state_void); + const auto* keys = reinterpret_cast<const absl::uint128*>(keys_void); const Vector128 prev_inner = Vector128Load(state); diff --git a/absl/random/internal/randen_hwaes_test.cc b/absl/random/internal/randen_hwaes_test.cc index 66ddb43f..2348b55c 100644 --- a/absl/random/internal/randen_hwaes_test.cc +++ b/absl/random/internal/randen_hwaes_test.cc @@ -27,44 +27,39 @@ namespace { using absl::random_internal::RandenHwAes; using absl::random_internal::RandenTraits; -// Local state parameters. -constexpr size_t kSeedBytes = - RandenTraits::kStateBytes - RandenTraits::kCapacityBytes; -constexpr size_t kStateSizeT = RandenTraits::kStateBytes / sizeof(uint64_t); -constexpr size_t kSeedSizeT = kSeedBytes / sizeof(uint32_t); - -struct alignas(16) randen { - uint64_t state[kStateSizeT]; - uint32_t seed[kSeedSizeT]; -}; - TEST(RandenHwAesTest, Default) { EXPECT_TRUE(absl::random_internal::CPUSupportsRandenHwAes()); - constexpr uint64_t kGolden[] = { - 0x6c6534090ee6d3ee, 0x044e2b9b9d5333c6, 0xc3c14f134e433977, - 0xdda9f47cd90410ee, 0x887bf3087fd8ca10, 0xf0b780f545c72912, - 0x15dbb1d37696599f, 0x30ec63baff3c6d59, 0xb29f73606f7f20a6, - 0x02808a316f49a54c, 0x3b8feaf9d5c8e50e, 0x9cbf605e3fd9de8a, - 0xc970ae1a78183bbb, 0xd8b2ffd356301ed5, 0xf4b327fe0fc73c37, - 0xcdfd8d76eb8f9a19, 0xc3a506eb91420c9d, 0xd5af05dd3eff9556, - 0x48db1bb78f83c4a1, 0x7023920e0d6bfe8c, 0x58d3575834956d42, - 0xed1ef4c26b87b840, 0x8eef32a23e0b2df3, 0x497cabf3431154fc, - 0x4e24370570029a8b, 0xd88b5749f090e5ea, 0xc651a582a970692f, - 0x78fcec2cbb6342f5, 0x463cb745612f55db, 0x352ee4ad1816afe3, - 0x026ff374c101da7e, 0x811ef0821c3de851, + constexpr uint8_t kGolden[] = { + 0xee, 0xd3, 0xe6, 0x0e, 0x09, 0x34, 0x65, 0x6c, 0xc6, 0x33, 0x53, 0x9d, + 0x9b, 0x2b, 0x4e, 0x04, 0x77, 0x39, 0x43, 0x4e, 0x13, 0x4f, 0xc1, 0xc3, + 0xee, 0x10, 0x04, 0xd9, 0x7c, 0xf4, 0xa9, 0xdd, 0x10, 0xca, 0xd8, 0x7f, + 0x08, 0xf3, 0x7b, 0x88, 0x12, 0x29, 0xc7, 0x45, 0xf5, 0x80, 0xb7, 0xf0, + 0x9f, 0x59, 0x96, 0x76, 0xd3, 0xb1, 0xdb, 0x15, 0x59, 0x6d, 0x3c, 0xff, + 0xba, 0x63, 0xec, 0x30, 0xa6, 0x20, 0x7f, 0x6f, 0x60, 0x73, 0x9f, 0xb2, + 0x4c, 0xa5, 0x49, 0x6f, 0x31, 0x8a, 0x80, 0x02, 0x0e, 0xe5, 0xc8, 0xd5, + 0xf9, 0xea, 0x8f, 0x3b, 0x8a, 0xde, 0xd9, 0x3f, 0x5e, 0x60, 0xbf, 0x9c, + 0xbb, 0x3b, 0x18, 0x78, 0x1a, 0xae, 0x70, 0xc9, 0xd5, 0x1e, 0x30, 0x56, + 0xd3, 0xff, 0xb2, 0xd8, 0x37, 0x3c, 0xc7, 0x0f, 0xfe, 0x27, 0xb3, 0xf4, + 0x19, 0x9a, 0x8f, 0xeb, 0x76, 0x8d, 0xfd, 0xcd, 0x9d, 0x0c, 0x42, 0x91, + 0xeb, 0x06, 0xa5, 0xc3, 0x56, 0x95, 0xff, 0x3e, 0xdd, 0x05, 0xaf, 0xd5, + 0xa1, 0xc4, 0x83, 0x8f, 0xb7, 0x1b, 0xdb, 0x48, 0x8c, 0xfe, 0x6b, 0x0d, + 0x0e, 0x92, 0x23, 0x70, 0x42, 0x6d, 0x95, 0x34, 0x58, 0x57, 0xd3, 0x58, + 0x40, 0xb8, 0x87, 0x6b, 0xc2, 0xf4, 0x1e, 0xed, 0xf3, 0x2d, 0x0b, 0x3e, + 0xa2, 0x32, 0xef, 0x8e, 0xfc, 0x54, 0x11, 0x43, 0xf3, 0xab, 0x7c, 0x49, + 0x8b, 0x9a, 0x02, 0x70, 0x05, 0x37, 0x24, 0x4e, 0xea, 0xe5, 0x90, 0xf0, + 0x49, 0x57, 0x8b, 0xd8, 0x2f, 0x69, 0x70, 0xa9, 0x82, 0xa5, 0x51, 0xc6, + 0xf5, 0x42, 0x63, 0xbb, 0x2c, 0xec, 0xfc, 0x78, 0xdb, 0x55, 0x2f, 0x61, + 0x45, 0xb7, 0x3c, 0x46, 0xe3, 0xaf, 0x16, 0x18, 0xad, 0xe4, 0x2e, 0x35, + 0x7e, 0xda, 0x01, 0xc1, 0x74, 0xf3, 0x6f, 0x02, 0x51, 0xe8, 0x3d, 0x1c, + 0x82, 0xf0, 0x1e, 0x81, }; - alignas(16) randen d; - memset(d.state, 0, sizeof(d.state)); - RandenHwAes::Generate(RandenHwAes::GetKeys(), d.state); + alignas(16) uint8_t state[RandenTraits::kStateBytes]; + std::memset(state, 0, sizeof(state)); - uint64_t* id = d.state; - for (const auto& elem : kGolden) { - auto a = absl::StrFormat("%#x", elem); - auto b = absl::StrFormat("%#x", *id++); - EXPECT_EQ(a, b); - } + RandenHwAes::Generate(RandenHwAes::GetKeys(), state); + EXPECT_EQ(0, std::memcmp(state, kGolden, sizeof(state))); } } // namespace diff --git a/absl/random/internal/randen_slow.cc b/absl/random/internal/randen_slow.cc index 4e5f3dc1..9bfd2a40 100644 --- a/absl/random/internal/randen_slow.cc +++ b/absl/random/internal/randen_slow.cc @@ -19,6 +19,8 @@ #include <cstring> #include "absl/base/attributes.h" +#include "absl/base/internal/endian.h" +#include "absl/numeric/int128.h" #include "absl/random/internal/platform.h" #include "absl/random/internal/randen_traits.h" @@ -38,192 +40,193 @@ namespace { // AES portions based on rijndael-alg-fst.c, -// https://fastcrypto.org/front/misc/rijndael-alg-fst.c +// https://fastcrypto.org/front/misc/rijndael-alg-fst.c, and modified for +// platform-endianness. // // Implementation of // http://www.csrc.nist.gov/publications/fips/fips197/fips-197.pdf constexpr uint32_t te0[256] = { - 0xc66363a5, 0xf87c7c84, 0xee777799, 0xf67b7b8d, 0xfff2f20d, 0xd66b6bbd, - 0xde6f6fb1, 0x91c5c554, 0x60303050, 0x02010103, 0xce6767a9, 0x562b2b7d, - 0xe7fefe19, 0xb5d7d762, 0x4dababe6, 0xec76769a, 0x8fcaca45, 0x1f82829d, - 0x89c9c940, 0xfa7d7d87, 0xeffafa15, 0xb25959eb, 0x8e4747c9, 0xfbf0f00b, - 0x41adadec, 0xb3d4d467, 0x5fa2a2fd, 0x45afafea, 0x239c9cbf, 0x53a4a4f7, - 0xe4727296, 0x9bc0c05b, 0x75b7b7c2, 0xe1fdfd1c, 0x3d9393ae, 0x4c26266a, - 0x6c36365a, 0x7e3f3f41, 0xf5f7f702, 0x83cccc4f, 0x6834345c, 0x51a5a5f4, - 0xd1e5e534, 0xf9f1f108, 0xe2717193, 0xabd8d873, 0x62313153, 0x2a15153f, - 0x0804040c, 0x95c7c752, 0x46232365, 0x9dc3c35e, 0x30181828, 0x379696a1, - 0x0a05050f, 0x2f9a9ab5, 0x0e070709, 0x24121236, 0x1b80809b, 0xdfe2e23d, - 0xcdebeb26, 0x4e272769, 0x7fb2b2cd, 0xea75759f, 0x1209091b, 0x1d83839e, - 0x582c2c74, 0x341a1a2e, 0x361b1b2d, 0xdc6e6eb2, 0xb45a5aee, 0x5ba0a0fb, - 0xa45252f6, 0x763b3b4d, 0xb7d6d661, 0x7db3b3ce, 0x5229297b, 0xdde3e33e, - 0x5e2f2f71, 0x13848497, 0xa65353f5, 0xb9d1d168, 0x00000000, 0xc1eded2c, - 0x40202060, 0xe3fcfc1f, 0x79b1b1c8, 0xb65b5bed, 0xd46a6abe, 0x8dcbcb46, - 0x67bebed9, 0x7239394b, 0x944a4ade, 0x984c4cd4, 0xb05858e8, 0x85cfcf4a, - 0xbbd0d06b, 0xc5efef2a, 0x4faaaae5, 0xedfbfb16, 0x864343c5, 0x9a4d4dd7, - 0x66333355, 0x11858594, 0x8a4545cf, 0xe9f9f910, 0x04020206, 0xfe7f7f81, - 0xa05050f0, 0x783c3c44, 0x259f9fba, 0x4ba8a8e3, 0xa25151f3, 0x5da3a3fe, - 0x804040c0, 0x058f8f8a, 0x3f9292ad, 0x219d9dbc, 0x70383848, 0xf1f5f504, - 0x63bcbcdf, 0x77b6b6c1, 0xafdada75, 0x42212163, 0x20101030, 0xe5ffff1a, - 0xfdf3f30e, 0xbfd2d26d, 0x81cdcd4c, 0x180c0c14, 0x26131335, 0xc3ecec2f, - 0xbe5f5fe1, 0x359797a2, 0x884444cc, 0x2e171739, 0x93c4c457, 0x55a7a7f2, - 0xfc7e7e82, 0x7a3d3d47, 0xc86464ac, 0xba5d5de7, 0x3219192b, 0xe6737395, - 0xc06060a0, 0x19818198, 0x9e4f4fd1, 0xa3dcdc7f, 0x44222266, 0x542a2a7e, - 0x3b9090ab, 0x0b888883, 0x8c4646ca, 0xc7eeee29, 0x6bb8b8d3, 0x2814143c, - 0xa7dede79, 0xbc5e5ee2, 0x160b0b1d, 0xaddbdb76, 0xdbe0e03b, 0x64323256, - 0x743a3a4e, 0x140a0a1e, 0x924949db, 0x0c06060a, 0x4824246c, 0xb85c5ce4, - 0x9fc2c25d, 0xbdd3d36e, 0x43acacef, 0xc46262a6, 0x399191a8, 0x319595a4, - 0xd3e4e437, 0xf279798b, 0xd5e7e732, 0x8bc8c843, 0x6e373759, 0xda6d6db7, - 0x018d8d8c, 0xb1d5d564, 0x9c4e4ed2, 0x49a9a9e0, 0xd86c6cb4, 0xac5656fa, - 0xf3f4f407, 0xcfeaea25, 0xca6565af, 0xf47a7a8e, 0x47aeaee9, 0x10080818, - 0x6fbabad5, 0xf0787888, 0x4a25256f, 0x5c2e2e72, 0x381c1c24, 0x57a6a6f1, - 0x73b4b4c7, 0x97c6c651, 0xcbe8e823, 0xa1dddd7c, 0xe874749c, 0x3e1f1f21, - 0x964b4bdd, 0x61bdbddc, 0x0d8b8b86, 0x0f8a8a85, 0xe0707090, 0x7c3e3e42, - 0x71b5b5c4, 0xcc6666aa, 0x904848d8, 0x06030305, 0xf7f6f601, 0x1c0e0e12, - 0xc26161a3, 0x6a35355f, 0xae5757f9, 0x69b9b9d0, 0x17868691, 0x99c1c158, - 0x3a1d1d27, 0x279e9eb9, 0xd9e1e138, 0xebf8f813, 0x2b9898b3, 0x22111133, - 0xd26969bb, 0xa9d9d970, 0x078e8e89, 0x339494a7, 0x2d9b9bb6, 0x3c1e1e22, - 0x15878792, 0xc9e9e920, 0x87cece49, 0xaa5555ff, 0x50282878, 0xa5dfdf7a, - 0x038c8c8f, 0x59a1a1f8, 0x09898980, 0x1a0d0d17, 0x65bfbfda, 0xd7e6e631, - 0x844242c6, 0xd06868b8, 0x824141c3, 0x299999b0, 0x5a2d2d77, 0x1e0f0f11, - 0x7bb0b0cb, 0xa85454fc, 0x6dbbbbd6, 0x2c16163a, + 0xa56363c6, 0x847c7cf8, 0x997777ee, 0x8d7b7bf6, 0x0df2f2ff, 0xbd6b6bd6, + 0xb16f6fde, 0x54c5c591, 0x50303060, 0x03010102, 0xa96767ce, 0x7d2b2b56, + 0x19fefee7, 0x62d7d7b5, 0xe6abab4d, 0x9a7676ec, 0x45caca8f, 0x9d82821f, + 0x40c9c989, 0x877d7dfa, 0x15fafaef, 0xeb5959b2, 0xc947478e, 0x0bf0f0fb, + 0xecadad41, 0x67d4d4b3, 0xfda2a25f, 0xeaafaf45, 0xbf9c9c23, 0xf7a4a453, + 0x967272e4, 0x5bc0c09b, 0xc2b7b775, 0x1cfdfde1, 0xae93933d, 0x6a26264c, + 0x5a36366c, 0x413f3f7e, 0x02f7f7f5, 0x4fcccc83, 0x5c343468, 0xf4a5a551, + 0x34e5e5d1, 0x08f1f1f9, 0x937171e2, 0x73d8d8ab, 0x53313162, 0x3f15152a, + 0x0c040408, 0x52c7c795, 0x65232346, 0x5ec3c39d, 0x28181830, 0xa1969637, + 0x0f05050a, 0xb59a9a2f, 0x0907070e, 0x36121224, 0x9b80801b, 0x3de2e2df, + 0x26ebebcd, 0x6927274e, 0xcdb2b27f, 0x9f7575ea, 0x1b090912, 0x9e83831d, + 0x742c2c58, 0x2e1a1a34, 0x2d1b1b36, 0xb26e6edc, 0xee5a5ab4, 0xfba0a05b, + 0xf65252a4, 0x4d3b3b76, 0x61d6d6b7, 0xceb3b37d, 0x7b292952, 0x3ee3e3dd, + 0x712f2f5e, 0x97848413, 0xf55353a6, 0x68d1d1b9, 0x00000000, 0x2cededc1, + 0x60202040, 0x1ffcfce3, 0xc8b1b179, 0xed5b5bb6, 0xbe6a6ad4, 0x46cbcb8d, + 0xd9bebe67, 0x4b393972, 0xde4a4a94, 0xd44c4c98, 0xe85858b0, 0x4acfcf85, + 0x6bd0d0bb, 0x2aefefc5, 0xe5aaaa4f, 0x16fbfbed, 0xc5434386, 0xd74d4d9a, + 0x55333366, 0x94858511, 0xcf45458a, 0x10f9f9e9, 0x06020204, 0x817f7ffe, + 0xf05050a0, 0x443c3c78, 0xba9f9f25, 0xe3a8a84b, 0xf35151a2, 0xfea3a35d, + 0xc0404080, 0x8a8f8f05, 0xad92923f, 0xbc9d9d21, 0x48383870, 0x04f5f5f1, + 0xdfbcbc63, 0xc1b6b677, 0x75dadaaf, 0x63212142, 0x30101020, 0x1affffe5, + 0x0ef3f3fd, 0x6dd2d2bf, 0x4ccdcd81, 0x140c0c18, 0x35131326, 0x2fececc3, + 0xe15f5fbe, 0xa2979735, 0xcc444488, 0x3917172e, 0x57c4c493, 0xf2a7a755, + 0x827e7efc, 0x473d3d7a, 0xac6464c8, 0xe75d5dba, 0x2b191932, 0x957373e6, + 0xa06060c0, 0x98818119, 0xd14f4f9e, 0x7fdcdca3, 0x66222244, 0x7e2a2a54, + 0xab90903b, 0x8388880b, 0xca46468c, 0x29eeeec7, 0xd3b8b86b, 0x3c141428, + 0x79dedea7, 0xe25e5ebc, 0x1d0b0b16, 0x76dbdbad, 0x3be0e0db, 0x56323264, + 0x4e3a3a74, 0x1e0a0a14, 0xdb494992, 0x0a06060c, 0x6c242448, 0xe45c5cb8, + 0x5dc2c29f, 0x6ed3d3bd, 0xefacac43, 0xa66262c4, 0xa8919139, 0xa4959531, + 0x37e4e4d3, 0x8b7979f2, 0x32e7e7d5, 0x43c8c88b, 0x5937376e, 0xb76d6dda, + 0x8c8d8d01, 0x64d5d5b1, 0xd24e4e9c, 0xe0a9a949, 0xb46c6cd8, 0xfa5656ac, + 0x07f4f4f3, 0x25eaeacf, 0xaf6565ca, 0x8e7a7af4, 0xe9aeae47, 0x18080810, + 0xd5baba6f, 0x887878f0, 0x6f25254a, 0x722e2e5c, 0x241c1c38, 0xf1a6a657, + 0xc7b4b473, 0x51c6c697, 0x23e8e8cb, 0x7cdddda1, 0x9c7474e8, 0x211f1f3e, + 0xdd4b4b96, 0xdcbdbd61, 0x868b8b0d, 0x858a8a0f, 0x907070e0, 0x423e3e7c, + 0xc4b5b571, 0xaa6666cc, 0xd8484890, 0x05030306, 0x01f6f6f7, 0x120e0e1c, + 0xa36161c2, 0x5f35356a, 0xf95757ae, 0xd0b9b969, 0x91868617, 0x58c1c199, + 0x271d1d3a, 0xb99e9e27, 0x38e1e1d9, 0x13f8f8eb, 0xb398982b, 0x33111122, + 0xbb6969d2, 0x70d9d9a9, 0x898e8e07, 0xa7949433, 0xb69b9b2d, 0x221e1e3c, + 0x92878715, 0x20e9e9c9, 0x49cece87, 0xff5555aa, 0x78282850, 0x7adfdfa5, + 0x8f8c8c03, 0xf8a1a159, 0x80898909, 0x170d0d1a, 0xdabfbf65, 0x31e6e6d7, + 0xc6424284, 0xb86868d0, 0xc3414182, 0xb0999929, 0x772d2d5a, 0x110f0f1e, + 0xcbb0b07b, 0xfc5454a8, 0xd6bbbb6d, 0x3a16162c, }; constexpr uint32_t te1[256] = { - 0xa5c66363, 0x84f87c7c, 0x99ee7777, 0x8df67b7b, 0x0dfff2f2, 0xbdd66b6b, - 0xb1de6f6f, 0x5491c5c5, 0x50603030, 0x03020101, 0xa9ce6767, 0x7d562b2b, - 0x19e7fefe, 0x62b5d7d7, 0xe64dabab, 0x9aec7676, 0x458fcaca, 0x9d1f8282, - 0x4089c9c9, 0x87fa7d7d, 0x15effafa, 0xebb25959, 0xc98e4747, 0x0bfbf0f0, - 0xec41adad, 0x67b3d4d4, 0xfd5fa2a2, 0xea45afaf, 0xbf239c9c, 0xf753a4a4, - 0x96e47272, 0x5b9bc0c0, 0xc275b7b7, 0x1ce1fdfd, 0xae3d9393, 0x6a4c2626, - 0x5a6c3636, 0x417e3f3f, 0x02f5f7f7, 0x4f83cccc, 0x5c683434, 0xf451a5a5, - 0x34d1e5e5, 0x08f9f1f1, 0x93e27171, 0x73abd8d8, 0x53623131, 0x3f2a1515, - 0x0c080404, 0x5295c7c7, 0x65462323, 0x5e9dc3c3, 0x28301818, 0xa1379696, - 0x0f0a0505, 0xb52f9a9a, 0x090e0707, 0x36241212, 0x9b1b8080, 0x3ddfe2e2, - 0x26cdebeb, 0x694e2727, 0xcd7fb2b2, 0x9fea7575, 0x1b120909, 0x9e1d8383, - 0x74582c2c, 0x2e341a1a, 0x2d361b1b, 0xb2dc6e6e, 0xeeb45a5a, 0xfb5ba0a0, - 0xf6a45252, 0x4d763b3b, 0x61b7d6d6, 0xce7db3b3, 0x7b522929, 0x3edde3e3, - 0x715e2f2f, 0x97138484, 0xf5a65353, 0x68b9d1d1, 0x00000000, 0x2cc1eded, - 0x60402020, 0x1fe3fcfc, 0xc879b1b1, 0xedb65b5b, 0xbed46a6a, 0x468dcbcb, - 0xd967bebe, 0x4b723939, 0xde944a4a, 0xd4984c4c, 0xe8b05858, 0x4a85cfcf, - 0x6bbbd0d0, 0x2ac5efef, 0xe54faaaa, 0x16edfbfb, 0xc5864343, 0xd79a4d4d, - 0x55663333, 0x94118585, 0xcf8a4545, 0x10e9f9f9, 0x06040202, 0x81fe7f7f, - 0xf0a05050, 0x44783c3c, 0xba259f9f, 0xe34ba8a8, 0xf3a25151, 0xfe5da3a3, - 0xc0804040, 0x8a058f8f, 0xad3f9292, 0xbc219d9d, 0x48703838, 0x04f1f5f5, - 0xdf63bcbc, 0xc177b6b6, 0x75afdada, 0x63422121, 0x30201010, 0x1ae5ffff, - 0x0efdf3f3, 0x6dbfd2d2, 0x4c81cdcd, 0x14180c0c, 0x35261313, 0x2fc3ecec, - 0xe1be5f5f, 0xa2359797, 0xcc884444, 0x392e1717, 0x5793c4c4, 0xf255a7a7, - 0x82fc7e7e, 0x477a3d3d, 0xacc86464, 0xe7ba5d5d, 0x2b321919, 0x95e67373, - 0xa0c06060, 0x98198181, 0xd19e4f4f, 0x7fa3dcdc, 0x66442222, 0x7e542a2a, - 0xab3b9090, 0x830b8888, 0xca8c4646, 0x29c7eeee, 0xd36bb8b8, 0x3c281414, - 0x79a7dede, 0xe2bc5e5e, 0x1d160b0b, 0x76addbdb, 0x3bdbe0e0, 0x56643232, - 0x4e743a3a, 0x1e140a0a, 0xdb924949, 0x0a0c0606, 0x6c482424, 0xe4b85c5c, - 0x5d9fc2c2, 0x6ebdd3d3, 0xef43acac, 0xa6c46262, 0xa8399191, 0xa4319595, - 0x37d3e4e4, 0x8bf27979, 0x32d5e7e7, 0x438bc8c8, 0x596e3737, 0xb7da6d6d, - 0x8c018d8d, 0x64b1d5d5, 0xd29c4e4e, 0xe049a9a9, 0xb4d86c6c, 0xfaac5656, - 0x07f3f4f4, 0x25cfeaea, 0xafca6565, 0x8ef47a7a, 0xe947aeae, 0x18100808, - 0xd56fbaba, 0x88f07878, 0x6f4a2525, 0x725c2e2e, 0x24381c1c, 0xf157a6a6, - 0xc773b4b4, 0x5197c6c6, 0x23cbe8e8, 0x7ca1dddd, 0x9ce87474, 0x213e1f1f, - 0xdd964b4b, 0xdc61bdbd, 0x860d8b8b, 0x850f8a8a, 0x90e07070, 0x427c3e3e, - 0xc471b5b5, 0xaacc6666, 0xd8904848, 0x05060303, 0x01f7f6f6, 0x121c0e0e, - 0xa3c26161, 0x5f6a3535, 0xf9ae5757, 0xd069b9b9, 0x91178686, 0x5899c1c1, - 0x273a1d1d, 0xb9279e9e, 0x38d9e1e1, 0x13ebf8f8, 0xb32b9898, 0x33221111, - 0xbbd26969, 0x70a9d9d9, 0x89078e8e, 0xa7339494, 0xb62d9b9b, 0x223c1e1e, - 0x92158787, 0x20c9e9e9, 0x4987cece, 0xffaa5555, 0x78502828, 0x7aa5dfdf, - 0x8f038c8c, 0xf859a1a1, 0x80098989, 0x171a0d0d, 0xda65bfbf, 0x31d7e6e6, - 0xc6844242, 0xb8d06868, 0xc3824141, 0xb0299999, 0x775a2d2d, 0x111e0f0f, - 0xcb7bb0b0, 0xfca85454, 0xd66dbbbb, 0x3a2c1616, + 0x6363c6a5, 0x7c7cf884, 0x7777ee99, 0x7b7bf68d, 0xf2f2ff0d, 0x6b6bd6bd, + 0x6f6fdeb1, 0xc5c59154, 0x30306050, 0x01010203, 0x6767cea9, 0x2b2b567d, + 0xfefee719, 0xd7d7b562, 0xabab4de6, 0x7676ec9a, 0xcaca8f45, 0x82821f9d, + 0xc9c98940, 0x7d7dfa87, 0xfafaef15, 0x5959b2eb, 0x47478ec9, 0xf0f0fb0b, + 0xadad41ec, 0xd4d4b367, 0xa2a25ffd, 0xafaf45ea, 0x9c9c23bf, 0xa4a453f7, + 0x7272e496, 0xc0c09b5b, 0xb7b775c2, 0xfdfde11c, 0x93933dae, 0x26264c6a, + 0x36366c5a, 0x3f3f7e41, 0xf7f7f502, 0xcccc834f, 0x3434685c, 0xa5a551f4, + 0xe5e5d134, 0xf1f1f908, 0x7171e293, 0xd8d8ab73, 0x31316253, 0x15152a3f, + 0x0404080c, 0xc7c79552, 0x23234665, 0xc3c39d5e, 0x18183028, 0x969637a1, + 0x05050a0f, 0x9a9a2fb5, 0x07070e09, 0x12122436, 0x80801b9b, 0xe2e2df3d, + 0xebebcd26, 0x27274e69, 0xb2b27fcd, 0x7575ea9f, 0x0909121b, 0x83831d9e, + 0x2c2c5874, 0x1a1a342e, 0x1b1b362d, 0x6e6edcb2, 0x5a5ab4ee, 0xa0a05bfb, + 0x5252a4f6, 0x3b3b764d, 0xd6d6b761, 0xb3b37dce, 0x2929527b, 0xe3e3dd3e, + 0x2f2f5e71, 0x84841397, 0x5353a6f5, 0xd1d1b968, 0x00000000, 0xededc12c, + 0x20204060, 0xfcfce31f, 0xb1b179c8, 0x5b5bb6ed, 0x6a6ad4be, 0xcbcb8d46, + 0xbebe67d9, 0x3939724b, 0x4a4a94de, 0x4c4c98d4, 0x5858b0e8, 0xcfcf854a, + 0xd0d0bb6b, 0xefefc52a, 0xaaaa4fe5, 0xfbfbed16, 0x434386c5, 0x4d4d9ad7, + 0x33336655, 0x85851194, 0x45458acf, 0xf9f9e910, 0x02020406, 0x7f7ffe81, + 0x5050a0f0, 0x3c3c7844, 0x9f9f25ba, 0xa8a84be3, 0x5151a2f3, 0xa3a35dfe, + 0x404080c0, 0x8f8f058a, 0x92923fad, 0x9d9d21bc, 0x38387048, 0xf5f5f104, + 0xbcbc63df, 0xb6b677c1, 0xdadaaf75, 0x21214263, 0x10102030, 0xffffe51a, + 0xf3f3fd0e, 0xd2d2bf6d, 0xcdcd814c, 0x0c0c1814, 0x13132635, 0xececc32f, + 0x5f5fbee1, 0x979735a2, 0x444488cc, 0x17172e39, 0xc4c49357, 0xa7a755f2, + 0x7e7efc82, 0x3d3d7a47, 0x6464c8ac, 0x5d5dbae7, 0x1919322b, 0x7373e695, + 0x6060c0a0, 0x81811998, 0x4f4f9ed1, 0xdcdca37f, 0x22224466, 0x2a2a547e, + 0x90903bab, 0x88880b83, 0x46468cca, 0xeeeec729, 0xb8b86bd3, 0x1414283c, + 0xdedea779, 0x5e5ebce2, 0x0b0b161d, 0xdbdbad76, 0xe0e0db3b, 0x32326456, + 0x3a3a744e, 0x0a0a141e, 0x494992db, 0x06060c0a, 0x2424486c, 0x5c5cb8e4, + 0xc2c29f5d, 0xd3d3bd6e, 0xacac43ef, 0x6262c4a6, 0x919139a8, 0x959531a4, + 0xe4e4d337, 0x7979f28b, 0xe7e7d532, 0xc8c88b43, 0x37376e59, 0x6d6ddab7, + 0x8d8d018c, 0xd5d5b164, 0x4e4e9cd2, 0xa9a949e0, 0x6c6cd8b4, 0x5656acfa, + 0xf4f4f307, 0xeaeacf25, 0x6565caaf, 0x7a7af48e, 0xaeae47e9, 0x08081018, + 0xbaba6fd5, 0x7878f088, 0x25254a6f, 0x2e2e5c72, 0x1c1c3824, 0xa6a657f1, + 0xb4b473c7, 0xc6c69751, 0xe8e8cb23, 0xdddda17c, 0x7474e89c, 0x1f1f3e21, + 0x4b4b96dd, 0xbdbd61dc, 0x8b8b0d86, 0x8a8a0f85, 0x7070e090, 0x3e3e7c42, + 0xb5b571c4, 0x6666ccaa, 0x484890d8, 0x03030605, 0xf6f6f701, 0x0e0e1c12, + 0x6161c2a3, 0x35356a5f, 0x5757aef9, 0xb9b969d0, 0x86861791, 0xc1c19958, + 0x1d1d3a27, 0x9e9e27b9, 0xe1e1d938, 0xf8f8eb13, 0x98982bb3, 0x11112233, + 0x6969d2bb, 0xd9d9a970, 0x8e8e0789, 0x949433a7, 0x9b9b2db6, 0x1e1e3c22, + 0x87871592, 0xe9e9c920, 0xcece8749, 0x5555aaff, 0x28285078, 0xdfdfa57a, + 0x8c8c038f, 0xa1a159f8, 0x89890980, 0x0d0d1a17, 0xbfbf65da, 0xe6e6d731, + 0x424284c6, 0x6868d0b8, 0x414182c3, 0x999929b0, 0x2d2d5a77, 0x0f0f1e11, + 0xb0b07bcb, 0x5454a8fc, 0xbbbb6dd6, 0x16162c3a, }; constexpr uint32_t te2[256] = { - 0x63a5c663, 0x7c84f87c, 0x7799ee77, 0x7b8df67b, 0xf20dfff2, 0x6bbdd66b, - 0x6fb1de6f, 0xc55491c5, 0x30506030, 0x01030201, 0x67a9ce67, 0x2b7d562b, - 0xfe19e7fe, 0xd762b5d7, 0xabe64dab, 0x769aec76, 0xca458fca, 0x829d1f82, - 0xc94089c9, 0x7d87fa7d, 0xfa15effa, 0x59ebb259, 0x47c98e47, 0xf00bfbf0, - 0xadec41ad, 0xd467b3d4, 0xa2fd5fa2, 0xafea45af, 0x9cbf239c, 0xa4f753a4, - 0x7296e472, 0xc05b9bc0, 0xb7c275b7, 0xfd1ce1fd, 0x93ae3d93, 0x266a4c26, - 0x365a6c36, 0x3f417e3f, 0xf702f5f7, 0xcc4f83cc, 0x345c6834, 0xa5f451a5, - 0xe534d1e5, 0xf108f9f1, 0x7193e271, 0xd873abd8, 0x31536231, 0x153f2a15, - 0x040c0804, 0xc75295c7, 0x23654623, 0xc35e9dc3, 0x18283018, 0x96a13796, - 0x050f0a05, 0x9ab52f9a, 0x07090e07, 0x12362412, 0x809b1b80, 0xe23ddfe2, - 0xeb26cdeb, 0x27694e27, 0xb2cd7fb2, 0x759fea75, 0x091b1209, 0x839e1d83, - 0x2c74582c, 0x1a2e341a, 0x1b2d361b, 0x6eb2dc6e, 0x5aeeb45a, 0xa0fb5ba0, - 0x52f6a452, 0x3b4d763b, 0xd661b7d6, 0xb3ce7db3, 0x297b5229, 0xe33edde3, - 0x2f715e2f, 0x84971384, 0x53f5a653, 0xd168b9d1, 0x00000000, 0xed2cc1ed, - 0x20604020, 0xfc1fe3fc, 0xb1c879b1, 0x5bedb65b, 0x6abed46a, 0xcb468dcb, - 0xbed967be, 0x394b7239, 0x4ade944a, 0x4cd4984c, 0x58e8b058, 0xcf4a85cf, - 0xd06bbbd0, 0xef2ac5ef, 0xaae54faa, 0xfb16edfb, 0x43c58643, 0x4dd79a4d, - 0x33556633, 0x85941185, 0x45cf8a45, 0xf910e9f9, 0x02060402, 0x7f81fe7f, - 0x50f0a050, 0x3c44783c, 0x9fba259f, 0xa8e34ba8, 0x51f3a251, 0xa3fe5da3, - 0x40c08040, 0x8f8a058f, 0x92ad3f92, 0x9dbc219d, 0x38487038, 0xf504f1f5, - 0xbcdf63bc, 0xb6c177b6, 0xda75afda, 0x21634221, 0x10302010, 0xff1ae5ff, - 0xf30efdf3, 0xd26dbfd2, 0xcd4c81cd, 0x0c14180c, 0x13352613, 0xec2fc3ec, - 0x5fe1be5f, 0x97a23597, 0x44cc8844, 0x17392e17, 0xc45793c4, 0xa7f255a7, - 0x7e82fc7e, 0x3d477a3d, 0x64acc864, 0x5de7ba5d, 0x192b3219, 0x7395e673, - 0x60a0c060, 0x81981981, 0x4fd19e4f, 0xdc7fa3dc, 0x22664422, 0x2a7e542a, - 0x90ab3b90, 0x88830b88, 0x46ca8c46, 0xee29c7ee, 0xb8d36bb8, 0x143c2814, - 0xde79a7de, 0x5ee2bc5e, 0x0b1d160b, 0xdb76addb, 0xe03bdbe0, 0x32566432, - 0x3a4e743a, 0x0a1e140a, 0x49db9249, 0x060a0c06, 0x246c4824, 0x5ce4b85c, - 0xc25d9fc2, 0xd36ebdd3, 0xacef43ac, 0x62a6c462, 0x91a83991, 0x95a43195, - 0xe437d3e4, 0x798bf279, 0xe732d5e7, 0xc8438bc8, 0x37596e37, 0x6db7da6d, - 0x8d8c018d, 0xd564b1d5, 0x4ed29c4e, 0xa9e049a9, 0x6cb4d86c, 0x56faac56, - 0xf407f3f4, 0xea25cfea, 0x65afca65, 0x7a8ef47a, 0xaee947ae, 0x08181008, - 0xbad56fba, 0x7888f078, 0x256f4a25, 0x2e725c2e, 0x1c24381c, 0xa6f157a6, - 0xb4c773b4, 0xc65197c6, 0xe823cbe8, 0xdd7ca1dd, 0x749ce874, 0x1f213e1f, - 0x4bdd964b, 0xbddc61bd, 0x8b860d8b, 0x8a850f8a, 0x7090e070, 0x3e427c3e, - 0xb5c471b5, 0x66aacc66, 0x48d89048, 0x03050603, 0xf601f7f6, 0x0e121c0e, - 0x61a3c261, 0x355f6a35, 0x57f9ae57, 0xb9d069b9, 0x86911786, 0xc15899c1, - 0x1d273a1d, 0x9eb9279e, 0xe138d9e1, 0xf813ebf8, 0x98b32b98, 0x11332211, - 0x69bbd269, 0xd970a9d9, 0x8e89078e, 0x94a73394, 0x9bb62d9b, 0x1e223c1e, - 0x87921587, 0xe920c9e9, 0xce4987ce, 0x55ffaa55, 0x28785028, 0xdf7aa5df, - 0x8c8f038c, 0xa1f859a1, 0x89800989, 0x0d171a0d, 0xbfda65bf, 0xe631d7e6, - 0x42c68442, 0x68b8d068, 0x41c38241, 0x99b02999, 0x2d775a2d, 0x0f111e0f, - 0xb0cb7bb0, 0x54fca854, 0xbbd66dbb, 0x163a2c16, + 0x63c6a563, 0x7cf8847c, 0x77ee9977, 0x7bf68d7b, 0xf2ff0df2, 0x6bd6bd6b, + 0x6fdeb16f, 0xc59154c5, 0x30605030, 0x01020301, 0x67cea967, 0x2b567d2b, + 0xfee719fe, 0xd7b562d7, 0xab4de6ab, 0x76ec9a76, 0xca8f45ca, 0x821f9d82, + 0xc98940c9, 0x7dfa877d, 0xfaef15fa, 0x59b2eb59, 0x478ec947, 0xf0fb0bf0, + 0xad41ecad, 0xd4b367d4, 0xa25ffda2, 0xaf45eaaf, 0x9c23bf9c, 0xa453f7a4, + 0x72e49672, 0xc09b5bc0, 0xb775c2b7, 0xfde11cfd, 0x933dae93, 0x264c6a26, + 0x366c5a36, 0x3f7e413f, 0xf7f502f7, 0xcc834fcc, 0x34685c34, 0xa551f4a5, + 0xe5d134e5, 0xf1f908f1, 0x71e29371, 0xd8ab73d8, 0x31625331, 0x152a3f15, + 0x04080c04, 0xc79552c7, 0x23466523, 0xc39d5ec3, 0x18302818, 0x9637a196, + 0x050a0f05, 0x9a2fb59a, 0x070e0907, 0x12243612, 0x801b9b80, 0xe2df3de2, + 0xebcd26eb, 0x274e6927, 0xb27fcdb2, 0x75ea9f75, 0x09121b09, 0x831d9e83, + 0x2c58742c, 0x1a342e1a, 0x1b362d1b, 0x6edcb26e, 0x5ab4ee5a, 0xa05bfba0, + 0x52a4f652, 0x3b764d3b, 0xd6b761d6, 0xb37dceb3, 0x29527b29, 0xe3dd3ee3, + 0x2f5e712f, 0x84139784, 0x53a6f553, 0xd1b968d1, 0x00000000, 0xedc12ced, + 0x20406020, 0xfce31ffc, 0xb179c8b1, 0x5bb6ed5b, 0x6ad4be6a, 0xcb8d46cb, + 0xbe67d9be, 0x39724b39, 0x4a94de4a, 0x4c98d44c, 0x58b0e858, 0xcf854acf, + 0xd0bb6bd0, 0xefc52aef, 0xaa4fe5aa, 0xfbed16fb, 0x4386c543, 0x4d9ad74d, + 0x33665533, 0x85119485, 0x458acf45, 0xf9e910f9, 0x02040602, 0x7ffe817f, + 0x50a0f050, 0x3c78443c, 0x9f25ba9f, 0xa84be3a8, 0x51a2f351, 0xa35dfea3, + 0x4080c040, 0x8f058a8f, 0x923fad92, 0x9d21bc9d, 0x38704838, 0xf5f104f5, + 0xbc63dfbc, 0xb677c1b6, 0xdaaf75da, 0x21426321, 0x10203010, 0xffe51aff, + 0xf3fd0ef3, 0xd2bf6dd2, 0xcd814ccd, 0x0c18140c, 0x13263513, 0xecc32fec, + 0x5fbee15f, 0x9735a297, 0x4488cc44, 0x172e3917, 0xc49357c4, 0xa755f2a7, + 0x7efc827e, 0x3d7a473d, 0x64c8ac64, 0x5dbae75d, 0x19322b19, 0x73e69573, + 0x60c0a060, 0x81199881, 0x4f9ed14f, 0xdca37fdc, 0x22446622, 0x2a547e2a, + 0x903bab90, 0x880b8388, 0x468cca46, 0xeec729ee, 0xb86bd3b8, 0x14283c14, + 0xdea779de, 0x5ebce25e, 0x0b161d0b, 0xdbad76db, 0xe0db3be0, 0x32645632, + 0x3a744e3a, 0x0a141e0a, 0x4992db49, 0x060c0a06, 0x24486c24, 0x5cb8e45c, + 0xc29f5dc2, 0xd3bd6ed3, 0xac43efac, 0x62c4a662, 0x9139a891, 0x9531a495, + 0xe4d337e4, 0x79f28b79, 0xe7d532e7, 0xc88b43c8, 0x376e5937, 0x6ddab76d, + 0x8d018c8d, 0xd5b164d5, 0x4e9cd24e, 0xa949e0a9, 0x6cd8b46c, 0x56acfa56, + 0xf4f307f4, 0xeacf25ea, 0x65caaf65, 0x7af48e7a, 0xae47e9ae, 0x08101808, + 0xba6fd5ba, 0x78f08878, 0x254a6f25, 0x2e5c722e, 0x1c38241c, 0xa657f1a6, + 0xb473c7b4, 0xc69751c6, 0xe8cb23e8, 0xdda17cdd, 0x74e89c74, 0x1f3e211f, + 0x4b96dd4b, 0xbd61dcbd, 0x8b0d868b, 0x8a0f858a, 0x70e09070, 0x3e7c423e, + 0xb571c4b5, 0x66ccaa66, 0x4890d848, 0x03060503, 0xf6f701f6, 0x0e1c120e, + 0x61c2a361, 0x356a5f35, 0x57aef957, 0xb969d0b9, 0x86179186, 0xc19958c1, + 0x1d3a271d, 0x9e27b99e, 0xe1d938e1, 0xf8eb13f8, 0x982bb398, 0x11223311, + 0x69d2bb69, 0xd9a970d9, 0x8e07898e, 0x9433a794, 0x9b2db69b, 0x1e3c221e, + 0x87159287, 0xe9c920e9, 0xce8749ce, 0x55aaff55, 0x28507828, 0xdfa57adf, + 0x8c038f8c, 0xa159f8a1, 0x89098089, 0x0d1a170d, 0xbf65dabf, 0xe6d731e6, + 0x4284c642, 0x68d0b868, 0x4182c341, 0x9929b099, 0x2d5a772d, 0x0f1e110f, + 0xb07bcbb0, 0x54a8fc54, 0xbb6dd6bb, 0x162c3a16, }; constexpr uint32_t te3[256] = { - 0x6363a5c6, 0x7c7c84f8, 0x777799ee, 0x7b7b8df6, 0xf2f20dff, 0x6b6bbdd6, - 0x6f6fb1de, 0xc5c55491, 0x30305060, 0x01010302, 0x6767a9ce, 0x2b2b7d56, - 0xfefe19e7, 0xd7d762b5, 0xababe64d, 0x76769aec, 0xcaca458f, 0x82829d1f, - 0xc9c94089, 0x7d7d87fa, 0xfafa15ef, 0x5959ebb2, 0x4747c98e, 0xf0f00bfb, - 0xadadec41, 0xd4d467b3, 0xa2a2fd5f, 0xafafea45, 0x9c9cbf23, 0xa4a4f753, - 0x727296e4, 0xc0c05b9b, 0xb7b7c275, 0xfdfd1ce1, 0x9393ae3d, 0x26266a4c, - 0x36365a6c, 0x3f3f417e, 0xf7f702f5, 0xcccc4f83, 0x34345c68, 0xa5a5f451, - 0xe5e534d1, 0xf1f108f9, 0x717193e2, 0xd8d873ab, 0x31315362, 0x15153f2a, - 0x04040c08, 0xc7c75295, 0x23236546, 0xc3c35e9d, 0x18182830, 0x9696a137, - 0x05050f0a, 0x9a9ab52f, 0x0707090e, 0x12123624, 0x80809b1b, 0xe2e23ddf, - 0xebeb26cd, 0x2727694e, 0xb2b2cd7f, 0x75759fea, 0x09091b12, 0x83839e1d, - 0x2c2c7458, 0x1a1a2e34, 0x1b1b2d36, 0x6e6eb2dc, 0x5a5aeeb4, 0xa0a0fb5b, - 0x5252f6a4, 0x3b3b4d76, 0xd6d661b7, 0xb3b3ce7d, 0x29297b52, 0xe3e33edd, - 0x2f2f715e, 0x84849713, 0x5353f5a6, 0xd1d168b9, 0x00000000, 0xeded2cc1, - 0x20206040, 0xfcfc1fe3, 0xb1b1c879, 0x5b5bedb6, 0x6a6abed4, 0xcbcb468d, - 0xbebed967, 0x39394b72, 0x4a4ade94, 0x4c4cd498, 0x5858e8b0, 0xcfcf4a85, - 0xd0d06bbb, 0xefef2ac5, 0xaaaae54f, 0xfbfb16ed, 0x4343c586, 0x4d4dd79a, - 0x33335566, 0x85859411, 0x4545cf8a, 0xf9f910e9, 0x02020604, 0x7f7f81fe, - 0x5050f0a0, 0x3c3c4478, 0x9f9fba25, 0xa8a8e34b, 0x5151f3a2, 0xa3a3fe5d, - 0x4040c080, 0x8f8f8a05, 0x9292ad3f, 0x9d9dbc21, 0x38384870, 0xf5f504f1, - 0xbcbcdf63, 0xb6b6c177, 0xdada75af, 0x21216342, 0x10103020, 0xffff1ae5, - 0xf3f30efd, 0xd2d26dbf, 0xcdcd4c81, 0x0c0c1418, 0x13133526, 0xecec2fc3, - 0x5f5fe1be, 0x9797a235, 0x4444cc88, 0x1717392e, 0xc4c45793, 0xa7a7f255, - 0x7e7e82fc, 0x3d3d477a, 0x6464acc8, 0x5d5de7ba, 0x19192b32, 0x737395e6, - 0x6060a0c0, 0x81819819, 0x4f4fd19e, 0xdcdc7fa3, 0x22226644, 0x2a2a7e54, - 0x9090ab3b, 0x8888830b, 0x4646ca8c, 0xeeee29c7, 0xb8b8d36b, 0x14143c28, - 0xdede79a7, 0x5e5ee2bc, 0x0b0b1d16, 0xdbdb76ad, 0xe0e03bdb, 0x32325664, - 0x3a3a4e74, 0x0a0a1e14, 0x4949db92, 0x06060a0c, 0x24246c48, 0x5c5ce4b8, - 0xc2c25d9f, 0xd3d36ebd, 0xacacef43, 0x6262a6c4, 0x9191a839, 0x9595a431, - 0xe4e437d3, 0x79798bf2, 0xe7e732d5, 0xc8c8438b, 0x3737596e, 0x6d6db7da, - 0x8d8d8c01, 0xd5d564b1, 0x4e4ed29c, 0xa9a9e049, 0x6c6cb4d8, 0x5656faac, - 0xf4f407f3, 0xeaea25cf, 0x6565afca, 0x7a7a8ef4, 0xaeaee947, 0x08081810, - 0xbabad56f, 0x787888f0, 0x25256f4a, 0x2e2e725c, 0x1c1c2438, 0xa6a6f157, - 0xb4b4c773, 0xc6c65197, 0xe8e823cb, 0xdddd7ca1, 0x74749ce8, 0x1f1f213e, - 0x4b4bdd96, 0xbdbddc61, 0x8b8b860d, 0x8a8a850f, 0x707090e0, 0x3e3e427c, - 0xb5b5c471, 0x6666aacc, 0x4848d890, 0x03030506, 0xf6f601f7, 0x0e0e121c, - 0x6161a3c2, 0x35355f6a, 0x5757f9ae, 0xb9b9d069, 0x86869117, 0xc1c15899, - 0x1d1d273a, 0x9e9eb927, 0xe1e138d9, 0xf8f813eb, 0x9898b32b, 0x11113322, - 0x6969bbd2, 0xd9d970a9, 0x8e8e8907, 0x9494a733, 0x9b9bb62d, 0x1e1e223c, - 0x87879215, 0xe9e920c9, 0xcece4987, 0x5555ffaa, 0x28287850, 0xdfdf7aa5, - 0x8c8c8f03, 0xa1a1f859, 0x89898009, 0x0d0d171a, 0xbfbfda65, 0xe6e631d7, - 0x4242c684, 0x6868b8d0, 0x4141c382, 0x9999b029, 0x2d2d775a, 0x0f0f111e, - 0xb0b0cb7b, 0x5454fca8, 0xbbbbd66d, 0x16163a2c, + 0xc6a56363, 0xf8847c7c, 0xee997777, 0xf68d7b7b, 0xff0df2f2, 0xd6bd6b6b, + 0xdeb16f6f, 0x9154c5c5, 0x60503030, 0x02030101, 0xcea96767, 0x567d2b2b, + 0xe719fefe, 0xb562d7d7, 0x4de6abab, 0xec9a7676, 0x8f45caca, 0x1f9d8282, + 0x8940c9c9, 0xfa877d7d, 0xef15fafa, 0xb2eb5959, 0x8ec94747, 0xfb0bf0f0, + 0x41ecadad, 0xb367d4d4, 0x5ffda2a2, 0x45eaafaf, 0x23bf9c9c, 0x53f7a4a4, + 0xe4967272, 0x9b5bc0c0, 0x75c2b7b7, 0xe11cfdfd, 0x3dae9393, 0x4c6a2626, + 0x6c5a3636, 0x7e413f3f, 0xf502f7f7, 0x834fcccc, 0x685c3434, 0x51f4a5a5, + 0xd134e5e5, 0xf908f1f1, 0xe2937171, 0xab73d8d8, 0x62533131, 0x2a3f1515, + 0x080c0404, 0x9552c7c7, 0x46652323, 0x9d5ec3c3, 0x30281818, 0x37a19696, + 0x0a0f0505, 0x2fb59a9a, 0x0e090707, 0x24361212, 0x1b9b8080, 0xdf3de2e2, + 0xcd26ebeb, 0x4e692727, 0x7fcdb2b2, 0xea9f7575, 0x121b0909, 0x1d9e8383, + 0x58742c2c, 0x342e1a1a, 0x362d1b1b, 0xdcb26e6e, 0xb4ee5a5a, 0x5bfba0a0, + 0xa4f65252, 0x764d3b3b, 0xb761d6d6, 0x7dceb3b3, 0x527b2929, 0xdd3ee3e3, + 0x5e712f2f, 0x13978484, 0xa6f55353, 0xb968d1d1, 0x00000000, 0xc12ceded, + 0x40602020, 0xe31ffcfc, 0x79c8b1b1, 0xb6ed5b5b, 0xd4be6a6a, 0x8d46cbcb, + 0x67d9bebe, 0x724b3939, 0x94de4a4a, 0x98d44c4c, 0xb0e85858, 0x854acfcf, + 0xbb6bd0d0, 0xc52aefef, 0x4fe5aaaa, 0xed16fbfb, 0x86c54343, 0x9ad74d4d, + 0x66553333, 0x11948585, 0x8acf4545, 0xe910f9f9, 0x04060202, 0xfe817f7f, + 0xa0f05050, 0x78443c3c, 0x25ba9f9f, 0x4be3a8a8, 0xa2f35151, 0x5dfea3a3, + 0x80c04040, 0x058a8f8f, 0x3fad9292, 0x21bc9d9d, 0x70483838, 0xf104f5f5, + 0x63dfbcbc, 0x77c1b6b6, 0xaf75dada, 0x42632121, 0x20301010, 0xe51affff, + 0xfd0ef3f3, 0xbf6dd2d2, 0x814ccdcd, 0x18140c0c, 0x26351313, 0xc32fecec, + 0xbee15f5f, 0x35a29797, 0x88cc4444, 0x2e391717, 0x9357c4c4, 0x55f2a7a7, + 0xfc827e7e, 0x7a473d3d, 0xc8ac6464, 0xbae75d5d, 0x322b1919, 0xe6957373, + 0xc0a06060, 0x19988181, 0x9ed14f4f, 0xa37fdcdc, 0x44662222, 0x547e2a2a, + 0x3bab9090, 0x0b838888, 0x8cca4646, 0xc729eeee, 0x6bd3b8b8, 0x283c1414, + 0xa779dede, 0xbce25e5e, 0x161d0b0b, 0xad76dbdb, 0xdb3be0e0, 0x64563232, + 0x744e3a3a, 0x141e0a0a, 0x92db4949, 0x0c0a0606, 0x486c2424, 0xb8e45c5c, + 0x9f5dc2c2, 0xbd6ed3d3, 0x43efacac, 0xc4a66262, 0x39a89191, 0x31a49595, + 0xd337e4e4, 0xf28b7979, 0xd532e7e7, 0x8b43c8c8, 0x6e593737, 0xdab76d6d, + 0x018c8d8d, 0xb164d5d5, 0x9cd24e4e, 0x49e0a9a9, 0xd8b46c6c, 0xacfa5656, + 0xf307f4f4, 0xcf25eaea, 0xcaaf6565, 0xf48e7a7a, 0x47e9aeae, 0x10180808, + 0x6fd5baba, 0xf0887878, 0x4a6f2525, 0x5c722e2e, 0x38241c1c, 0x57f1a6a6, + 0x73c7b4b4, 0x9751c6c6, 0xcb23e8e8, 0xa17cdddd, 0xe89c7474, 0x3e211f1f, + 0x96dd4b4b, 0x61dcbdbd, 0x0d868b8b, 0x0f858a8a, 0xe0907070, 0x7c423e3e, + 0x71c4b5b5, 0xccaa6666, 0x90d84848, 0x06050303, 0xf701f6f6, 0x1c120e0e, + 0xc2a36161, 0x6a5f3535, 0xaef95757, 0x69d0b9b9, 0x17918686, 0x9958c1c1, + 0x3a271d1d, 0x27b99e9e, 0xd938e1e1, 0xeb13f8f8, 0x2bb39898, 0x22331111, + 0xd2bb6969, 0xa970d9d9, 0x07898e8e, 0x33a79494, 0x2db69b9b, 0x3c221e1e, + 0x15928787, 0xc920e9e9, 0x8749cece, 0xaaff5555, 0x50782828, 0xa57adfdf, + 0x038f8c8c, 0x59f8a1a1, 0x09808989, 0x1a170d0d, 0x65dabfbf, 0xd731e6e6, + 0x84c64242, 0xd0b86868, 0x82c34141, 0x29b09999, 0x5a772d2d, 0x1e110f0f, + 0x7bcbb0b0, 0xa8fc5454, 0x6dd6bbbb, 0x2c3a1616, }; // Software implementation of the Vector128 class, using uint32_t @@ -235,45 +238,13 @@ struct alignas(16) Vector128 { inline ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE Vector128 Vector128Load(const void* from) { Vector128 result; - const uint8_t* src = reinterpret_cast<const uint8_t*>(from); - result.s[0] = static_cast<uint32_t>(src[0]) << 24 | - static_cast<uint32_t>(src[1]) << 16 | - static_cast<uint32_t>(src[2]) << 8 | - static_cast<uint32_t>(src[3]); - result.s[1] = static_cast<uint32_t>(src[4]) << 24 | - static_cast<uint32_t>(src[5]) << 16 | - static_cast<uint32_t>(src[6]) << 8 | - static_cast<uint32_t>(src[7]); - result.s[2] = static_cast<uint32_t>(src[8]) << 24 | - static_cast<uint32_t>(src[9]) << 16 | - static_cast<uint32_t>(src[10]) << 8 | - static_cast<uint32_t>(src[11]); - result.s[3] = static_cast<uint32_t>(src[12]) << 24 | - static_cast<uint32_t>(src[13]) << 16 | - static_cast<uint32_t>(src[14]) << 8 | - static_cast<uint32_t>(src[15]); + std::memcpy(result.s, from, sizeof(Vector128)); return result; } inline ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE void Vector128Store( const Vector128& v, void* to) { - uint8_t* dst = reinterpret_cast<uint8_t*>(to); - dst[0] = static_cast<uint8_t>(v.s[0] >> 24); - dst[1] = static_cast<uint8_t>(v.s[0] >> 16); - dst[2] = static_cast<uint8_t>(v.s[0] >> 8); - dst[3] = static_cast<uint8_t>(v.s[0]); - dst[4] = static_cast<uint8_t>(v.s[1] >> 24); - dst[5] = static_cast<uint8_t>(v.s[1] >> 16); - dst[6] = static_cast<uint8_t>(v.s[1] >> 8); - dst[7] = static_cast<uint8_t>(v.s[1]); - dst[8] = static_cast<uint8_t>(v.s[2] >> 24); - dst[9] = static_cast<uint8_t>(v.s[2] >> 16); - dst[10] = static_cast<uint8_t>(v.s[2] >> 8); - dst[11] = static_cast<uint8_t>(v.s[2]); - dst[12] = static_cast<uint8_t>(v.s[3] >> 24); - dst[13] = static_cast<uint8_t>(v.s[3] >> 16); - dst[14] = static_cast<uint8_t>(v.s[3] >> 8); - dst[15] = static_cast<uint8_t>(v.s[3]); + std::memcpy(to, v.s, sizeof(Vector128)); } // One round of AES. "round_key" is a public constant for breaking the @@ -281,39 +252,57 @@ inline ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE void Vector128Store( inline ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE Vector128 AesRound(const Vector128& state, const Vector128& round_key) { Vector128 result; +#ifdef ABSL_IS_LITTLE_ENDIAN result.s[0] = round_key.s[0] ^ // - te0[uint8_t(state.s[0] >> 24)] ^ // - te1[uint8_t(state.s[1] >> 16)] ^ // - te2[uint8_t(state.s[2] >> 8)] ^ // - te3[uint8_t(state.s[3])]; + te0[uint8_t(state.s[0])] ^ // + te1[uint8_t(state.s[1] >> 8)] ^ // + te2[uint8_t(state.s[2] >> 16)] ^ // + te3[uint8_t(state.s[3] >> 24)]; result.s[1] = round_key.s[1] ^ // - te0[uint8_t(state.s[1] >> 24)] ^ // - te1[uint8_t(state.s[2] >> 16)] ^ // - te2[uint8_t(state.s[3] >> 8)] ^ // - te3[uint8_t(state.s[0])]; + te0[uint8_t(state.s[1])] ^ // + te1[uint8_t(state.s[2] >> 8)] ^ // + te2[uint8_t(state.s[3] >> 16)] ^ // + te3[uint8_t(state.s[0] >> 24)]; result.s[2] = round_key.s[2] ^ // - te0[uint8_t(state.s[2] >> 24)] ^ // - te1[uint8_t(state.s[3] >> 16)] ^ // - te2[uint8_t(state.s[0] >> 8)] ^ // - te3[uint8_t(state.s[1])]; + te0[uint8_t(state.s[2])] ^ // + te1[uint8_t(state.s[3] >> 8)] ^ // + te2[uint8_t(state.s[0] >> 16)] ^ // + te3[uint8_t(state.s[1] >> 24)]; result.s[3] = round_key.s[3] ^ // - te0[uint8_t(state.s[3] >> 24)] ^ // - te1[uint8_t(state.s[0] >> 16)] ^ // - te2[uint8_t(state.s[1] >> 8)] ^ // - te3[uint8_t(state.s[2])]; + te0[uint8_t(state.s[3])] ^ // + te1[uint8_t(state.s[0] >> 8)] ^ // + te2[uint8_t(state.s[1] >> 16)] ^ // + te3[uint8_t(state.s[2] >> 24)]; +#else + result.s[0] = round_key.s[0] ^ // + te0[uint8_t(state.s[0])] ^ // + te1[uint8_t(state.s[3] >> 8)] ^ // + te2[uint8_t(state.s[2] >> 16)] ^ // + te3[uint8_t(state.s[1] >> 24)]; + result.s[1] = round_key.s[1] ^ // + te0[uint8_t(state.s[1])] ^ // + te1[uint8_t(state.s[0] >> 8)] ^ // + te2[uint8_t(state.s[3] >> 16)] ^ // + te3[uint8_t(state.s[2] >> 24)]; + result.s[2] = round_key.s[2] ^ // + te0[uint8_t(state.s[2])] ^ // + te1[uint8_t(state.s[1] >> 8)] ^ // + te2[uint8_t(state.s[0] >> 16)] ^ // + te3[uint8_t(state.s[3] >> 24)]; + result.s[3] = round_key.s[3] ^ // + te0[uint8_t(state.s[3])] ^ // + te1[uint8_t(state.s[2] >> 8)] ^ // + te2[uint8_t(state.s[1] >> 16)] ^ // + te3[uint8_t(state.s[0] >> 24)]; +#endif return result; } using ::absl::random_internal::RandenTraits; -// Randen operates on 128-bit vectors. -struct alignas(16) u64x2 { - uint64_t data[2]; -}; - // The improved Feistel block shuffle function for 16 blocks. inline ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE void BlockShuffle( - u64x2* state) { + absl::uint128* state) { static_assert(RandenTraits::kFeistelBlocks == 16, "Feistel block shuffle only works for 16 blocks."); @@ -323,31 +312,31 @@ inline ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE void BlockShuffle( // The fully unrolled loop without the memcpy improves the speed by about // 30% over the equivalent: #if 0 - u64x2 source[RandenTraits::kFeistelBlocks]; + absl::uint128 source[RandenTraits::kFeistelBlocks]; std::memcpy(source, state, sizeof(source)); for (size_t i = 0; i < RandenTraits::kFeistelBlocks; i++) { - const u64x2 v0 = source[shuffle[i]]; + const absl::uint128 v0 = source[shuffle[i]]; state[i] = v0; } return; #endif - const u64x2 v0 = state[shuffle[0]]; - const u64x2 v1 = state[shuffle[1]]; - const u64x2 v2 = state[shuffle[2]]; - const u64x2 v3 = state[shuffle[3]]; - const u64x2 v4 = state[shuffle[4]]; - const u64x2 v5 = state[shuffle[5]]; - const u64x2 v6 = state[shuffle[6]]; - const u64x2 v7 = state[shuffle[7]]; - const u64x2 w0 = state[shuffle[8]]; - const u64x2 w1 = state[shuffle[9]]; - const u64x2 w2 = state[shuffle[10]]; - const u64x2 w3 = state[shuffle[11]]; - const u64x2 w4 = state[shuffle[12]]; - const u64x2 w5 = state[shuffle[13]]; - const u64x2 w6 = state[shuffle[14]]; - const u64x2 w7 = state[shuffle[15]]; + const absl::uint128 v0 = state[shuffle[0]]; + const absl::uint128 v1 = state[shuffle[1]]; + const absl::uint128 v2 = state[shuffle[2]]; + const absl::uint128 v3 = state[shuffle[3]]; + const absl::uint128 v4 = state[shuffle[4]]; + const absl::uint128 v5 = state[shuffle[5]]; + const absl::uint128 v6 = state[shuffle[6]]; + const absl::uint128 v7 = state[shuffle[7]]; + const absl::uint128 w0 = state[shuffle[8]]; + const absl::uint128 w1 = state[shuffle[9]]; + const absl::uint128 w2 = state[shuffle[10]]; + const absl::uint128 w3 = state[shuffle[11]]; + const absl::uint128 w4 = state[shuffle[12]]; + const absl::uint128 w5 = state[shuffle[13]]; + const absl::uint128 w6 = state[shuffle[14]]; + const absl::uint128 w7 = state[shuffle[15]]; state[0] = v0; state[1] = v1; state[2] = v2; @@ -371,9 +360,9 @@ inline ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE void BlockShuffle( // 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 const u64x2* FeistelRound( - u64x2* ABSL_RANDOM_INTERNAL_RESTRICT state, - const u64x2* ABSL_RANDOM_INTERNAL_RESTRICT keys) { +inline ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE const absl::uint128* +FeistelRound(absl::uint128* ABSL_RANDOM_INTERNAL_RESTRICT state, + const absl::uint128* ABSL_RANDOM_INTERNAL_RESTRICT keys) { for (size_t branch = 0; branch < RandenTraits::kFeistelBlocks; branch += 4) { const Vector128 s0 = Vector128Load(state + branch); const Vector128 s1 = Vector128Load(state + branch + 1); @@ -398,13 +387,31 @@ inline ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE const u64x2* FeistelRound( // 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 void Permute( - u64x2* state, const u64x2* ABSL_RANDOM_INTERNAL_RESTRICT keys) { + absl::uint128* state, + const absl::uint128* ABSL_RANDOM_INTERNAL_RESTRICT keys) { for (size_t round = 0; round < RandenTraits::kFeistelRounds; ++round) { keys = FeistelRound(state, keys); BlockShuffle(state); } } +// Enables native loads in the round loop by pre-swapping. +inline ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE void SwapEndian( + absl::uint128* state) { +#ifdef ABSL_IS_BIG_ENDIAN + for (uint32_t block = 0; block < RandenTraits::kFeistelBlocks; ++block) { + uint64_t new_lo = absl::little_endian::ToHost64( + static_cast<uint64_t>(state[block] >> 64)); + uint64_t new_hi = absl::little_endian::ToHost64( + static_cast<uint64_t>((state[block] << 64) >> 64)); + state[block] = (static_cast<absl::uint128>(new_hi) << 64) | new_lo; + } +#else + // Avoid warning about unused variable. + (void)state; +#endif +} + } // namespace namespace absl { @@ -414,7 +421,11 @@ namespace random_internal { const void* RandenSlow::GetKeys() { // Round keys for one AES per Feistel round and branch. // The canonical implementation uses first digits of Pi. +#ifdef ABSL_IS_LITTLE_ENDIAN return kRandenRoundKeys; +#else + return kRandenRoundKeysBE; +#endif } void RandenSlow::Absorb(const void* seed_void, void* state_void) { @@ -437,19 +448,22 @@ void RandenSlow::Absorb(const void* seed_void, void* state_void) { } void RandenSlow::Generate(const void* keys_void, void* state_void) { - static_assert(RandenTraits::kCapacityBytes == sizeof(u64x2), + static_assert(RandenTraits::kCapacityBytes == sizeof(absl::uint128), "Capacity mismatch"); - auto* state = reinterpret_cast<u64x2*>(state_void); - const auto* keys = reinterpret_cast<const u64x2*>(keys_void); + auto* state = reinterpret_cast<absl::uint128*>(state_void); + const auto* keys = reinterpret_cast<const absl::uint128*>(keys_void); - const u64x2 prev_inner = state[0]; + const absl::uint128 prev_inner = state[0]; + + SwapEndian(state); Permute(state, keys); + SwapEndian(state); + // Ensure backtracking resistance. - state[0].data[0] ^= prev_inner.data[0]; - state[0].data[1] ^= prev_inner.data[1]; + *state ^= prev_inner; } } // namespace random_internal diff --git a/absl/random/internal/randen_slow_test.cc b/absl/random/internal/randen_slow_test.cc index 4861ffa4..ed603958 100644 --- a/absl/random/internal/randen_slow_test.cc +++ b/absl/random/internal/randen_slow_test.cc @@ -25,40 +25,37 @@ namespace { using absl::random_internal::RandenSlow; using absl::random_internal::RandenTraits; -// Local state parameters. -constexpr size_t kSeedBytes = - RandenTraits::kStateBytes - RandenTraits::kCapacityBytes; -constexpr size_t kStateSizeT = RandenTraits::kStateBytes / sizeof(uint64_t); -constexpr size_t kSeedSizeT = kSeedBytes / sizeof(uint32_t); - -struct alignas(16) randen { - uint64_t state[kStateSizeT]; - uint32_t seed[kSeedSizeT]; -}; - TEST(RandenSlowTest, Default) { - constexpr uint64_t kGolden[] = { - 0x6c6534090ee6d3ee, 0x044e2b9b9d5333c6, 0xc3c14f134e433977, - 0xdda9f47cd90410ee, 0x887bf3087fd8ca10, 0xf0b780f545c72912, - 0x15dbb1d37696599f, 0x30ec63baff3c6d59, 0xb29f73606f7f20a6, - 0x02808a316f49a54c, 0x3b8feaf9d5c8e50e, 0x9cbf605e3fd9de8a, - 0xc970ae1a78183bbb, 0xd8b2ffd356301ed5, 0xf4b327fe0fc73c37, - 0xcdfd8d76eb8f9a19, 0xc3a506eb91420c9d, 0xd5af05dd3eff9556, - 0x48db1bb78f83c4a1, 0x7023920e0d6bfe8c, 0x58d3575834956d42, - 0xed1ef4c26b87b840, 0x8eef32a23e0b2df3, 0x497cabf3431154fc, - 0x4e24370570029a8b, 0xd88b5749f090e5ea, 0xc651a582a970692f, - 0x78fcec2cbb6342f5, 0x463cb745612f55db, 0x352ee4ad1816afe3, - 0x026ff374c101da7e, 0x811ef0821c3de851, + constexpr uint8_t kGolden[] = { + 0xee, 0xd3, 0xe6, 0x0e, 0x09, 0x34, 0x65, 0x6c, 0xc6, 0x33, 0x53, 0x9d, + 0x9b, 0x2b, 0x4e, 0x04, 0x77, 0x39, 0x43, 0x4e, 0x13, 0x4f, 0xc1, 0xc3, + 0xee, 0x10, 0x04, 0xd9, 0x7c, 0xf4, 0xa9, 0xdd, 0x10, 0xca, 0xd8, 0x7f, + 0x08, 0xf3, 0x7b, 0x88, 0x12, 0x29, 0xc7, 0x45, 0xf5, 0x80, 0xb7, 0xf0, + 0x9f, 0x59, 0x96, 0x76, 0xd3, 0xb1, 0xdb, 0x15, 0x59, 0x6d, 0x3c, 0xff, + 0xba, 0x63, 0xec, 0x30, 0xa6, 0x20, 0x7f, 0x6f, 0x60, 0x73, 0x9f, 0xb2, + 0x4c, 0xa5, 0x49, 0x6f, 0x31, 0x8a, 0x80, 0x02, 0x0e, 0xe5, 0xc8, 0xd5, + 0xf9, 0xea, 0x8f, 0x3b, 0x8a, 0xde, 0xd9, 0x3f, 0x5e, 0x60, 0xbf, 0x9c, + 0xbb, 0x3b, 0x18, 0x78, 0x1a, 0xae, 0x70, 0xc9, 0xd5, 0x1e, 0x30, 0x56, + 0xd3, 0xff, 0xb2, 0xd8, 0x37, 0x3c, 0xc7, 0x0f, 0xfe, 0x27, 0xb3, 0xf4, + 0x19, 0x9a, 0x8f, 0xeb, 0x76, 0x8d, 0xfd, 0xcd, 0x9d, 0x0c, 0x42, 0x91, + 0xeb, 0x06, 0xa5, 0xc3, 0x56, 0x95, 0xff, 0x3e, 0xdd, 0x05, 0xaf, 0xd5, + 0xa1, 0xc4, 0x83, 0x8f, 0xb7, 0x1b, 0xdb, 0x48, 0x8c, 0xfe, 0x6b, 0x0d, + 0x0e, 0x92, 0x23, 0x70, 0x42, 0x6d, 0x95, 0x34, 0x58, 0x57, 0xd3, 0x58, + 0x40, 0xb8, 0x87, 0x6b, 0xc2, 0xf4, 0x1e, 0xed, 0xf3, 0x2d, 0x0b, 0x3e, + 0xa2, 0x32, 0xef, 0x8e, 0xfc, 0x54, 0x11, 0x43, 0xf3, 0xab, 0x7c, 0x49, + 0x8b, 0x9a, 0x02, 0x70, 0x05, 0x37, 0x24, 0x4e, 0xea, 0xe5, 0x90, 0xf0, + 0x49, 0x57, 0x8b, 0xd8, 0x2f, 0x69, 0x70, 0xa9, 0x82, 0xa5, 0x51, 0xc6, + 0xf5, 0x42, 0x63, 0xbb, 0x2c, 0xec, 0xfc, 0x78, 0xdb, 0x55, 0x2f, 0x61, + 0x45, 0xb7, 0x3c, 0x46, 0xe3, 0xaf, 0x16, 0x18, 0xad, 0xe4, 0x2e, 0x35, + 0x7e, 0xda, 0x01, 0xc1, 0x74, 0xf3, 0x6f, 0x02, 0x51, 0xe8, 0x3d, 0x1c, + 0x82, 0xf0, 0x1e, 0x81, }; - alignas(16) randen d; - std::memset(d.state, 0, sizeof(d.state)); - RandenSlow::Generate(RandenSlow::GetKeys(), d.state); + alignas(16) uint8_t state[RandenTraits::kStateBytes]; + std::memset(state, 0, sizeof(state)); - uint64_t* id = d.state; - for (const auto& elem : kGolden) { - EXPECT_EQ(absl::little_endian::FromHost64(elem), *id++); - } + RandenSlow::Generate(RandenSlow::GetKeys(), state); + EXPECT_EQ(0, std::memcmp(state, kGolden, sizeof(state))); } } // namespace diff --git a/absl/random/internal/randen_test.cc b/absl/random/internal/randen_test.cc index c186fe0d..92773b8d 100644 --- a/absl/random/internal/randen_test.cc +++ b/absl/random/internal/randen_test.cc @@ -23,9 +23,6 @@ namespace { using absl::random_internal::Randen; -// Local state parameters. -constexpr size_t kStateSizeT = Randen::kStateBytes / sizeof(uint64_t); - TEST(RandenTest, CopyAndMove) { static_assert(std::is_copy_constructible<Randen>::value, "Randen must be copy constructible"); @@ -41,30 +38,38 @@ TEST(RandenTest, CopyAndMove) { } TEST(RandenTest, Default) { - constexpr uint64_t kGolden[] = { - 0x6c6534090ee6d3ee, 0x044e2b9b9d5333c6, 0xc3c14f134e433977, - 0xdda9f47cd90410ee, 0x887bf3087fd8ca10, 0xf0b780f545c72912, - 0x15dbb1d37696599f, 0x30ec63baff3c6d59, 0xb29f73606f7f20a6, - 0x02808a316f49a54c, 0x3b8feaf9d5c8e50e, 0x9cbf605e3fd9de8a, - 0xc970ae1a78183bbb, 0xd8b2ffd356301ed5, 0xf4b327fe0fc73c37, - 0xcdfd8d76eb8f9a19, 0xc3a506eb91420c9d, 0xd5af05dd3eff9556, - 0x48db1bb78f83c4a1, 0x7023920e0d6bfe8c, 0x58d3575834956d42, - 0xed1ef4c26b87b840, 0x8eef32a23e0b2df3, 0x497cabf3431154fc, - 0x4e24370570029a8b, 0xd88b5749f090e5ea, 0xc651a582a970692f, - 0x78fcec2cbb6342f5, 0x463cb745612f55db, 0x352ee4ad1816afe3, - 0x026ff374c101da7e, 0x811ef0821c3de851, + constexpr uint8_t kGolden[] = { + 0xee, 0xd3, 0xe6, 0x0e, 0x09, 0x34, 0x65, 0x6c, 0xc6, 0x33, 0x53, 0x9d, + 0x9b, 0x2b, 0x4e, 0x04, 0x77, 0x39, 0x43, 0x4e, 0x13, 0x4f, 0xc1, 0xc3, + 0xee, 0x10, 0x04, 0xd9, 0x7c, 0xf4, 0xa9, 0xdd, 0x10, 0xca, 0xd8, 0x7f, + 0x08, 0xf3, 0x7b, 0x88, 0x12, 0x29, 0xc7, 0x45, 0xf5, 0x80, 0xb7, 0xf0, + 0x9f, 0x59, 0x96, 0x76, 0xd3, 0xb1, 0xdb, 0x15, 0x59, 0x6d, 0x3c, 0xff, + 0xba, 0x63, 0xec, 0x30, 0xa6, 0x20, 0x7f, 0x6f, 0x60, 0x73, 0x9f, 0xb2, + 0x4c, 0xa5, 0x49, 0x6f, 0x31, 0x8a, 0x80, 0x02, 0x0e, 0xe5, 0xc8, 0xd5, + 0xf9, 0xea, 0x8f, 0x3b, 0x8a, 0xde, 0xd9, 0x3f, 0x5e, 0x60, 0xbf, 0x9c, + 0xbb, 0x3b, 0x18, 0x78, 0x1a, 0xae, 0x70, 0xc9, 0xd5, 0x1e, 0x30, 0x56, + 0xd3, 0xff, 0xb2, 0xd8, 0x37, 0x3c, 0xc7, 0x0f, 0xfe, 0x27, 0xb3, 0xf4, + 0x19, 0x9a, 0x8f, 0xeb, 0x76, 0x8d, 0xfd, 0xcd, 0x9d, 0x0c, 0x42, 0x91, + 0xeb, 0x06, 0xa5, 0xc3, 0x56, 0x95, 0xff, 0x3e, 0xdd, 0x05, 0xaf, 0xd5, + 0xa1, 0xc4, 0x83, 0x8f, 0xb7, 0x1b, 0xdb, 0x48, 0x8c, 0xfe, 0x6b, 0x0d, + 0x0e, 0x92, 0x23, 0x70, 0x42, 0x6d, 0x95, 0x34, 0x58, 0x57, 0xd3, 0x58, + 0x40, 0xb8, 0x87, 0x6b, 0xc2, 0xf4, 0x1e, 0xed, 0xf3, 0x2d, 0x0b, 0x3e, + 0xa2, 0x32, 0xef, 0x8e, 0xfc, 0x54, 0x11, 0x43, 0xf3, 0xab, 0x7c, 0x49, + 0x8b, 0x9a, 0x02, 0x70, 0x05, 0x37, 0x24, 0x4e, 0xea, 0xe5, 0x90, 0xf0, + 0x49, 0x57, 0x8b, 0xd8, 0x2f, 0x69, 0x70, 0xa9, 0x82, 0xa5, 0x51, 0xc6, + 0xf5, 0x42, 0x63, 0xbb, 0x2c, 0xec, 0xfc, 0x78, 0xdb, 0x55, 0x2f, 0x61, + 0x45, 0xb7, 0x3c, 0x46, 0xe3, 0xaf, 0x16, 0x18, 0xad, 0xe4, 0x2e, 0x35, + 0x7e, 0xda, 0x01, 0xc1, 0x74, 0xf3, 0x6f, 0x02, 0x51, 0xe8, 0x3d, 0x1c, + 0x82, 0xf0, 0x1e, 0x81, }; - alignas(16) uint64_t state[kStateSizeT]; + alignas(16) uint8_t state[Randen::kStateBytes]; std::memset(state, 0, sizeof(state)); Randen r; r.Generate(state); - auto id = std::begin(state); - for (const auto& elem : kGolden) { - EXPECT_EQ(elem, *id++); - } + EXPECT_EQ(0, std::memcmp(state, kGolden, sizeof(state))); } } // namespace diff --git a/absl/random/internal/salted_seed_seq.h b/absl/random/internal/salted_seed_seq.h index 5953a090..06291865 100644 --- a/absl/random/internal/salted_seed_seq.h +++ b/absl/random/internal/salted_seed_seq.h @@ -22,6 +22,7 @@ #include <memory> #include <type_traits> #include <utility> +#include <vector> #include "absl/container/inlined_vector.h" #include "absl/meta/type_traits.h" @@ -65,15 +66,19 @@ class SaltedSeedSeq { template <typename RandomAccessIterator> void generate(RandomAccessIterator begin, RandomAccessIterator end) { + using U = typename std::iterator_traits<RandomAccessIterator>::value_type; + // The common case is that generate is called with ContiguousIterators // to uint arrays. Such contiguous memory regions may be optimized, // which we detect here. - using tag = absl::conditional_t< - (std::is_pointer<RandomAccessIterator>::value && - std::is_same<absl::decay_t<decltype(*begin)>, uint32_t>::value), + using TagType = absl::conditional_t< + (std::is_same<U, uint32_t>::value && + (std::is_pointer<RandomAccessIterator>::value || + std::is_same<RandomAccessIterator, + typename std::vector<U>::iterator>::value)), ContiguousAndUint32Tag, DefaultTag>; if (begin != end) { - generate_impl(begin, end, tag{}); + generate_impl(TagType{}, begin, end, std::distance(begin, end)); } } @@ -89,8 +94,15 @@ class SaltedSeedSeq { struct DefaultTag {}; // Generate which requires the iterators are contiguous pointers to uint32_t. - void generate_impl(uint32_t* begin, uint32_t* end, ContiguousAndUint32Tag) { - generate_contiguous(absl::MakeSpan(begin, end)); + // Fills the initial seed buffer the underlying SSeq::generate() call, + // then mixes in the salt material. + template <typename Contiguous> + void generate_impl(ContiguousAndUint32Tag, Contiguous begin, Contiguous end, + size_t n) { + seq_->generate(begin, end); + const uint32_t salt = absl::random_internal::GetSaltMaterial().value_or(0); + auto span = absl::Span<uint32_t>(&*begin, n); + MixIntoSeedMaterial(absl::MakeConstSpan(&salt, 1), span); } // The uncommon case for generate is that it is called with iterators over @@ -98,27 +110,13 @@ class SaltedSeedSeq { // case we allocate a temporary 32-bit buffer and then copy-assign back // to the initial inputs. template <typename RandomAccessIterator> - void generate_impl(RandomAccessIterator begin, RandomAccessIterator end, - DefaultTag) { - return generate_and_copy(std::distance(begin, end), begin); - } - - // Fills the initial seed buffer the underlying SSeq::generate() call, - // mixing in the salt material. - void generate_contiguous(absl::Span<uint32_t> buffer) { - seq_->generate(buffer.begin(), buffer.end()); - const uint32_t salt = absl::random_internal::GetSaltMaterial().value_or(0); - MixIntoSeedMaterial(absl::MakeConstSpan(&salt, 1), buffer); - } - - // Allocates a seed buffer of `n` elements, generates the seed, then - // copies the result into the `out` iterator. - template <typename Iterator> - void generate_and_copy(size_t n, Iterator out) { - // Allocate a temporary buffer, generate, and then copy. + void generate_impl(DefaultTag, RandomAccessIterator begin, + RandomAccessIterator, size_t n) { + // Allocates a seed buffer of `n` elements, generates the seed, then + // copies the result into the `out` iterator. absl::InlinedVector<uint32_t, 8> data(n, 0); - generate_contiguous(absl::MakeSpan(data.data(), data.size())); - std::copy(data.begin(), data.end(), out); + generate_impl(ContiguousAndUint32Tag{}, data.begin(), data.end(), n); + std::copy(data.begin(), data.end(), begin); } // Because [rand.req.seedseq] is not required to be copy-constructible, diff --git a/absl/random/internal/seed_material.cc b/absl/random/internal/seed_material.cc index 4d38a574..c03cad85 100644 --- a/absl/random/internal/seed_material.cc +++ b/absl/random/internal/seed_material.cc @@ -28,6 +28,7 @@ #include <cstdlib> #include <cstring> +#include "absl/base/dynamic_annotations.h" #include "absl/base/internal/raw_logging.h" #include "absl/strings/ascii.h" #include "absl/strings/escaping.h" @@ -50,6 +51,18 @@ #endif +#if defined(__GLIBC__) && \ + (__GLIBC__ > 2 || (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 25)) +// glibc >= 2.25 has getentropy() +#define ABSL_RANDOM_USE_GET_ENTROPY 1 +#endif + +#if defined(__EMSCRIPTEN__) +#include <sys/random.h> +// Emscripten has getentropy, but it resides in a different header. +#define ABSL_RANDOM_USE_GET_ENTROPY 1 +#endif + #if defined(ABSL_RANDOM_USE_BCRYPT) #include <bcrypt.h> @@ -122,8 +135,32 @@ bool ReadSeedMaterialFromOSEntropyImpl(absl::Span<uint32_t> values) { #else +#if defined(ABSL_RANDOM_USE_GET_ENTROPY) +// On *nix, use getentropy() if supported. Note that libc may support +// getentropy(), but the kernel may not, in which case this function will return +// false. +bool ReadSeedMaterialFromGetEntropy(absl::Span<uint32_t> values) { + auto buffer = reinterpret_cast<uint8_t*>(values.data()); + size_t buffer_size = sizeof(uint32_t) * values.size(); + while (buffer_size > 0) { + // getentropy() has a maximum permitted length of 256. + size_t to_read = std::min<size_t>(buffer_size, 256); + int result = getentropy(buffer, to_read); + if (result < 0) { + return false; + } + // https://github.com/google/sanitizers/issues/1173 + // MemorySanitizer can't see through getentropy(). + ABSL_ANNOTATE_MEMORY_IS_INITIALIZED(buffer, to_read); + buffer += to_read; + buffer_size -= to_read; + } + return true; +} +#endif // defined(ABSL_RANDOM_GETENTROPY) + // On *nix, read entropy from /dev/urandom. -bool ReadSeedMaterialFromOSEntropyImpl(absl::Span<uint32_t> values) { +bool ReadSeedMaterialFromDevURandom(absl::Span<uint32_t> values) { const char kEntropyFile[] = "/dev/urandom"; auto buffer = reinterpret_cast<uint8_t*>(values.data()); @@ -150,6 +187,17 @@ bool ReadSeedMaterialFromOSEntropyImpl(absl::Span<uint32_t> values) { return success; } +bool ReadSeedMaterialFromOSEntropyImpl(absl::Span<uint32_t> values) { +#if defined(ABSL_RANDOM_USE_GET_ENTROPY) + if (ReadSeedMaterialFromGetEntropy(values)) { + return true; + } +#endif + // Libc may support getentropy, but the kernel may not, so we still have + // to fallback to ReadSeedMaterialFromDevURandom(). + return ReadSeedMaterialFromDevURandom(values); +} + #endif } // namespace diff --git a/absl/random/internal/traits.h b/absl/random/internal/traits.h index 75772bd9..f874a0f7 100644 --- a/absl/random/internal/traits.h +++ b/absl/random/internal/traits.h @@ -20,6 +20,8 @@ #include <type_traits> #include "absl/base/config.h" +#include "absl/numeric/bits.h" +#include "absl/numeric/int128.h" namespace absl { ABSL_NAMESPACE_BEGIN @@ -59,6 +61,31 @@ class is_widening_convertible { rank<A>() <= rank<B>(); }; +template <typename T> +struct IsIntegral : std::is_integral<T> {}; +template <> +struct IsIntegral<absl::int128> : std::true_type {}; +template <> +struct IsIntegral<absl::uint128> : std::true_type {}; + +template <typename T> +struct MakeUnsigned : std::make_unsigned<T> {}; +template <> +struct MakeUnsigned<absl::int128> { + using type = absl::uint128; +}; +template <> +struct MakeUnsigned<absl::uint128> { + using type = absl::uint128; +}; + +template <typename T> +struct IsUnsigned : std::is_unsigned<T> {}; +template <> +struct IsUnsigned<absl::int128> : std::false_type {}; +template <> +struct IsUnsigned<absl::uint128> : std::true_type {}; + // unsigned_bits<N>::type returns the unsigned int type with the indicated // number of bits. template <size_t N> @@ -81,19 +108,40 @@ struct unsigned_bits<64> { using type = uint64_t; }; -#ifdef ABSL_HAVE_INTRINSIC_INT128 template <> struct unsigned_bits<128> { - using type = __uint128_t; + using type = absl::uint128; +}; + +// 256-bit wrapper for wide multiplications. +struct U256 { + uint128 hi; + uint128 lo; +}; +template <> +struct unsigned_bits<256> { + using type = U256; }; -#endif template <typename IntType> struct make_unsigned_bits { - using type = typename unsigned_bits<std::numeric_limits< - typename std::make_unsigned<IntType>::type>::digits>::type; + using type = typename unsigned_bits< + std::numeric_limits<typename MakeUnsigned<IntType>::type>::digits>::type; }; +template <typename T> +int BitWidth(T v) { + // Workaround for bit_width not supporting int128. + // Don't hardcode `64` to make sure this code does not trigger compiler + // warnings in smaller types. + constexpr int half_bits = sizeof(T) * 8 / 2; + if (sizeof(T) == 16 && (v >> half_bits) != 0) { + return bit_width(static_cast<uint64_t>(v >> half_bits)) + half_bits; + } else { + return bit_width(static_cast<uint64_t>(v)); + } +} + } // namespace random_internal ABSL_NAMESPACE_END } // namespace absl diff --git a/absl/random/internal/uniform_helper.h b/absl/random/internal/uniform_helper.h index 1243bc1c..e68b82ee 100644 --- a/absl/random/internal/uniform_helper.h +++ b/absl/random/internal/uniform_helper.h @@ -100,7 +100,7 @@ using uniform_inferred_return_t = template <typename IntType, typename Tag> typename absl::enable_if_t< absl::conjunction< - std::is_integral<IntType>, + IsIntegral<IntType>, absl::disjunction<std::is_same<Tag, IntervalOpenClosedTag>, std::is_same<Tag, IntervalOpenOpenTag>>>::value, IntType> @@ -131,7 +131,7 @@ uniform_lower_bound(Tag, NumType a, NumType) { template <typename IntType, typename Tag> typename absl::enable_if_t< absl::conjunction< - std::is_integral<IntType>, + IsIntegral<IntType>, absl::disjunction<std::is_same<Tag, IntervalClosedOpenTag>, std::is_same<Tag, IntervalOpenOpenTag>>>::value, IntType> @@ -153,7 +153,7 @@ uniform_upper_bound(Tag, FloatType, FloatType b) { template <typename IntType, typename Tag> typename absl::enable_if_t< absl::conjunction< - std::is_integral<IntType>, + IsIntegral<IntType>, absl::disjunction<std::is_same<Tag, IntervalClosedClosedTag>, std::is_same<Tag, IntervalOpenClosedTag>>>::value, IntType> @@ -201,7 +201,7 @@ is_uniform_range_valid(FloatType a, FloatType b) { } template <typename IntType> -absl::enable_if_t<std::is_integral<IntType>::value, bool> +absl::enable_if_t<IsIntegral<IntType>::value, bool> is_uniform_range_valid(IntType a, IntType b) { return a <= b; } @@ -210,7 +210,7 @@ is_uniform_range_valid(IntType a, IntType b) { // or absl::uniform_real_distribution depending on the NumType parameter. template <typename NumType> using UniformDistribution = - typename std::conditional<std::is_integral<NumType>::value, + typename std::conditional<IsIntegral<NumType>::value, absl::uniform_int_distribution<NumType>, absl::uniform_real_distribution<NumType>>::type; diff --git a/absl/random/internal/wide_multiply.h b/absl/random/internal/wide_multiply.h index b6e6c4b6..891e3630 100644 --- a/absl/random/internal/wide_multiply.h +++ b/absl/random/internal/wide_multiply.h @@ -34,43 +34,6 @@ 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 absl::uint128 MultiplyU64ToU128(uint64_t a, uint64_t b) { -#if defined(ABSL_HAVE_INTRINSIC_INT128) - return absl::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 { @@ -82,27 +45,49 @@ struct wide_multiply { 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 input_type hi(result_type r) { + return static_cast<input_type>(r >> kN); + } + static input_type lo(result_type r) { return static_cast<input_type>(r); } static_assert(std::is_unsigned<UIntType>::value, "Class-template wide_multiply<> argument must be unsigned."); }; -#ifndef ABSL_HAVE_INTRINSIC_INT128 +// MultiplyU128ToU256 multiplies two 128-bit values to a 256-bit value. +inline U256 MultiplyU128ToU256(uint128 a, uint128 b) { + const uint128 a00 = static_cast<uint64_t>(a); + const uint128 a64 = a >> 64; + const uint128 b00 = static_cast<uint64_t>(b); + const uint128 b64 = b >> 64; + + const uint128 c00 = a00 * b00; + const uint128 c64a = a00 * b64; + const uint128 c64b = a64 * b00; + const uint128 c128 = a64 * b64; + + const uint64_t carry = + static_cast<uint64_t>(((c00 >> 64) + static_cast<uint64_t>(c64a) + + static_cast<uint64_t>(c64b)) >> + 64); + + return {c128 + (c64a >> 64) + (c64b >> 64) + carry, + c00 + (c64a << 64) + (c64b << 64)}; +} + + template <> -struct wide_multiply<uint64_t> { - using input_type = uint64_t; - using result_type = absl::uint128; +struct wide_multiply<uint128> { + using input_type = uint128; + using result_type = U256; - static result_type multiply(uint64_t a, uint64_t b) { - return MultiplyU64ToU128(a, b); + static result_type multiply(input_type a, input_type b) { + return MultiplyU128ToU256(a, b); } - static uint64_t hi(result_type r) { return absl::Uint128High64(r); } - static uint64_t lo(result_type r) { return absl::Uint128Low64(r); } + static input_type hi(result_type r) { return r.hi; } + static input_type lo(result_type r) { return r.lo; } }; -#endif } // namespace random_internal ABSL_NAMESPACE_END diff --git a/absl/random/internal/wide_multiply_test.cc b/absl/random/internal/wide_multiply_test.cc index e276cb51..f8ee35c0 100644 --- a/absl/random/internal/wide_multiply_test.cc +++ b/absl/random/internal/wide_multiply_test.cc @@ -14,52 +14,106 @@ #include "absl/random/internal/wide_multiply.h" +#include "gmock/gmock.h" #include "gtest/gtest.h" #include "absl/numeric/int128.h" -using absl::random_internal::MultiplyU64ToU128; +using absl::random_internal::MultiplyU128ToU256; +using absl::random_internal::U256; namespace { -TEST(WideMultiplyTest, MultiplyU64ToU128Test) { - constexpr uint64_t k1 = 1; - constexpr uint64_t kMax = ~static_cast<uint64_t>(0); +U256 LeftShift(U256 v, int s) { + if (s == 0) { + return v; + } else if (s < 128) { + return {(v.hi << s) | (v.lo >> (128 - s)), v.lo << s}; + } else { + return {v.lo << (s - 128), 0}; + } +} + +MATCHER_P2(Eq256, hi, lo, "") { return arg.hi == hi && arg.lo == lo; } +MATCHER_P(Eq256, v, "") { return arg.hi == v.hi && arg.lo == v.lo; } + +TEST(WideMultiplyTest, MultiplyU128ToU256Test) { + using absl::uint128; + constexpr uint128 k1 = 1; + constexpr uint128 kMax = ~static_cast<uint128>(0); - EXPECT_EQ(absl::uint128(0), MultiplyU64ToU128(0, 0)); + EXPECT_THAT(MultiplyU128ToU256(0, 0), Eq256(0, 0)); - // Max uint64_t - 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)); + // Max uin128_t + EXPECT_THAT(MultiplyU128ToU256(kMax, kMax), Eq256(kMax << 1, 1)); + EXPECT_THAT(MultiplyU128ToU256(kMax, 1), Eq256(0, kMax)); + EXPECT_THAT(MultiplyU128ToU256(1, kMax), Eq256(0, 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)); + SCOPED_TRACE(i); + EXPECT_THAT(MultiplyU128ToU256(kMax, k1 << i), + Eq256(LeftShift({0, kMax}, i))); + EXPECT_THAT(MultiplyU128ToU256(k1 << i, kMax), + Eq256(LeftShift({0, kMax}, i))); } // 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)); + EXPECT_THAT(MultiplyU128ToU256(k1 << i, k1 << j), + Eq256(LeftShift({0, 1}, i + 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)); + EXPECT_THAT(MultiplyU128ToU256( + absl::MakeUint128(0xc502da0d6ea99fe8, 0xfa3c9141a1f50912), + absl::MakeUint128(0x96bcf1ac37f97bd6, 0x27e2cdeb5fb2299e)), + Eq256(absl::MakeUint128(0x740113d838f96a64, 0x22e8cfa4d71f89ea), + absl::MakeUint128(0x19184a345c62e993, 0x237871b630337b1c))); + EXPECT_THAT(MultiplyU128ToU256( + absl::MakeUint128(0x6f29e670cee07230, 0xc3d8e6c3e4d86759), + absl::MakeUint128(0x3227d29fa6386db1, 0x231682bb1e4b764f)), + Eq256(absl::MakeUint128(0x15c779d9d5d3b07c, 0xd7e6c827f0c81cbe), + absl::MakeUint128(0xf88e3914f7fa287a, 0x15b79975137dea77))); + EXPECT_THAT(MultiplyU128ToU256( + absl::MakeUint128(0xafb77107215646e1, 0x3b844cb1ac5769e7), + absl::MakeUint128(0x1ff7b2d888b62479, 0x92f758ae96fcba0b)), + Eq256(absl::MakeUint128(0x15f13b70181f6985, 0x2adb36bbabce7d02), + absl::MakeUint128(0x6c470d72e13aad04, 0x63fba3f5841762ed))); + EXPECT_THAT(MultiplyU128ToU256( + absl::MakeUint128(0xd85d5558d67ac905, 0xf88c70654dae19b1), + absl::MakeUint128(0x17252c6727db3738, 0x399ff658c511eedc)), + Eq256(absl::MakeUint128(0x138fcdaf8b0421ee, 0x1b465ddf2a0d03f6), + absl::MakeUint128(0x8f573ba68296860f, 0xf327d2738741a21c))); + EXPECT_THAT(MultiplyU128ToU256( + absl::MakeUint128(0x46f0421a37ff6bee, 0xa61df89f09d140b1), + absl::MakeUint128(0x3d712ec9f37ca2e1, 0x9658a2cba47ef4b1)), + Eq256(absl::MakeUint128(0x11069cc48ee7c95d, 0xd35fb1c7aa91c978), + absl::MakeUint128(0xbe2f4a6de874b015, 0xd2f7ac1b76746e61))); + EXPECT_THAT(MultiplyU128ToU256( + absl::MakeUint128(0x730d27c72d58fa49, 0x3ebeda7498f8827c), + absl::MakeUint128(0xa2c959eca9f503af, 0x189c687eb842bbd8)), + Eq256(absl::MakeUint128(0x4928d0ea356ba022, 0x1546d34a2963393), + absl::MakeUint128(0x7481531e1e0a16d1, 0xdd8025015cf6aca0))); + EXPECT_THAT(MultiplyU128ToU256( + absl::MakeUint128(0x6ca41020f856d2f1, 0xb9b0838c04a7f4aa), + absl::MakeUint128(0x9cf41d28a8396f54, 0x1d681695e377ffe6)), + Eq256(absl::MakeUint128(0x429b92934d9be6f1, 0xea182877157c1e7), + absl::MakeUint128(0x7135c23f0a4a475, 0xc1adc366f4a126bc))); + EXPECT_THAT(MultiplyU128ToU256( + absl::MakeUint128(0x57472833797c332, 0x6c79272fdec4687a), + absl::MakeUint128(0xb5f022ea3838e46b, 0x16face2f003e27a6)), + Eq256(absl::MakeUint128(0x3e072e0962b3400, 0x5d9fe8fdc3d0e1f4), + absl::MakeUint128(0x7dc0df47cedafd62, 0xbe6501f1acd2551c))); + EXPECT_THAT(MultiplyU128ToU256( + absl::MakeUint128(0xf0fb4198322eb1c2, 0xfe7f5f31f3885938), + absl::MakeUint128(0xd99012b71bb7aa31, 0xac7a6f9eb190789)), + Eq256(absl::MakeUint128(0xcccc998cf075ca01, 0x642d144322fb873a), + absl::MakeUint128(0xc79dc12b69d91ed4, 0xa83459132ce046f8))); + EXPECT_THAT(MultiplyU128ToU256( + absl::MakeUint128(0xb5c04120848cdb47, 0x8aa62a827bf52635), + absl::MakeUint128(0x8d07a359be2f1380, 0x467bb90d59da0dea)), + Eq256(absl::MakeUint128(0x64205019d139a9ce, 0x99425c5fb6e7a977), + absl::MakeUint128(0xd3e99628a9e5fca7, 0x9c7824cb7279d72))); } } // namespace diff --git a/absl/random/log_uniform_int_distribution.h b/absl/random/log_uniform_int_distribution.h index 43e10116..4afff8f6 100644 --- a/absl/random/log_uniform_int_distribution.h +++ b/absl/random/log_uniform_int_distribution.h @@ -69,10 +69,8 @@ class log_uniform_int_distribution { if (base_ == 2) { // Determine where the first set bit is on range(), giving a log2(range) // value which can be used to construct bounds. - log_range_ = - (std::min)(bit_width(range()), - static_cast<unsigned_type>( - std::numeric_limits<unsigned_type>::digits)); + log_range_ = (std::min)(random_internal::BitWidth(range()), + std::numeric_limits<unsigned_type>::digits); } else { // NOTE: Computing the logN(x) introduces error from 2 sources: // 1. Conversion of int to double loses precision for values >= @@ -83,7 +81,7 @@ class log_uniform_int_distribution { // // Thus a result which should equal K may equal K +/- epsilon, // which can eliminate some values depending on where the bounds fall. - const double inv_log_base = 1.0 / std::log(base_); + const double inv_log_base = 1.0 / std::log(static_cast<double>(base_)); const double log_range = std::log(static_cast<double>(range()) + 0.5); log_range_ = static_cast<int>(std::ceil(inv_log_base * log_range)); } @@ -113,7 +111,7 @@ class log_uniform_int_distribution { unsigned_type range_; // max - min int log_range_; // ceil(logN(range_)) - static_assert(std::is_integral<IntType>::value, + static_assert(random_internal::IsIntegral<IntType>::value, "Class-template absl::log_uniform_int_distribution<> must be " "parameterized using an integral type."); }; @@ -139,7 +137,7 @@ class log_uniform_int_distribution { template <typename URBG> result_type operator()(URBG& g, // NOLINT(runtime/references) const param_type& p) { - return (p.min)() + Generate(g, p); + return static_cast<result_type>((p.min)() + Generate(g, p)); } result_type(min)() const { return (param_.min)(); } @@ -193,8 +191,8 @@ log_uniform_int_distribution<IntType>::Generate( ? (std::numeric_limits<unsigned_type>::max)() : (static_cast<unsigned_type>(1) << e) - 1; } else { - const double r = std::pow(p.base(), d); - const double s = (r * p.base()) - 1.0; + const double r = std::pow(static_cast<double>(p.base()), d); + const double s = (r * static_cast<double>(p.base())) - 1.0; base_e = (r > static_cast<double>((std::numeric_limits<unsigned_type>::max)())) @@ -211,7 +209,8 @@ log_uniform_int_distribution<IntType>::Generate( const unsigned_type hi = (top_e >= p.range()) ? p.range() : top_e; // choose uniformly over [lo, hi] - return absl::uniform_int_distribution<result_type>(lo, hi)(g); + return absl::uniform_int_distribution<result_type>( + static_cast<result_type>(lo), static_cast<result_type>(hi))(g); } template <typename CharT, typename Traits, typename IntType> diff --git a/absl/random/log_uniform_int_distribution_test.cc b/absl/random/log_uniform_int_distribution_test.cc index 5e780d96..0d0fcb95 100644 --- a/absl/random/log_uniform_int_distribution_test.cc +++ b/absl/random/log_uniform_int_distribution_test.cc @@ -42,7 +42,7 @@ class LogUniformIntDistributionTypeTest : public ::testing::Test {}; using IntTypes = ::testing::Types<int8_t, int16_t, int32_t, int64_t, // uint8_t, uint16_t, uint32_t, uint64_t>; -TYPED_TEST_CASE(LogUniformIntDistributionTypeTest, IntTypes); +TYPED_TEST_SUITE(LogUniformIntDistributionTypeTest, IntTypes); TYPED_TEST(LogUniformIntDistributionTypeTest, SerializeTest) { using param_type = diff --git a/absl/random/mocking_bit_gen.h b/absl/random/mocking_bit_gen.h index 7b2b80eb..89fa5a47 100644 --- a/absl/random/mocking_bit_gen.h +++ b/absl/random/mocking_bit_gen.h @@ -87,7 +87,7 @@ class BitGenRef; // // ON_CALL(absl::MockUniform<int>(), Call(bitgen, testing::_, testing::_)) // .WillByDefault([] (int low, int high) { -// return (low + high) / 2; +// return low + (high - low) / 2; // }); // // EXPECT_EQ(absl::Uniform<int>(gen, 0, 10), 5); diff --git a/absl/random/mocking_bit_gen_test.cc b/absl/random/mocking_bit_gen_test.cc index f63b6e42..c713ceaf 100644 --- a/absl/random/mocking_bit_gen_test.cc +++ b/absl/random/mocking_bit_gen_test.cc @@ -15,6 +15,7 @@ // #include "absl/random/mocking_bit_gen.h" +#include <cmath> #include <numeric> #include <random> @@ -328,8 +329,9 @@ TEST(BasicMocking, WillByDefaultWithArgs) { absl::MockingBitGen gen; ON_CALL(absl::MockPoisson<int>(), Call(gen, _)) - .WillByDefault( - [](double lambda) { return static_cast<int>(lambda * 10); }); + .WillByDefault([](double lambda) { + return static_cast<int>(std::rint(lambda * 10)); + }); EXPECT_EQ(absl::Poisson<int>(gen, 1.7), 17); EXPECT_EQ(absl::Poisson<int>(gen, 0.03), 0); } diff --git a/absl/random/poisson_distribution.h b/absl/random/poisson_distribution.h index cb5f5d5d..f4573082 100644 --- a/absl/random/poisson_distribution.h +++ b/absl/random/poisson_distribution.h @@ -26,6 +26,7 @@ #include "absl/random/internal/fastmath.h" #include "absl/random/internal/generate_real.h" #include "absl/random/internal/iostream_state_saver.h" +#include "absl/random/internal/traits.h" namespace absl { ABSL_NAMESPACE_BEGIN @@ -80,7 +81,7 @@ class poisson_distribution { double log_k_; int split_; - static_assert(std::is_integral<IntType>::value, + static_assert(random_internal::IsIntegral<IntType>::value, "Class-template absl::poisson_distribution<> must be " "parameterized using an integral type."); }; @@ -133,7 +134,8 @@ template <typename IntType> poisson_distribution<IntType>::param_type::param_type(double mean) : mean_(mean), split_(0) { assert(mean >= 0); - assert(mean <= (std::numeric_limits<result_type>::max)()); + assert(mean <= + static_cast<double>((std::numeric_limits<result_type>::max)())); // As a defensive measure, avoid large values of the mean. The rejection // algorithm used does not support very large values well. It my be worth // changing algorithms to better deal with these cases. @@ -222,8 +224,9 @@ poisson_distribution<IntType>::operator()( // clang-format on const double lhs = 2.0 * std::log(u) + p.log_k_ + s; if (lhs < rhs) { - return x > (max)() ? (max)() - : static_cast<result_type>(x); // f(x)/k >= u^2 + return x > static_cast<double>((max)()) + ? (max)() + : static_cast<result_type>(x); // f(x)/k >= u^2 } } } diff --git a/absl/random/poisson_distribution_test.cc b/absl/random/poisson_distribution_test.cc index 8baabd11..4f585b9b 100644 --- a/absl/random/poisson_distribution_test.cc +++ b/absl/random/poisson_distribution_test.cc @@ -73,7 +73,7 @@ class PoissonDistributionInterfaceTest : public ::testing::Test {}; using IntTypes = ::testing::Types<int, int8_t, int16_t, int32_t, int64_t, uint8_t, uint16_t, uint32_t, uint64_t>; -TYPED_TEST_CASE(PoissonDistributionInterfaceTest, IntTypes); +TYPED_TEST_SUITE(PoissonDistributionInterfaceTest, IntTypes); TYPED_TEST(PoissonDistributionInterfaceTest, SerializeTest) { using param_type = typename absl::poisson_distribution<TypeParam>::param_type; diff --git a/absl/random/seed_sequences.h b/absl/random/seed_sequences.h index ff1340cc..c3af4b00 100644 --- a/absl/random/seed_sequences.h +++ b/absl/random/seed_sequences.h @@ -28,6 +28,7 @@ #include <iterator> #include <random> +#include "absl/base/config.h" #include "absl/random/internal/salted_seed_seq.h" #include "absl/random/internal/seed_material.h" #include "absl/random/seed_gen_exception.h" diff --git a/absl/random/uniform_int_distribution.h b/absl/random/uniform_int_distribution.h index c1f54cce..fae80252 100644 --- a/absl/random/uniform_int_distribution.h +++ b/absl/random/uniform_int_distribution.h @@ -97,7 +97,7 @@ class uniform_int_distribution { result_type lo_; unsigned_type range_; - static_assert(std::is_integral<result_type>::value, + static_assert(random_internal::IsIntegral<result_type>::value, "Class-template absl::uniform_int_distribution<> must be " "parameterized using an integral type."); }; // param_type @@ -125,7 +125,7 @@ class uniform_int_distribution { template <typename URBG> result_type operator()( URBG& gen, const param_type& param) { // NOLINT(runtime/references) - return param.a() + Generate(gen, param.range()); + return static_cast<result_type>(param.a() + Generate(gen, param.range())); } result_type a() const { return param_.a(); } diff --git a/absl/random/uniform_real_distribution.h b/absl/random/uniform_real_distribution.h index 5ba17b23..19683341 100644 --- a/absl/random/uniform_real_distribution.h +++ b/absl/random/uniform_real_distribution.h @@ -73,12 +73,12 @@ class uniform_real_distribution { : lo_(lo), hi_(hi), range_(hi - lo) { // [rand.dist.uni.real] preconditions 2 & 3 assert(lo <= hi); + // NOTE: For integral types, we can promote the range to an unsigned type, // which gives full width of the range. However for real (fp) types, this // is not possible, so value generation cannot use the full range of the // real type. assert(range_ <= (std::numeric_limits<result_type>::max)()); - assert(std::isfinite(range_)); } result_type a() const { return lo_; } diff --git a/absl/random/uniform_real_distribution_test.cc b/absl/random/uniform_real_distribution_test.cc index 18bcd3bc..07f199d3 100644 --- a/absl/random/uniform_real_distribution_test.cc +++ b/absl/random/uniform_real_distribution_test.cc @@ -14,6 +14,7 @@ #include "absl/random/uniform_real_distribution.h" +#include <cfloat> #include <cmath> #include <cstdint> #include <iterator> @@ -70,61 +71,81 @@ using RealTypes = TYPED_TEST_SUITE(UniformRealDistributionTest, RealTypes); TYPED_TEST(UniformRealDistributionTest, ParamSerializeTest) { - using param_type = - typename absl::uniform_real_distribution<TypeParam>::param_type; +#if (defined(__i386__) || defined(_M_IX86)) && FLT_EVAL_METHOD != 0 + // We're using an x87-compatible FPU, and intermediate operations are + // performed with 80-bit floats. This produces slightly different results from + // what we expect below. + GTEST_SKIP() + << "Skipping the test because we detected x87 floating-point semantics"; +#endif + using DistributionType = absl::uniform_real_distribution<TypeParam>; + using real_type = TypeParam; + using param_type = typename DistributionType::param_type; + + constexpr const real_type kMax = std::numeric_limits<real_type>::max(); + constexpr const real_type kMin = std::numeric_limits<real_type>::min(); + constexpr const real_type kEpsilon = + std::numeric_limits<real_type>::epsilon(); + constexpr const real_type kLowest = + std::numeric_limits<real_type>::lowest(); // -max + + const real_type kDenormMax = std::nextafter(kMin, real_type{0}); + const real_type kOneMinusE = + std::nextafter(real_type{1}, real_type{0}); // 1 - epsilon - constexpr const TypeParam a{1152921504606846976}; + constexpr const real_type kTwo60{1152921504606846976}; // 2^60 constexpr int kCount = 1000; absl::InsecureBitGen gen; for (const auto& param : { param_type(), - param_type(TypeParam(2.0), TypeParam(2.0)), // Same - param_type(TypeParam(-0.1), TypeParam(0.1)), - param_type(TypeParam(0.05), TypeParam(0.12)), - param_type(TypeParam(-0.05), TypeParam(0.13)), - param_type(TypeParam(-0.05), TypeParam(-0.02)), + param_type(real_type{0}, real_type{1}), + param_type(real_type(-0.1), real_type(0.1)), + param_type(real_type(0.05), real_type(0.12)), + param_type(real_type(-0.05), real_type(0.13)), + param_type(real_type(-0.05), real_type(-0.02)), + // range = 0 + param_type(real_type(2.0), real_type(2.0)), // Same // double range = 0 // 2^60 , 2^60 + 2^6 - param_type(a, TypeParam(1152921504606847040)), + param_type(kTwo60, real_type(1152921504606847040)), // 2^60 , 2^60 + 2^7 - param_type(a, TypeParam(1152921504606847104)), + param_type(kTwo60, real_type(1152921504606847104)), // double range = 2^8 // 2^60 , 2^60 + 2^8 - param_type(a, TypeParam(1152921504606847232)), + param_type(kTwo60, real_type(1152921504606847232)), // float range = 0 // 2^60 , 2^60 + 2^36 - param_type(a, TypeParam(1152921573326323712)), + param_type(kTwo60, real_type(1152921573326323712)), // 2^60 , 2^60 + 2^37 - param_type(a, TypeParam(1152921642045800448)), + param_type(kTwo60, real_type(1152921642045800448)), // float range = 2^38 // 2^60 , 2^60 + 2^38 - param_type(a, TypeParam(1152921779484753920)), + param_type(kTwo60, real_type(1152921779484753920)), // Limits - param_type(0, std::numeric_limits<TypeParam>::max()), - param_type(std::numeric_limits<TypeParam>::lowest(), 0), - param_type(0, std::numeric_limits<TypeParam>::epsilon()), - param_type(-std::numeric_limits<TypeParam>::epsilon(), - std::numeric_limits<TypeParam>::epsilon()), - param_type(std::numeric_limits<TypeParam>::epsilon(), - 2 * std::numeric_limits<TypeParam>::epsilon()), + param_type(0, kMax), + param_type(kLowest, 0), + param_type(0, kMin), + param_type(0, kEpsilon), + param_type(-kEpsilon, kEpsilon), + param_type(0, kOneMinusE), + param_type(0, kDenormMax), }) { // Validate parameters. const auto a = param.a(); const auto b = param.b(); - absl::uniform_real_distribution<TypeParam> before(a, b); + DistributionType before(a, b); EXPECT_EQ(before.a(), param.a()); EXPECT_EQ(before.b(), param.b()); { - absl::uniform_real_distribution<TypeParam> via_param(param); + DistributionType via_param(param); EXPECT_EQ(via_param, before); } std::stringstream ss; ss << before; - absl::uniform_real_distribution<TypeParam> after(TypeParam(1.0), - TypeParam(3.1)); + DistributionType after(real_type(1.0), real_type(3.1)); EXPECT_NE(before.a(), after.a()); EXPECT_NE(before.b(), after.b()); @@ -159,7 +180,7 @@ TYPED_TEST(UniformRealDistributionTest, ParamSerializeTest) { } } - if (!std::is_same<TypeParam, long double>::value) { + if (!std::is_same<real_type, long double>::value) { // static_cast<double>(long double) can overflow. std::string msg = absl::StrCat("Range: ", static_cast<double>(sample_min), ", ", static_cast<double>(sample_max)); @@ -173,33 +194,52 @@ TYPED_TEST(UniformRealDistributionTest, ParamSerializeTest) { #pragma warning(disable:4756) // Constant arithmetic overflow. #endif TYPED_TEST(UniformRealDistributionTest, ViolatesPreconditionsDeathTest) { + using DistributionType = absl::uniform_real_distribution<TypeParam>; + using real_type = TypeParam; + #if GTEST_HAS_DEATH_TEST // Hi < Lo - EXPECT_DEBUG_DEATH( - { absl::uniform_real_distribution<TypeParam> dist(10.0, 1.0); }, ""); + EXPECT_DEBUG_DEATH({ DistributionType dist(10.0, 1.0); }, ""); // Hi - Lo > numeric_limits<>::max() EXPECT_DEBUG_DEATH( { - absl::uniform_real_distribution<TypeParam> dist( - std::numeric_limits<TypeParam>::lowest(), - std::numeric_limits<TypeParam>::max()); + DistributionType dist(std::numeric_limits<real_type>::lowest(), + std::numeric_limits<real_type>::max()); + }, + ""); + + // kEpsilon guarantees that max + kEpsilon = inf. + const auto kEpsilon = std::nexttoward( + (std::numeric_limits<real_type>::max() - + std::nexttoward(std::numeric_limits<real_type>::max(), 0.0)) / + 2, + std::numeric_limits<real_type>::max()); + EXPECT_DEBUG_DEATH( + { + DistributionType dist(-kEpsilon, std::numeric_limits<real_type>::max()); + }, + ""); + EXPECT_DEBUG_DEATH( + { + DistributionType dist(std::numeric_limits<real_type>::lowest(), + kEpsilon); }, ""); + #endif // GTEST_HAS_DEATH_TEST #if defined(NDEBUG) // opt-mode, for invalid parameters, will generate a garbage value, // but should not enter an infinite loop. absl::InsecureBitGen gen; { - absl::uniform_real_distribution<TypeParam> dist(10.0, 1.0); + DistributionType dist(10.0, 1.0); auto x = dist(gen); EXPECT_FALSE(std::isnan(x)) << x; } { - absl::uniform_real_distribution<TypeParam> dist( - std::numeric_limits<TypeParam>::lowest(), - std::numeric_limits<TypeParam>::max()); + DistributionType dist(std::numeric_limits<real_type>::lowest(), + std::numeric_limits<real_type>::max()); auto x = dist(gen); // Infinite result. EXPECT_FALSE(std::isfinite(x)) << x; @@ -211,6 +251,8 @@ TYPED_TEST(UniformRealDistributionTest, ViolatesPreconditionsDeathTest) { #endif TYPED_TEST(UniformRealDistributionTest, TestMoments) { + using DistributionType = absl::uniform_real_distribution<TypeParam>; + constexpr int kSize = 1000000; std::vector<double> values(kSize); @@ -219,7 +261,7 @@ TYPED_TEST(UniformRealDistributionTest, TestMoments) { // implementation. absl::random_internal::pcg64_2018_engine rng{0x2B7E151628AED2A6}; - absl::uniform_real_distribution<TypeParam> dist; + DistributionType dist; for (int i = 0; i < kSize; i++) { values[i] = dist(rng); } @@ -233,9 +275,10 @@ TYPED_TEST(UniformRealDistributionTest, TestMoments) { } TYPED_TEST(UniformRealDistributionTest, ChiSquaredTest50) { + using DistributionType = absl::uniform_real_distribution<TypeParam>; + using param_type = typename DistributionType::param_type; + using absl::random_internal::kChiSquared; - using param_type = - typename absl::uniform_real_distribution<TypeParam>::param_type; constexpr size_t kTrials = 100000; constexpr int kBuckets = 50; @@ -260,7 +303,7 @@ TYPED_TEST(UniformRealDistributionTest, ChiSquaredTest50) { const double factor = kBuckets / (max_val - min_val); std::vector<int32_t> counts(kBuckets, 0); - absl::uniform_real_distribution<TypeParam> dist(param); + DistributionType dist(param); for (size_t i = 0; i < kTrials; i++) { auto x = dist(rng); auto bucket = static_cast<size_t>((x - min_val) * factor); @@ -288,8 +331,11 @@ TYPED_TEST(UniformRealDistributionTest, ChiSquaredTest50) { } TYPED_TEST(UniformRealDistributionTest, StabilityTest) { + using DistributionType = absl::uniform_real_distribution<TypeParam>; + using real_type = TypeParam; + // absl::uniform_real_distribution stability relies only on - // random_internal::RandU64ToDouble and random_internal::RandU64ToFloat. + // random_internal::GenerateRealFromBits. absl::random_internal::sequence_urbg urbg( {0x0003eb76f6f7f755ull, 0xFFCEA50FDB2F953Bull, 0xC332DDEFBE6C5AA5ull, 0x6558218568AB9702ull, 0x2AEF7DAD5B6E2F84ull, 0x1521B62829076170ull, @@ -298,9 +344,9 @@ TYPED_TEST(UniformRealDistributionTest, StabilityTest) { std::vector<int> output(12); - absl::uniform_real_distribution<TypeParam> dist; + DistributionType dist; std::generate(std::begin(output), std::end(output), [&] { - return static_cast<int>(TypeParam(1000000) * dist(urbg)); + return static_cast<int>(real_type(1000000) * dist(urbg)); }); EXPECT_THAT( diff --git a/absl/random/zipf_distribution.h b/absl/random/zipf_distribution.h index 22ebc756..03497b1b 100644 --- a/absl/random/zipf_distribution.h +++ b/absl/random/zipf_distribution.h @@ -23,13 +23,14 @@ #include <type_traits> #include "absl/random/internal/iostream_state_saver.h" +#include "absl/random/internal/traits.h" #include "absl/random/uniform_real_distribution.h" namespace absl { ABSL_NAMESPACE_BEGIN // absl::zipf_distribution produces random integer-values in the range [0, k], -// distributed according to the discrete probability function: +// distributed according to the unnormalized discrete probability function: // // P(x) = (v + x) ^ -q // @@ -94,7 +95,7 @@ class zipf_distribution { double hxm_; // h(k + 0.5) double hx0_minus_hxm_; // h(x0) - h(k + 0.5) - static_assert(std::is_integral<IntType>::value, + static_assert(random_internal::IsIntegral<IntType>::value, "Class-template absl::zipf_distribution<> must be " "parameterized using an integral type."); }; @@ -221,7 +222,7 @@ zipf_distribution<IntType>::operator()( const double u = p.hxm_ + v * p.hx0_minus_hxm_; const double x = p.hinv(u); k = rint(x); // std::floor(x + 0.5); - if (k > p.k()) continue; // reject k > max_k + if (k > static_cast<double>(p.k())) continue; // reject k > max_k if (k - x <= p.s_) break; const double h = p.h(k + 0.5); const double r = p.pow_negative_q(p.v_ + k); diff --git a/absl/random/zipf_distribution_test.cc b/absl/random/zipf_distribution_test.cc index f8cf70e0..c8bb89db 100644 --- a/absl/random/zipf_distribution_test.cc +++ b/absl/random/zipf_distribution_test.cc @@ -44,7 +44,7 @@ class ZipfDistributionTypedTest : public ::testing::Test {}; using IntTypes = ::testing::Types<int, int8_t, int16_t, int32_t, int64_t, uint8_t, uint16_t, uint32_t, uint64_t>; -TYPED_TEST_CASE(ZipfDistributionTypedTest, IntTypes); +TYPED_TEST_SUITE(ZipfDistributionTypedTest, IntTypes); TYPED_TEST(ZipfDistributionTypedTest, SerializeTest) { using param_type = typename absl::zipf_distribution<TypeParam>::param_type; |