Squashed 'third_party/abseil_cpp/' changes from 768eb2ca2..ccdbb5941

ccdbb5941 Export of internal Abseil changes
01f5f81f9 Export of internal Abseil changes
2c92bdc7c Export of internal Abseil changes
e7ebf9803 Export of internal Abseil changes
2eba343b5 Export of internal Abseil changes
a8b03d90e Export of internal Abseil changes
1d31b5c36 Export of internal Abseil changes
da3a87690 Export of internal Abseil changes
8faf20461 Exclude empty directories (#697)
2069dc796 Export of internal Abseil changes
4832bf6bf Added a BUILD file in root to expose license. (#695)
af8f994af Export of internal Abseil changes
33caf1097 Export of internal Abseil changes
cf1a02e2d Export of internal Abseil changes

git-subtree-dir: third_party/abseil_cpp
git-subtree-split: ccdbb5941f992fabda7eae3ce72f55efc17c826a

4 files changed, 126 insertions, 77 deletions

diff --git a/absl/numeric/BUILD.bazel b/absl/numeric/BUILD.bazel
index e09e52d21fe6..da3af4d0cec7 100644
--- a/absl/numeric/BUILD.bazel
+++ b/absl/numeric/BUILD.bazel
@@ -35,6 +35,7 @@ cc_library(
     copts = ABSL_DEFAULT_COPTS,
     linkopts = ABSL_DEFAULT_LINKOPTS,
     deps = [
+        "//absl/base:bits",
         "//absl/base:config",
         "//absl/base:core_headers",
     ],
diff --git a/absl/numeric/CMakeLists.txt b/absl/numeric/CMakeLists.txt
index 242889f088ad..1e12d80f7ce9 100644
--- a/absl/numeric/CMakeLists.txt
+++ b/absl/numeric/CMakeLists.txt
@@ -26,6 +26,7 @@ absl_cc_library(
   COPTS
     ${ABSL_DEFAULT_COPTS}
   DEPS
+    absl::bits
     absl::config
     absl::core_headers
   PUBLIC
diff --git a/absl/numeric/int128.cc b/absl/numeric/int128.cc
index b605a87042c1..e21e5e9a4ad4 100644
--- a/absl/numeric/int128.cc
+++ b/absl/numeric/int128.cc
@@ -15,6 +15,7 @@
 #include "absl/numeric/int128.h"
 
 #include <stddef.h>
+
 #include <cassert>
 #include <iomanip>
 #include <ostream>  // NOLINT(readability/streams)
@@ -22,6 +23,9 @@
 #include <string>
 #include <type_traits>
 
+#include "absl/base/internal/bits.h"
+#include "absl/base/optimization.h"
+
 namespace absl {
 ABSL_NAMESPACE_BEGIN
 
@@ -31,44 +35,26 @@ ABSL_DLL const uint128 kuint128max = MakeUint128(
 namespace {
 
 // Returns the 0-based position of the last set bit (i.e., most significant bit)
-// in the given uint64_t. The argument may not be 0.
+// in the given uint128. The argument is not 0.
 //
 // For example:
 //   Given: 5 (decimal) == 101 (binary)
 //   Returns: 2
-#define STEP(T, n, pos, sh)                   \
-  do {                                        \
-    if ((n) >= (static_cast<T>(1) << (sh))) { \
-      (n) = (n) >> (sh);                      \
-      (pos) |= (sh);                          \
-    }                                         \
-  } while (0)
-static inline int Fls64(uint64_t n) {
-  assert(n != 0);
-  int pos = 0;
-  STEP(uint64_t, n, pos, 0x20);
-  uint32_t n32 = static_cast<uint32_t>(n);
-  STEP(uint32_t, n32, pos, 0x10);
-  STEP(uint32_t, n32, pos, 0x08);
-  STEP(uint32_t, n32, pos, 0x04);
-  return pos + ((uint64_t{0x3333333322221100} >> (n32 << 2)) & 0x3);
-}
-#undef STEP
-
-// Like Fls64() above, but returns the 0-based position of the last set bit
-// (i.e., most significant bit) in the given uint128. The argument may not be 0.
-static inline int Fls128(uint128 n) {
+inline ABSL_ATTRIBUTE_ALWAYS_INLINE int Fls128(uint128 n) {
   if (uint64_t hi = Uint128High64(n)) {
-    return Fls64(hi) + 64;
+    ABSL_INTERNAL_ASSUME(hi != 0);
+    return 127 - base_internal::CountLeadingZeros64(hi);
   }
-  return Fls64(Uint128Low64(n));
+  const uint64_t low = Uint128Low64(n);
+  ABSL_INTERNAL_ASSUME(low != 0);
+  return 63 - base_internal::CountLeadingZeros64(low);
 }
 
 // Long division/modulo for uint128 implemented using the shift-subtract
 // division algorithm adapted from:
 // https://stackoverflow.com/questions/5386377/division-without-using
-void DivModImpl(uint128 dividend, uint128 divisor, uint128* quotient_ret,
-                uint128* remainder_ret) {
+inline void DivModImpl(uint128 dividend, uint128 divisor, uint128* quotient_ret,
+                       uint128* remainder_ret) {
   assert(divisor != 0);
 
   if (divisor > dividend) {
diff --git a/absl/numeric/int128_benchmark.cc b/absl/numeric/int128_benchmark.cc
index a5502d927c08..eab1515c0ad8 100644
--- a/absl/numeric/int128_benchmark.cc
+++ b/absl/numeric/int128_benchmark.cc
@@ -12,15 +12,15 @@
 // See the License for the specific language governing permissions and
 // limitations under the License.
 
-#include "absl/numeric/int128.h"
-
 #include <algorithm>
 #include <cstdint>
+#include <limits>
 #include <random>
 #include <vector>
 
 #include "benchmark/benchmark.h"
 #include "absl/base/config.h"
+#include "absl/numeric/int128.h"
 
 namespace {
 
@@ -32,57 +32,85 @@ std::mt19937 MakeRandomEngine() {
   return std::mt19937(seed);
 }
 
-std::vector<std::pair<absl::uint128, absl::uint128>>
-GetRandomClass128SampleUniformDivisor() {
-  std::vector<std::pair<absl::uint128, absl::uint128>> values;
+template <typename T,
+          typename H = typename std::conditional<
+              std::numeric_limits<T>::is_signed, int64_t, uint64_t>::type>
+std::vector<std::pair<T, T>> GetRandomClass128SampleUniformDivisor() {
+  std::vector<std::pair<T, T>> values;
   std::mt19937 random = MakeRandomEngine();
-  std::uniform_int_distribution<uint64_t> uniform_uint64;
+  std::uniform_int_distribution<H> uniform_h;
   values.reserve(kSampleSize);
   for (size_t i = 0; i < kSampleSize; ++i) {
-    absl::uint128 a =
-        absl::MakeUint128(uniform_uint64(random), uniform_uint64(random));
-    absl::uint128 b =
-        absl::MakeUint128(uniform_uint64(random), uniform_uint64(random));
-    values.emplace_back(std::max(a, b),
-                        std::max(absl::uint128(2), std::min(a, b)));
+    T a{absl::MakeUint128(uniform_h(random), uniform_h(random))};
+    T b{absl::MakeUint128(uniform_h(random), uniform_h(random))};
+    values.emplace_back(std::max(a, b), std::max(T(2), std::min(a, b)));
   }
   return values;
 }
 
+template <typename T>
 void BM_DivideClass128UniformDivisor(benchmark::State& state) {
-  auto values = GetRandomClass128SampleUniformDivisor();
+  auto values = GetRandomClass128SampleUniformDivisor<T>();
   while (state.KeepRunningBatch(values.size())) {
     for (const auto& pair : values) {
       benchmark::DoNotOptimize(pair.first / pair.second);
     }
   }
 }
-BENCHMARK(BM_DivideClass128UniformDivisor);
+BENCHMARK_TEMPLATE(BM_DivideClass128UniformDivisor, absl::uint128);
+BENCHMARK_TEMPLATE(BM_DivideClass128UniformDivisor, absl::int128);
+
+template <typename T>
+void BM_RemainderClass128UniformDivisor(benchmark::State& state) {
+  auto values = GetRandomClass128SampleUniformDivisor<T>();
+  while (state.KeepRunningBatch(values.size())) {
+    for (const auto& pair : values) {
+      benchmark::DoNotOptimize(pair.first % pair.second);
+    }
+  }
+}
+BENCHMARK_TEMPLATE(BM_RemainderClass128UniformDivisor, absl::uint128);
+BENCHMARK_TEMPLATE(BM_RemainderClass128UniformDivisor, absl::int128);
 
-std::vector<std::pair<absl::uint128, uint64_t>>
-GetRandomClass128SampleSmallDivisor() {
-  std::vector<std::pair<absl::uint128, uint64_t>> values;
+template <typename T,
+          typename H = typename std::conditional<
+              std::numeric_limits<T>::is_signed, int64_t, uint64_t>::type>
+std::vector<std::pair<T, H>> GetRandomClass128SampleSmallDivisor() {
+  std::vector<std::pair<T, H>> values;
   std::mt19937 random = MakeRandomEngine();
-  std::uniform_int_distribution<uint64_t> uniform_uint64;
+  std::uniform_int_distribution<H> uniform_h;
   values.reserve(kSampleSize);
   for (size_t i = 0; i < kSampleSize; ++i) {
-    absl::uint128 a =
-        absl::MakeUint128(uniform_uint64(random), uniform_uint64(random));
-    uint64_t b = std::max(uint64_t{2}, uniform_uint64(random));
-    values.emplace_back(std::max(a, absl::uint128(b)), b);
+    T a{absl::MakeUint128(uniform_h(random), uniform_h(random))};
+    H b{std::max(H{2}, uniform_h(random))};
+    values.emplace_back(std::max(a, T(b)), b);
   }
   return values;
 }
 
+template <typename T>
 void BM_DivideClass128SmallDivisor(benchmark::State& state) {
-  auto values = GetRandomClass128SampleSmallDivisor();
+  auto values = GetRandomClass128SampleSmallDivisor<T>();
   while (state.KeepRunningBatch(values.size())) {
     for (const auto& pair : values) {
       benchmark::DoNotOptimize(pair.first / pair.second);
     }
   }
 }
-BENCHMARK(BM_DivideClass128SmallDivisor);
+BENCHMARK_TEMPLATE(BM_DivideClass128SmallDivisor, absl::uint128);
+BENCHMARK_TEMPLATE(BM_DivideClass128SmallDivisor, absl::int128);
+
+template <typename T>
+void BM_RemainderClass128SmallDivisor(benchmark::State& state) {
+  auto values = GetRandomClass128SampleSmallDivisor<T>();
+  while (state.KeepRunningBatch(values.size())) {
+    for (const auto& pair : values) {
+      benchmark::DoNotOptimize(pair.first % pair.second);
+    }
+  }
+}
+BENCHMARK_TEMPLATE(BM_RemainderClass128SmallDivisor, absl::uint128);
+BENCHMARK_TEMPLATE(BM_RemainderClass128SmallDivisor, absl::int128);
 
 std::vector<std::pair<absl::uint128, absl::uint128>> GetRandomClass128Sample() {
   std::vector<std::pair<absl::uint128, absl::uint128>> values;
@@ -121,74 +149,107 @@ BENCHMARK(BM_AddClass128);
 
 // Some implementations of <random> do not support __int128 when it is
 // available, so we make our own uniform_int_distribution-like type.
+template <typename T,
+          typename H = typename std::conditional<
+              std::is_same<T, __int128>::value, int64_t, uint64_t>::type>
 class UniformIntDistribution128 {
  public:
   // NOLINTNEXTLINE: mimicking std::uniform_int_distribution API
-  unsigned __int128 operator()(std::mt19937& generator) {
-    return (static_cast<unsigned __int128>(dist64_(generator)) << 64) |
-           dist64_(generator);
+  T operator()(std::mt19937& generator) {
+    return (static_cast<T>(dist64_(generator)) << 64) | dist64_(generator);
   }
 
  private:
-  std::uniform_int_distribution<uint64_t> dist64_;
+  std::uniform_int_distribution<H> dist64_;
 };
 
-std::vector<std::pair<unsigned __int128, unsigned __int128>>
-GetRandomIntrinsic128SampleUniformDivisor() {
-  std::vector<std::pair<unsigned __int128, unsigned __int128>> values;
+template <typename T,
+          typename H = typename std::conditional<
+              std::is_same<T, __int128>::value, int64_t, uint64_t>::type>
+std::vector<std::pair<T, T>> GetRandomIntrinsic128SampleUniformDivisor() {
+  std::vector<std::pair<T, T>> values;
   std::mt19937 random = MakeRandomEngine();
-  UniformIntDistribution128 uniform_uint128;
+  UniformIntDistribution128<T> uniform_128;
   values.reserve(kSampleSize);
   for (size_t i = 0; i < kSampleSize; ++i) {
-    unsigned __int128 a = uniform_uint128(random);
-    unsigned __int128 b = uniform_uint128(random);
-    values.emplace_back(
-        std::max(a, b),
-        std::max(static_cast<unsigned __int128>(2), std::min(a, b)));
+    T a = uniform_128(random);
+    T b = uniform_128(random);
+    values.emplace_back(std::max(a, b),
+                        std::max(static_cast<T>(2), std::min(a, b)));
   }
   return values;
 }
 
+template <typename T>
 void BM_DivideIntrinsic128UniformDivisor(benchmark::State& state) {
-  auto values = GetRandomIntrinsic128SampleUniformDivisor();
+  auto values = GetRandomIntrinsic128SampleUniformDivisor<T>();
   while (state.KeepRunningBatch(values.size())) {
     for (const auto& pair : values) {
       benchmark::DoNotOptimize(pair.first / pair.second);
     }
   }
 }
-BENCHMARK(BM_DivideIntrinsic128UniformDivisor);
+BENCHMARK_TEMPLATE(BM_DivideIntrinsic128UniformDivisor, unsigned __int128);
+BENCHMARK_TEMPLATE(BM_DivideIntrinsic128UniformDivisor, __int128);
+
+template <typename T>
+void BM_RemainderIntrinsic128UniformDivisor(benchmark::State& state) {
+  auto values = GetRandomIntrinsic128SampleUniformDivisor<T>();
+  while (state.KeepRunningBatch(values.size())) {
+    for (const auto& pair : values) {
+      benchmark::DoNotOptimize(pair.first % pair.second);
+    }
+  }
+}
+BENCHMARK_TEMPLATE(BM_RemainderIntrinsic128UniformDivisor, unsigned __int128);
+BENCHMARK_TEMPLATE(BM_RemainderIntrinsic128UniformDivisor, __int128);
 
-std::vector<std::pair<unsigned __int128, uint64_t>>
-GetRandomIntrinsic128SampleSmallDivisor() {
-  std::vector<std::pair<unsigned __int128, uint64_t>> values;
+template <typename T,
+          typename H = typename std::conditional<
+              std::is_same<T, __int128>::value, int64_t, uint64_t>::type>
+std::vector<std::pair<T, H>> GetRandomIntrinsic128SampleSmallDivisor() {
+  std::vector<std::pair<T, H>> values;
   std::mt19937 random = MakeRandomEngine();
-  UniformIntDistribution128 uniform_uint128;
-  std::uniform_int_distribution<uint64_t> uniform_uint64;
+  UniformIntDistribution128<T> uniform_int128;
+  std::uniform_int_distribution<H> uniform_int64;
   values.reserve(kSampleSize);
   for (size_t i = 0; i < kSampleSize; ++i) {
-    unsigned __int128 a = uniform_uint128(random);
-    uint64_t b = std::max(uint64_t{2}, uniform_uint64(random));
-    values.emplace_back(std::max(a, static_cast<unsigned __int128>(b)), b);
+    T a = uniform_int128(random);
+    H b = std::max(H{2}, uniform_int64(random));
+    values.emplace_back(std::max(a, static_cast<T>(b)), b);
   }
   return values;
 }
 
+template <typename T>
 void BM_DivideIntrinsic128SmallDivisor(benchmark::State& state) {
-  auto values = GetRandomIntrinsic128SampleSmallDivisor();
+  auto values = GetRandomIntrinsic128SampleSmallDivisor<T>();
   while (state.KeepRunningBatch(values.size())) {
     for (const auto& pair : values) {
       benchmark::DoNotOptimize(pair.first / pair.second);
     }
   }
 }
-BENCHMARK(BM_DivideIntrinsic128SmallDivisor);
+BENCHMARK_TEMPLATE(BM_DivideIntrinsic128SmallDivisor, unsigned __int128);
+BENCHMARK_TEMPLATE(BM_DivideIntrinsic128SmallDivisor, __int128);
+
+template <typename T>
+void BM_RemainderIntrinsic128SmallDivisor(benchmark::State& state) {
+  auto values = GetRandomIntrinsic128SampleSmallDivisor<T>();
+  while (state.KeepRunningBatch(values.size())) {
+    for (const auto& pair : values) {
+      benchmark::DoNotOptimize(pair.first % pair.second);
+    }
+  }
+}
+BENCHMARK_TEMPLATE(BM_RemainderIntrinsic128SmallDivisor, unsigned __int128);
+BENCHMARK_TEMPLATE(BM_RemainderIntrinsic128SmallDivisor, __int128);
 
 std::vector<std::pair<unsigned __int128, unsigned __int128>>
       GetRandomIntrinsic128Sample() {
   std::vector<std::pair<unsigned __int128, unsigned __int128>> values;
   std::mt19937 random = MakeRandomEngine();
-  UniformIntDistribution128 uniform_uint128;
+  UniformIntDistribution128<unsigned __int128> uniform_uint128;
   values.reserve(kSampleSize);
   for (size_t i = 0; i < kSampleSize; ++i) {
     values.emplace_back(uniform_uint128(random), uniform_uint128(random));