aboutsummaryrefslogtreecommitdiffstats
path: root/chilbert/BigBitVec.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'chilbert/BigBitVec.hpp')
-rw-r--r--chilbert/BigBitVec.hpp123
1 files changed, 58 insertions, 65 deletions
diff --git a/chilbert/BigBitVec.hpp b/chilbert/BigBitVec.hpp
index 8b315a0..83b8a5b 100644
--- a/chilbert/BigBitVec.hpp
+++ b/chilbert/BigBitVec.hpp
@@ -23,24 +23,19 @@
#include <algorithm>
#include <cassert>
+#include <cstddef>
#include <cstdlib>
#include <cstring>
#include <memory>
-#define FBVS_NEEDED(b) ((std::max(b, 1) + FBV_BITS - 1) / FBV_BITS)
-#define BBV_MODSPLIT(r, b, k) \
- { \
- b = (k); \
- r = b / FBV_BITS; \
- b -= r * FBV_BITS; \
- }
+#define FBVS_NEEDED(b) ((std::max(b, size_t(1)) + FBV_BITS - 1) / FBV_BITS)
namespace chilbert {
class CBigBitVec
{
public:
- CBigBitVec(const int bits = 0)
+ CBigBitVec(const size_t bits = 0)
: m_pcRacks{make_racks(FBVS_NEEDED(bits))}
, m_iRacks{bits == 0 ? 0 : FBVS_NEEDED(bits)}
{
@@ -67,7 +62,7 @@ public:
}
/// Return the size in bits
- int size() const { return m_iRacks * FBV_BITS; }
+ size_t size() const { return m_iRacks * FBV_BITS; }
/// Set all bits to zero
CBigBitVec& reset()
@@ -84,9 +79,9 @@ public:
}
/// Truncate to a given precision in bits (zero MSBs)
- CBigBitVec& truncate(const int bits)
+ CBigBitVec& truncate(const size_t bits)
{
- assert(bits >= 0 && bits <= size());
+ assert(bits <= size());
const Ref ref(bits);
if (ref.rack >= m_iRacks) {
return *this;
@@ -95,7 +90,7 @@ public:
// Truncate rack that contains the split point
m_pcRacks[ref.rack] &= FBVN1S(ref.bit);
- for (int i = ref.rack + 1; i < m_iRacks; ++i) {
+ for (size_t i = ref.rack + 1; i < m_iRacks; ++i) {
m_pcRacks[i] = 0;
}
@@ -159,44 +154,44 @@ public:
}
/// Return the value of the `index`th bit
- bool test(const int index) const
+ bool test(const size_t index) const
{
- assert(index >= 0 && index < size());
+ assert(index < size());
const Ref ref(index);
return testBit(m_pcRacks[ref.rack], ref.bit);
}
/// Set the `index`th bit to 1
- CBigBitVec& set(const int index)
+ CBigBitVec& set(const size_t index)
{
- assert(index >= 0 && index < size());
+ assert(index < size());
const Ref ref(index);
setBit(m_pcRacks[ref.rack], ref.bit);
return *this;
}
/// Reset the `index`th bit to 0
- CBigBitVec& reset(const int index)
+ CBigBitVec& reset(const size_t index)
{
- assert(index >= 0 && index < size());
+ assert(index < size());
const Ref ref(index);
- m_pcRacks[ref.rack] &= ~((FBV_UINT)1 << ref.bit);
+ m_pcRacks[ref.rack] &= ~(FBV_UINT{1} << ref.bit);
return *this;
}
/// Set the `index`th bit to `value`
- CBigBitVec& set(const int index, const bool value)
+ CBigBitVec& set(const size_t index, const bool value)
{
- assert(index >= 0 && index < size());
+ assert(index < size());
const Ref ref(index);
setBit(m_pcRacks[ref.rack], ref.bit, value);
return *this;
}
/// Flip the value of the `index`th bit
- CBigBitVec& flip(const int index)
+ CBigBitVec& flip(const size_t index)
{
- assert(index >= 0 && index < size());
+ assert(index < size());
const Ref ref(index);
m_pcRacks[ref.rack] ^= (FBV1 << ref.bit);
return *this;
@@ -204,7 +199,7 @@ public:
CBigBitVec& operator&=(const CBigBitVec& vec)
{
- for (int i = 0; i < std::min(m_iRacks, vec.m_iRacks); ++i) {
+ for (size_t i = 0; i < std::min(m_iRacks, vec.m_iRacks); ++i) {
m_pcRacks[i] &= vec.m_pcRacks[i];
}
@@ -221,7 +216,7 @@ public:
CBigBitVec& operator|=(const CBigBitVec& vec)
{
- for (int i = 0; i < std::min(m_iRacks, vec.m_iRacks); ++i) {
+ for (size_t i = 0; i < std::min(m_iRacks, vec.m_iRacks); ++i) {
m_pcRacks[i] |= vec.m_pcRacks[i];
}
@@ -238,7 +233,7 @@ public:
CBigBitVec& operator^=(const CBigBitVec& vec)
{
- for (int i = 0; i < std::min(m_iRacks, vec.m_iRacks); ++i) {
+ for (size_t i = 0; i < std::min(m_iRacks, vec.m_iRacks); ++i) {
m_pcRacks[i] ^= vec.m_pcRacks[i];
}
@@ -253,9 +248,9 @@ public:
return t;
}
- CBigBitVec& operator<<=(const int bits)
+ CBigBitVec& operator<<=(const size_t bits)
{
- assert(bits >= 0);
+ assert(bits < size());
// No shift?
if (bits == 0) {
@@ -272,19 +267,18 @@ public:
// Do rack shifts.
if (ref.rack > 0) {
- int i;
- for (i = m_iRacks - 1; i >= ref.rack; --i) {
+ for (size_t i = m_iRacks - 1; i >= ref.rack; --i) {
m_pcRacks[i] = m_pcRacks[i - ref.rack];
}
- for (; i >= 0; --i) {
+ for (size_t i = 0; i < ref.rack; ++i) {
m_pcRacks[i] = 0;
}
}
// Do bit shifts.
if (ref.bit > 0) {
- int bi = FBV_BITS - ref.bit;
- int i;
+ size_t bi = FBV_BITS - ref.bit;
+ size_t i;
for (i = m_iRacks - 1; i >= ref.rack + 1; --i) {
m_pcRacks[i] <<= ref.bit;
m_pcRacks[i] |= m_pcRacks[i - 1] >> bi;
@@ -295,16 +289,16 @@ public:
return *this;
}
- CBigBitVec operator<<(const int bits) const
+ CBigBitVec operator<<(const size_t bits) const
{
CBigBitVec t(*this);
t <<= bits;
return t;
}
- CBigBitVec& operator>>=(const int bits)
+ CBigBitVec& operator>>=(const size_t bits)
{
- assert(bits >= 0);
+ assert(bits < size());
// No shift?
if (bits == 0) {
@@ -321,7 +315,7 @@ public:
// Do rack shifts.
if (ref.rack > 0) {
- int i;
+ size_t i;
for (i = 0; i < m_iRacks - ref.rack; ++i) {
m_pcRacks[i] = m_pcRacks[i + ref.rack];
}
@@ -332,8 +326,8 @@ public:
// Do bit shifts.
if (ref.bit > 0) {
- int bi = FBV_BITS - ref.bit;
- int i;
+ size_t bi = FBV_BITS - ref.bit;
+ size_t i;
for (i = 0; i < m_iRacks - ref.rack - 1; ++i) {
m_pcRacks[i] >>= ref.bit;
m_pcRacks[i] |= m_pcRacks[i + 1] << bi;
@@ -344,7 +338,7 @@ public:
return *this;
}
- CBigBitVec operator>>(const int bits) const
+ CBigBitVec operator>>(const size_t bits) const
{
CBigBitVec t(*this);
t >>= bits;
@@ -352,10 +346,8 @@ public:
}
/// Right-rotate the least significant `width` bits by `bits` positions
- CBigBitVec& rotr(const int bits, int width)
+ CBigBitVec& rotr(const size_t bits, size_t width)
{
- assert(bits >= 0);
-
// Fill in the width, if necessary.
if (width <= 0) {
width = size();
@@ -381,10 +373,8 @@ public:
}
/// Left-rotate the least significant `width` bits by `bits` positions
- CBigBitVec& rotl(const int bits, int width)
+ CBigBitVec& rotl(const size_t bits, size_t width)
{
- assert(bits >= 0);
-
// Fill in the width, if necessary.
if (width <= 0) {
width = size();
@@ -412,7 +402,7 @@ public:
/// Return true iff all bits are zero
bool none() const
{
- for (int i = 0; i < m_iRacks; ++i) {
+ for (size_t i = 0; i < m_iRacks; ++i) {
if (m_pcRacks[i]) {
return false;
}
@@ -421,12 +411,12 @@ public:
}
/// Return 1 + the index of the first set bit, or 0 if there are none
- int find_first() const
+ size_t find_first() const
{
- for (int i = 0; i < m_iRacks; ++i) {
+ for (size_t i = 0; i < m_iRacks; ++i) {
const int j = ffs(m_pcRacks[i]);
if (j) {
- return (i * FBV_BITS) + j;
+ return (i * FBV_BITS) + static_cast<size_t>(j);
}
}
return 0;
@@ -435,7 +425,7 @@ public:
/// Flip all bits (one's complement)
CBigBitVec& flip()
{
- for (int i = 0; i < m_iRacks; ++i) {
+ for (size_t i = 0; i < m_iRacks; ++i) {
m_pcRacks[i] = ~m_pcRacks[i];
}
return *this;
@@ -450,19 +440,19 @@ public:
const FBV_UINT* racks() const { return m_pcRacks.get(); }
/// Return the number of racks
- int rackCount() const { return m_iRacks; }
+ size_t rackCount() const { return m_iRacks; }
private:
struct Ref
{
- Ref(const int bits)
+ Ref(const size_t bits)
: rack{bits / FBV_BITS}
, bit{bits - rack * FBV_BITS}
{
}
- int rack;
- int bit;
+ size_t rack;
+ size_t bit;
};
struct RacksDeleter
@@ -472,24 +462,25 @@ private:
using RacksPtr = std::unique_ptr<FBV_UINT[], RacksDeleter>;
- static RacksPtr make_racks(const int n)
+ static RacksPtr make_racks(const size_t n)
{
return RacksPtr{static_cast<FBV_UINT*>(calloc(n, sizeof(FBV_UINT)))};
}
// Right rotates entire racks (in place).
- void rackRotr(int k)
+ void rackRotr(const size_t k)
{
- assert(0 <= k && k < m_iRacks);
+ assert(k < m_iRacks);
if (k == 0) {
return;
}
- int c = 0;
- for (int v = 0; c < m_iRacks; ++v) {
- int t = v, tp = v + k;
- const int tmp = m_pcRacks[v];
+ size_t c = 0;
+ for (size_t v = 0; c < m_iRacks; ++v) {
+ size_t t = v;
+ size_t tp = v + k;
+ const FBV_UINT tmp = m_pcRacks[v];
c++;
while (tp != v) {
m_pcRacks[t] = m_pcRacks[tp];
@@ -505,7 +496,7 @@ private:
}
RacksPtr m_pcRacks;
- int m_iRacks;
+ size_t m_iRacks;
};
template <>
@@ -514,7 +505,8 @@ grayCode(CBigBitVec& value)
{
FBV_UINT s = 0;
- for (int i = value.rackCount() - 1; i >= 0; --i) {
+ for (intptr_t i = static_cast<intptr_t>(value.rackCount() - 1); i >= 0;
+ --i) {
const FBV_UINT t = value.racks()[i] & 1;
grayCode(value.racks()[i]);
value.racks()[i] ^= (s << (FBV_BITS - 1));
@@ -528,7 +520,8 @@ grayCodeInv(CBigBitVec& value)
{
FBV_UINT s = 0;
- for (int i = value.rackCount() - 1; i >= 0; --i) {
+ for (intptr_t i = static_cast<intptr_t>(value.rackCount() - 1); i >= 0;
+ --i) {
FBV_UINT& rack = value.racks()[i];
grayCodeInv(rack);
if (s) {
generated by cgit v1.2.1 (git 2.18.0) at 2024-10-01 20:47:12 +0000