diff options
Diffstat (limited to 'chilbert/BigBitVec.hpp')
| -rw-r--r-- | chilbert/BigBitVec.hpp | 608 |
1 files changed, 242 insertions, 366 deletions
diff --git a/chilbert/BigBitVec.hpp b/chilbert/BigBitVec.hpp index 129f5d8..c5ade5d 100644 --- a/chilbert/BigBitVec.hpp +++ b/chilbert/BigBitVec.hpp @@ -19,574 +19,450 @@ #ifndef CHILBERT_BIGBITVEC_HPP #define CHILBERT_BIGBITVEC_HPP - #include "chilbert/FixBitVec.hpp" +#include <algorithm> #include <cassert> #include <cstring> #include <memory> -#define BBV_MIN(a,b) ((a)<(b)?(a):(b)) -#define BBV_MAX(a,b) ((a)>(b)?(a):(b)) -#define FBVS_NEEDED(b) ((BBV_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, 1) + FBV_BITS - 1) / FBV_BITS) +#define BBV_MODSPLIT(r, b, k) \ + { \ + b = (k); \ + r = b / FBV_BITS; \ + b -= r * FBV_BITS; \ + } namespace chilbert { class CBigBitVec { public: - - // Constructor, with optional number of bits. - CBigBitVec( - int iBits = FBV_BITS - ) - : m_pcRacks{new FBV_UINT[iBits == 0 ? 0 : FBVS_NEEDED(iBits)]} - , m_iRacks{iBits == 0 ? 0 : FBVS_NEEDED(iBits)} + CBigBitVec(const int bits = 0) + : m_pcRacks{new FBV_UINT[bits == 0 ? 0 : FBVS_NEEDED(bits)]} + , m_iRacks{bits == 0 ? 0 : FBVS_NEEDED(bits)} { } - - - // Copy construct. Creates duplicate. - CBigBitVec( - const CBigBitVec &cBBV - ) - : m_pcRacks{new FBV_UINT[cBBV.m_iRacks]} - , m_iRacks{cBBV.m_iRacks} + + CBigBitVec(const CBigBitVec& vec) + : m_pcRacks{new FBV_UINT[vec.m_iRacks]} + , m_iRacks{vec.m_iRacks} { - if (cBBV.m_pcRacks) { + if (vec.m_pcRacks) { memcpy(m_pcRacks.get(), - cBBV.m_pcRacks.get(), + vec.m_pcRacks.get(), sizeof(FBV_UINT) * m_iRacks); } } - // Move construct. - CBigBitVec( - CBigBitVec &&cBBV - ) = default; + CBigBitVec(CBigBitVec&& vec) = default; - // Copy constructor. - CBigBitVec( - const CFixBitVec &cFBV - ) - : m_pcRacks{new FBV_UINT[1]} - , m_iRacks{1} + CBigBitVec(const CFixBitVec& vec) + : m_pcRacks{new FBV_UINT[1]} + , m_iRacks{1} { - m_pcRacks[0] = cFBV.rack(); + m_pcRacks[0] = vec.rack(); } + /// Return the size in bits + int size() const { return m_iRacks * FBV_BITS; } - // Returns the current size in bits. - int - size() const + /// Set all bits to zero + CBigBitVec& reset() { - return m_iRacks*FBV_BITS; - } - - - // zeros the bit-vector. - CBigBitVec & - reset() - { - memset(m_pcRacks.get(), 0, sizeof(CFixBitVec) * m_iRacks); - - return (*this); + return *this; } - - // truncates the bit-vector to a given precision in - // bits (zeroes MSBs without shrinking the vector) - CBigBitVec & - truncate( - int iBits - ) + /// Truncate to a given precision in bits (zero MSBs) + CBigBitVec& truncate(const int bits) { - assert( iBits >= 0 && iBits <= size() ); - int r, b, i; + assert(bits >= 0 && bits <= size()); + int r, b; + + BBV_MODSPLIT(r, b, bits); - BBV_MODSPLIT(r,b,iBits); - - if ( r >= m_iRacks ) - return (*this); + if (r >= m_iRacks) { + return *this; + } // Truncate rack that contains the split point - m_pcRacks[r] &= FBVN1S(iBits); - - for ( i = r+1; i < m_iRacks; i++ ) + m_pcRacks[r] &= FBVN1S(bits); + + for (int i = r + 1; i < m_iRacks; ++i) { m_pcRacks[i] = 0; + } - return (*this); + return *this; } - - // Assignment operator. No resizing. - CBigBitVec & - operator=( - const CBigBitVec &cBBV - ) + /// Non-resizing assignment + CBigBitVec& operator=(const CBigBitVec& vec) { - if ( m_iRacks < cBBV.m_iRacks ) - { - memcpy(m_pcRacks.get(), cBBV.m_pcRacks.get(), sizeof(CFixBitVec) * m_iRacks); + if (m_iRacks < vec.m_iRacks) { + memcpy(m_pcRacks.get(), + vec.m_pcRacks.get(), + sizeof(CFixBitVec) * m_iRacks); } else { if (m_pcRacks) { - if (cBBV.m_pcRacks) { + if (vec.m_pcRacks) { memcpy(m_pcRacks.get(), - cBBV.m_pcRacks.get(), - sizeof(CFixBitVec) * cBBV.m_iRacks); + vec.m_pcRacks.get(), + sizeof(CFixBitVec) * vec.m_iRacks); } - memset(m_pcRacks.get() + cBBV.m_iRacks, + memset(m_pcRacks.get() + vec.m_iRacks, 0, - sizeof(CFixBitVec) * (m_iRacks - cBBV.m_iRacks)); + sizeof(CFixBitVec) * (m_iRacks - vec.m_iRacks)); } } - return (*this); + return *this; } - CBigBitVec & - operator=( - CBigBitVec &&cBBV - ) = default; - CBigBitVec & - operator=( - const CFixBitVec &cFBV - ) + CBigBitVec& operator=(CBigBitVec&& vec) = default; + + CBigBitVec& operator=(const CFixBitVec& vec) { - m_pcRacks[0] = cFBV.rack(); + m_pcRacks[0] = vec.rack(); memset(m_pcRacks.get() + 1, 0, sizeof(FBV_UINT) * (m_iRacks - 1)); - return (*this); + return *this; } - CBigBitVec & - operator=( - FBV_UINT j - ) + + CBigBitVec& operator=(const FBV_UINT j) { m_pcRacks[0] = j; memset(m_pcRacks.get() + 1, 0, sizeof(CFixBitVec) * (m_iRacks - 1)); - return (*this); + return *this; } - // Returns the value of the nth bit. - bool - test( - int iIndex - ) const + /// Return the value of the `index`th bit + bool test(const int index) const { - assert( iIndex >= 0 && iIndex < size() ); + assert(index >= 0 && index < size()); int r, b; - BBV_MODSPLIT(r,b,iIndex); + BBV_MODSPLIT(r, b, index); return testBit(m_pcRacks[r], b); } - - // Sets the value of the nth bit. - CBigBitVec & - set( - int iIndex, - bool bBit = true - ) + /// Set the `index`th bit to 1 + CBigBitVec& set(const int index) { - assert( iIndex >= 0 && iIndex < size() ); + assert(index >= 0 && index < size()); int r, b; - BBV_MODSPLIT(r,b,iIndex); - setBit(m_pcRacks[r], b, bBit); - return (*this); + BBV_MODSPLIT(r, b, index); + setBit(m_pcRacks[r], b); + return *this; } - - // Toggles the value of the nth bit. - CBigBitVec & - toggle( - int iIndex - ) + /// Reset the `index`th bit to 0 + CBigBitVec& reset(const int index) { - assert( iIndex >= 0 && iIndex < size() ); + assert(index >= 0 && index < size()); int r, b; - BBV_MODSPLIT(r,b,iIndex); - m_pcRacks[r] ^= (FBV1<<iIndex); - return (*this); + BBV_MODSPLIT(r, b, index); + m_pcRacks[r] &= ~((FBV_UINT)1 << b); + return *this; } + /// Set the `index`th bit to `value` + CBigBitVec& set(const int index, const bool value) + { + assert(index >= 0 && index < size()); + int r, b; + BBV_MODSPLIT(r, b, index); + setBit(m_pcRacks[r], b, value); + return *this; + } - // In place AND. - CBigBitVec & - operator&=( - const CBigBitVec &cBBV - ) + /// Toggle the value of the `index`th bit + CBigBitVec& toggle(const int index) { - int i; - - for ( i = 0; i < BBV_MIN(m_iRacks,cBBV.m_iRacks); i++ ) - m_pcRacks[i] &= cBBV.m_pcRacks[i]; - - return (*this); + assert(index >= 0 && index < size()); + int r, b; + BBV_MODSPLIT(r, b, index); + m_pcRacks[r] ^= (FBV1 << index); + return *this; } + CBigBitVec& operator&=(const CBigBitVec& vec) + { + for (int i = 0; i < std::min(m_iRacks, vec.m_iRacks); ++i) { + m_pcRacks[i] &= vec.m_pcRacks[i]; + } - // AND operator. - CBigBitVec - operator&( - const CBigBitVec &cBBV - ) const + return *this; + } + + CBigBitVec operator&(const CBigBitVec& vec) const { - CBigBitVec t( *this ); - t &= cBBV; + CBigBitVec t(*this); + t &= vec; return t; } - - // In place OR. - CBigBitVec & - operator|=( - const CBigBitVec &cBBV - ) + CBigBitVec& operator|=(const CBigBitVec& vec) { - int i; - - for ( i = 0; i < BBV_MIN(m_iRacks,cBBV.m_iRacks); i++ ) - m_pcRacks[i] |= cBBV.m_pcRacks[i]; - - return (*this); - } + for (int i = 0; i < std::min(m_iRacks, vec.m_iRacks); ++i) { + m_pcRacks[i] |= vec.m_pcRacks[i]; + } + return *this; + } - // OR operator. - CBigBitVec - operator|( - const CBigBitVec &cBBV - ) const + CBigBitVec operator|(const CBigBitVec& vec) const { - CBigBitVec t( *this ); - t |= cBBV; + CBigBitVec t(*this); + t |= vec; return t; } - - // In place XOR. - CBigBitVec & - operator^=( - const CBigBitVec &cBBV - ) + CBigBitVec& operator^=(const CBigBitVec& vec) { - int i; - - for ( i = 0; i < BBV_MIN(m_iRacks,cBBV.m_iRacks); i++ ) - m_pcRacks[i] ^= cBBV.m_pcRacks[i]; - - return (*this); - } + for (int i = 0; i < std::min(m_iRacks, vec.m_iRacks); ++i) { + m_pcRacks[i] ^= vec.m_pcRacks[i]; + } + return *this; + } - // XOR operator. - CBigBitVec - operator^( - const CBigBitVec &cBBV - ) const + CBigBitVec operator^(const CBigBitVec& vec) const { - CBigBitVec t( *this ); - t ^= cBBV; + CBigBitVec t(*this); + t ^= vec; return t; } - - // Shift left operation, in place. - CBigBitVec & - operator<<=( - int iBits - ) + CBigBitVec& operator<<=(const int bits) { - assert( iBits >= 0 ); + assert(bits >= 0); int r, b, i; // No shift? - if ( iBits == 0 ) - return (*this); + if (bits == 0) { + return *this; + } - BBV_MODSPLIT(r,b,iBits); + BBV_MODSPLIT(r, b, bits); // All racks? - if ( r >= m_iRacks ) - { + if (r >= m_iRacks) { reset(); - return (*this); + return *this; } // Do rack shifts. - if ( r > 0 ) - { - for ( i = m_iRacks-1; i >= r; i-- ) - m_pcRacks[i] = m_pcRacks[i-r]; - for ( ; i >= 0; i-- ) + if (r > 0) { + for (i = m_iRacks - 1; i >= r; --i) { + m_pcRacks[i] = m_pcRacks[i - r]; + } + for (; i >= 0; --i) { m_pcRacks[i] = 0; + } } // Do bit shifts. - if ( b > 0 ) - { + if (b > 0) { int bi = FBV_BITS - b; - for ( i = m_iRacks-1; i >= r+1; i-- ) - { + for (i = m_iRacks - 1; i >= r + 1; --i) { m_pcRacks[i] <<= b; - m_pcRacks[i] |= m_pcRacks[i-1] >> bi; + m_pcRacks[i] |= m_pcRacks[i - 1] >> bi; } m_pcRacks[i] <<= b; } - return (*this); + return *this; } - - // Shift left operation. - CBigBitVec - operator<<( - int iBits - ) const + CBigBitVec operator<<(const int bits) const { - CBigBitVec t( *this ); - t <<= iBits; + CBigBitVec t(*this); + t <<= bits; return t; } - - // Shift right operation, in place. - CBigBitVec & - operator>>=( - int iBits - ) + CBigBitVec& operator>>=(const int bits) { - assert( iBits >= 0 ); + assert(bits >= 0); int r, b, i; // No shift? - if ( iBits == 0 ) - return (*this); + if (bits == 0) { + return *this; + } - BBV_MODSPLIT(r,b,iBits); + BBV_MODSPLIT(r, b, bits); // All racks? - if ( r >= m_iRacks ) - { + if (r >= m_iRacks) { reset(); - return (*this); + return *this; } // Do rack shifts. - if ( r > 0 ) - { - for ( i = 0; i < m_iRacks-r; i++ ) - m_pcRacks[i] = m_pcRacks[i+r]; - for ( ; i < m_iRacks; i++ ) + if (r > 0) { + for (i = 0; i < m_iRacks - r; ++i) { + m_pcRacks[i] = m_pcRacks[i + r]; + } + for (; i < m_iRacks; ++i) { m_pcRacks[i] = 0; + } } // Do bit shifts. - if ( b > 0 ) - { + if (b > 0) { int bi = FBV_BITS - b; - for ( i = 0; i < m_iRacks-r-1; i++ ) - { + for (i = 0; i < m_iRacks - r - 1; ++i) { m_pcRacks[i] >>= b; - m_pcRacks[i] |= m_pcRacks[i+1] << bi; + m_pcRacks[i] |= m_pcRacks[i + 1] << bi; } m_pcRacks[i] >>= b; } - return (*this); + return *this; } - - // Shift right operation. - CBigBitVec - operator>>( - int iBits - ) const + CBigBitVec operator>>(const int bits) const { - CBigBitVec t( *this ); - t >>= iBits; + CBigBitVec t(*this); + t >>= bits; return t; } - - // Right rotation, in place. - CBigBitVec & - rotr( - int iBits, - int iWidth - ) + /// Right-rotate the least significant `width` bits by `bits` positions + CBigBitVec& rotr(const int bits, int width) { - assert( iBits >= 0 ); + assert(bits >= 0); // Fill in the width, if necessary. - if ( iWidth <= 0 ) - iWidth = size(); + if (width <= 0) { + width = size(); + } // Modulo the number of bits. - assert( iBits < iWidth ); - if ( iBits == 0 ) return (*this); + assert(bits < width); + if (bits == 0) { + return *this; + } // Ensure we are truncated appropriately. - truncate(iWidth); + truncate(width); - CBigBitVec t1( *this ); - (*this) >>= iBits; - t1 <<= (iWidth-iBits); + CBigBitVec t1(*this); + (*this) >>= bits; + t1 <<= (width - bits); (*this) |= t1; - - truncate(iWidth); - return (*this); - } + truncate(width); + return *this; + } - // Left rotation, in place. - CBigBitVec & - rotl( - int iBits, - int iWidth - ) + /// Left-rotate the least significant `width` bits by `bits` positions + CBigBitVec& rotl(const int bits, int width) { - assert( iBits >= 0 ); + assert(bits >= 0); // Fill in the width, if necessary. - if ( iWidth <= 0 ) - iWidth = size(); + if (width <= 0) { + width = size(); + } // Modulo the number of bits. - assert( iBits < iWidth ); - if ( iBits == 0 ) return (*this); + assert(bits < width); + if (bits == 0) { + return *this; + } // Ensure we are truncated appropriately. - truncate(iWidth); + truncate(width); - CBigBitVec t1( *this ); - (*this) <<= iBits; - t1 >>= (iWidth-iBits); + CBigBitVec t1(*this); + (*this) <<= bits; + t1 >>= (width - bits); (*this) |= t1; - truncate(iWidth); + truncate(width); - return (*this); + return *this; } - - // Returns true if the rack is zero valued. - bool - none() const + /// Return true iff all bits are zero + bool none() const { - int i; - for ( i = 0; i < m_iRacks; i++ ) - if ( m_pcRacks[i] ) return false; + for (int i = 0; i < m_iRacks; ++i) { + if (m_pcRacks[i]) { + return false; + } + } return true; } - - // Returns the index of the first set bit. - // (numbered 1 to n, with 0 meaning no bits were set) - int - fsb() const + /// Return 1 + the index of the first set bit, or 0 if there are none + int fsb() const { - for (int i = 0; i < m_iRacks; ++i ) - { + for (int i = 0; i < m_iRacks; ++i) { const int j = ffs(m_pcRacks[i]); - if ( j ) { + if (j) { return (i * FBV_BITS) + j; } } return 0; } - - // Complement - CBigBitVec & - flip() + /// Flip all bits (one's complement) + CBigBitVec& flip() { - int i; - for ( i = 0; i < m_iRacks; i++ ) + for (int i = 0; i < m_iRacks; ++i) { m_pcRacks[i] = ~m_pcRacks[i]; - return (*this); - } - - - // Returns the first rack. - FBV_UINT & - rack() - { - return m_pcRacks[0]; - } - FBV_UINT - rack() const - { - return m_pcRacks[0]; + } + return *this; } + /// Return the first rack + FBV_UINT& rack() { return m_pcRacks[0]; } + FBV_UINT rack() const { return m_pcRacks[0]; } - // Returns the racks. - FBV_UINT * - racks() - { - return m_pcRacks.get(); - } - const FBV_UINT * - racks() const - { - return m_pcRacks.get(); - } - + /// Return a pointer to the racks + FBV_UINT* racks() { return m_pcRacks.get(); } + const FBV_UINT* racks() const { return m_pcRacks.get(); } - // Returns the number of racks. - int - rackCount() const - { - return m_iRacks; - } + /// Return the number of racks + int rackCount() const { return m_iRacks; } - private: - friend void grayCode<CBigBitVec>(CBigBitVec&); - friend void grayCodeInv<CBigBitVec>(CBigBitVec&); - // Right rotates entire racks (in place). - void - rackRotr( - int k - ) + void rackRotr(int k) { - assert( 0 <= k && k < m_iRacks ); - - int c, v; - FBV_UINT tmp; - - if (k == 0) return; - - c = 0; - for (v = 0; c < m_iRacks; v++) - { - int t = v, tp = v + k; - tmp = m_pcRacks[v]; + assert(0 <= k && 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]; c++; - while (tp != v) - { + while (tp != v) { m_pcRacks[t] = m_pcRacks[tp]; - t = tp; + t = tp; tp += k; - if (tp >= m_iRacks) tp -= m_iRacks; + if (tp >= m_iRacks) { + tp -= m_iRacks; + } c++; } m_pcRacks[t] = tmp; } - - return; } - std::unique_ptr<FBV_UINT[]> m_pcRacks; - int m_iRacks; + int m_iRacks; }; template <> @@ -595,10 +471,10 @@ grayCode(CBigBitVec& value) { FBV_UINT s = 0; - for (int i = value.rackCount() - 1; i >= 0; i--) { + for (int i = value.rackCount() - 1; i >= 0; --i) { const FBV_UINT t = value.racks()[i] & 1; - grayCode(value.m_pcRacks[i]); - value.m_pcRacks[i] ^= (s << (FBV_BITS - 1)); + grayCode(value.racks()[i]); + value.racks()[i] ^= (s << (FBV_BITS - 1)); s = t; } } @@ -610,7 +486,7 @@ grayCodeInv(CBigBitVec& value) FBV_UINT s = 0; for (int i = value.rackCount() - 1; i >= 0; --i) { - FBV_UINT& rack = value.m_pcRacks[i]; + FBV_UINT& rack = value.racks()[i]; grayCodeInv(rack); if (s) { rack = ~rack; |