Export of internal Abseil changes

--
75504b9d2eb7560359b98b69136d071f980e04f2 by Abseil Team <absl-team@google.com>:

Fix typos in documentation.

PiperOrigin-RevId: 423376798

--
bf87e5de48a868f49a57d516be027e6e3a3cc3bd by Gennadiy Rozental <rogeeff@google.com>:

Correct WEAK attribute enabling condition.

ABSL_ATTRIBUTE_WEAK is present if:
    compiler has built-in attribute weak
  OR
    we are using gcc (and not clang)
AND
    we are not on windows
  OR
    we use windows clang version >= 9.0.0
AND
  we are not on MinGW

PiperOrigin-RevId: 423357629

--
a01a8f1b7ea3da4ec349db452162a3333953dd9d by Abseil Team <absl-team@google.com>:

There are magic numbers in the expected load factors and probe lengths, and they seem to be wrong especially under msvc.  Even under the linux tool chain, these tests fail occasionally.  Fix the magic numbers to make the tests succeed.

PiperOrigin-RevId: 423320829

--
fd109295a1425ca1cb2b69fe34a294b6189542c0 by Laramie Leavitt <lar@google.com>:

Manually align buffers in randen_engine.

In C++ it's implementation defined whether types with extended alignment are supported.

randen_engine uses vector intrinsics with 16-byte alignment requirements in
some instances, so internally we allocate an extra 8 bytes to manually align to 16.

No detectable performance impact.

PiperOrigin-RevId: 423109265
GitOrigin-RevId: 75504b9d2eb7560359b98b69136d071f980e04f2
Change-Id: I8c5ab2269ff6d9e89d3b4d0e95d36ddb6ce8096e

2 files changed, 53 insertions, 34 deletions

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_engine.h b/absl/random/internal/randen_engine.h
index 372c3ac2..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,8 @@ 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.
@@ -146,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;
@@ -159,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;
     }
@@ -169,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 {
@@ -185,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_;
@@ -215,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;
   }
@@ -226,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_;
 };