From 81f652c80c086ea008a4cd325f4e73764a9aa10a Mon Sep 17 00:00:00 2001 From: David Robillard Date: Sat, 18 Aug 2018 21:49:38 +0200 Subject: Add mask interface and isolate rack details from algorithm --- chilbert/FixBitVec.hpp | 184 ++++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 158 insertions(+), 26 deletions(-) (limited to 'chilbert/FixBitVec.hpp') diff --git a/chilbert/FixBitVec.hpp b/chilbert/FixBitVec.hpp index 36667f3..0dab483 100644 --- a/chilbert/FixBitVec.hpp +++ b/chilbert/FixBitVec.hpp @@ -47,6 +47,38 @@ public: static constexpr size_t bits_per_rack = sizeof(Rack) * CHAR_BIT; + /** Mask for a bit that can be incremented like an index. + * + * This enables fast iteration while setting or resetting bits since it is + * internally stored as a mask which avoids repeated index math. + */ + class Mask + { + public: + void operator++() { m_mask <<= 1; } + void operator--() { m_mask >>= 1; } + + bool operator==(const Mask& mask) const + { + return m_mask == mask.m_mask; + } + + bool operator!=(const Mask& mask) const + { + return m_mask == mask.m_mask; + } + + private: + friend class CFixBitVec; + + Mask(const size_t index) + : m_mask{index < bits_per_rack ? Rack{1} << index : 0} + { + } + + Rack m_mask; + }; + CFixBitVec(const size_t bits = bits_per_rack) : m_rack{0} { @@ -76,45 +108,55 @@ public: return *this; } + /// Return the value of the bit covered by `mask` + bool test(const Mask mask) const { return m_rack & mask.m_mask; } + /// Return the value of the `index`th bit - bool test(const size_t index) const + bool test(const size_t index) const { return test(mask(index)); } + + /// Set the bit covered by `mask` to 1 + CFixBitVec& set(const Mask mask) { - assert(index < bits_per_rack); - return ((m_rack & (FBV1 << index)) > 0); + m_rack |= mask.m_mask; + return *this; } /// Set the `index`th bit to 1 - CFixBitVec& set(const size_t index) + CFixBitVec& set(const size_t index) { return set(mask(index)); } + + /// Reset the bit covered by `mask` to 0 + CFixBitVec& reset(const Mask mask) { - assert(index < bits_per_rack); - m_rack |= (Rack{1} << index); + m_rack &= ~mask.m_mask; return *this; } /// Reset the `index`th bit to 0 - CFixBitVec& reset(const size_t index) + CFixBitVec& reset(const size_t index) { return reset(mask(index)); } + + /// Set the bit covered by `mask` to `value` + CFixBitVec& set(const Mask mask, const bool value) { - assert(index < bits_per_rack); - m_rack &= ~(Rack{1} << index); + m_rack ^= (-Rack{value} ^ m_rack) & mask.m_mask; return *this; } /// Set the `index`th bit to `value` CFixBitVec& set(const size_t index, const bool value) { - assert(index < bits_per_rack); - m_rack ^= (-Rack{value} ^ m_rack) & (Rack{1U} << index); - return *this; + return set(mask(index), value); } - /// Flip the value of the `index`th bit - CFixBitVec& flip(const size_t index) + /// Flip the value of the bit covered by `mask` + CFixBitVec& flip(const Mask mask) { - assert(index < bits_per_rack); - m_rack ^= (FBV1 << index); + m_rack ^= mask.m_mask; return *this; } + /// Flip the value of the `index`th bit + CFixBitVec& flip(const size_t index) { return flip(mask(index)); } + bool operator==(const CFixBitVec& vec) const { return m_rack == vec.m_rack; @@ -216,22 +258,30 @@ public: /// Right-rotate the least significant `width` bits by `bits` positions CFixBitVec& rotr(const size_t bits, const size_t width) { - assert(width > 0); - assert(bits < width); - m_rack &= FBVN1S(width); - m_rack = (m_rack >> bits) | (m_rack << (width - bits)); - m_rack &= FBVN1S(width); + 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); + } return *this; } /// Left-rotate the least significant `width` bits by `bits` positions CFixBitVec& rotl(const size_t bits, const size_t width) { - assert(width > 0); - assert(bits < width); - m_rack &= FBVN1S(width); - m_rack = (m_rack << bits) | (m_rack >> (width - bits)); - m_rack &= FBVN1S(width); + 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); + } return *this; } @@ -265,6 +315,88 @@ public: /// Return the number of racks int rackCount() const { return 1; } + template + class iterator_base : public Mask + { + public: + iterator_base& operator++() + { + Mask::operator++(); + return *this; + } + + iterator_base& operator--() + { + Mask::operator--(); + return *this; + } + + bool operator==(const iterator_base& iterator_base) const + { + return m_vec == iterator_base.m_vec && + Mask::operator==(iterator_base); + } + + bool operator!=(const iterator_base& iterator_base) const + { + return !operator==(iterator_base); + } + + bool operator*() const { return m_vec->test(*this); } + + protected: + iterator_base(BitVec& vec, const size_t index) + : Mask{index} + , m_vec{&vec} + { + } + + BitVec* m_vec; + }; + + class iterator : public iterator_base + { + public: + void set() { m_vec->set(*this); } + void reset() { m_vec->reset(*this); } + + private: + friend class CFixBitVec; + + iterator(CFixBitVec& vec, const size_t index) + : iterator_base{vec, index} + { + } + }; + + class const_iterator : public iterator_base + { + private: + friend class CFixBitVec; + + const_iterator(const CFixBitVec& vec, const size_t index) + : iterator_base{vec, index} + { + } + }; + + Mask mask(const size_t i = 0) const + { + assert(i <= size()); + return Mask{i}; + } + + iterator begin(const size_t i = 0) { return iterator(*this, i); } + + iterator end() { return iterator(*this, size()); } + + const_iterator begin(const size_t i = 0) const + { + return const_iterator(*this, i); + } + + const_iterator end() const { return const_iterator(*this, size()); } + private: static_assert(8 * sizeof(Rack) == bits_per_rack, ""); static_assert((sizeof(Rack) == 4) || (sizeof(Rack) == 8), ""); -- cgit v1.2.1