| 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 |
} |