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 #if defined(_WIN64) 72 fprintf(stderr, "%llu ", *it); 73 #else 74 fprintf(stderr, "%zu ", *it); 75 #endif 76 } 77 fprintf(stderr, "\n"); 78 } 79 80 template <class BV> 81 void TestBitVector(uptr expected_size) { 82 std::mt19937 r; 83 BV bv, bv1, t_bv; 84 EXPECT_EQ(expected_size, BV::kSize); 85 bv.clear(); 86 EXPECT_TRUE(bv.empty()); 87 bv.setBit(5); 88 EXPECT_FALSE(bv.empty()); 89 EXPECT_FALSE(bv.getBit(4)); 90 EXPECT_FALSE(bv.getBit(6)); 91 EXPECT_TRUE(bv.getBit(5)); 92 bv.clearBit(5); 93 EXPECT_FALSE(bv.getBit(5)); 94 95 // test random bits 96 bv.clear(); 97 set<uptr> s; 98 for (uptr it = 0; it < 1000; it++) { 99 uptr bit = ((uptr)my_rand() % bv.size()); 100 EXPECT_EQ(bv.getBit(bit), s.count(bit) == 1); 101 switch (my_rand() % 2) { 102 case 0: 103 EXPECT_EQ(bv.setBit(bit), s.insert(bit).second); 104 break; 105 case 1: 106 size_t old_size = s.size(); 107 s.erase(bit); 108 EXPECT_EQ(bv.clearBit(bit), old_size > s.size()); 109 break; 110 } 111 EXPECT_EQ(bv.getBit(bit), s.count(bit) == 1); 112 } 113 114 vector<uptr>bits(bv.size()); 115 // Test setUnion, setIntersection, setDifference, 116 // intersectsWith, and getAndClearFirstOne. 117 for (uptr it = 0; it < 30; it++) { 118 // iota 119 for (size_t j = 0; j < bits.size(); j++) bits[j] = j; 120 std::shuffle(bits.begin(), bits.end(), r); 121 set<uptr> s, s1, t_s; 122 bv.clear(); 123 bv1.clear(); 124 uptr n_bits = ((uptr)my_rand() % bv.size()) + 1; 125 uptr n_bits1 = (uptr)my_rand() % (bv.size() / 2); 126 EXPECT_TRUE(n_bits > 0 && n_bits <= bv.size()); 127 EXPECT_TRUE(n_bits1 < bv.size() / 2); 128 for (uptr i = 0; i < n_bits; i++) { 129 bv.setBit(bits[i]); 130 s.insert(bits[i]); 131 } 132 CheckBV(bv, s); 133 for (uptr i = 0; i < n_bits1; i++) { 134 bv1.setBit(bits[bv.size() / 2 + i]); 135 s1.insert(bits[bv.size() / 2 + i]); 136 } 137 CheckBV(bv1, s1); 138 139 vector<uptr> vec; 140 set_intersection(s.begin(), s.end(), s1.begin(), s1.end(), 141 back_insert_iterator<vector<uptr> >(vec)); 142 EXPECT_EQ(bv.intersectsWith(bv1), !vec.empty()); 143 144 // setUnion 145 t_s = s; 146 t_bv.copyFrom(bv); 147 t_s.insert(s1.begin(), s1.end()); 148 EXPECT_EQ(t_bv.setUnion(bv1), s.size() != t_s.size()); 149 CheckBV(t_bv, t_s); 150 151 // setIntersection 152 t_s = set<uptr>(vec.begin(), vec.end()); 153 t_bv.copyFrom(bv); 154 EXPECT_EQ(t_bv.setIntersection(bv1), s.size() != t_s.size()); 155 CheckBV(t_bv, t_s); 156 157 // setDifference 158 vec.clear(); 159 set_difference(s.begin(), s.end(), s1.begin(), s1.end(), 160 back_insert_iterator<vector<uptr> >(vec)); 161 t_s = set<uptr>(vec.begin(), vec.end()); 162 t_bv.copyFrom(bv); 163 EXPECT_EQ(t_bv.setDifference(bv1), s.size() != t_s.size()); 164 CheckBV(t_bv, t_s); 165 } 166 } 167 168 TEST(SanitizerCommon, BasicBitVector) { 169 TestBitVector<BasicBitVector<u8> >(8); 170 TestBitVector<BasicBitVector<u16> >(16); 171 TestBitVector<BasicBitVector<> >(SANITIZER_WORDSIZE); 172 } 173 174 TEST(SanitizerCommon, TwoLevelBitVector) { 175 uptr ws = SANITIZER_WORDSIZE; 176 TestBitVector<TwoLevelBitVector<1, BasicBitVector<u8> > >(8 * 8); 177 TestBitVector<TwoLevelBitVector<> >(ws * ws); 178 TestBitVector<TwoLevelBitVector<2> >(ws * ws * 2); 179 TestBitVector<TwoLevelBitVector<3> >(ws * ws * 3); 180 TestBitVector<TwoLevelBitVector<3, BasicBitVector<u16> > >(16 * 16 * 3); 181 } 182