commit 7fa9a6776a34cb482056d42f8b781a2a5fe3e539
author Kapandaria <dvoreader@gmail.com> Mon May 16 07:30:40 2022 +0000
committer Commit Bot <commit-bot@chromium.org> Mon May 16 07:30:40 2022 +0000
tree ede7b2b8e08a2c62d30a67a48bfccb772a6ec039
parent aa616d6ad84b4fc4bfe0cef7c24aadba64fcd50b

[vm] Update bit algorithms in utils.cc

Closes https://github.com/dart-lang/sdk/pull/48942

GitOrigin-RevId: 484c201343c546abdfdc8669f87e844c26c0fd43
Change-Id: Ib918e0deca4cccbeef2cc6a17a84ec95a74e80f5
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/243361
Commit-Queue: Slava Egorov <vegorov@google.com>
Reviewed-by: Slava Egorov <vegorov@google.com>
Reviewed-by: Martin Kustermann <kustermann@google.com>

runtime/platform/utils.cc

diff --git a/runtime/platform/utils.cc b/runtime/platform/utils.cc
index eb833e7..6d577eb 100644
--- a/runtime/platform/utils.cc
+++ b/runtime/platform/utils.cc
@@ -34,8 +34,10 @@
 #if __GNUC__ && !defined(HOST_ARCH_IA32) && !defined(HOST_ARCH_X64)
   return __builtin_popcountll(x);
 #else
-  return CountOneBits32(static_cast<uint32_t>(x)) +
-         CountOneBits32(static_cast<uint32_t>(x >> 32));
+  x = x - ((x >> 1) & 0x5555555555555555);
+  x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
+  x = (((x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f) * 0x0101010101010101) >> 56;
+  return x;
 #endif
 }
 
@@ -108,23 +110,22 @@
 }
 
 uint64_t Utils::ReverseBits64(uint64_t x) {
-  const uint64_t one = static_cast<uint64_t>(1);
-  uint64_t result = 0;
-  for (uint64_t rbit = one << 63; x != 0; x >>= 1) {
-    if ((x & one) != 0) result |= rbit;
-    rbit >>= 1;
-  }
-  return result;
+  x = ( (x >> 32) & 0x00000000ffffffff  ) | ( x << 32 );
+  x = ( (x >> 16) & 0x0000ffff0000ffff  ) | ( (x & 0x0000ffff0000ffff) << 16 );
+  x = ( (x >> 8) & 0x00ff00ff00ff00ff  ) | ( (x & 0x00ff00ff00ff00ff) << 8 );
+  x = ( (x >> 4) & 0x0f0f0f0f0f0f0f0f  ) | ( (x & 0x0f0f0f0f0f0f0f0f) << 4 );
+  x = ( (x >> 2) & 0x3333333333333333  ) | ( (x & 0x3333333333333333) << 2 );
+  x = ( (x >> 1) & 0x5555555555555555  ) | ( (x & 0x5555555555555555) << 1 );
+  return x;
 }
 
 uint32_t Utils::ReverseBits32(uint32_t x) {
-  const uint32_t one = static_cast<uint32_t>(1);
-  uint32_t result = 0;
-  for (uint32_t rbit = one << 31; x != 0; x >>= 1) {
-    if ((x & one) != 0) result |= rbit;
-    rbit >>= 1;
-  }
-  return result;
+  x = ( (x >> 16) & 0x0000ffff  ) | ( (x & 0x0000ffff) << 16 );
+  x = ( (x >> 8) & 0x00ff00ff  ) | ( (x & 0x00ff00ff) << 8 );
+  x = ( (x >> 4) & 0x0f0f0f0f  ) | ( (x & 0x0f0f0f0f) << 4 );
+  x = ( (x >> 2) & 0x33333333  ) | ( (x & 0x33333333) << 2 );
+  x = ( (x >> 1) & 0x55555555  ) | ( (x & 0x55555555) << 1 );
+  return x;
 }
 
 // Implementation according to H.S.Warren's "Hacker's Delight"