Update BitSet32

Cherry-pick several BitSet32 changes from Android, including fixes for
64-bit platforms and several additional unit tests.

BUG=513806

Review URL: https://codereview.chromium.org/1264503002

Cr-Commit-Position: refs/heads/master@{#340955}

2 files changed, 156 insertions, 5 deletions

diff --git a/ui/events/gesture_detection/bitset_32.h b/ui/events/gesture_detection/bitset_32.h
index 7b347f1..6900e28 100644
--- a/ui/events/gesture_detection/bitset_32.h
+++ b/ui/events/gesture_detection/bitset_32.h
@@ -12,7 +12,7 @@ namespace ui {
 
 // Port of BitSet32 from Android
 // * platform/system/core/include/utils/BitSet.h
-// * Change-Id: I9bbf41f9d2d4a2593b0e6d7d8be7e283f985bade
+// * Change-Id: 02c9460a0a05f27e0501f9e64cdf24091e7d3579
 // * Please update the Change-Id as upstream Android changes are pulled.
 struct BitSet32 {
   uint32_t value;
@@ -100,12 +100,41 @@ struct BitSet32 {
   inline bool operator!=(const BitSet32& other) const {
     return value != other.value;
   }
+  inline BitSet32 operator&(const BitSet32& other) const {
+    return BitSet32(value & other.value);
+  }
+  inline BitSet32& operator&=(const BitSet32& other) {
+    value &= other.value;
+    return *this;
+  }
+  inline BitSet32 operator|(const BitSet32& other) const {
+    return BitSet32(value | other.value);
+  }
+  inline BitSet32& operator|=(const BitSet32& other) {
+    value |= other.value;
+    return *this;
+  }
 
  private:
 #if defined(COMPILER_GCC) || defined(__clang__)
-  static inline uint32_t popcnt(uint32_t v) { return __builtin_popcount(v); }
-  static inline uint32_t clz(uint32_t v) { return __builtin_clz(v); }
-  static inline uint32_t ctz(uint32_t v) { return __builtin_ctz(v); }
+  static inline uint32_t popcnt(uint32_t v) { return __builtin_popcountl(v); }
+  // We use these helpers as the signature of __builtin_c{l,t}z has
+  // "unsigned int" for the input, which is only guaranteed to be 16b, not 32.
+  // The compiler should optimize this away.
+  static inline uint32_t clz(uint32_t v) {
+    if (sizeof(unsigned int) == sizeof(uint32_t)) {
+      return __builtin_clz(v);
+    } else {
+      return __builtin_clzl(v);
+    }
+  }
+  static inline uint32_t ctz(uint32_t v) {
+    if (sizeof(unsigned int) == sizeof(uint32_t)) {
+      return __builtin_ctz(v);
+    } else {
+      return __builtin_ctzl(v);
+    }
+  }
 #else
   // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
   static inline uint32_t popcnt(uint32_t v) {
diff --git a/ui/events/gesture_detection/bitset_32_unittest.cc b/ui/events/gesture_detection/bitset_32_unittest.cc
index 2e5d271..a684af8 100644
--- a/ui/events/gesture_detection/bitset_32_unittest.cc
+++ b/ui/events/gesture_detection/bitset_32_unittest.cc
@@ -8,7 +8,17 @@
 
 namespace ui {
 
-class BitSet32Test : public testing::Test {};
+class BitSet32Test : public testing::Test {
+ public:
+  void TearDown() override {
+    b1.clear();
+    b2.clear();
+  }
+
+ protected:
+  BitSet32 b1;
+  BitSet32 b2;
+};
 
 TEST_F(BitSet32Test, Basic) {
   BitSet32 bits;
@@ -97,4 +107,116 @@ TEST_F(BitSet32Test, Basic) {
   EXPECT_EQ(2U, bits.get_index_of_bit(2));
 }
 
+TEST_F(BitSet32Test, BitWiseOr) {
+  b1.mark_bit(2);
+  b2.mark_bit(4);
+
+  BitSet32 tmp = b1 | b2;
+  EXPECT_EQ(tmp.count(), 2u);
+  EXPECT_TRUE(tmp.has_bit(2) && tmp.has_bit(4));
+  // Check that the operator is symmetric.
+  EXPECT_TRUE((b2 | b1) == (b1 | b2));
+
+  b1 |= b2;
+  EXPECT_EQ(b1.count(), 2u);
+  EXPECT_TRUE(b1.has_bit(2) && b1.has_bit(4));
+  EXPECT_TRUE(b2.has_bit(4) && b2.count() == 1u);
+}
+
+TEST_F(BitSet32Test, BitWiseAnd_Disjoint) {
+  b1.mark_bit(2);
+  b1.mark_bit(4);
+  b1.mark_bit(6);
+
+  BitSet32 tmp = b1 & b2;
+  EXPECT_TRUE(tmp.is_empty());
+  // Check that the operator is symmetric.
+  EXPECT_TRUE((b2 & b1) == (b1 & b2));
+
+  b2 &= b1;
+  EXPECT_TRUE(b2.is_empty());
+  EXPECT_EQ(b1.count(), 3u);
+  EXPECT_TRUE(b1.has_bit(2) && b1.has_bit(4) && b1.has_bit(6));
+}
+
+TEST_F(BitSet32Test, BitWiseAnd_NonDisjoint) {
+  b1.mark_bit(2);
+  b1.mark_bit(4);
+  b1.mark_bit(6);
+  b2.mark_bit(3);
+  b2.mark_bit(6);
+  b2.mark_bit(9);
+
+  BitSet32 tmp = b1 & b2;
+  EXPECT_EQ(tmp.count(), 1u);
+  EXPECT_TRUE(tmp.has_bit(6));
+  // Check that the operator is symmetric.
+  EXPECT_TRUE((b2 & b1) == (b1 & b2));
+
+  b1 &= b2;
+  EXPECT_EQ(b1.count(), 1u);
+  EXPECT_EQ(b2.count(), 3u);
+  EXPECT_TRUE(b2.has_bit(3) && b2.has_bit(6) && b2.has_bit(9));
+}
+
+TEST_F(BitSet32Test, MarkFirstUnmarkedBit) {
+  b1.mark_bit(1);
+
+  b1.mark_first_unmarked_bit();
+  EXPECT_EQ(b1.count(), 2u);
+  EXPECT_TRUE(b1.has_bit(0) && b1.has_bit(1));
+
+  b1.mark_first_unmarked_bit();
+  EXPECT_EQ(b1.count(), 3u);
+  EXPECT_TRUE(b1.has_bit(0) && b1.has_bit(1) && b1.has_bit(2));
+}
+
+TEST_F(BitSet32Test, ClearFirstMarkedBit) {
+  b1.mark_bit(0);
+  b1.mark_bit(10);
+
+  b1.clear_first_marked_bit();
+  EXPECT_EQ(b1.count(), 1u);
+  EXPECT_TRUE(b1.has_bit(10));
+
+  b1.mark_bit(30);
+  b1.clear_first_marked_bit();
+  EXPECT_EQ(b1.count(), 1u);
+  EXPECT_TRUE(b1.has_bit(30));
+}
+
+TEST_F(BitSet32Test, ClearLastMarkedBit) {
+  b1.mark_bit(10);
+  b1.mark_bit(31);
+
+  b1.clear_last_marked_bit();
+  EXPECT_EQ(b1.count(), 1u);
+  EXPECT_TRUE(b1.has_bit(10));
+
+  b1.mark_bit(5);
+  b1.clear_last_marked_bit();
+  EXPECT_EQ(b1.count(), 1u);
+  EXPECT_TRUE(b1.has_bit(5));
+}
+
+TEST_F(BitSet32Test, FillAndClear) {
+  EXPECT_TRUE(b1.is_empty());
+  for (size_t i = 0; i < 32; i++) {
+    b1.mark_first_unmarked_bit();
+  }
+  EXPECT_TRUE(b1.is_full());
+  b1.clear();
+  EXPECT_TRUE(b1.is_empty());
+}
+
+TEST_F(BitSet32Test, GetIndexOfBit) {
+  b1.mark_bit(11);
+  b1.mark_bit(29);
+  EXPECT_EQ(b1.get_index_of_bit(11), 0u);
+  EXPECT_EQ(b1.get_index_of_bit(29), 1u);
+  b1.mark_first_unmarked_bit();
+  EXPECT_EQ(b1.get_index_of_bit(11), 1u);
+  EXPECT_EQ(b1.get_index_of_bit(29), 2u);
+}
+
 }  // namespace ui