1*3cab2bb3Spatrick //===-- sanitizer_bitvector.h -----------------------------------*- C++ -*-===// 2*3cab2bb3Spatrick // 3*3cab2bb3Spatrick // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4*3cab2bb3Spatrick // See https://llvm.org/LICENSE.txt for license information. 5*3cab2bb3Spatrick // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6*3cab2bb3Spatrick // 7*3cab2bb3Spatrick //===----------------------------------------------------------------------===// 8*3cab2bb3Spatrick // 9*3cab2bb3Spatrick // Specializer BitVector implementation. 10*3cab2bb3Spatrick // 11*3cab2bb3Spatrick //===----------------------------------------------------------------------===// 12*3cab2bb3Spatrick 13*3cab2bb3Spatrick #ifndef SANITIZER_BITVECTOR_H 14*3cab2bb3Spatrick #define SANITIZER_BITVECTOR_H 15*3cab2bb3Spatrick 16*3cab2bb3Spatrick #include "sanitizer_common.h" 17*3cab2bb3Spatrick 18*3cab2bb3Spatrick namespace __sanitizer { 19*3cab2bb3Spatrick 20*3cab2bb3Spatrick // Fixed size bit vector based on a single basic integer. 21*3cab2bb3Spatrick template <class basic_int_t = uptr> 22*3cab2bb3Spatrick class BasicBitVector { 23*3cab2bb3Spatrick public: 24*3cab2bb3Spatrick enum SizeEnum : uptr { kSize = sizeof(basic_int_t) * 8 }; 25*3cab2bb3Spatrick size()26*3cab2bb3Spatrick uptr size() const { return kSize; } 27*3cab2bb3Spatrick // No CTOR. clear()28*3cab2bb3Spatrick void clear() { bits_ = 0; } setAll()29*3cab2bb3Spatrick void setAll() { bits_ = ~(basic_int_t)0; } empty()30*3cab2bb3Spatrick bool empty() const { return bits_ == 0; } 31*3cab2bb3Spatrick 32*3cab2bb3Spatrick // Returns true if the bit has changed from 0 to 1. setBit(uptr idx)33*3cab2bb3Spatrick bool setBit(uptr idx) { 34*3cab2bb3Spatrick basic_int_t old = bits_; 35*3cab2bb3Spatrick bits_ |= mask(idx); 36*3cab2bb3Spatrick return bits_ != old; 37*3cab2bb3Spatrick } 38*3cab2bb3Spatrick 39*3cab2bb3Spatrick // Returns true if the bit has changed from 1 to 0. clearBit(uptr idx)40*3cab2bb3Spatrick bool clearBit(uptr idx) { 41*3cab2bb3Spatrick basic_int_t old = bits_; 42*3cab2bb3Spatrick bits_ &= ~mask(idx); 43*3cab2bb3Spatrick return bits_ != old; 44*3cab2bb3Spatrick } 45*3cab2bb3Spatrick getBit(uptr idx)46*3cab2bb3Spatrick bool getBit(uptr idx) const { return (bits_ & mask(idx)) != 0; } 47*3cab2bb3Spatrick getAndClearFirstOne()48*3cab2bb3Spatrick uptr getAndClearFirstOne() { 49*3cab2bb3Spatrick CHECK(!empty()); 50*3cab2bb3Spatrick uptr idx = LeastSignificantSetBitIndex(bits_); 51*3cab2bb3Spatrick clearBit(idx); 52*3cab2bb3Spatrick return idx; 53*3cab2bb3Spatrick } 54*3cab2bb3Spatrick 55*3cab2bb3Spatrick // Do "this |= v" and return whether new bits have been added. setUnion(const BasicBitVector & v)56*3cab2bb3Spatrick bool setUnion(const BasicBitVector &v) { 57*3cab2bb3Spatrick basic_int_t old = bits_; 58*3cab2bb3Spatrick bits_ |= v.bits_; 59*3cab2bb3Spatrick return bits_ != old; 60*3cab2bb3Spatrick } 61*3cab2bb3Spatrick 62*3cab2bb3Spatrick // Do "this &= v" and return whether any bits have been removed. setIntersection(const BasicBitVector & v)63*3cab2bb3Spatrick bool setIntersection(const BasicBitVector &v) { 64*3cab2bb3Spatrick basic_int_t old = bits_; 65*3cab2bb3Spatrick bits_ &= v.bits_; 66*3cab2bb3Spatrick return bits_ != old; 67*3cab2bb3Spatrick } 68*3cab2bb3Spatrick 69*3cab2bb3Spatrick // Do "this &= ~v" and return whether any bits have been removed. setDifference(const BasicBitVector & v)70*3cab2bb3Spatrick bool setDifference(const BasicBitVector &v) { 71*3cab2bb3Spatrick basic_int_t old = bits_; 72*3cab2bb3Spatrick bits_ &= ~v.bits_; 73*3cab2bb3Spatrick return bits_ != old; 74*3cab2bb3Spatrick } 75*3cab2bb3Spatrick copyFrom(const BasicBitVector & v)76*3cab2bb3Spatrick void copyFrom(const BasicBitVector &v) { bits_ = v.bits_; } 77*3cab2bb3Spatrick 78*3cab2bb3Spatrick // Returns true if 'this' intersects with 'v'. intersectsWith(const BasicBitVector & v)79*3cab2bb3Spatrick bool intersectsWith(const BasicBitVector &v) const { 80*3cab2bb3Spatrick return (bits_ & v.bits_) != 0; 81*3cab2bb3Spatrick } 82*3cab2bb3Spatrick 83*3cab2bb3Spatrick // for (BasicBitVector<>::Iterator it(bv); it.hasNext();) { 84*3cab2bb3Spatrick // uptr idx = it.next(); 85*3cab2bb3Spatrick // use(idx); 86*3cab2bb3Spatrick // } 87*3cab2bb3Spatrick class Iterator { 88*3cab2bb3Spatrick public: Iterator()89*3cab2bb3Spatrick Iterator() { } Iterator(const BasicBitVector & bv)90*3cab2bb3Spatrick explicit Iterator(const BasicBitVector &bv) : bv_(bv) {} hasNext()91*3cab2bb3Spatrick bool hasNext() const { return !bv_.empty(); } next()92*3cab2bb3Spatrick uptr next() { return bv_.getAndClearFirstOne(); } clear()93*3cab2bb3Spatrick void clear() { bv_.clear(); } 94*3cab2bb3Spatrick private: 95*3cab2bb3Spatrick BasicBitVector bv_; 96*3cab2bb3Spatrick }; 97*3cab2bb3Spatrick 98*3cab2bb3Spatrick private: mask(uptr idx)99*3cab2bb3Spatrick basic_int_t mask(uptr idx) const { 100*3cab2bb3Spatrick CHECK_LT(idx, size()); 101*3cab2bb3Spatrick return (basic_int_t)1UL << idx; 102*3cab2bb3Spatrick } 103*3cab2bb3Spatrick basic_int_t bits_; 104*3cab2bb3Spatrick }; 105*3cab2bb3Spatrick 106*3cab2bb3Spatrick // Fixed size bit vector of (kLevel1Size*BV::kSize**2) bits. 107*3cab2bb3Spatrick // The implementation is optimized for better performance on 108*3cab2bb3Spatrick // sparse bit vectors, i.e. the those with few set bits. 109*3cab2bb3Spatrick template <uptr kLevel1Size = 1, class BV = BasicBitVector<> > 110*3cab2bb3Spatrick class TwoLevelBitVector { 111*3cab2bb3Spatrick // This is essentially a 2-level bit vector. 112*3cab2bb3Spatrick // Set bit in the first level BV indicates that there are set bits 113*3cab2bb3Spatrick // in the corresponding BV of the second level. 114*3cab2bb3Spatrick // This structure allows O(kLevel1Size) time for clear() and empty(), 115*3cab2bb3Spatrick // as well fast handling of sparse BVs. 116*3cab2bb3Spatrick public: 117*3cab2bb3Spatrick enum SizeEnum : uptr { kSize = BV::kSize * BV::kSize * kLevel1Size }; 118*3cab2bb3Spatrick // No CTOR. 119*3cab2bb3Spatrick size()120*3cab2bb3Spatrick uptr size() const { return kSize; } 121*3cab2bb3Spatrick clear()122*3cab2bb3Spatrick void clear() { 123*3cab2bb3Spatrick for (uptr i = 0; i < kLevel1Size; i++) 124*3cab2bb3Spatrick l1_[i].clear(); 125*3cab2bb3Spatrick } 126*3cab2bb3Spatrick setAll()127*3cab2bb3Spatrick void setAll() { 128*3cab2bb3Spatrick for (uptr i0 = 0; i0 < kLevel1Size; i0++) { 129*3cab2bb3Spatrick l1_[i0].setAll(); 130*3cab2bb3Spatrick for (uptr i1 = 0; i1 < BV::kSize; i1++) 131*3cab2bb3Spatrick l2_[i0][i1].setAll(); 132*3cab2bb3Spatrick } 133*3cab2bb3Spatrick } 134*3cab2bb3Spatrick empty()135*3cab2bb3Spatrick bool empty() const { 136*3cab2bb3Spatrick for (uptr i = 0; i < kLevel1Size; i++) 137*3cab2bb3Spatrick if (!l1_[i].empty()) 138*3cab2bb3Spatrick return false; 139*3cab2bb3Spatrick return true; 140*3cab2bb3Spatrick } 141*3cab2bb3Spatrick 142*3cab2bb3Spatrick // Returns true if the bit has changed from 0 to 1. setBit(uptr idx)143*3cab2bb3Spatrick bool setBit(uptr idx) { 144*3cab2bb3Spatrick check(idx); 145*3cab2bb3Spatrick uptr i0 = idx0(idx); 146*3cab2bb3Spatrick uptr i1 = idx1(idx); 147*3cab2bb3Spatrick uptr i2 = idx2(idx); 148*3cab2bb3Spatrick if (!l1_[i0].getBit(i1)) { 149*3cab2bb3Spatrick l1_[i0].setBit(i1); 150*3cab2bb3Spatrick l2_[i0][i1].clear(); 151*3cab2bb3Spatrick } 152*3cab2bb3Spatrick bool res = l2_[i0][i1].setBit(i2); 153*3cab2bb3Spatrick // Printf("%s: %zd => %zd %zd %zd; %d\n", __func__, 154*3cab2bb3Spatrick // idx, i0, i1, i2, res); 155*3cab2bb3Spatrick return res; 156*3cab2bb3Spatrick } 157*3cab2bb3Spatrick clearBit(uptr idx)158*3cab2bb3Spatrick bool clearBit(uptr idx) { 159*3cab2bb3Spatrick check(idx); 160*3cab2bb3Spatrick uptr i0 = idx0(idx); 161*3cab2bb3Spatrick uptr i1 = idx1(idx); 162*3cab2bb3Spatrick uptr i2 = idx2(idx); 163*3cab2bb3Spatrick bool res = false; 164*3cab2bb3Spatrick if (l1_[i0].getBit(i1)) { 165*3cab2bb3Spatrick res = l2_[i0][i1].clearBit(i2); 166*3cab2bb3Spatrick if (l2_[i0][i1].empty()) 167*3cab2bb3Spatrick l1_[i0].clearBit(i1); 168*3cab2bb3Spatrick } 169*3cab2bb3Spatrick return res; 170*3cab2bb3Spatrick } 171*3cab2bb3Spatrick getBit(uptr idx)172*3cab2bb3Spatrick bool getBit(uptr idx) const { 173*3cab2bb3Spatrick check(idx); 174*3cab2bb3Spatrick uptr i0 = idx0(idx); 175*3cab2bb3Spatrick uptr i1 = idx1(idx); 176*3cab2bb3Spatrick uptr i2 = idx2(idx); 177*3cab2bb3Spatrick // Printf("%s: %zd => %zd %zd %zd\n", __func__, idx, i0, i1, i2); 178*3cab2bb3Spatrick return l1_[i0].getBit(i1) && l2_[i0][i1].getBit(i2); 179*3cab2bb3Spatrick } 180*3cab2bb3Spatrick getAndClearFirstOne()181*3cab2bb3Spatrick uptr getAndClearFirstOne() { 182*3cab2bb3Spatrick for (uptr i0 = 0; i0 < kLevel1Size; i0++) { 183*3cab2bb3Spatrick if (l1_[i0].empty()) continue; 184*3cab2bb3Spatrick uptr i1 = l1_[i0].getAndClearFirstOne(); 185*3cab2bb3Spatrick uptr i2 = l2_[i0][i1].getAndClearFirstOne(); 186*3cab2bb3Spatrick if (!l2_[i0][i1].empty()) 187*3cab2bb3Spatrick l1_[i0].setBit(i1); 188*3cab2bb3Spatrick uptr res = i0 * BV::kSize * BV::kSize + i1 * BV::kSize + i2; 189*3cab2bb3Spatrick // Printf("getAndClearFirstOne: %zd %zd %zd => %zd\n", i0, i1, i2, res); 190*3cab2bb3Spatrick return res; 191*3cab2bb3Spatrick } 192*3cab2bb3Spatrick CHECK(0); 193*3cab2bb3Spatrick return 0; 194*3cab2bb3Spatrick } 195*3cab2bb3Spatrick 196*3cab2bb3Spatrick // Do "this |= v" and return whether new bits have been added. setUnion(const TwoLevelBitVector & v)197*3cab2bb3Spatrick bool setUnion(const TwoLevelBitVector &v) { 198*3cab2bb3Spatrick bool res = false; 199*3cab2bb3Spatrick for (uptr i0 = 0; i0 < kLevel1Size; i0++) { 200*3cab2bb3Spatrick BV t = v.l1_[i0]; 201*3cab2bb3Spatrick while (!t.empty()) { 202*3cab2bb3Spatrick uptr i1 = t.getAndClearFirstOne(); 203*3cab2bb3Spatrick if (l1_[i0].setBit(i1)) 204*3cab2bb3Spatrick l2_[i0][i1].clear(); 205*3cab2bb3Spatrick if (l2_[i0][i1].setUnion(v.l2_[i0][i1])) 206*3cab2bb3Spatrick res = true; 207*3cab2bb3Spatrick } 208*3cab2bb3Spatrick } 209*3cab2bb3Spatrick return res; 210*3cab2bb3Spatrick } 211*3cab2bb3Spatrick 212*3cab2bb3Spatrick // Do "this &= v" and return whether any bits have been removed. setIntersection(const TwoLevelBitVector & v)213*3cab2bb3Spatrick bool setIntersection(const TwoLevelBitVector &v) { 214*3cab2bb3Spatrick bool res = false; 215*3cab2bb3Spatrick for (uptr i0 = 0; i0 < kLevel1Size; i0++) { 216*3cab2bb3Spatrick if (l1_[i0].setIntersection(v.l1_[i0])) 217*3cab2bb3Spatrick res = true; 218*3cab2bb3Spatrick if (!l1_[i0].empty()) { 219*3cab2bb3Spatrick BV t = l1_[i0]; 220*3cab2bb3Spatrick while (!t.empty()) { 221*3cab2bb3Spatrick uptr i1 = t.getAndClearFirstOne(); 222*3cab2bb3Spatrick if (l2_[i0][i1].setIntersection(v.l2_[i0][i1])) 223*3cab2bb3Spatrick res = true; 224*3cab2bb3Spatrick if (l2_[i0][i1].empty()) 225*3cab2bb3Spatrick l1_[i0].clearBit(i1); 226*3cab2bb3Spatrick } 227*3cab2bb3Spatrick } 228*3cab2bb3Spatrick } 229*3cab2bb3Spatrick return res; 230*3cab2bb3Spatrick } 231*3cab2bb3Spatrick 232*3cab2bb3Spatrick // Do "this &= ~v" and return whether any bits have been removed. setDifference(const TwoLevelBitVector & v)233*3cab2bb3Spatrick bool setDifference(const TwoLevelBitVector &v) { 234*3cab2bb3Spatrick bool res = false; 235*3cab2bb3Spatrick for (uptr i0 = 0; i0 < kLevel1Size; i0++) { 236*3cab2bb3Spatrick BV t = l1_[i0]; 237*3cab2bb3Spatrick t.setIntersection(v.l1_[i0]); 238*3cab2bb3Spatrick while (!t.empty()) { 239*3cab2bb3Spatrick uptr i1 = t.getAndClearFirstOne(); 240*3cab2bb3Spatrick if (l2_[i0][i1].setDifference(v.l2_[i0][i1])) 241*3cab2bb3Spatrick res = true; 242*3cab2bb3Spatrick if (l2_[i0][i1].empty()) 243*3cab2bb3Spatrick l1_[i0].clearBit(i1); 244*3cab2bb3Spatrick } 245*3cab2bb3Spatrick } 246*3cab2bb3Spatrick return res; 247*3cab2bb3Spatrick } 248*3cab2bb3Spatrick copyFrom(const TwoLevelBitVector & v)249*3cab2bb3Spatrick void copyFrom(const TwoLevelBitVector &v) { 250*3cab2bb3Spatrick clear(); 251*3cab2bb3Spatrick setUnion(v); 252*3cab2bb3Spatrick } 253*3cab2bb3Spatrick 254*3cab2bb3Spatrick // Returns true if 'this' intersects with 'v'. intersectsWith(const TwoLevelBitVector & v)255*3cab2bb3Spatrick bool intersectsWith(const TwoLevelBitVector &v) const { 256*3cab2bb3Spatrick for (uptr i0 = 0; i0 < kLevel1Size; i0++) { 257*3cab2bb3Spatrick BV t = l1_[i0]; 258*3cab2bb3Spatrick t.setIntersection(v.l1_[i0]); 259*3cab2bb3Spatrick while (!t.empty()) { 260*3cab2bb3Spatrick uptr i1 = t.getAndClearFirstOne(); 261*3cab2bb3Spatrick if (!v.l1_[i0].getBit(i1)) continue; 262*3cab2bb3Spatrick if (l2_[i0][i1].intersectsWith(v.l2_[i0][i1])) 263*3cab2bb3Spatrick return true; 264*3cab2bb3Spatrick } 265*3cab2bb3Spatrick } 266*3cab2bb3Spatrick return false; 267*3cab2bb3Spatrick } 268*3cab2bb3Spatrick 269*3cab2bb3Spatrick // for (TwoLevelBitVector<>::Iterator it(bv); it.hasNext();) { 270*3cab2bb3Spatrick // uptr idx = it.next(); 271*3cab2bb3Spatrick // use(idx); 272*3cab2bb3Spatrick // } 273*3cab2bb3Spatrick class Iterator { 274*3cab2bb3Spatrick public: Iterator()275*3cab2bb3Spatrick Iterator() { } Iterator(const TwoLevelBitVector & bv)276*3cab2bb3Spatrick explicit Iterator(const TwoLevelBitVector &bv) : bv_(bv), i0_(0), i1_(0) { 277*3cab2bb3Spatrick it1_.clear(); 278*3cab2bb3Spatrick it2_.clear(); 279*3cab2bb3Spatrick } 280*3cab2bb3Spatrick hasNext()281*3cab2bb3Spatrick bool hasNext() const { 282*3cab2bb3Spatrick if (it1_.hasNext()) return true; 283*3cab2bb3Spatrick for (uptr i = i0_; i < kLevel1Size; i++) 284*3cab2bb3Spatrick if (!bv_.l1_[i].empty()) return true; 285*3cab2bb3Spatrick return false; 286*3cab2bb3Spatrick } 287*3cab2bb3Spatrick next()288*3cab2bb3Spatrick uptr next() { 289*3cab2bb3Spatrick // Printf("++++: %zd %zd; %d %d; size %zd\n", i0_, i1_, it1_.hasNext(), 290*3cab2bb3Spatrick // it2_.hasNext(), kSize); 291*3cab2bb3Spatrick if (!it1_.hasNext() && !it2_.hasNext()) { 292*3cab2bb3Spatrick for (; i0_ < kLevel1Size; i0_++) { 293*3cab2bb3Spatrick if (bv_.l1_[i0_].empty()) continue; 294*3cab2bb3Spatrick it1_ = typename BV::Iterator(bv_.l1_[i0_]); 295*3cab2bb3Spatrick // Printf("+i0: %zd %zd; %d %d; size %zd\n", i0_, i1_, it1_.hasNext(), 296*3cab2bb3Spatrick // it2_.hasNext(), kSize); 297*3cab2bb3Spatrick break; 298*3cab2bb3Spatrick } 299*3cab2bb3Spatrick } 300*3cab2bb3Spatrick if (!it2_.hasNext()) { 301*3cab2bb3Spatrick CHECK(it1_.hasNext()); 302*3cab2bb3Spatrick i1_ = it1_.next(); 303*3cab2bb3Spatrick it2_ = typename BV::Iterator(bv_.l2_[i0_][i1_]); 304*3cab2bb3Spatrick // Printf("++i1: %zd %zd; %d %d; size %zd\n", i0_, i1_, it1_.hasNext(), 305*3cab2bb3Spatrick // it2_.hasNext(), kSize); 306*3cab2bb3Spatrick } 307*3cab2bb3Spatrick CHECK(it2_.hasNext()); 308*3cab2bb3Spatrick uptr i2 = it2_.next(); 309*3cab2bb3Spatrick uptr res = i0_ * BV::kSize * BV::kSize + i1_ * BV::kSize + i2; 310*3cab2bb3Spatrick // Printf("+ret: %zd %zd; %d %d; size %zd; res: %zd\n", i0_, i1_, 311*3cab2bb3Spatrick // it1_.hasNext(), it2_.hasNext(), kSize, res); 312*3cab2bb3Spatrick if (!it1_.hasNext() && !it2_.hasNext()) 313*3cab2bb3Spatrick i0_++; 314*3cab2bb3Spatrick return res; 315*3cab2bb3Spatrick } 316*3cab2bb3Spatrick 317*3cab2bb3Spatrick private: 318*3cab2bb3Spatrick const TwoLevelBitVector &bv_; 319*3cab2bb3Spatrick uptr i0_, i1_; 320*3cab2bb3Spatrick typename BV::Iterator it1_, it2_; 321*3cab2bb3Spatrick }; 322*3cab2bb3Spatrick 323*3cab2bb3Spatrick private: check(uptr idx)324*3cab2bb3Spatrick void check(uptr idx) const { CHECK_LE(idx, size()); } 325*3cab2bb3Spatrick idx0(uptr idx)326*3cab2bb3Spatrick uptr idx0(uptr idx) const { 327*3cab2bb3Spatrick uptr res = idx / (BV::kSize * BV::kSize); 328*3cab2bb3Spatrick CHECK_LE(res, kLevel1Size); 329*3cab2bb3Spatrick return res; 330*3cab2bb3Spatrick } 331*3cab2bb3Spatrick idx1(uptr idx)332*3cab2bb3Spatrick uptr idx1(uptr idx) const { 333*3cab2bb3Spatrick uptr res = (idx / BV::kSize) % BV::kSize; 334*3cab2bb3Spatrick CHECK_LE(res, BV::kSize); 335*3cab2bb3Spatrick return res; 336*3cab2bb3Spatrick } 337*3cab2bb3Spatrick idx2(uptr idx)338*3cab2bb3Spatrick uptr idx2(uptr idx) const { 339*3cab2bb3Spatrick uptr res = idx % BV::kSize; 340*3cab2bb3Spatrick CHECK_LE(res, BV::kSize); 341*3cab2bb3Spatrick return res; 342*3cab2bb3Spatrick } 343*3cab2bb3Spatrick 344*3cab2bb3Spatrick BV l1_[kLevel1Size]; 345*3cab2bb3Spatrick BV l2_[kLevel1Size][BV::kSize]; 346*3cab2bb3Spatrick }; 347*3cab2bb3Spatrick 348*3cab2bb3Spatrick } // namespace __sanitizer 349*3cab2bb3Spatrick 350*3cab2bb3Spatrick #endif // SANITIZER_BITVECTOR_H 351