Export of internal Abseil changes

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

Optimize 128 bit division in absl::uint128 when the intrinsic does not exist

PiperOrigin-RevId: 316413322

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

Add additional 128 bit division benchmarks.

PiperOrigin-RevId: 316358648

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

Add tests for ABSL_PREDICT_TRUE and ABSL_PREDICT_FALSE macros.

PiperOrigin-RevId: 316325593

--
3d7fe4ab8bc1e736b9697098eeb2cdb7e9910105 by Andy Soffer <asoffer@google.com>:

Removing unnecessary comment using hurtful words.

PiperOrigin-RevId: 316192184
GitOrigin-RevId: ede5d8e8877c81d7e69549e05076f62cb334ef7f
Change-Id: I4e447286d0b823d99cdd658dd49fb66725bb7a30

1 files changed, 13 insertions, 27 deletions

diff --git a/absl/numeric/int128.cc b/absl/numeric/int128.cc
index b605a870..e21e5e9a 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) {