Changeset 262030 in webkit


Ignore:
Timestamp:
May 21, 2020 3:12:43 PM (4 years ago)
Author:
mark.lam@apple.com
Message:

Add more Bitmap methods.
​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):

Location:
trunk
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WTF/ChangeLog

    r262022 r262030  
     12020-05-20  Mark Lam  <mark.lam@apple.com>
     2
     3        Add more Bitmap methods.
     4        https://bugs.webkit.org/show_bug.cgi?id=212190
     5        <rdar://problem/63481333>
     6
     7        Reviewed by Robin Morisset.
     8
     9        Specifically,
     10            setEachNthBit - sets every Nth bit starting at a specified start bit
     11            operator=     - assignment
     12            operator|=    - bit or and assignment
     13            operator&=    - bit and and assignment
     14            operator^=    - bit xor and assignment
     15
     16        * wtf/Bitmap.h:
     17
    1182020-05-21  Yoshiaki Jitsukawa  <yoshiaki.jitsukawa@sony.com>
    219

  • trunk/Source/WTF/wtf/Bitmap.h

    r261827 r262030  
    119119    void mergeAndClear(Bitmap&);
    120120    void setAndClear(Bitmap&);
    121    
     121
     122    void setEachNthBit(size_t start, size_t n);
     123
    122124    bool operator==(const Bitmap&) const;
    123125    bool operator!=(const Bitmap&) const;
    124    
     126
     127    void operator=(const Bitmap&);
     128    void operator|=(const Bitmap&);
     129    void operator&=(const Bitmap&);
     130    void operator^=(const Bitmap&);
     131
    125132    unsigned hash() const;
    126133
    … …  
    424431
    425432template<size_t bitmapSize, typename WordType>
     433inline void Bitmap<bitmapSize, WordType>::setEachNthBit(size_t start, size_t n)
     434{
     435    size_t index = start;
     436    size_t wordIndex = index / wordSize;
     437    index = index - wordIndex * wordSize;
     438    while (wordIndex < words) {
     439        while (index < wordSize) {
     440            bits[wordIndex] |= (one << index);
     441            index += n;
     442        }
     443        index -= wordSize;
     444        wordIndex++;
     445    }
     446    if constexpr (!!(bitmapSize % wordSize)) {
     447        constexpr size_t remainingBits = bitmapSize % wordSize;
     448        constexpr WordType mask = (static_cast<WordType>(1) << remainingBits) - 1;
     449        bits[words - 1] &= mask;
     450    }
     451}
     452
     453template<size_t bitmapSize, typename WordType>
    426454inline bool Bitmap<bitmapSize, WordType>::operator==(const Bitmap& other) const
    427455{
    … …  
    440468
    441469template<size_t bitmapSize, typename WordType>
     470inline void Bitmap<bitmapSize, WordType>::operator=(const Bitmap& other)
     471{
     472    for (size_t i = 0; i < words; ++i)
     473        bits[i] = other.bits[i];
     474}
     475
     476template<size_t bitmapSize, typename WordType>
     477inline void Bitmap<bitmapSize, WordType>::operator|=(const Bitmap& other)
     478{
     479    for (size_t i = 0; i < words; ++i)
     480        bits[i] |= other.bits[i];
     481}
     482
     483template<size_t bitmapSize, typename WordType>
     484inline void Bitmap<bitmapSize, WordType>::operator&=(const Bitmap& other)
     485{
     486    for (size_t i = 0; i < words; ++i)
     487        bits[i] &= other.bits[i];
     488}
     489
     490template<size_t bitmapSize, typename WordType>
     491inline void Bitmap<bitmapSize, WordType>::operator^=(const Bitmap& other)
     492{
     493    for (size_t i = 0; i < words; ++i)
     494        bits[i] ^= other.bits[i];
     495}
     496
     497template<size_t bitmapSize, typename WordType>
    442498inline unsigned Bitmap<bitmapSize, WordType>::hash() const
    443499{

  • trunk/Tools/ChangeLog

    r262022 r262030  
     12020-05-20  Mark Lam  <mark.lam@apple.com>
     2
     3        Add more Bitmap methods.
     4        https://bugs.webkit.org/show_bug.cgi?id=212190
     5        <rdar://problem/63481333>
     6
     7        Reviewed by Robin Morisset.
     8
     9        Added test coverage for the new WTF::Bitmap methods.
     10
     11        * TestWebKitAPI/Tests/WTF/Bitmap.cpp:
     12        (TestWebKitAPI::testBitmapSetEachNthBit):
     13        (TestWebKitAPI::testBitmapOperatorAssignment):
     14        (TestWebKitAPI::testBitmapOperatorBitOrAssignment):
     15        (TestWebKitAPI::testBitmapOperatorBitAndAssignment):
     16        (TestWebKitAPI::testBitmapOperatorBitXorAssignment):
     17        (TestWebKitAPI::TEST):
     18
    1192020-05-21  Yoshiaki Jitsukawa  <yoshiaki.jitsukawa@sony.com>
    220

  • trunk/Tools/TestWebKitAPI/Tests/WTF/Bitmap.cpp

    r261179 r262030  
    7171};
    7272
     73static constexpr bool expectedSmallBits1[smallSize] = {
     74    false, true, true,  false,  true,  false, false, true,
     75    true,
     76};
     77
     78static constexpr bool expectedSmallBits2[smallSize] = {
     79    true,  true, false, false,  false, false, true,  true,
     80    false,
     81};
     82
    7383constexpr size_t countBits(const bool boolArray[], size_t size)
    7484{
    … …  
    91101    Bitmap<size, WordType> bitmapFilled; \
    92102    Bitmap<smallSize, WordType> bitmapSmallZeroed; \
    93     Bitmap<smallSize, WordType> bitmapSmallFilled;
     103    Bitmap<smallSize, WordType> bitmapSmallFilled; \
     104    Bitmap<smallSize, WordType> bitmapSmall1; /* Will hold values specified in expectedSmallBits1. */ \
     105    Bitmap<smallSize, WordType> bitmapSmall2; /* Will hold values specified in expectedSmallBits2. */ \
    94106
    95107#define DECLARE_AND_INIT_BITMAPS_FOR_TEST() \
    … …  
    101113        bitmapFilled.set(i); \
    102114    } \
    103     for (size_t i = 0; i < smallSize; ++i) \
    104         bitmapSmallFilled.set(i);
     115    for (size_t i = 0; i < smallSize; ++i) { \
     116        bitmapSmall1.set(i, expectedSmallBits1[i]); \
     117        bitmapSmall2.set(i, expectedSmallBits2[i]); \
     118        bitmapSmallFilled.set(i); \
     119    }
    105120
    106121template<typename WordType>
    … …  
    961976}
    962977
     978template<typename Bitmap>
     979void testBitmapSetEachNthBitImpl(size_t size, size_t wordSize, const Bitmap& zeroes, const Bitmap& ones)
     980{
     981    Bitmap temp;
     982
     983    EXPECT_TRUE(temp == zeroes);
     984    temp.setEachNthBit(0, 1);
     985    EXPECT_TRUE(temp == ones);
     986
     987    size_t nValues[] = { 1, 2, wordSize / 2, wordSize - 1, wordSize, size / 2, size - 1, size };
     988    size_t nValuesCount = sizeof(nValues) / sizeof(nValues[0]);
     989
     990    for (size_t start = 0; start < wordSize; ++start) {
     991        for (size_t j = 0; j < nValuesCount; ++j) {
     992            size_t n = nValues[j];
     993            temp.clearAll();
     994            temp.setEachNthBit(start, n);
     995
     996            for (size_t i = 0; i < start; ++i)
     997                EXPECT_FALSE(temp.get(i));
     998
     999            size_t count = 0;
     1000            for (size_t i = start; i < size; ++i) {
     1001                bool expected = !count;
     1002                EXPECT_TRUE(temp.get(i) == expected);
     1003                count++;
     1004                count = count % n;
     1005            }
     1006        }
     1007    }
     1008}
     1009
     1010template<typename WordType>
     1011void testBitmapSetEachNthBit()
     1012{
     1013    DECLARE_AND_INIT_BITMAPS_FOR_TEST();
     1014    constexpr size_t wordSize = sizeof(WordType) * 8;
     1015    testBitmapSetEachNthBitImpl(size, wordSize, bitmap0, bitmapFilled);
     1016    testBitmapSetEachNthBitImpl(smallSize, wordSize, bitmapSmallZeroed, bitmapSmallFilled);
     1017}
     1018
    9631019template<typename WordType>
    9641020void testBitmapOperatorEqual()
    … …  
    9891045    EXPECT_TRUE(bitmapFilled != bitmap1);
    9901046    EXPECT_TRUE(bitmapSmallZeroed != bitmapSmallFilled);
     1047}
     1048
     1049template<typename Bitmap>
     1050void testBitmapOperatorAssignmentImpl(const Bitmap& bitmap1, const Bitmap& bitmap2, const Bitmap& zeroes, const Bitmap& ones)
     1051{
     1052    Bitmap temp;
     1053    Bitmap temp2;
     1054    EXPECT_TRUE(temp.isEmpty());
     1055    EXPECT_TRUE(temp2.isEmpty());
     1056
     1057    EXPECT_TRUE(temp == zeroes);
     1058    EXPECT_TRUE(temp != bitmap1);
     1059    temp = bitmap1;
     1060    EXPECT_TRUE(temp != zeroes);
     1061    EXPECT_TRUE(temp == bitmap1);
     1062
     1063    EXPECT_TRUE(temp != bitmap2);
     1064    temp = bitmap2;
     1065    EXPECT_TRUE(temp == bitmap2);
     1066    EXPECT_TRUE(temp != bitmap1);
     1067
     1068    temp.clearAll();
     1069    temp2.clearAll();
     1070    for (size_t i = 0; i < bitmap1.size(); ++i)
     1071        temp.set(i, bitmap1.get(i));
     1072
     1073    EXPECT_TRUE(temp == bitmap1);
     1074    EXPECT_TRUE(temp2.isEmpty());
     1075    EXPECT_TRUE(temp2 != bitmap1);
     1076    temp2 = temp;
     1077    EXPECT_TRUE(temp2 == bitmap1);
     1078}
     1079
     1080template<typename WordType>
     1081void testBitmapOperatorAssignment()
     1082{
     1083    DECLARE_AND_INIT_BITMAPS_FOR_TEST();
     1084    testBitmapOperatorAssignmentImpl(bitmap1, bitmap2, bitmap0, bitmapFilled);
     1085    testBitmapOperatorAssignmentImpl(bitmapSmall1, bitmapSmall2, bitmapSmallZeroed, bitmapSmallFilled);
     1086}
     1087
     1088template<typename Bitmap>
     1089void testBitmapOperatorBitOrAssignmentImpl(size_t size, const Bitmap& bitmap1, const Bitmap& bitmap2, const Bitmap& zeroes, const Bitmap& ones)
     1090{
     1091    Bitmap temp;
     1092    Bitmap temp1;
     1093
     1094    // 0 | 0
     1095    EXPECT_TRUE(temp == zeroes);
     1096    EXPECT_TRUE(temp != ones);
     1097    temp |= zeroes;
     1098    EXPECT_TRUE(temp == zeroes);
     1099    EXPECT_TRUE(temp != ones);
     1100
     1101    // 0 | 1
     1102    EXPECT_TRUE(temp == zeroes);
     1103    EXPECT_TRUE(temp != ones);
     1104    temp |= ones;
     1105    EXPECT_TRUE(temp != zeroes);
     1106    EXPECT_TRUE(temp == ones);
     1107
     1108    // 1 | 0
     1109    EXPECT_TRUE(temp != zeroes);
     1110    EXPECT_TRUE(temp == ones);
     1111    temp |= zeroes;
     1112    EXPECT_TRUE(temp != zeroes);
     1113    EXPECT_TRUE(temp == ones);
     1114
     1115    // 1 | 1
     1116    EXPECT_TRUE(temp != zeroes);
     1117    EXPECT_TRUE(temp == ones);
     1118    temp |= ones;
     1119    EXPECT_TRUE(temp != zeroes);
     1120    EXPECT_TRUE(temp == ones);
     1121
     1122    temp = zeroes;
     1123    EXPECT_TRUE(temp.isEmpty());
     1124    EXPECT_TRUE(temp != bitmap1);
     1125    temp |= bitmap1;
     1126    EXPECT_TRUE(temp == bitmap1);
     1127
     1128    temp |= bitmap2;
     1129    for (size_t i = 0; i < size; ++i)
     1130        EXPECT_EQ(temp.get(i), bitmap1.get(i) | bitmap2.get(i));
     1131
     1132    temp1 = temp;
     1133    EXPECT_TRUE(temp1 == temp);
     1134
     1135    temp |= zeroes;
     1136    EXPECT_TRUE(temp == temp1);
     1137    EXPECT_TRUE(temp != zeroes);
     1138
     1139    temp |= ones;
     1140    EXPECT_TRUE(temp != temp1);
     1141    EXPECT_TRUE(temp == ones);
     1142}
     1143
     1144template<typename WordType>
     1145void testBitmapOperatorBitOrAssignment()
     1146{
     1147    DECLARE_AND_INIT_BITMAPS_FOR_TEST();
     1148    testBitmapOperatorBitOrAssignmentImpl(size, bitmap1, bitmap2, bitmap0, bitmapFilled);
     1149    testBitmapOperatorBitOrAssignmentImpl(smallSize, bitmapSmall1, bitmapSmall2, bitmapSmallZeroed, bitmapSmallFilled);
     1150}
     1151
     1152template<typename Bitmap>
     1153void testBitmapOperatorBitAndAssignmentImpl(size_t size, const Bitmap& bitmap1, const Bitmap& bitmap2, const Bitmap& zeroes, const Bitmap& ones)
     1154{
     1155    Bitmap temp;
     1156    Bitmap temp1;
     1157
     1158    // 0 & 0
     1159    temp = zeroes;
     1160    EXPECT_TRUE(temp == zeroes);
     1161    EXPECT_TRUE(temp != ones);
     1162    temp &= zeroes;
     1163    EXPECT_TRUE(temp == zeroes);
     1164    EXPECT_TRUE(temp != ones);
     1165
     1166    // 0 & 1
     1167    temp = zeroes;
     1168    EXPECT_TRUE(temp == zeroes);
     1169    EXPECT_TRUE(temp != ones);
     1170    temp &= ones;
     1171    EXPECT_TRUE(temp == zeroes);
     1172    EXPECT_TRUE(temp != ones);
     1173
     1174    // 1 & 0
     1175    temp = ones;
     1176    EXPECT_TRUE(temp != zeroes);
     1177    EXPECT_TRUE(temp == ones);
     1178    temp &= zeroes;
     1179    EXPECT_TRUE(temp == zeroes);
     1180    EXPECT_TRUE(temp != ones);
     1181
     1182    // 1 & 1
     1183    temp = ones;
     1184    EXPECT_TRUE(temp != zeroes);
     1185    EXPECT_TRUE(temp == ones);
     1186    temp &= ones;
     1187    EXPECT_TRUE(temp != zeroes);
     1188    EXPECT_TRUE(temp == ones);
     1189
     1190    temp = ones;
     1191    EXPECT_TRUE(temp == ones);
     1192    EXPECT_TRUE(temp != bitmap1);
     1193    temp &= bitmap1;
     1194    EXPECT_TRUE(temp == bitmap1);
     1195
     1196    temp &= bitmap2;
     1197    for (size_t i = 0; i < size; ++i)
     1198        EXPECT_EQ(temp.get(i), bitmap1.get(i) & bitmap2.get(i));
     1199
     1200    EXPECT_TRUE(!temp.isEmpty());
     1201    temp1 = temp;
     1202    EXPECT_TRUE(temp1 == temp);
     1203
     1204    temp &= zeroes;
     1205    EXPECT_TRUE(temp != temp1);
     1206    EXPECT_TRUE(temp == zeroes);
     1207
     1208    temp = temp1;
     1209    temp &= ones;
     1210    EXPECT_TRUE(temp == temp1);
     1211    EXPECT_TRUE(temp != ones);
     1212}
     1213
     1214template<typename WordType>
     1215void testBitmapOperatorBitAndAssignment()
     1216{
     1217    DECLARE_AND_INIT_BITMAPS_FOR_TEST();
     1218    testBitmapOperatorBitAndAssignmentImpl(size, bitmap1, bitmap2, bitmap0, bitmapFilled);
     1219    testBitmapOperatorBitAndAssignmentImpl(smallSize, bitmapSmall1, bitmapSmall2, bitmapSmallZeroed, bitmapSmallFilled);
     1220}
     1221
     1222template<typename Bitmap>
     1223void testBitmapOperatorBitXorAssignmentImpl(size_t size, const Bitmap& bitmap1, const Bitmap& bitmap2, const Bitmap& zeroes, const Bitmap& ones)
     1224{
     1225    Bitmap temp;
     1226    Bitmap temp1;
     1227
     1228    // 0 ^ 0
     1229    temp = zeroes;
     1230    EXPECT_TRUE(temp == zeroes);
     1231    EXPECT_TRUE(temp != ones);
     1232    temp ^= zeroes;
     1233    EXPECT_TRUE(temp == zeroes);
     1234    EXPECT_TRUE(temp != ones);
     1235
     1236    // 0 ^ 1
     1237    temp = zeroes;
     1238    EXPECT_TRUE(temp == zeroes);
     1239    EXPECT_TRUE(temp != ones);
     1240    temp ^= ones;
     1241    EXPECT_TRUE(temp != zeroes);
     1242    EXPECT_TRUE(temp == ones);
     1243
     1244    // 1 ^ 0
     1245    temp = ones;
     1246    EXPECT_TRUE(temp != zeroes);
     1247    EXPECT_TRUE(temp == ones);
     1248    temp ^= zeroes;
     1249    EXPECT_TRUE(temp != zeroes);
     1250    EXPECT_TRUE(temp == ones);
     1251
     1252    // 1 ^ 1
     1253    temp = ones;
     1254    EXPECT_TRUE(temp != zeroes);
     1255    EXPECT_TRUE(temp == ones);
     1256    temp ^= ones;
     1257    EXPECT_TRUE(temp == zeroes);
     1258    EXPECT_TRUE(temp != ones);
     1259
     1260    temp.clearAll();
     1261    EXPECT_TRUE(temp.isEmpty());
     1262    EXPECT_TRUE(temp != bitmap1);
     1263    temp ^= bitmap1;
     1264    EXPECT_TRUE(temp == bitmap1);
     1265
     1266    temp ^= bitmap2;
     1267    for (size_t i = 0; i < size; ++i)
     1268        EXPECT_EQ(temp.get(i), bitmap1.get(i) ^ bitmap2.get(i));
     1269
     1270    temp1 = temp;
     1271    EXPECT_TRUE(temp1 == temp);
     1272
     1273    temp ^= zeroes;
     1274    EXPECT_TRUE(temp == temp1);
     1275    EXPECT_TRUE(temp != zeroes);
     1276
     1277    temp ^= ones;
     1278    EXPECT_TRUE(temp != temp1);
     1279    EXPECT_TRUE(temp != ones);
     1280    temp1.invert();
     1281    EXPECT_TRUE(temp == temp1);
     1282    EXPECT_TRUE(temp != ones);
     1283}
     1284
     1285template<typename WordType>
     1286void testBitmapOperatorBitXorAssignment()
     1287{
     1288    DECLARE_AND_INIT_BITMAPS_FOR_TEST();
     1289    testBitmapOperatorBitXorAssignmentImpl(size, bitmap1, bitmap2, bitmap0, bitmapFilled);
     1290    testBitmapOperatorBitXorAssignmentImpl(smallSize, bitmapSmall1, bitmapSmall2, bitmapSmallZeroed, bitmapSmallFilled);
    9911291}
    9921292
    … …  
    10771377TEST(WTF_Bitmap, MergeAndClear_uint32_t) { testBitmapMergeAndClear<uint32_t>(); }
    10781378TEST(WTF_Bitmap, SetAndClear_uint32_t) { testBitmapSetAndClear<uint32_t>(); }
     1379TEST(WTF_Bitmap, SetEachNthBit_uint32_t) { testBitmapSetEachNthBit<uint32_t>(); }
    10791380TEST(WTF_Bitmap, OperatorEqualAccess_uint32_t) { testBitmapOperatorEqual<uint32_t>(); }
    10801381TEST(WTF_Bitmap, OperatorNotEqualAccess_uint32_t) { testBitmapOperatorNotEqual<uint32_t>(); }
     1382TEST(WTF_Bitmap, OperatorAssignment_uint32_t) { testBitmapOperatorAssignment<uint32_t>(); }
     1383TEST(WTF_Bitmap, OperatorBitOrAssignment_uint32_t) { testBitmapOperatorBitOrAssignment<uint32_t>(); }
     1384TEST(WTF_Bitmap, OperatorBitAndAssignment_uint32_t) { testBitmapOperatorBitAndAssignment<uint32_t>(); }
     1385TEST(WTF_Bitmap, OperatorBitXorAssignment_uint32_t) { testBitmapOperatorBitXorAssignment<uint32_t>(); }
    10811386TEST(WTF_Bitmap, Hash_uint32_t) { testBitmapHash<uint32_t>(); }
    10821387
    … …  
    11071412TEST(WTF_Bitmap, MergeAndClear_uint64_t) { testBitmapMergeAndClear<uint64_t>(); }
    11081413TEST(WTF_Bitmap, SetAndClear_uint64_t) { testBitmapSetAndClear<uint64_t>(); }
     1414TEST(WTF_Bitmap, SetEachNthBit_uint64_t) { testBitmapSetEachNthBit<uint64_t>(); }
    11091415TEST(WTF_Bitmap, OperatorEqualAccess_uint64_t) { testBitmapOperatorEqual<uint64_t>(); }
    11101416TEST(WTF_Bitmap, OperatorNotEqualAccess_uint64_t) { testBitmapOperatorNotEqual<uint64_t>(); }
     1417TEST(WTF_Bitmap, OperatorAssignment_uint64_t) { testBitmapOperatorAssignment<uint64_t>(); }
     1418TEST(WTF_Bitmap, OperatorBitOrAssignment_uint64_t) { testBitmapOperatorBitOrAssignment<uint64_t>(); }
     1419TEST(WTF_Bitmap, OperatorBitAndAssignment_uint64_t) { testBitmapOperatorBitAndAssignment<uint64_t>(); }
     1420TEST(WTF_Bitmap, OperatorBitXorAssignment_uint64_t) { testBitmapOperatorBitXorAssignment<uint64_t>(); }
    11111421TEST(WTF_Bitmap, Hash_uint64_t) { testBitmapHash<uint64_t>(); }
    11121422
Note: See TracChangeset for help on using the changeset viewer.