Make size of bit vectors precise

4 files changed, 96 insertions, 132 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 <>
diff --git a/chilbert/FixBitVec.hpp b/chilbert/FixBitVec.hpp
index 0dab483..f9ce94a 100644
--- a/chilbert/FixBitVec.hpp
+++ b/chilbert/FixBitVec.hpp
@@ -79,25 +79,27 @@ public:
 		Rack m_mask;
 	};
 
-	CFixBitVec(const size_t bits = bits_per_rack)
+	explicit CFixBitVec(const size_t bits)
 	  : m_rack{0}
+	  , m_size{bits}
 	{
 		assert(bits <= bits_per_rack);
 	}
 
 	CFixBitVec(const size_t bits, const Rack value)
 	  : m_rack{value}
+	  , m_size{bits}
 	{
 		assert(bits <= bits_per_rack);
 	}
 
 	/// Return the size in bits
-	size_t size() const { return bits_per_rack; }
+	size_t size() const { return m_size; }
 
 	/// Set all bits to one
 	CFixBitVec& set()
 	{
-		m_rack = FBV1S;
+		m_rack = FBV1S & FBVN1S(size());
 		return *this;
 	}
 
@@ -255,32 +257,26 @@ public:
 		return t;
 	}
 
-	/// Right-rotate the least significant `width` bits by `bits` positions
-	CFixBitVec& rotr(const size_t bits, const size_t width)
+	/// Right-rotate by `bits` positions
+	CFixBitVec& rotr(const size_t bits)
 	{
 		if (bits) {
-			assert(width > 0);
-			assert(bits < width);
-			assert(bits < bits_per_rack);
-			assert((width - bits) < bits_per_rack);
-			m_rack &= FBVN1S(width);
-			m_rack = (m_rack >> bits) | (m_rack << (width - bits));
-			m_rack &= FBVN1S(width);
+			assert(bits <= bits_per_rack);
+			m_rack &= FBVN1S(size());
+			m_rack = (m_rack >> bits) | (m_rack << (size() - bits));
+			m_rack &= FBVN1S(size());
 		}
 		return *this;
 	}
 
-	/// Left-rotate the least significant `width` bits by `bits` positions
-	CFixBitVec& rotl(const size_t bits, const size_t width)
+	/// Left-rotate by `bits` positions
+	CFixBitVec& rotl(const size_t bits)
 	{
 		if (bits > 0) {
-			assert(width > 0);
-			assert(bits < width);
-			assert(bits < bits_per_rack);
-			assert((width - bits) < bits_per_rack);
-			m_rack &= FBVN1S(width);
-			m_rack = (m_rack << bits) | (m_rack >> (width - bits));
-			m_rack &= FBVN1S(width);
+			assert(bits <= bits_per_rack);
+			m_rack &= FBVN1S(size());
+			m_rack = (m_rack << bits) | (m_rack >> (size() - bits));
+			m_rack &= FBVN1S(size());
 		}
 		return *this;
 	}
@@ -401,7 +397,8 @@ private:
 	static_assert(8 * sizeof(Rack) == bits_per_rack, "");
 	static_assert((sizeof(Rack) == 4) || (sizeof(Rack) == 8), "");
 
-	Rack m_rack{};
+	Rack   m_rack{};
+	size_t m_size{};
 };
 
 template <>
diff --git a/chilbert/Hilbert.ipp b/chilbert/Hilbert.ipp
index 523bfec..92a2f0e 100644
--- a/chilbert/Hilbert.ipp
+++ b/chilbert/Hilbert.ipp
@@ -77,8 +77,9 @@ template <class I>
 inline void
 transform(const I& e, const size_t d, const size_t n, I& a)
 {
+	assert(a.size() == n);
 	a ^= e;
-	a.rotr(d, n); //#D d+1, n );
+	a.rotr(d);
 }
 
 // Inverse 'transforms' a point.
@@ -86,7 +87,8 @@ template <class I>
 inline void
 transformInv(const I& e, const size_t d, const size_t n, I& a)
 {
-	a.rotl(d, n); //#D d+1, n );
+	assert(a.size() == n);
+	a.rotl(d);
 	a ^= e;
 }
 
@@ -206,7 +208,7 @@ coordsToIndex(const P* const p, // [in ] point
 
 	if (n <= FBV_BITS) {
 		// Intermediate variables will fit in fixed width
-		_coordsToIndex<P, H, CFixBitVec>(p, m, n, h, CFixBitVec{});
+		_coordsToIndex<P, H, CFixBitVec>(p, m, n, h, CFixBitVec(n));
 	} else {
 		// Otherwise, they must be BigBitVecs
 		_coordsToIndex<P, H, CBigBitVec>(p, m, n, h, CBigBitVec(n));
@@ -277,7 +279,7 @@ indexToCoords(P* const     p, // [out] point
 
 	if (n <= FBV_BITS) {
 		// Intermediate variables will fit in fixed width
-		_indexToCoords<P, H, CFixBitVec>(p, m, n, h, CFixBitVec{});
+		_indexToCoords<P, H, CFixBitVec>(p, m, n, h, CFixBitVec(n));
 	} else {
 		// Otherwise, they must be BigBitVecs
 		_indexToCoords<P, H, CBigBitVec>(p, m, n, h, CBigBitVec(n));
@@ -320,7 +322,7 @@ _coordsToCompactIndex(const P* const      p,
 		_coordsToIndex<P, CBigBitVec, I>(p, m, n, h, std::move(scratch), ds);
 		compactIndex<CBigBitVec, HC>(ms, ds, n, m, h, hc);
 	} else {
-		CFixBitVec h;
+		CFixBitVec h(mn);
 		_coordsToIndex<P, CFixBitVec, I>(p, m, n, h, std::move(scratch), ds);
 		compactIndex<CFixBitVec, HC>(ms, ds, n, m, h, hc);
 	}
@@ -347,7 +349,7 @@ coordsToCompactIndex(
 	if (n <= FBV_BITS) {
 		// Intermediate variables will fit in fixed width?
 		_coordsToCompactIndex<P, HC, CFixBitVec>(
-		  p, ms, n, hc, CFixBitVec{}, M, m);
+		  p, ms, n, hc, CFixBitVec(n), M, m);
 	} else {
 		// Otherwise, they must be BigBitVecs.
 		_coordsToCompactIndex<P, HC, CBigBitVec>(
@@ -403,7 +405,8 @@ _compactIndexToCoords(P* const      p,
 		size_t b = 0;
 		extractMask<I>(ms, n, d, static_cast<size_t>(i), mask, b);
 		ptrn = e;
-		ptrn.rotr(d, n); //#D ptrn.Rotr(d+1,n);
+		assert(ptrn.size() == n);
+		ptrn.rotr(d);
 
 		// Get the Hilbert index bits
 		M -= b;
@@ -447,9 +450,9 @@ compactIndexToCoords(
 {
 	if (n <= FBV_BITS) {
 		// Intermediate variables will fit in fixed width
-		CFixBitVec scratch;
+		CFixBitVec scratch(n);
 		_compactIndexToCoords<P, HC, CFixBitVec>(
-		  p, ms, n, hc, CFixBitVec{}, M, m);
+		  p, ms, n, hc, std::move(scratch), M, m);
 	} else {
 		// Otherwise, they must be BigBitVecs
 		CBigBitVec scratch(n);
diff --git a/test/test_bitvec.cpp b/test/test_bitvec.cpp
index 2fa62ca..178b39a 100644
--- a/test/test_bitvec.cpp
+++ b/test/test_bitvec.cpp
@@ -200,13 +200,13 @@ void
 test_left_rotate(Context& ctx)
 {
 	const T v = make_random_bitvec<T, N>(ctx);
-	for (size_t width = 0; width < std::min(N, size_t(128)); ++width) {
-		for (size_t bits = 0; bits <= width; ++bits) {
-			T r = v;
-			r.rotl(bits, width);
+	for (size_t bits = 0; bits <= N; ++bits) {
+		T r = v;
+		r.rotl(bits);
 
-			for (size_t i = 0; i < width; ++i) {
-				assert(r.test((i + bits) % width) == v.test(i));
+		if (N > 0) {
+			for (size_t i = 0; i < N; ++i) {
+				assert(r.test((i + bits) % N) == v.test(i));
 			}
 		}
 	}
@@ -217,13 +217,13 @@ void
 test_right_rotate(Context& ctx)
 {
 	const T v = make_random_bitvec<T, N>(ctx);
-	for (size_t width = 0; width < std::min(N, size_t(128)); ++width) {
-		for (size_t bits = 0; bits <= width; ++bits) {
-			T r = v;
-			r.rotr(bits, width);
+	for (size_t bits = 0; bits <= N; ++bits) {
+		T r = v;
+		r.rotr(bits);
 
-			for (size_t i = 0; i < width; ++i) {
-				assert(r.test(i) == v.test((i + bits) % width));
+		if (N > 0) {
+			for (size_t i = 0; i < N; ++i) {
+				assert(r.test(i) == v.test((i + bits) % N));
 			}
 		}
 	}