| 1 |
/*========================== begin_copyright_notice ============================ |
| 2 |
|
| 3 |
Copyright (C) 2017-2021 Intel Corporation |
| 4 |
|
| 5 |
SPDX-License-Identifier: MIT |
| 6 |
|
| 7 |
============================= end_copyright_notice ===========================*/ |
| 8 |
|
| 9 |
#ifndef _IGA_BITSET_HPP |
| 10 |
#define _IGA_BITSET_HPP |
| 11 |
|
| 12 |
#include "../asserts.hpp" |
| 13 |
#include "common/secure_mem.h" |
| 14 |
|
| 15 |
#include <algorithm> |
| 16 |
#include <bitset> |
| 17 |
#include <cstdint> |
| 18 |
#include <cstring> |
| 19 |
#include <ostream> |
| 20 |
#include <sstream> |
| 21 |
#include <string> |
| 22 |
#include <utility> |
| 23 |
|
| 24 |
// Align N up to the nearest multiple of A |
| 25 |
#define ALIGN_UP_TO(A, N) ((N + (A)-1) - (N + (A)-1) % (A)) |
| 26 |
|
| 27 |
namespace iga { |
| 28 |
|
| 29 |
// I so badly wanted to just use std::bitset and then drink beer with my free |
| 30 |
// time. Alas this lacks some of the APIs that I need to efficiently |
| 31 |
// perform data flow. Specifically, I need efficient testAny/testAll |
| 32 |
// predicates. |
| 33 |
template <typename I = uint32_t> class BitSet { |
| 34 |
public: |
| 35 |
static const size_t BITS_PER_WORD = 8 * sizeof(I); |
| 36 |
|
| 37 |
// allocate and zero bits |
| 38 |
BitSet(size_t numBits) |
| 39 |
: N(numBits), |
| 40 |
wordsSize(ALIGN_UP_TO(BITS_PER_WORD, numBits) / BITS_PER_WORD) { |
| 41 |
words = new I[wordsSize]; |
| 42 |
reset(); |
| 43 |
} |
| 44 |
BitSet(const BitSet<I> &rhs) |
| 45 |
: N(rhs.N), wordsSize(ALIGN_UP_TO(BITS_PER_WORD, rhs.N) / BITS_PER_WORD) |
| 46 |
|
| 47 |
{ |
| 48 |
words = new I[wordsSize]; |
| 49 |
memcpy_s(words, wordsSize * sizeof(I), rhs.words, wordsSize * sizeof(I)); |
| 50 |
} |
| 51 |
|
| 52 |
BitSet(BitSet<I> &©) noexcept |
| 53 |
: N(copy.N), wordsSize(copy.wordsSize), words(copy.words) { |
| 54 |
copy.words = nullptr; |
| 55 |
copy.N = copy.wordsSize = 0; |
| 56 |
} |
| 57 |
|
| 58 |
BitSet<I> &operator=(const BitSet<I> &rhs) { |
| 59 |
if (this == &rhs) { |
| 60 |
return *this; |
| 61 |
} |
| 62 |
if (rhs.N != N) { |
| 63 |
// resize |
| 64 |
if (words) |
| 65 |
delete[] words; |
| 66 |
N = rhs.N; |
| 67 |
wordsSize = rhs.wordsSize; |
| 68 |
words = new I[wordsSize]; |
| 69 |
} |
| 70 |
memcpy_s(words, wordsSize * sizeof(I), rhs.words, wordsSize * sizeof(I)); |
| 71 |
return *this; |
| 72 |
} |
| 73 |
|
| 74 |
BitSet<I> &operator=(BitSet<I> &&rhs) { |
| 75 |
if (this == &rhs) { |
| 76 |
return *this; |
| 77 |
} |
| 78 |
if (words) { |
| 79 |
delete[] words; |
| 80 |
} |
| 81 |
|
| 82 |
N = rhs.N; |
| 83 |
wordsSize = rhs.wordsSize; |
| 84 |
words = rhs.words; |
| 85 |
|
| 86 |
rhs.words = nullptr; |
| 87 |
|
| 88 |
return *this; |
| 89 |
} |
| 90 |
|
| 91 |
~BitSet() { |
| 92 |
if (words) { |
| 93 |
delete[] words; |
| 94 |
words = nullptr; |
| 95 |
} |
| 96 |
} |
| 97 |
|
| 98 |
// TODO: remove |
| 99 |
void reset() { clear(); } |
| 100 |
|
| 101 |
void clear() { memset(words, 0, wordsSize * sizeof(I)); } |
| 102 |
bool set(size_t off, size_t len = 1, bool val = true); // sets/clears range |
| 103 |
bool test(size_t off) const { return testAny(off, 1); } |
| 104 |
bool testAny(size_t off, size_t len) const; |
| 105 |
bool testAll(size_t off, size_t len) const; |
| 106 |
void containsAll(const BitSet<I> &rhs) const; |
| 107 |
bool empty() const { return !testAny(0, N); } |
| 108 |
|
| 109 |
bool intersects(const BitSet<I> &rhs) const; |
| 110 |
|
| 111 |
// If the bitSets have intersects in given range, start from off and with |
| 112 |
// legnth len off: bit offset len: range length in bits |
| 113 |
bool intersects(const BitSet<I> &rhs, size_t off, size_t len) const; |
| 114 |
|
| 115 |
// if the given rhs is completely the same as itself |
| 116 |
bool equal(const BitSet<I> &rhs) const; |
| 117 |
|
| 118 |
// THERE EXISTS WORD w such that ((w & mask) == eq) |
| 119 |
// bool testAnyEq(size_t off, size_t len, const I &mask, const I &eq) const; |
| 120 |
// FOR ALL ... |
| 121 |
// bool testAllEq(size_t off, size_t len, const I &mask, const I &eq) const; |
| 122 |
|
| 123 |
// BitSet& operator ~() const; |
| 124 |
bool andNot(const BitSet<I> &rhs); // set subtraction |
| 125 |
bool add(const BitSet<I> &rhs); // set union |
| 126 |
bool intersectInto(const BitSet<I> &rhs, BitSet<I> &into) |
| 127 |
const; // set intersection (returns true if result non-empty) |
| 128 |
|
| 129 |
bool operator[](const size_t &ix) const { return test(ix); } |
| 130 |
bool operator==(const BitSet<I> &bs) const; |
| 131 |
bool operator!=(const BitSet<I> &bs) const { return !(*this == bs); } |
| 132 |
std::string str() const { |
| 133 |
std::stringstream ss; |
| 134 |
str(ss); |
| 135 |
return ss.str(); |
| 136 |
} |
| 137 |
void str(std::ostream &os) const; |
| 138 |
size_t cardinality() const; |
| 139 |
|
| 140 |
static BitSet<I> intersection(const BitSet<I> &bs1, const BitSet<I> &bs2) { |
| 141 |
BitSet<I> bsI(bs1.N); |
| 142 |
bs1.intersectInto(bs2, bsI); |
| 143 |
return bsI; |
| 144 |
} |
| 145 |
|
| 146 |
private: |
| 147 |
size_t N; |
| 148 |
size_t wordsSize; |
| 149 |
I *words; |
| 150 |
|
| 151 |
static I makeMask(size_t len) { |
| 152 |
IGA_ASSERT(len <= BITS_PER_WORD, |
| 153 |
"BitSet::makeMask: length too large for mask"); |
| 154 |
if (len == BITS_PER_WORD) { |
| 155 |
return (I)-1; |
| 156 |
} |
| 157 |
return (1 << len) - 1; |
| 158 |
} |
| 159 |
}; |
| 160 |
|
| 161 |
template <typename I> |
| 162 |
inline bool BitSet<I>::set(size_t off, size_t len, bool val) { |
| 163 |
IGA_ASSERT(off >= 0 && off + len <= N, "BitSet::set: index out of bounds"); |
| 164 |
|
| 165 |
// check the first word (misaligned mask) |
| 166 |
auto w_ix = off / BITS_PER_WORD; |
| 167 |
auto w_off = off % BITS_PER_WORD; |
| 168 |
auto misaligned_len = std::min<size_t>(BITS_PER_WORD - w_off, len); |
| 169 |
auto misaligned_mask = makeMask(misaligned_len) << w_off; |
| 170 |
auto oldWord0 = words[w_ix]; |
| 171 |
if (val) { |
| 172 |
words[w_ix] |= misaligned_mask; |
| 173 |
} else { |
| 174 |
words[w_ix] &= ~misaligned_mask; |
| 175 |
} |
| 176 |
bool changed = oldWord0 != words[w_ix]; |
| 177 |
|
| 178 |
// check successive words (all aligned now) |
| 179 |
len -= misaligned_len; |
| 180 |
off += misaligned_len; |
| 181 |
while (len > 0) { |
| 182 |
w_ix++; // next word |
| 183 |
|
| 184 |
auto aligned_len = len >= 32 ? 32 : len % BITS_PER_WORD; // last will be <32 |
| 185 |
auto aligned_mask = makeMask(aligned_len); |
| 186 |
auto oldWord = words[w_ix]; |
| 187 |
if (val) { |
| 188 |
words[w_ix] |= aligned_mask; |
| 189 |
} else { |
| 190 |
words[w_ix] &= ~aligned_mask; |
| 191 |
} |
| 192 |
changed |= words[w_ix] != oldWord; |
| 193 |
|
| 194 |
len -= aligned_len; |
| 195 |
off += aligned_len; |
| 196 |
} |
| 197 |
|
| 198 |
return changed; |
| 199 |
} |
| 200 |
|
| 201 |
template <typename I> |
| 202 |
inline bool BitSet<I>::intersects(const BitSet<I> &rhs) const { |
| 203 |
for (size_t i = 0; i < wordsSize; i++) { |
| 204 |
if (words[i] & rhs.words[i]) { |
| 205 |
return true; |
| 206 |
} |
| 207 |
} |
| 208 |
return false; |
| 209 |
} |
| 210 |
|
| 211 |
template <typename I> |
| 212 |
inline bool BitSet<I>::intersects(const BitSet<I> &rhs, size_t off, |
| 213 |
size_t len) const { |
| 214 |
|
| 215 |
IGA_ASSERT(off >= 0 && off + len <= N, |
| 216 |
"BitSet::intersects: index out of bounds"); |
| 217 |
|
| 218 |
// check the first word (may misaligned) |
| 219 |
auto w_ix = off / BITS_PER_WORD; // idx of the first word |
| 220 |
auto w_off = off % BITS_PER_WORD; // length from w_ix to off |
| 221 |
size_t misaligned_len = std::min<size_t>(BITS_PER_WORD - w_off, len); |
| 222 |
I misaligned_mask = makeMask(misaligned_len); |
| 223 |
if (((words[w_ix] >> w_off) & misaligned_mask) & |
| 224 |
((rhs.words[w_ix] >> w_off) & misaligned_mask)) { |
| 225 |
return true; |
| 226 |
} |
| 227 |
|
| 228 |
// check successive words (all aligned now) |
| 229 |
len -= misaligned_len; |
| 230 |
off += misaligned_len; |
| 231 |
while (len > 0) { |
| 232 |
w_ix++; // next word |
| 233 |
|
| 234 |
auto aligned_len = len >= 32 ? 32 : len % BITS_PER_WORD; // last will be <32 |
| 235 |
auto aligned_mask = makeMask(aligned_len); |
| 236 |
if ((words[w_ix] & aligned_mask) & (rhs.words[w_ix] & aligned_mask)) { |
| 237 |
return true; |
| 238 |
} |
| 239 |
len -= aligned_len; |
| 240 |
off += aligned_len; |
| 241 |
} |
| 242 |
return false; |
| 243 |
} |
| 244 |
|
| 245 |
template <typename I> inline bool BitSet<I>::equal(const BitSet<I> &rhs) const { |
| 246 |
bool result = true; |
| 247 |
for (size_t i = 0; i < wordsSize; i++) { |
| 248 |
result = (words[i] == rhs.words[i]) ? true : false; |
| 249 |
if (!result) |
| 250 |
break; |
| 251 |
} |
| 252 |
// padding will remain 0 since both padding are 0's |
| 253 |
// 0 & 0 is 0 so no need special handling on padding |
| 254 |
return result; |
| 255 |
} |
| 256 |
|
| 257 |
template <typename I> inline bool BitSet<I>::andNot(const BitSet<I> &rhs) { |
| 258 |
bool changed = false; |
| 259 |
for (size_t i = 0; i < wordsSize; i++) { |
| 260 |
auto old = words[i]; |
| 261 |
words[i] &= ~rhs.words[i]; |
| 262 |
changed |= (words[i] != old); |
| 263 |
} |
| 264 |
// padding will remain 0 since padding is already 0's |
| 265 |
// ((0x...000 & 0x...FFF) == 0x...000) |
| 266 |
// this rhs |
| 267 |
return changed; |
| 268 |
} |
| 269 |
|
| 270 |
template <typename I> inline bool BitSet<I>::add(const BitSet<I> &rhs) { |
| 271 |
bool changed = false; |
| 272 |
for (size_t i = 0; i < wordsSize; i++) { |
| 273 |
auto old = words[i]; |
| 274 |
words[i] |= rhs.words[i]; |
| 275 |
changed |= (words[i] != old); |
| 276 |
} |
| 277 |
// padding will remain 0 since both padding are 0's |
| 278 |
// ((0x...000 & 0x...FFF) == 0x...000) |
| 279 |
// this rhs |
| 280 |
return changed; |
| 281 |
} |
| 282 |
|
| 283 |
template <typename I> |
| 284 |
inline bool BitSet<I>::intersectInto(const BitSet<I> &rhs, |
| 285 |
BitSet<I> &into) const { |
| 286 |
bool notEmpty = false; |
| 287 |
for (size_t i = 0; i < wordsSize; i++) { |
| 288 |
into.words[i] = words[i] & rhs.words[i]; |
| 289 |
notEmpty |= (into.words[i] != 0); |
| 290 |
} |
| 291 |
// doesn't matter if the padding matches (it'll be correct either way) |
| 292 |
return notEmpty; |
| 293 |
} |
| 294 |
|
| 295 |
template <typename I> |
| 296 |
inline bool BitSet<I>::testAny(size_t off, size_t len) const { |
| 297 |
IGA_ASSERT(off >= 0 && off + len <= N, |
| 298 |
"BitSet::testAll: index out of bounds"); |
| 299 |
|
| 300 |
// check the first word (misaligned mask) |
| 301 |
auto w_ix = off / BITS_PER_WORD; |
| 302 |
auto w_off = off % BITS_PER_WORD; |
| 303 |
size_t misaligned_len = std::min<size_t>(BITS_PER_WORD - w_off, len); |
| 304 |
I misaligned_mask = makeMask(misaligned_len); |
| 305 |
if ((words[w_ix] >> w_off) & misaligned_mask) { |
| 306 |
return true; |
| 307 |
} |
| 308 |
|
| 309 |
// check successive words (all aligned now) |
| 310 |
len -= misaligned_len; |
| 311 |
off += misaligned_len; |
| 312 |
while (len > 0) { |
| 313 |
w_ix++; // next word |
| 314 |
|
| 315 |
auto aligned_len = len >= 32 ? 32 : len % BITS_PER_WORD; // last will be <32 |
| 316 |
auto aligned_mask = makeMask(aligned_len); |
| 317 |
if (words[w_ix] & aligned_mask) { |
| 318 |
return true; |
| 319 |
} |
| 320 |
len -= aligned_len; |
| 321 |
off += aligned_len; |
| 322 |
} |
| 323 |
return false; |
| 324 |
} |
| 325 |
|
| 326 |
template <typename I> |
| 327 |
inline bool BitSet<I>::testAll(size_t off, size_t len) const { |
| 328 |
IGA_ASSERT(off >= 0 && off + len <= N, |
| 329 |
"BitSet::testAll: index out of bounds"); |
| 330 |
|
| 331 |
// check the first word (misaligned mask) |
| 332 |
auto w_ix = off / BITS_PER_WORD; |
| 333 |
auto w_off = off % BITS_PER_WORD; |
| 334 |
auto misaligned_len = std::min<size_t>(BITS_PER_WORD - w_off, len); |
| 335 |
auto misaligned_mask = makeMask(misaligned_len); |
| 336 |
if (((words[w_ix] >> w_off) & misaligned_mask) != misaligned_mask) { |
| 337 |
return false; |
| 338 |
} |
| 339 |
|
| 340 |
// check successive words (all aligned now) |
| 341 |
len -= misaligned_len; |
| 342 |
off += misaligned_len; |
| 343 |
while (len > 0) { |
| 344 |
w_ix++; // next word |
| 345 |
|
| 346 |
auto aligned_len = len >= 32 ? 32 : len % BITS_PER_WORD; // last will be <32 |
| 347 |
auto aligned_mask = makeMask(aligned_len); |
| 348 |
if ((words[w_ix] & aligned_mask) != aligned_mask) { |
| 349 |
return false; |
| 350 |
} |
| 351 |
len -= aligned_len; |
| 352 |
off += aligned_len; |
| 353 |
} |
| 354 |
return true; |
| 355 |
} |
| 356 |
|
| 357 |
template <typename I> bool BitSet<I>::operator==(const BitSet<I> &bs) const { |
| 358 |
// do we have to worry about the ragged padding. |
| 359 |
// e.g. given 32b words if the bitset is 31 bits long, we have to |
| 360 |
// worry about the trailing bit |
| 361 |
if (N != bs.N) { // We should not compare BitSets of different size |
| 362 |
return false; |
| 363 |
} |
| 364 |
return memcmp(&words[0], &bs.words[0], wordsSize * sizeof(I)) == 0; |
| 365 |
} |
| 366 |
|
| 367 |
// C++20 gets std::popcount |
| 368 |
// until then, provide a couple instances of likely uses and call it a day |
| 369 |
static inline size_t bsPopcount(uint32_t i) { |
| 370 |
// this should end up as __popcountsi2 |
| 371 |
return std::bitset<32>(i).count(); |
| 372 |
} |
| 373 |
static inline size_t bsPopcount(uint64_t i) { |
| 374 |
if (sizeof(unsigned long) == 8) { |
| 375 |
// __popcountti2 |
| 376 |
return std::bitset<64>(i).count(); |
| 377 |
} else { |
| 378 |
// __popcountsi2; __popcountsi2 |
| 379 |
return bsPopcount((uint32_t)i) + bsPopcount((uint32_t)(i >> 32)); |
| 380 |
} |
| 381 |
} |
| 382 |
static inline size_t bsPopcount(uint16_t i) { return bsPopcount((uint32_t)i); } |
| 383 |
|
| 384 |
template <typename I> inline size_t BitSet<I>::cardinality() const { |
| 385 |
size_t n = 0; |
| 386 |
for (size_t i = 0; i < wordsSize; i++) { |
| 387 |
n += bsPopcount(words[i]); |
| 388 |
} |
| 389 |
return n; |
| 390 |
} |
| 391 |
|
| 392 |
template <typename I> inline void BitSet<I>::str(std::ostream &os) const { |
| 393 |
int i = 0; |
| 394 |
bool first = false; |
| 395 |
os << "{"; |
| 396 |
while (i < N) { |
| 397 |
if (test(i)) { |
| 398 |
if (first) |
| 399 |
first = false; |
| 400 |
else |
| 401 |
os << ","; |
| 402 |
int start = i + 1; |
| 403 |
while (i < N && test(i)) { |
| 404 |
i++; |
| 405 |
} |
| 406 |
os << start; |
| 407 |
if (i != start + 1) { |
| 408 |
os << "-"; |
| 409 |
os << i + start - 1; |
| 410 |
} |
| 411 |
} else { |
| 412 |
i++; |
| 413 |
} |
| 414 |
} |
| 415 |
os << "}"; |
| 416 |
} |
| 417 |
|
| 418 |
} // namespace iga |
| 419 |
|
| 420 |
#endif // _IGA_BITSET_HPP |