aboutsummaryrefslogtreecommitdiffstats
path: root/chilbert/BigBitVec.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'chilbert/BigBitVec.hpp')
-rw-r--r--chilbert/BigBitVec.hpp142
1 files changed, 53 insertions, 89 deletions
diff --git a/chilbert/BigBitVec.hpp b/chilbert/BigBitVec.hpp
index 29d9a5a..7fe260e 100644
--- a/chilbert/BigBitVec.hpp
+++ b/chilbert/BigBitVec.hpp
@@ -85,7 +85,7 @@ public:
explicit CBigBitVec(const size_t bits)
: m_pcRacks{make_racks(num_racks(bits))}
- , m_iRacks{bits == 0 ? 0 : num_racks(bits)}
+ , m_size{bits}
{
}
@@ -96,31 +96,38 @@ public:
}
CBigBitVec(const CBigBitVec& vec)
- : m_pcRacks{make_racks(vec.m_iRacks)}
- , m_iRacks{vec.m_iRacks}
+ : m_pcRacks{make_racks(vec.rackCount())}
+ , m_size{vec.m_size}
{
if (vec.m_pcRacks) {
memcpy(
- m_pcRacks.get(), vec.m_pcRacks.get(), sizeof(Rack) * m_iRacks);
+ m_pcRacks.get(), vec.m_pcRacks.get(), sizeof(Rack) * rackCount());
}
}
CBigBitVec(CBigBitVec&& vec) = default;
/// Return the size in bits
- size_t size() const { return m_iRacks * bits_per_rack; }
+ size_t size() const { return m_size; }
/// Set all bits to zero
CBigBitVec& reset()
{
- memset(m_pcRacks.get(), 0, sizeof(Rack) * m_iRacks);
+ memset(m_pcRacks.get(), 0, sizeof(Rack) * rackCount());
return *this;
}
/// Set all bits to one
CBigBitVec& set()
{
- memset(m_pcRacks.get(), 0xFF, sizeof(Rack) * m_iRacks);
+ if (m_size) {
+ memset(m_pcRacks.get(), 0xFF, sizeof(Rack) * rackCount());
+ const auto pad = m_size % bits_per_rack;
+ if (pad) {
+ m_pcRacks[rackCount() - 1] |= ~Rack{0} >> pad;
+ }
+ }
+
return *this;
}
@@ -131,7 +138,7 @@ public:
m_pcRacks[m.m_rack] &= (m.m_mask - 1);
- for (size_t i = m.m_rack + 1; i < m_iRacks; ++i) {
+ for (size_t i = m.m_rack + 1; i < rackCount(); ++i) {
m_pcRacks[i] = 0;
}
@@ -151,8 +158,8 @@ public:
{
assert(size() == vec.size());
- for (size_t ri = 0; ri < m_iRacks; ++ri) {
- size_t i = m_iRacks - ri - 1;
+ for (size_t ri = 0; ri < rackCount(); ++ri) {
+ size_t i = rackCount() - ri - 1;
if (m_pcRacks[i] < vec.m_pcRacks[i]) {
return true;
} else if (m_pcRacks[i] > vec.m_pcRacks[i]) {
@@ -162,20 +169,19 @@ public:
return false;
}
- /// Non-resizing assignment
CBigBitVec& operator=(const CBigBitVec& vec)
{
- if (m_iRacks < vec.m_iRacks) {
- m_iRacks = vec.m_iRacks;
- m_pcRacks = make_racks(m_iRacks);
+ if (rackCount() < vec.rackCount()) {
+ m_pcRacks = make_racks(vec.rackCount());
+ m_size = vec.m_size;
memcpy(
- m_pcRacks.get(), vec.m_pcRacks.get(), sizeof(Rack) * m_iRacks);
- } else if (vec.m_iRacks > 0) {
- m_iRacks = vec.m_iRacks;
+ m_pcRacks.get(), vec.m_pcRacks.get(), sizeof(Rack) * rackCount());
+ } else if (vec.rackCount() > 0) {
+ m_size = vec.m_size;
memcpy(
- m_pcRacks.get(), vec.m_pcRacks.get(), sizeof(Rack) * m_iRacks);
+ m_pcRacks.get(), vec.m_pcRacks.get(), sizeof(Rack) * rackCount());
} else {
- m_iRacks = 0;
+ m_size = 0;
m_pcRacks.reset();
}
@@ -239,7 +245,7 @@ public:
CBigBitVec& operator&=(const CBigBitVec& vec)
{
- for (size_t i = 0; i < std::min(m_iRacks, vec.m_iRacks); ++i) {
+ for (size_t i = 0; i < std::min(rackCount(), vec.rackCount()); ++i) {
m_pcRacks[i] &= vec.m_pcRacks[i];
}
@@ -256,7 +262,7 @@ public:
CBigBitVec& operator|=(const CBigBitVec& vec)
{
- for (size_t i = 0; i < std::min(m_iRacks, vec.m_iRacks); ++i) {
+ for (size_t i = 0; i < std::min(rackCount(), vec.rackCount()); ++i) {
m_pcRacks[i] |= vec.m_pcRacks[i];
}
@@ -273,7 +279,7 @@ public:
CBigBitVec& operator^=(const CBigBitVec& vec)
{
- for (size_t i = 0; i < std::min(m_iRacks, vec.m_iRacks); ++i) {
+ for (size_t i = 0; i < std::min(rackCount(), vec.rackCount()); ++i) {
m_pcRacks[i] ^= vec.m_pcRacks[i];
}
@@ -308,7 +314,7 @@ public:
if (index.rack > 0) {
// Shift entire racks
- for (size_t i = m_iRacks - 1; i >= index.rack; --i) {
+ for (size_t i = rackCount() - 1; i >= index.rack; --i) {
m_pcRacks[i] = m_pcRacks[i - index.rack];
}
for (size_t i = 0; i < index.rack; ++i) {
@@ -320,7 +326,7 @@ public:
// Shift bits within racks
size_t bi = bits_per_rack - index.bit;
size_t i;
- for (i = m_iRacks - 1; i >= index.rack + 1; --i) {
+ for (i = rackCount() - 1; i >= index.rack + 1; --i) {
m_pcRacks[i] <<= index.bit;
m_pcRacks[i] |= m_pcRacks[i - 1] >> bi;
}
@@ -351,10 +357,10 @@ public:
if (index.rack > 0) {
// Shift entire racks
size_t i;
- for (i = 0; i < m_iRacks - index.rack; ++i) {
+ for (i = 0; i < rackCount() - index.rack; ++i) {
m_pcRacks[i] = m_pcRacks[i + index.rack];
}
- for (; i < m_iRacks; ++i) {
+ for (; i < rackCount(); ++i) {
m_pcRacks[i] = 0;
}
}
@@ -363,7 +369,7 @@ public:
// Shift bits within racks
size_t bi = bits_per_rack - index.bit;
size_t i;
- for (i = 0; i < m_iRacks - index.rack - 1; ++i) {
+ for (i = 0; i < rackCount() - index.rack - 1; ++i) {
m_pcRacks[i] >>= index.bit;
m_pcRacks[i] |= m_pcRacks[i + 1] << bi;
}
@@ -380,56 +386,42 @@ public:
return t;
}
- /// Right-rotate the least significant `width` bits by `bits` positions
- CBigBitVec& rotr(const size_t bits, size_t width)
+ /// Right-rotate by `bits` positions
+ CBigBitVec& rotr(const size_t bits)
{
- // Fill in the width, if necessary.
- if (width <= 0) {
- width = size();
- }
-
- // Modulo the number of bits.
- assert(bits < width);
- if (bits == 0) {
+ assert(bits <= size());
+ if (bits == 0 || bits == size()) {
return *this;
}
- // Ensure we are truncated appropriately.
- truncate(width);
+ truncate(size());
CBigBitVec t1(*this);
(*this) >>= bits;
- t1 <<= (width - bits);
+ t1 <<= (size() - bits);
(*this) |= t1;
- truncate(width);
+ truncate(size());
return *this;
}
- /// Left-rotate the least significant `width` bits by `bits` positions
- CBigBitVec& rotl(const size_t bits, size_t width)
+ /// Left-rotate by `bits` positions
+ CBigBitVec& rotl(const size_t bits)
{
- // Fill in the width, if necessary.
- if (width <= 0) {
- width = size();
- }
-
- // Modulo the number of bits.
- assert(bits < width);
- if (bits == 0) {
+ assert(bits <= size());
+ if (bits == 0 || bits == size()) {
return *this;
}
- // Ensure we are truncated appropriately.
- truncate(width);
+ truncate(size());
CBigBitVec t1(*this);
(*this) <<= bits;
- t1 >>= (width - bits);
+ t1 >>= (size() - bits);
(*this) |= t1;
- truncate(width);
+ truncate(size());
return *this;
}
@@ -437,7 +429,7 @@ public:
/// Return true iff all bits are zero
bool none() const
{
- for (size_t i = 0; i < m_iRacks; ++i) {
+ for (size_t i = 0; i < rackCount(); ++i) {
if (m_pcRacks[i]) {
return false;
}
@@ -448,7 +440,7 @@ public:
/// Return 1 + the index of the first set bit, or 0 if there are none
size_t find_first() const
{
- for (size_t i = 0; i < m_iRacks; ++i) {
+ for (size_t i = 0; i < rackCount(); ++i) {
const int j = ffs(m_pcRacks[i]);
if (j) {
return (i * bits_per_rack) + static_cast<size_t>(j);
@@ -461,7 +453,7 @@ public:
size_t count() const
{
size_t c = 0;
- for (size_t i = 0; i < m_iRacks; ++i) {
+ for (size_t i = 0; i < rackCount(); ++i) {
c += static_cast<size_t>(pop_count(m_pcRacks[i]));
}
return c;
@@ -470,7 +462,7 @@ public:
/// Flip all bits (one's complement)
CBigBitVec& flip()
{
- for (size_t i = 0; i < m_iRacks; ++i) {
+ for (size_t i = 0; i < rackCount(); ++i) {
m_pcRacks[i] = ~m_pcRacks[i];
}
return *this;
@@ -485,7 +477,7 @@ public:
const Rack* racks() const { return m_pcRacks.get(); }
/// Return the number of racks
- size_t rackCount() const { return m_iRacks; }
+ size_t rackCount() const { return num_racks(m_size); }
template <class BitVec>
class iterator_base : public Mask
@@ -600,36 +592,8 @@ private:
return RacksPtr{static_cast<Rack*>(calloc(n, sizeof(Rack)))};
}
- // Right rotates entire racks (in place).
- void rackRotr(const size_t k)
- {
- assert(k < m_iRacks);
-
- if (k == 0) {
- return;
- }
-
- size_t c = 0;
- for (size_t v = 0; c < m_iRacks; ++v) {
- size_t t = v;
- size_t tp = v + k;
- const Rack tmp = m_pcRacks[v];
- c++;
- while (tp != v) {
- m_pcRacks[t] = m_pcRacks[tp];
- t = tp;
- tp += k;
- if (tp >= m_iRacks) {
- tp -= m_iRacks;
- }
- c++;
- }
- m_pcRacks[t] = tmp;
- }
- }
-
RacksPtr m_pcRacks;
- size_t m_iRacks;
+ size_t m_size;
};
template <>
generated by cgit v1.2.1 (git 2.18.0) at 2024-06-30 08:19:31 +0000