Add more Bitmap methods.
authormark.lam@apple.com <mark.lam@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 21 May 2020 22:12:43 +0000 (22:12 +0000)
committermark.lam@apple.com <mark.lam@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 21 May 2020 22:12:43 +0000 (22:12 +0000)
https://bugs.webkit.org/show_bug.cgi?id=212190
<rdar://problem/63481333>

Reviewed by Robin Morisset.

Source/WTF:

Specifically,
    setEachNthBit - sets every Nth bit starting at a specified start bit
    operator=     - assignment
    operator|=    - bit or and assignment
    operator&=    - bit and and assignment
    operator^=    - bit xor and assignment

* wtf/Bitmap.h:

Tools:

Added test coverage for the new WTF::Bitmap methods.

* TestWebKitAPI/Tests/WTF/Bitmap.cpp:
(TestWebKitAPI::testBitmapSetEachNthBit):
(TestWebKitAPI::testBitmapOperatorAssignment):
(TestWebKitAPI::testBitmapOperatorBitOrAssignment):
(TestWebKitAPI::testBitmapOperatorBitAndAssignment):
(TestWebKitAPI::testBitmapOperatorBitXorAssignment):
(TestWebKitAPI::TEST):

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@262030 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/WTF/ChangeLog
Source/WTF/wtf/Bitmap.h
Tools/ChangeLog
Tools/TestWebKitAPI/Tests/WTF/Bitmap.cpp

index 1413467..f347002 100644 (file)
@@ -1,3 +1,20 @@
+2020-05-20  Mark Lam  <mark.lam@apple.com>
+
+        Add more Bitmap methods.
+        https://bugs.webkit.org/show_bug.cgi?id=212190
+        <rdar://problem/63481333>
+
+        Reviewed by Robin Morisset.
+
+        Specifically,
+            setEachNthBit - sets every Nth bit starting at a specified start bit
+            operator=     - assignment
+            operator|=    - bit or and assignment
+            operator&=    - bit and and assignment
+            operator^=    - bit xor and assignment
+
+        * wtf/Bitmap.h:
+
 2020-05-21  Yoshiaki Jitsukawa  <yoshiaki.jitsukawa@sony.com>
 
         [PlayStation] Add minimal WKView API to enable TestWebKitAPI
index bd4f0b0..6152312 100644 (file)
@@ -118,10 +118,17 @@ public:
     
     void mergeAndClear(Bitmap&);
     void setAndClear(Bitmap&);
-    
+
+    void setEachNthBit(size_t start, size_t n);
+
     bool operator==(const Bitmap&) const;
     bool operator!=(const Bitmap&) const;
-    
+
+    void operator=(const Bitmap&);
+    void operator|=(const Bitmap&);
+    void operator&=(const Bitmap&);
+    void operator^=(const Bitmap&);
+
     unsigned hash() const;
 
 private:
@@ -423,6 +430,27 @@ inline void Bitmap<bitmapSize, WordType>::setAndClear(Bitmap& other)
 }
 
 template<size_t bitmapSize, typename WordType>
+inline void Bitmap<bitmapSize, WordType>::setEachNthBit(size_t start, size_t n)
+{
+    size_t index = start;
+    size_t wordIndex = index / wordSize;
+    index = index - wordIndex * wordSize;
+    while (wordIndex < words) {
+        while (index < wordSize) {
+            bits[wordIndex] |= (one << index);
+            index += n;
+        }
+        index -= wordSize;
+        wordIndex++;
+    }
+    if constexpr (!!(bitmapSize % wordSize)) {
+        constexpr size_t remainingBits = bitmapSize % wordSize;
+        constexpr WordType mask = (static_cast<WordType>(1) << remainingBits) - 1;
+        bits[words - 1] &= mask;
+    }
+}
+
+template<size_t bitmapSize, typename WordType>
 inline bool Bitmap<bitmapSize, WordType>::operator==(const Bitmap& other) const
 {
     for (size_t i = 0; i < words; ++i) {
@@ -439,6 +467,34 @@ inline bool Bitmap<bitmapSize, WordType>::operator!=(const Bitmap& other) const
 }
 
 template<size_t bitmapSize, typename WordType>
+inline void Bitmap<bitmapSize, WordType>::operator=(const Bitmap& other)
+{
+    for (size_t i = 0; i < words; ++i)
+        bits[i] = other.bits[i];
+}
+
+template<size_t bitmapSize, typename WordType>
+inline void Bitmap<bitmapSize, WordType>::operator|=(const Bitmap& other)
+{
+    for (size_t i = 0; i < words; ++i)
+        bits[i] |= other.bits[i];
+}
+
+template<size_t bitmapSize, typename WordType>
+inline void Bitmap<bitmapSize, WordType>::operator&=(const Bitmap& other)
+{
+    for (size_t i = 0; i < words; ++i)
+        bits[i] &= other.bits[i];
+}
+
+template<size_t bitmapSize, typename WordType>
+inline void Bitmap<bitmapSize, WordType>::operator^=(const Bitmap& other)
+{
+    for (size_t i = 0; i < words; ++i)
+        bits[i] ^= other.bits[i];
+}
+
+template<size_t bitmapSize, typename WordType>
 inline unsigned Bitmap<bitmapSize, WordType>::hash() const
 {
     unsigned result = 0;
index fc8626e..6fae07f 100644 (file)
@@ -1,3 +1,21 @@
+2020-05-20  Mark Lam  <mark.lam@apple.com>
+
+        Add more Bitmap methods.
+        https://bugs.webkit.org/show_bug.cgi?id=212190
+        <rdar://problem/63481333>
+
+        Reviewed by Robin Morisset.
+
+        Added test coverage for the new WTF::Bitmap methods.
+
+        * TestWebKitAPI/Tests/WTF/Bitmap.cpp:
+        (TestWebKitAPI::testBitmapSetEachNthBit):
+        (TestWebKitAPI::testBitmapOperatorAssignment):
+        (TestWebKitAPI::testBitmapOperatorBitOrAssignment):
+        (TestWebKitAPI::testBitmapOperatorBitAndAssignment):
+        (TestWebKitAPI::testBitmapOperatorBitXorAssignment):
+        (TestWebKitAPI::TEST):
+
 2020-05-21  Yoshiaki Jitsukawa  <yoshiaki.jitsukawa@sony.com>
 
         [PlayStation] Add minimal WKView API to enable TestWebKitAPI
index ef03e29..618161f 100644 (file)
@@ -70,6 +70,16 @@ static constexpr bool expectedBits2[size] = {
     false, true,  false, true,   true,  true,  true,  true,
 };
 
+static constexpr bool expectedSmallBits1[smallSize] = {
+    false, true, true,  false,  true,  false, false, true,
+    true,
+};
+
+static constexpr bool expectedSmallBits2[smallSize] = {
+    true,  true, false, false,  false, false, true,  true,
+    false,
+};
+
 constexpr size_t countBits(const bool boolArray[], size_t size)
 {
     size_t result = 0;
@@ -90,7 +100,9 @@ constexpr size_t expectedNumberOfSetBits2 = countBits(expectedBits2, size);
     Bitmap<size, WordType> bitmap3; /* Same as bitmap2. */ \
     Bitmap<size, WordType> bitmapFilled; \
     Bitmap<smallSize, WordType> bitmapSmallZeroed; \
-    Bitmap<smallSize, WordType> bitmapSmallFilled;
+    Bitmap<smallSize, WordType> bitmapSmallFilled; \
+    Bitmap<smallSize, WordType> bitmapSmall1; /* Will hold values specified in expectedSmallBits1. */ \
+    Bitmap<smallSize, WordType> bitmapSmall2; /* Will hold values specified in expectedSmallBits2. */ \
 
 #define DECLARE_AND_INIT_BITMAPS_FOR_TEST() \
     DECLARE_BITMAPS_FOR_TEST() \
@@ -100,8 +112,11 @@ constexpr size_t expectedNumberOfSetBits2 = countBits(expectedBits2, size);
         bitmap3.set(i, expectedBits2[i]); \
         bitmapFilled.set(i); \
     } \
-    for (size_t i = 0; i < smallSize; ++i) \
-        bitmapSmallFilled.set(i);
+    for (size_t i = 0; i < smallSize; ++i) { \
+        bitmapSmall1.set(i, expectedSmallBits1[i]); \
+        bitmapSmall2.set(i, expectedSmallBits2[i]); \
+        bitmapSmallFilled.set(i); \
+    }
 
 template<typename WordType>
 void testBitmapSize()
@@ -960,6 +975,47 @@ void testBitmapSetAndClear()
     ASSERT_TRUE(bitmapSmallFilled.isEmpty());
 }
 
+template<typename Bitmap>
+void testBitmapSetEachNthBitImpl(size_t size, size_t wordSize, const Bitmap& zeroes, const Bitmap& ones)
+{
+    Bitmap temp;
+
+    EXPECT_TRUE(temp == zeroes);
+    temp.setEachNthBit(0, 1);
+    EXPECT_TRUE(temp == ones);
+
+    size_t nValues[] = { 1, 2, wordSize / 2, wordSize - 1, wordSize, size / 2, size - 1, size };
+    size_t nValuesCount = sizeof(nValues) / sizeof(nValues[0]);
+
+    for (size_t start = 0; start < wordSize; ++start) {
+        for (size_t j = 0; j < nValuesCount; ++j) {
+            size_t n = nValues[j];
+            temp.clearAll();
+            temp.setEachNthBit(start, n);
+
+            for (size_t i = 0; i < start; ++i)
+                EXPECT_FALSE(temp.get(i));
+
+            size_t count = 0;
+            for (size_t i = start; i < size; ++i) {
+                bool expected = !count;
+                EXPECT_TRUE(temp.get(i) == expected);
+                count++;
+                count = count % n;
+            }
+        }
+    }
+}
+
+template<typename WordType>
+void testBitmapSetEachNthBit()
+{
+    DECLARE_AND_INIT_BITMAPS_FOR_TEST();
+    constexpr size_t wordSize = sizeof(WordType) * 8;
+    testBitmapSetEachNthBitImpl(size, wordSize, bitmap0, bitmapFilled);
+    testBitmapSetEachNthBitImpl(smallSize, wordSize, bitmapSmallZeroed, bitmapSmallFilled);
+}
+
 template<typename WordType>
 void testBitmapOperatorEqual()
 {
@@ -990,6 +1046,250 @@ void testBitmapOperatorNotEqual()
     EXPECT_TRUE(bitmapSmallZeroed != bitmapSmallFilled);
 }
 
+template<typename Bitmap>
+void testBitmapOperatorAssignmentImpl(const Bitmap& bitmap1, const Bitmap& bitmap2, const Bitmap& zeroes, const Bitmap& ones)
+{
+    Bitmap temp;
+    Bitmap temp2;
+    EXPECT_TRUE(temp.isEmpty());
+    EXPECT_TRUE(temp2.isEmpty());
+
+    EXPECT_TRUE(temp == zeroes);
+    EXPECT_TRUE(temp != bitmap1);
+    temp = bitmap1;
+    EXPECT_TRUE(temp != zeroes);
+    EXPECT_TRUE(temp == bitmap1);
+
+    EXPECT_TRUE(temp != bitmap2);
+    temp = bitmap2;
+    EXPECT_TRUE(temp == bitmap2);
+    EXPECT_TRUE(temp != bitmap1);
+
+    temp.clearAll();
+    temp2.clearAll();
+    for (size_t i = 0; i < bitmap1.size(); ++i)
+        temp.set(i, bitmap1.get(i));
+
+    EXPECT_TRUE(temp == bitmap1);
+    EXPECT_TRUE(temp2.isEmpty());
+    EXPECT_TRUE(temp2 != bitmap1);
+    temp2 = temp;
+    EXPECT_TRUE(temp2 == bitmap1);
+}
+
+template<typename WordType>
+void testBitmapOperatorAssignment()
+{
+    DECLARE_AND_INIT_BITMAPS_FOR_TEST();
+    testBitmapOperatorAssignmentImpl(bitmap1, bitmap2, bitmap0, bitmapFilled);
+    testBitmapOperatorAssignmentImpl(bitmapSmall1, bitmapSmall2, bitmapSmallZeroed, bitmapSmallFilled);
+}
+
+template<typename Bitmap>
+void testBitmapOperatorBitOrAssignmentImpl(size_t size, const Bitmap& bitmap1, const Bitmap& bitmap2, const Bitmap& zeroes, const Bitmap& ones)
+{
+    Bitmap temp;
+    Bitmap temp1;
+
+    // 0 | 0
+    EXPECT_TRUE(temp == zeroes);
+    EXPECT_TRUE(temp != ones);
+    temp |= zeroes;
+    EXPECT_TRUE(temp == zeroes);
+    EXPECT_TRUE(temp != ones);
+
+    // 0 | 1
+    EXPECT_TRUE(temp == zeroes);
+    EXPECT_TRUE(temp != ones);
+    temp |= ones;
+    EXPECT_TRUE(temp != zeroes);
+    EXPECT_TRUE(temp == ones);
+
+    // 1 | 0
+    EXPECT_TRUE(temp != zeroes);
+    EXPECT_TRUE(temp == ones);
+    temp |= zeroes;
+    EXPECT_TRUE(temp != zeroes);
+    EXPECT_TRUE(temp == ones);
+
+    // 1 | 1
+    EXPECT_TRUE(temp != zeroes);
+    EXPECT_TRUE(temp == ones);
+    temp |= ones;
+    EXPECT_TRUE(temp != zeroes);
+    EXPECT_TRUE(temp == ones);
+
+    temp = zeroes;
+    EXPECT_TRUE(temp.isEmpty());
+    EXPECT_TRUE(temp != bitmap1);
+    temp |= bitmap1;
+    EXPECT_TRUE(temp == bitmap1);
+
+    temp |= bitmap2;
+    for (size_t i = 0; i < size; ++i)
+        EXPECT_EQ(temp.get(i), bitmap1.get(i) | bitmap2.get(i));
+
+    temp1 = temp;
+    EXPECT_TRUE(temp1 == temp);
+
+    temp |= zeroes;
+    EXPECT_TRUE(temp == temp1);
+    EXPECT_TRUE(temp != zeroes);
+
+    temp |= ones;
+    EXPECT_TRUE(temp != temp1);
+    EXPECT_TRUE(temp == ones);
+}
+
+template<typename WordType>
+void testBitmapOperatorBitOrAssignment()
+{
+    DECLARE_AND_INIT_BITMAPS_FOR_TEST();
+    testBitmapOperatorBitOrAssignmentImpl(size, bitmap1, bitmap2, bitmap0, bitmapFilled);
+    testBitmapOperatorBitOrAssignmentImpl(smallSize, bitmapSmall1, bitmapSmall2, bitmapSmallZeroed, bitmapSmallFilled);
+}
+
+template<typename Bitmap>
+void testBitmapOperatorBitAndAssignmentImpl(size_t size, const Bitmap& bitmap1, const Bitmap& bitmap2, const Bitmap& zeroes, const Bitmap& ones)
+{
+    Bitmap temp;
+    Bitmap temp1;
+
+    // 0 & 0
+    temp = zeroes;
+    EXPECT_TRUE(temp == zeroes);
+    EXPECT_TRUE(temp != ones);
+    temp &= zeroes;
+    EXPECT_TRUE(temp == zeroes);
+    EXPECT_TRUE(temp != ones);
+
+    // 0 & 1
+    temp = zeroes;
+    EXPECT_TRUE(temp == zeroes);
+    EXPECT_TRUE(temp != ones);
+    temp &= ones;
+    EXPECT_TRUE(temp == zeroes);
+    EXPECT_TRUE(temp != ones);
+
+    // 1 & 0
+    temp = ones;
+    EXPECT_TRUE(temp != zeroes);
+    EXPECT_TRUE(temp == ones);
+    temp &= zeroes;
+    EXPECT_TRUE(temp == zeroes);
+    EXPECT_TRUE(temp != ones);
+
+    // 1 & 1
+    temp = ones;
+    EXPECT_TRUE(temp != zeroes);
+    EXPECT_TRUE(temp == ones);
+    temp &= ones;
+    EXPECT_TRUE(temp != zeroes);
+    EXPECT_TRUE(temp == ones);
+
+    temp = ones;
+    EXPECT_TRUE(temp == ones);
+    EXPECT_TRUE(temp != bitmap1);
+    temp &= bitmap1;
+    EXPECT_TRUE(temp == bitmap1);
+
+    temp &= bitmap2;
+    for (size_t i = 0; i < size; ++i)
+        EXPECT_EQ(temp.get(i), bitmap1.get(i) & bitmap2.get(i));
+
+    EXPECT_TRUE(!temp.isEmpty());
+    temp1 = temp;
+    EXPECT_TRUE(temp1 == temp);
+
+    temp &= zeroes;
+    EXPECT_TRUE(temp != temp1);
+    EXPECT_TRUE(temp == zeroes);
+
+    temp = temp1;
+    temp &= ones;
+    EXPECT_TRUE(temp == temp1);
+    EXPECT_TRUE(temp != ones);
+}
+
+template<typename WordType>
+void testBitmapOperatorBitAndAssignment()
+{
+    DECLARE_AND_INIT_BITMAPS_FOR_TEST();
+    testBitmapOperatorBitAndAssignmentImpl(size, bitmap1, bitmap2, bitmap0, bitmapFilled);
+    testBitmapOperatorBitAndAssignmentImpl(smallSize, bitmapSmall1, bitmapSmall2, bitmapSmallZeroed, bitmapSmallFilled);
+}
+
+template<typename Bitmap>
+void testBitmapOperatorBitXorAssignmentImpl(size_t size, const Bitmap& bitmap1, const Bitmap& bitmap2, const Bitmap& zeroes, const Bitmap& ones)
+{
+    Bitmap temp;
+    Bitmap temp1;
+
+    // 0 ^ 0
+    temp = zeroes;
+    EXPECT_TRUE(temp == zeroes);
+    EXPECT_TRUE(temp != ones);
+    temp ^= zeroes;
+    EXPECT_TRUE(temp == zeroes);
+    EXPECT_TRUE(temp != ones);
+
+    // 0 ^ 1
+    temp = zeroes;
+    EXPECT_TRUE(temp == zeroes);
+    EXPECT_TRUE(temp != ones);
+    temp ^= ones;
+    EXPECT_TRUE(temp != zeroes);
+    EXPECT_TRUE(temp == ones);
+
+    // 1 ^ 0
+    temp = ones;
+    EXPECT_TRUE(temp != zeroes);
+    EXPECT_TRUE(temp == ones);
+    temp ^= zeroes;
+    EXPECT_TRUE(temp != zeroes);
+    EXPECT_TRUE(temp == ones);
+
+    // 1 ^ 1
+    temp = ones;
+    EXPECT_TRUE(temp != zeroes);
+    EXPECT_TRUE(temp == ones);
+    temp ^= ones;
+    EXPECT_TRUE(temp == zeroes);
+    EXPECT_TRUE(temp != ones);
+
+    temp.clearAll();
+    EXPECT_TRUE(temp.isEmpty());
+    EXPECT_TRUE(temp != bitmap1);
+    temp ^= bitmap1;
+    EXPECT_TRUE(temp == bitmap1);
+
+    temp ^= bitmap2;
+    for (size_t i = 0; i < size; ++i)
+        EXPECT_EQ(temp.get(i), bitmap1.get(i) ^ bitmap2.get(i));
+
+    temp1 = temp;
+    EXPECT_TRUE(temp1 == temp);
+
+    temp ^= zeroes;
+    EXPECT_TRUE(temp == temp1);
+    EXPECT_TRUE(temp != zeroes);
+
+    temp ^= ones;
+    EXPECT_TRUE(temp != temp1);
+    EXPECT_TRUE(temp != ones);
+    temp1.invert();
+    EXPECT_TRUE(temp == temp1);
+    EXPECT_TRUE(temp != ones);
+}
+
+template<typename WordType>
+void testBitmapOperatorBitXorAssignment()
+{
+    DECLARE_AND_INIT_BITMAPS_FOR_TEST();
+    testBitmapOperatorBitXorAssignmentImpl(size, bitmap1, bitmap2, bitmap0, bitmapFilled);
+    testBitmapOperatorBitXorAssignmentImpl(smallSize, bitmapSmall1, bitmapSmall2, bitmapSmallZeroed, bitmapSmallFilled);
+}
+
 template<typename WordType>
 void testBitmapHash()
 {
@@ -1076,8 +1376,13 @@ TEST(WTF_Bitmap, FindBit_uint32_t) { testBitmapFindBit<uint32_t>(); }
 TEST(WTF_Bitmap, Iteration_uint32_t) { testBitmapIteration<uint32_t>(); }
 TEST(WTF_Bitmap, MergeAndClear_uint32_t) { testBitmapMergeAndClear<uint32_t>(); }
 TEST(WTF_Bitmap, SetAndClear_uint32_t) { testBitmapSetAndClear<uint32_t>(); }
+TEST(WTF_Bitmap, SetEachNthBit_uint32_t) { testBitmapSetEachNthBit<uint32_t>(); }
 TEST(WTF_Bitmap, OperatorEqualAccess_uint32_t) { testBitmapOperatorEqual<uint32_t>(); }
 TEST(WTF_Bitmap, OperatorNotEqualAccess_uint32_t) { testBitmapOperatorNotEqual<uint32_t>(); }
+TEST(WTF_Bitmap, OperatorAssignment_uint32_t) { testBitmapOperatorAssignment<uint32_t>(); }
+TEST(WTF_Bitmap, OperatorBitOrAssignment_uint32_t) { testBitmapOperatorBitOrAssignment<uint32_t>(); }
+TEST(WTF_Bitmap, OperatorBitAndAssignment_uint32_t) { testBitmapOperatorBitAndAssignment<uint32_t>(); }
+TEST(WTF_Bitmap, OperatorBitXorAssignment_uint32_t) { testBitmapOperatorBitXorAssignment<uint32_t>(); }
 TEST(WTF_Bitmap, Hash_uint32_t) { testBitmapHash<uint32_t>(); }
 
 #if CPU(REGISTER64)
@@ -1106,8 +1411,13 @@ TEST(WTF_Bitmap, FindBit_uint64_t) { testBitmapFindBit<uint64_t>(); }
 TEST(WTF_Bitmap, Iteration_uint64_t) { testBitmapIteration<uint64_t>(); }
 TEST(WTF_Bitmap, MergeAndClear_uint64_t) { testBitmapMergeAndClear<uint64_t>(); }
 TEST(WTF_Bitmap, SetAndClear_uint64_t) { testBitmapSetAndClear<uint64_t>(); }
+TEST(WTF_Bitmap, SetEachNthBit_uint64_t) { testBitmapSetEachNthBit<uint64_t>(); }
 TEST(WTF_Bitmap, OperatorEqualAccess_uint64_t) { testBitmapOperatorEqual<uint64_t>(); }
 TEST(WTF_Bitmap, OperatorNotEqualAccess_uint64_t) { testBitmapOperatorNotEqual<uint64_t>(); }
+TEST(WTF_Bitmap, OperatorAssignment_uint64_t) { testBitmapOperatorAssignment<uint64_t>(); }
+TEST(WTF_Bitmap, OperatorBitOrAssignment_uint64_t) { testBitmapOperatorBitOrAssignment<uint64_t>(); }
+TEST(WTF_Bitmap, OperatorBitAndAssignment_uint64_t) { testBitmapOperatorBitAndAssignment<uint64_t>(); }
+TEST(WTF_Bitmap, OperatorBitXorAssignment_uint64_t) { testBitmapOperatorBitXorAssignment<uint64_t>(); }
 TEST(WTF_Bitmap, Hash_uint64_t) { testBitmapHash<uint64_t>(); }
 
 #endif // CPU(REGISTER64)