1 //===-- sanitizer_bitvector_test.cpp --------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file is a part of Sanitizer runtime. 10 // Tests for sanitizer_bitvector.h. 11 // 12 //===----------------------------------------------------------------------===// 13 #include "sanitizer_common/sanitizer_bitvector.h" 14 15 #include "sanitizer_test_utils.h" 16 17 #include "gtest/gtest.h" 18 19 #include <algorithm> 20 #include <vector> 21 #include <random> 22 #include <set> 23 24 using namespace __sanitizer; 25 using namespace std; 26 27 28 // Check the 'bv' == 's' and that the indexes go in increasing order. 29 // Also check the BV::Iterator 30 template <class BV> 31 static void CheckBV(const BV &bv, const set<uptr> &s) { 32 BV t; 33 t.copyFrom(bv); 34 set<uptr> t_s(s); 35 uptr last_idx = bv.size(); 36 uptr count = 0; 37 for (typename BV::Iterator it(bv); it.hasNext();) { 38 uptr idx = it.next(); 39 count++; 40 if (last_idx != bv.size()) 41 EXPECT_LT(last_idx, idx); 42 last_idx = idx; 43 EXPECT_TRUE(s.count(idx)); 44 } 45 EXPECT_EQ(count, s.size()); 46 47 last_idx = bv.size(); 48 while (!t.empty()) { 49 uptr idx = t.getAndClearFirstOne(); 50 if (last_idx != bv.size()) 51 EXPECT_LT(last_idx, idx); 52 last_idx = idx; 53 EXPECT_TRUE(t_s.erase(idx)); 54 } 55 EXPECT_TRUE(t_s.empty()); 56 } 57 58 template <class BV> 59 void Print(const BV &bv) { 60 BV t; 61 t.copyFrom(bv); 62 while (!t.empty()) { 63 uptr idx = t.getAndClearFirstOne(); 64 fprintf(stderr, "%lu ", idx); 65 } 66 fprintf(stderr, "\n"); 67 } 68 69 void Print(const set<uptr> &s) { 70 for (set<uptr>::iterator it = s.begin(); it != s.end(); ++it) { 71 fprintf(stderr, "%lu ", *it); 72 } 73 fprintf(stderr, "\n"); 74 } 75 76 template <class BV> 77 void TestBitVector(uptr expected_size) { 78 std::mt19937 r; 79 BV bv, bv1, t_bv; 80 EXPECT_EQ(expected_size, BV::kSize); 81 bv.clear(); 82 EXPECT_TRUE(bv.empty()); 83 bv.setBit(5); 84 EXPECT_FALSE(bv.empty()); 85 EXPECT_FALSE(bv.getBit(4)); 86 EXPECT_FALSE(bv.getBit(6)); 87 EXPECT_TRUE(bv.getBit(5)); 88 bv.clearBit(5); 89 EXPECT_FALSE(bv.getBit(5)); 90 91 // test random bits 92 bv.clear(); 93 set<uptr> s; 94 for (uptr it = 0; it < 1000; it++) { 95 uptr bit = ((uptr)my_rand() % bv.size()); 96 EXPECT_EQ(bv.getBit(bit), s.count(bit) == 1); 97 switch (my_rand() % 2) { 98 case 0: 99 EXPECT_EQ(bv.setBit(bit), s.insert(bit).second); 100 break; 101 case 1: 102 size_t old_size = s.size(); 103 s.erase(bit); 104 EXPECT_EQ(bv.clearBit(bit), old_size > s.size()); 105 break; 106 } 107 EXPECT_EQ(bv.getBit(bit), s.count(bit) == 1); 108 } 109 110 vector<uptr>bits(bv.size()); 111 // Test setUnion, setIntersection, setDifference, 112 // intersectsWith, and getAndClearFirstOne. 113 for (uptr it = 0; it < 30; it++) { 114 // iota 115 for (size_t j = 0; j < bits.size(); j++) bits[j] = j; 116 std::shuffle(bits.begin(), bits.end(), r); 117 set<uptr> s, s1, t_s; 118 bv.clear(); 119 bv1.clear(); 120 uptr n_bits = ((uptr)my_rand() % bv.size()) + 1; 121 uptr n_bits1 = (uptr)my_rand() % (bv.size() / 2); 122 EXPECT_TRUE(n_bits > 0 && n_bits <= bv.size()); 123 EXPECT_TRUE(n_bits1 < bv.size() / 2); 124 for (uptr i = 0; i < n_bits; i++) { 125 bv.setBit(bits[i]); 126 s.insert(bits[i]); 127 } 128 CheckBV(bv, s); 129 for (uptr i = 0; i < n_bits1; i++) { 130 bv1.setBit(bits[bv.size() / 2 + i]); 131 s1.insert(bits[bv.size() / 2 + i]); 132 } 133 CheckBV(bv1, s1); 134 135 vector<uptr> vec; 136 set_intersection(s.begin(), s.end(), s1.begin(), s1.end(), 137 back_insert_iterator<vector<uptr> >(vec)); 138 EXPECT_EQ(bv.intersectsWith(bv1), !vec.empty()); 139 140 // setUnion 141 t_s = s; 142 t_bv.copyFrom(bv); 143 t_s.insert(s1.begin(), s1.end()); 144 EXPECT_EQ(t_bv.setUnion(bv1), s.size() != t_s.size()); 145 CheckBV(t_bv, t_s); 146 147 // setIntersection 148 t_s = set<uptr>(vec.begin(), vec.end()); 149 t_bv.copyFrom(bv); 150 EXPECT_EQ(t_bv.setIntersection(bv1), s.size() != t_s.size()); 151 CheckBV(t_bv, t_s); 152 153 // setDifference 154 vec.clear(); 155 set_difference(s.begin(), s.end(), s1.begin(), s1.end(), 156 back_insert_iterator<vector<uptr> >(vec)); 157 t_s = set<uptr>(vec.begin(), vec.end()); 158 t_bv.copyFrom(bv); 159 EXPECT_EQ(t_bv.setDifference(bv1), s.size() != t_s.size()); 160 CheckBV(t_bv, t_s); 161 } 162 } 163 164 TEST(SanitizerCommon, BasicBitVector) { 165 TestBitVector<BasicBitVector<u8> >(8); 166 TestBitVector<BasicBitVector<u16> >(16); 167 TestBitVector<BasicBitVector<> >(SANITIZER_WORDSIZE); 168 } 169 170 TEST(SanitizerCommon, TwoLevelBitVector) { 171 uptr ws = SANITIZER_WORDSIZE; 172 TestBitVector<TwoLevelBitVector<1, BasicBitVector<u8> > >(8 * 8); 173 TestBitVector<TwoLevelBitVector<> >(ws * ws); 174 TestBitVector<TwoLevelBitVector<2> >(ws * ws * 2); 175 TestBitVector<TwoLevelBitVector<3> >(ws * ws * 3); 176 TestBitVector<TwoLevelBitVector<3, BasicBitVector<u16> > >(16 * 16 * 3); 177 } 178