compiler-rt/lib/sanitizer_common/tests/sanitizer_bitvector_test.cpp

   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 }