From a7667a2540a9336c141a5f26a802a61bd719f79b Mon Sep 17 00:00:00 2001 From: David Robillard Date: Sun, 5 Aug 2018 15:23:54 +0200 Subject: Use raw integers in BigBitVec --- chilbert/Algorithm.hpp | 2 +- chilbert/BigBitVec.hpp | 135 +++++++++++++++++++----------------------------- chilbert/FixBitVec.hpp | 27 +++------- chilbert/Operations.hpp | 12 +++++ 4 files changed, 72 insertions(+), 104 deletions(-) (limited to 'chilbert') diff --git a/chilbert/Algorithm.hpp b/chilbert/Algorithm.hpp index e522554..31ae8ca 100644 --- a/chilbert/Algorithm.hpp +++ b/chilbert/Algorithm.hpp @@ -251,7 +251,7 @@ namespace chilbert // t = GrayCode(w) t = w; - t.grayCode(); + grayCode(t); // Reverse the transform // l = T^{-1}_{(e,d)}(t) diff --git a/chilbert/BigBitVec.hpp b/chilbert/BigBitVec.hpp index 07f954a..5e29d1a 100644 --- a/chilbert/BigBitVec.hpp +++ b/chilbert/BigBitVec.hpp @@ -46,7 +46,7 @@ public: // Allocate the memory. if (m_iRacks > 0) { - m_pcRacks = new CFixBitVec[m_iRacks]; + m_pcRacks = new FBV_UINT[m_iRacks]; } else { m_pcRacks = nullptr; } @@ -61,16 +61,11 @@ public: ) { m_iRacks = cBBV.m_iRacks; - m_pcRacks = new CFixBitVec[m_iRacks]; + m_pcRacks = new FBV_UINT[m_iRacks]; // Copy the rack values. - /*int i; - for ( i = 0; i < m_iRacks; i++ ) - m_pcRacks[i] = cBBV.m_pcRacks[i];*/ if (cBBV.m_pcRacks) { - memcpy( static_cast(m_pcRacks), - static_cast(cBBV.m_pcRacks), - sizeof(CFixBitVec)*m_iRacks ); + memcpy(m_pcRacks, cBBV.m_pcRacks, sizeof(FBV_UINT) * m_iRacks); } return; @@ -93,9 +88,9 @@ public: ) { m_iRacks = 1; - m_pcRacks = new CFixBitVec[m_iRacks]; + m_pcRacks = new FBV_UINT[m_iRacks]; - m_pcRacks[0] = cFBV; + m_pcRacks[0] = cFBV.rack(); return; } @@ -123,11 +118,7 @@ public: reset() { - /*int i; - for ( i = 0; i < m_iRacks; i++ ) - m_pcRacks[i].reset();*/ - memset( static_cast(m_pcRacks), 0, - sizeof(CFixBitVec)*m_iRacks ); + memset(m_pcRacks, 0, sizeof(CFixBitVec) * m_iRacks); return (*this); } @@ -148,10 +139,11 @@ public: if ( r >= m_iRacks ) return (*this); - m_pcRacks[r].truncate(b); + // Truncate rack that contains the split point + m_pcRacks[r] &= FBVN1S(iBits); for ( i = r+1; i < m_iRacks; i++ ) - m_pcRacks[i].reset(); + m_pcRacks[i] = 0; return (*this); } @@ -165,28 +157,17 @@ public: { if ( m_iRacks < cBBV.m_iRacks ) { - /*int i; - for ( i = 0; i < m_iRacks; i++ ) - m_pcRacks[i] = cBBV.m_pcRacks[i];*/ - memcpy( static_cast(m_pcRacks), - static_cast(cBBV.m_pcRacks), - sizeof(CFixBitVec)*m_iRacks ); - } - else - { - /*int i; - for ( i = 0; i < cBBV.m_iRacks; i++ ) - m_pcRacks[i] = cBBV.m_pcRacks[i]; - for ( ; i < m_iRacks; i++ ) - m_pcRacks[i].reset();*/ + memcpy(m_pcRacks, cBBV.m_pcRacks, sizeof(CFixBitVec) * m_iRacks); + } else { if (m_pcRacks) { if (cBBV.m_pcRacks) { - memcpy( static_cast(m_pcRacks), - static_cast(cBBV.m_pcRacks), - sizeof(CFixBitVec)*cBBV.m_iRacks ); + memcpy(m_pcRacks, + cBBV.m_pcRacks, + sizeof(CFixBitVec) * cBBV.m_iRacks); } - memset( static_cast(m_pcRacks+cBBV.m_iRacks), - 0, sizeof(CFixBitVec)*(m_iRacks-cBBV.m_iRacks) ); + memset(m_pcRacks + cBBV.m_iRacks, + 0, + sizeof(CFixBitVec) * (m_iRacks - cBBV.m_iRacks)); } } @@ -211,12 +192,8 @@ public: const CFixBitVec &cFBV ) { - m_pcRacks[0] = cFBV; - /*int i; - for ( i = 1; i < m_iRacks; i++ ) - m_pcRacks[i].reset();*/ - memset( static_cast(m_pcRacks+1), - 0, sizeof(CFixBitVec)*(m_iRacks-1) ); + m_pcRacks[0] = cFBV.rack(); + memset(m_pcRacks + 1, 0, sizeof(FBV_UINT) * (m_iRacks - 1)); return (*this); } CBigBitVec & @@ -225,11 +202,7 @@ public: ) { m_pcRacks[0] = j; - /*int i; - for ( i = 1; i < m_iRacks; i++ ) - m_pcRacks[i].reset();*/ - memset( static_cast(m_pcRacks+1), - 0, sizeof(CFixBitVec)*(m_iRacks-1) ); + memset(m_pcRacks + 1, 0, sizeof(CFixBitVec) * (m_iRacks - 1)); return (*this); } @@ -242,7 +215,7 @@ public: assert( iIndex >= 0 && iIndex < size() ); int r, b; BBV_MODSPLIT(r,b,iIndex); - return m_pcRacks[r].test(b); + return testBit(m_pcRacks[r], b); } @@ -256,7 +229,7 @@ public: assert( iIndex >= 0 && iIndex < size() ); int r, b; BBV_MODSPLIT(r,b,iIndex); - m_pcRacks[r].set(b,bBit); + setBit(m_pcRacks[r], b, bBit); return (*this); } @@ -270,7 +243,7 @@ public: assert( iIndex >= 0 && iIndex < size() ); int r, b; BBV_MODSPLIT(r,b,iIndex); - m_pcRacks[r].toggle(b); + m_pcRacks[r] ^= (FBV1<= r; i-- ) m_pcRacks[i] = m_pcRacks[i-r]; for ( ; i >= 0; i-- ) - m_pcRacks[i].reset(); + m_pcRacks[i] = 0; } // Do bit shifts. @@ -446,7 +419,7 @@ public: for ( i = 0; i < m_iRacks-r; i++ ) m_pcRacks[i] = m_pcRacks[i+r]; for ( ; i < m_iRacks; i++ ) - m_pcRacks[i].reset(); + m_pcRacks[i] = 0; } // Do bit shifts. @@ -545,7 +518,7 @@ public: { int i; for ( i = 0; i < m_iRacks; i++ ) - if ( !m_pcRacks[i].none() ) return false; + if ( m_pcRacks[i] ) return false; return true; } @@ -557,7 +530,7 @@ public: { for (int i = 0; i < m_iRacks; ++i ) { - const int j = m_pcRacks[i].fsb(); + const int j = ffs(m_pcRacks[i]); if ( j ) { return (i * FBV_BITS) + j; } @@ -566,32 +539,13 @@ public: } - // Gray Code - CBigBitVec & - grayCode() - { - int i; - FBV_UINT s = 0; - - for ( i = m_iRacks-1; i >= 0; i-- ) - { - FBV_UINT t = m_pcRacks[i].rack() & 1; - m_pcRacks[i].grayCode(); - m_pcRacks[i] ^= (s<<(FBV_BITS-1)); - s = t; - } - - return (*this); - } - - // Complement CBigBitVec & flip() { int i; for ( i = 0; i < m_iRacks; i++ ) - m_pcRacks[i].flip(); + m_pcRacks[i] = ~m_pcRacks[i]; return (*this); } @@ -600,12 +554,12 @@ public: FBV_UINT & rack() { - return m_pcRacks[0].rack(); + return m_pcRacks[0]; } FBV_UINT rack() const { - return m_pcRacks[0].rack(); + return m_pcRacks[0]; } @@ -613,12 +567,12 @@ public: FBV_UINT * racks() { - return reinterpret_cast(m_pcRacks); + return m_pcRacks; } const FBV_UINT * racks() const { - return reinterpret_cast(m_pcRacks); + return m_pcRacks; } @@ -631,6 +585,7 @@ public: private: + friend void grayCode(CBigBitVec&); friend void grayCodeInv(CBigBitVec&); // Right rotates entire racks (in place). @@ -642,7 +597,7 @@ private: assert( 0 <= k && k < m_iRacks ); int c, v; - CFixBitVec tmp; + FBV_UINT tmp; if (k == 0) return; @@ -667,10 +622,24 @@ private: } - CFixBitVec *m_pcRacks; + FBV_UINT *m_pcRacks; int m_iRacks; }; +template <> +void +grayCode(CBigBitVec& value) +{ + FBV_UINT s = 0; + + 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)); + s = t; + } +} + template <> void grayCodeInv(CBigBitVec& value) @@ -678,12 +647,12 @@ grayCodeInv(CBigBitVec& value) FBV_UINT s = 0; for (int i = value.rackCount() - 1; i >= 0; --i) { - CFixBitVec& rack = value.m_pcRacks[i]; + FBV_UINT& rack = value.m_pcRacks[i]; grayCodeInv(rack); if (s) { - rack.flip(); + rack = ~rack; } - s = rack.test(0); + s = rack & 1; } } diff --git a/chilbert/FixBitVec.hpp b/chilbert/FixBitVec.hpp index c03bbd8..bea1c1a 100644 --- a/chilbert/FixBitVec.hpp +++ b/chilbert/FixBitVec.hpp @@ -75,18 +75,6 @@ public: return (*this); } - // Truncates the bit-vector to a given precision in - // bits (zeroes MSBs without shrinking the vector) - CFixBitVec & - truncate( - int iBits - ) - { - assert( 0 <= iBits && iBits <= FBV_BITS ); - m_uiRack &= FBVN1S(iBits); - return (*this); - } - // Assignment operator. CFixBitVec & operator=( @@ -304,14 +292,6 @@ public: } - // Calculates the Gray Code. - CFixBitVec & - grayCode() - { - m_uiRack ^= (m_uiRack>>1); - return (*this); - } - // Ones-complements the rack CFixBitVec & flip() @@ -358,6 +338,13 @@ private: FBV_UINT m_uiRack; }; +template <> +void +grayCode(CFixBitVec& value) +{ + value.rack() ^= (value.rack() >> 1); +} + template <> void grayCodeInv(CFixBitVec& value) diff --git a/chilbert/Operations.hpp b/chilbert/Operations.hpp index c50136a..578daaf 100644 --- a/chilbert/Operations.hpp +++ b/chilbert/Operations.hpp @@ -88,6 +88,18 @@ ffs(const unsigned long long field) return __builtin_ffsll(field); } +/// Calculates the Gray Code of `value` in place +template +std::enable_if_t::value> grayCode(T& value); + +/// Implementation of grayCode for any integral type +template +std::enable_if_t::value> +grayCode(T& value) +{ + value ^= (value >> 1); +} + /// Calculates the inverse Gray Code of `value` in place template std::enable_if_t::value> grayCodeInv(T& value); -- cgit v1.2.1