aboutsummaryrefslogtreecommitdiffstats
path: root/Hilbert/BigBitVec.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'Hilbert/BigBitVec.hpp')
-rw-r--r--Hilbert/BigBitVec.hpp928
1 files changed, 928 insertions, 0 deletions
diff --git a/Hilbert/BigBitVec.hpp b/Hilbert/BigBitVec.hpp
new file mode 100644
index 0000000..2bb6db7
--- /dev/null
+++ b/Hilbert/BigBitVec.hpp
@@ -0,0 +1,928 @@
+/*
+ * Copyright (C) 2006-2007 Chris Hamilton <chamilton@cs.dal.ca>
+ * Copyright (C) 2016 David Robillard <d@drobilla.net>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#ifndef _BIGBITVEC_HPP_
+#define _BIGBITVEC_HPP_
+
+
+#include <Hilbert/Common.hpp>
+#include <Hilbert/FixBitVec.hpp>
+
+#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; }
+
+class CBigBitVec
+{
+public:
+
+ static EBitVecType
+ type()
+ {
+ return eBig;
+ }
+
+
+ // Constructor, with optional number of bits.
+ CBigBitVec(
+ int iBits = FBV_BITS
+ )
+ {
+ // Determine number of racks required.
+ m_iRacks = iBits == 0 ? 0 : FBVS_NEEDED(iBits);
+
+ // Allocate the memory.
+ if (m_iRacks > 0) {
+ m_pcRacks = new CFixBitVec[m_iRacks];
+ } else {
+ m_pcRacks = NULL;
+ }
+
+ return;
+ }
+
+
+ // Copy construct. Creates duplicate.
+ CBigBitVec(
+ const CBigBitVec &cBBV
+ )
+ {
+ m_iRacks = cBBV.m_iRacks;
+ m_pcRacks = new CFixBitVec[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<void*>(m_pcRacks),
+ static_cast<const void*>(cBBV.m_pcRacks),
+ sizeof(CFixBitVec)*m_iRacks );
+ }
+
+ return;
+ }
+
+ // Move construct.
+ CBigBitVec(
+ CBigBitVec &&cBBV
+ )
+ {
+ m_iRacks = cBBV.m_iRacks;
+ m_pcRacks = cBBV.m_pcRacks;
+ cBBV.m_iRacks = 0;
+ cBBV.m_pcRacks = NULL;
+ }
+
+ // Copy constructor.
+ CBigBitVec(
+ const CFixBitVec &cFBV
+ )
+ {
+ m_iRacks = 1;
+ m_pcRacks = new CFixBitVec[m_iRacks];
+
+ m_pcRacks[0] = cFBV;
+
+ return;
+ }
+
+
+ // Destructor
+ ~CBigBitVec()
+ {
+ delete [] m_pcRacks;
+
+ return;
+ }
+
+
+ // Returns the current size in bits.
+ int
+ getSize() const
+ {
+ return m_iRacks*FBV_BITS;
+ }
+
+
+ // Resize function. Returns the number of bits
+ // we can accomodate after resizing.
+ CBigBitVec &
+ setSize(
+ int iBits
+ )
+ {
+ int i;
+
+ // How many racks do we need?
+ int iRacks = FBVS_NEEDED(iBits);
+
+ // Same size?
+ if ( iRacks == m_iRacks )
+ return (*this);
+
+ // Allocate new racks.
+ CFixBitVec *pcRacks = new CFixBitVec[iRacks];
+
+ // Copy over the old values.
+ /*for ( i = 0; i < BBV_MIN(iRacks,m_iRacks); i++ )
+ pcRacks[i] = m_pcRacks[i];*/
+ i = BBV_MIN(iRacks,m_iRacks);
+ if (m_pcRacks) {
+ memcpy( static_cast<void*>(pcRacks),
+ static_cast<const void*>(m_pcRacks),
+ sizeof(CFixBitVec)*i );
+ }
+
+ // zero the new values
+ /*for ( ; i < iRacks; i++ )
+ pcRacks[i].zero();*/
+ if ( iRacks > i )
+ memset( static_cast<void*>(pcRacks + i), 0,
+ sizeof(CFixBitVec)*(iRacks-i) );
+
+ // Release the old stuff.
+ delete [] m_pcRacks;
+
+ // Replace old with new.
+ m_iRacks = iRacks;
+ m_pcRacks = pcRacks;
+
+ return (*this);
+ }
+
+
+ // zeros the bit-vector.
+ CBigBitVec &
+ zero()
+ {
+
+ /*int i;
+ for ( i = 0; i < m_iRacks; i++ )
+ m_pcRacks[i].zero();*/
+ memset( static_cast<void*>(m_pcRacks), 0,
+ sizeof(CFixBitVec)*m_iRacks );
+
+ return (*this);
+ }
+
+
+ // truncates the bit-vector to a given precision in
+ // bits (zeroes MSBs without shrinking the vector)
+ CBigBitVec &
+ truncate(
+ int iBits
+ )
+ {
+ assert( iBits >= 0 && iBits <= getSize() );
+ int r, b, i;
+
+ BBV_MODSPLIT(r,b,iBits);
+
+ if ( r >= m_iRacks )
+ return (*this);
+
+ m_pcRacks[r].truncate(b);
+
+ for ( i = r+1; i < m_iRacks; i++ )
+ m_pcRacks[i].zero();
+
+ return (*this);
+ }
+
+
+ // Assignment operator. No resizing.
+ CBigBitVec &
+ operator=(
+ const CBigBitVec &cBBV
+ )
+ {
+ 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<void*>(m_pcRacks),
+ static_cast<const void*>(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].zero();*/
+ if (m_pcRacks) {
+ if (cBBV.m_pcRacks) {
+ memcpy( static_cast<void*>(m_pcRacks),
+ static_cast<const void*>(cBBV.m_pcRacks),
+ sizeof(CFixBitVec)*cBBV.m_iRacks );
+ }
+ memset( static_cast<void*>(m_pcRacks+cBBV.m_iRacks),
+ 0, sizeof(CFixBitVec)*(m_iRacks-cBBV.m_iRacks) );
+ }
+ }
+
+ return (*this);
+ }
+ CBigBitVec &
+ operator=(
+ CBigBitVec &&cBBV
+ )
+ {
+ if (&cBBV != this) {
+ m_iRacks = cBBV.m_iRacks;
+ m_pcRacks = cBBV.m_pcRacks;
+ cBBV.m_iRacks = 0;
+ cBBV.m_pcRacks = NULL;
+ }
+
+ return (*this);
+ }
+ CBigBitVec &
+ operator=(
+ const CFixBitVec &cFBV
+ )
+ {
+ m_pcRacks[0] = cFBV;
+ /*int i;
+ for ( i = 1; i < m_iRacks; i++ )
+ m_pcRacks[i].zero();*/
+ memset( static_cast<void*>(m_pcRacks+1),
+ 0, sizeof(CFixBitVec)*(m_iRacks-1) );
+ return (*this);
+ }
+ CBigBitVec &
+ operator=(
+ FBV_UINT j
+ )
+ {
+ m_pcRacks[0] = j;
+ /*int i;
+ for ( i = 1; i < m_iRacks; i++ )
+ m_pcRacks[i].zero();*/
+ memset( static_cast<void*>(m_pcRacks+1),
+ 0, sizeof(CFixBitVec)*(m_iRacks-1) );
+ return (*this);
+ }
+
+ // Returns the value of the nth bit.
+ bool
+ getBit(
+ int iIndex
+ ) const
+ {
+ assert( iIndex >= 0 && iIndex < getSize() );
+ int r, b;
+ BBV_MODSPLIT(r,b,iIndex);
+ return m_pcRacks[r].getBit(b);
+ }
+
+
+ // Sets the value of the nth bit.
+ CBigBitVec &
+ setBit(
+ int iIndex,
+ bool bBit
+ )
+ {
+ assert( iIndex >= 0 && iIndex < getSize() );
+ int r, b;
+ BBV_MODSPLIT(r,b,iIndex);
+ m_pcRacks[r].setBit(b,bBit);
+ return (*this);
+ }
+
+
+ // Toggles the value of the nth bit.
+ CBigBitVec &
+ toggleBit(
+ int iIndex
+ )
+ {
+ assert( iIndex >= 0 && iIndex < getSize() );
+ int r, b;
+ BBV_MODSPLIT(r,b,iIndex);
+ m_pcRacks[r].toggleBit(b);
+ return (*this);
+ }
+
+
+ // In place AND.
+ CBigBitVec &
+ operator&=(
+ const CBigBitVec &cBBV
+ )
+ {
+ int i;
+
+ for ( i = 0; i < BBV_MIN(m_iRacks,cBBV.m_iRacks); i++ )
+ m_pcRacks[i] &= cBBV.m_pcRacks[i];
+
+ return (*this);
+ }
+ CBigBitVec &
+ operator&=(
+ const CFixBitVec &r
+ )
+ {
+ m_pcRacks[0] &= r;
+ return (*this);
+ }
+ CBigBitVec &
+ operator&=(
+ FBV_UINT i
+ )
+ {
+ m_pcRacks[0] &= i;
+ return (*this);
+ }
+
+
+ // AND operator.
+ CBigBitVec
+ operator&(
+ const CBigBitVec &cBBV
+ ) const
+ {
+ CBigBitVec t( *this );
+ t &= cBBV;
+
+ return t;
+ }
+ CBigBitVec
+ operator&(
+ const CFixBitVec &r
+ )
+ {
+ CBigBitVec t( *this );
+ t &= r;
+
+ return t;
+ }
+ CBigBitVec
+ operator&(
+ FBV_UINT i
+ )
+ {
+ CBigBitVec t( *this );
+ t &= i;
+
+ return t;
+ }
+
+
+ // In place OR.
+ CBigBitVec &
+ operator|=(
+ const CBigBitVec &cBBV
+ )
+ {
+ int i;
+
+ for ( i = 0; i < BBV_MIN(m_iRacks,cBBV.m_iRacks); i++ )
+ m_pcRacks[i] |= cBBV.m_pcRacks[i];
+
+ return (*this);
+ }
+ CBigBitVec &
+ operator|=(
+ const CFixBitVec &r
+ )
+ {
+ m_pcRacks[0] |= r;
+ return (*this);
+ }
+ CBigBitVec &
+ operator|=(
+ FBV_UINT i
+ )
+ {
+ m_pcRacks[0] |= i;
+ return (*this);
+ }
+
+
+ // OR operator.
+ CBigBitVec
+ operator|(
+ const CBigBitVec &cBBV
+ ) const
+ {
+ CBigBitVec t( *this );
+ t |= cBBV;
+
+ return t;
+ }
+ CBigBitVec
+ operator|(
+ const CFixBitVec &r
+ )
+ {
+ CBigBitVec t( *this );
+ t |= r;
+
+ return t;
+ }
+ CBigBitVec
+ operator|(
+ FBV_UINT i
+ )
+ {
+ CBigBitVec t( *this );
+ t |= i;
+
+ return t;
+ }
+
+
+ // In place XOR.
+ CBigBitVec &
+ operator^=(
+ const CBigBitVec &cBBV
+ )
+ {
+ int i;
+
+ for ( i = 0; i < BBV_MIN(m_iRacks,cBBV.m_iRacks); i++ )
+ m_pcRacks[i] ^= cBBV.m_pcRacks[i];
+
+ return (*this);
+ }
+ CBigBitVec &
+ operator^=(
+ const CFixBitVec &r
+ )
+ {
+ m_pcRacks[0] ^= r;
+ return (*this);
+ }
+ CBigBitVec &
+ operator^=(
+ FBV_UINT i
+ )
+ {
+ m_pcRacks[0] ^= i;
+ return (*this);
+ }
+
+
+ // XOR operator.
+ CBigBitVec
+ operator^(
+ const CBigBitVec &cBBV
+ ) const
+ {
+ CBigBitVec t( *this );
+ t ^= cBBV;
+
+ return t;
+ }
+ CBigBitVec
+ operator^(
+ const CFixBitVec &r
+ )
+ {
+ CBigBitVec t( *this );
+ t ^= r;
+
+ return t;
+ }
+ CBigBitVec
+ operator^(
+ FBV_UINT i
+ )
+ {
+ CBigBitVec t( *this );
+ t ^= i;
+
+ return t;
+ }
+
+
+ // Shift left operation, in place.
+ CBigBitVec &
+ operator<<=(
+ int iBits
+ )
+ {
+ assert( iBits >= 0 );
+ int r, b, i;
+
+ // No shift?
+ if ( iBits == 0 )
+ return (*this);
+
+ BBV_MODSPLIT(r,b,iBits);
+
+ // All racks?
+ if ( r >= m_iRacks )
+ {
+ zero();
+ 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-- )
+ m_pcRacks[i].zero();
+ }
+
+ // Do bit shifts.
+ if ( b > 0 )
+ {
+ int bi = FBV_BITS - b;
+ for ( i = m_iRacks-1; i >= r+1; i-- )
+ {
+ m_pcRacks[i] <<= b;
+ m_pcRacks[i] |= m_pcRacks[i-1] >> bi;
+ }
+ m_pcRacks[i] <<= b;
+ }
+
+ return (*this);
+ }
+
+
+ // Shift left operation.
+ CBigBitVec
+ operator<<(
+ int iBits
+ ) const
+ {
+ CBigBitVec t( *this );
+ t <<= iBits;
+ return t;
+ }
+
+
+ // Shift right operation, in place.
+ CBigBitVec &
+ operator>>=(
+ int iBits
+ )
+ {
+ assert( iBits >= 0 );
+ int r, b, i;
+
+ // No shift?
+ if ( iBits == 0 )
+ return (*this);
+
+ BBV_MODSPLIT(r,b,iBits);
+
+ // All racks?
+ if ( r >= m_iRacks )
+ {
+ zero();
+ 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++ )
+ m_pcRacks[i].zero();
+ }
+
+ // Do bit shifts.
+ if ( b > 0 )
+ {
+ int bi = FBV_BITS - b;
+ for ( i = 0; i < m_iRacks-r-1; i++ )
+ {
+ m_pcRacks[i] >>= b;
+ m_pcRacks[i] |= m_pcRacks[i+1] << bi;
+ }
+ m_pcRacks[i] >>= b;
+ }
+
+ return (*this);
+ }
+
+
+ // Shift right operation.
+ CBigBitVec
+ operator>>(
+ int iBits
+ ) const
+ {
+ CBigBitVec t( *this );
+ t >>= iBits;
+ return t;
+ }
+
+
+ // Right rotation, in place.
+ CBigBitVec &
+ rotr(
+ int iBits,
+ int iWidth
+ )
+ {
+ assert( iBits >= 0 );
+
+ // Fill in the width, if necessary.
+ if ( iWidth <= 0 )
+ iWidth = getSize();
+
+ // Modulo the number of bits.
+ //FBVMOD(iBits,iWidth);
+ assert( iBits < iWidth );
+ if ( iBits == 0 ) return (*this);
+
+ // Ensure we are truncated appropriately.
+ truncate(iWidth);
+
+ CBigBitVec t1( *this );
+ (*this) >>= iBits;
+ t1 <<= (iWidth-iBits);
+ (*this) |= t1;
+
+ truncate(iWidth);
+
+ return (*this);
+ }
+
+
+ // Right rotation.
+ CBigBitVec
+ rotrCopy(
+ int iBits,
+ int iWidth
+ ) const
+ {
+ CBigBitVec t( *this );
+ t.rotr(iBits,iWidth);
+ return t;
+ }
+
+
+ // Left rotation, in place.
+ CBigBitVec &
+ rotl(
+ int iBits,
+ int iWidth
+ )
+ {
+ assert( iBits >= 0 );
+
+ // Fill in the width, if necessary.
+ if ( iWidth <= 0 )
+ iWidth = getSize();
+
+ // Modulo the number of bits.
+ //FBVMOD(iBits,iWidth);
+ assert( iBits < iWidth );
+ if ( iBits == 0 ) return (*this);
+
+ // Ensure we are truncated appropriately.
+ truncate(iWidth);
+
+ CBigBitVec t1( *this );
+ (*this) <<= iBits;
+ t1 >>= (iWidth-iBits);
+ (*this) |= t1;
+
+ truncate(iWidth);
+
+ return (*this);
+ }
+
+
+ // Left rotation.
+ CBigBitVec
+ rotlCopy(
+ int iBits,
+ int iWidth
+ ) const
+ {
+ CBigBitVec t( *this );
+ t.rotl(iBits,iWidth);
+ return t;
+ }
+
+
+ // Returns true if the rack is zero valued.
+ bool
+ isZero() const
+ {
+ int i;
+ for ( i = 0; i < m_iRacks; i++ )
+ if ( !m_pcRacks[i].isZero() ) return false;
+ return true;
+ }
+
+
+ // Returns the number of trailing set bits.
+ int
+ tsb() const
+ {
+ int c, i, j;
+ c = 0;
+ for ( i = 0; i < m_iRacks; i++ )
+ {
+ j = m_pcRacks[i].tsb();
+ c += j;
+ if ( j < FBV_BITS )
+ break;
+ }
+ return c;
+ }
+
+ // OB:
+ // Returns the index of the most significant bit (numbered
+ // 1 to n)
+ int
+ msb() const
+ {
+ int c, i, j = 0;
+ c = FBV_BITS * m_iRacks;
+ for ( i = m_iRacks - 1; i >= 0 && !j; i-- )
+ {
+ j = m_pcRacks[i].msb();
+ if (j)
+ return c - (FBV_BITS - j);
+ else
+ c -= FBV_BITS;
+ }
+ return 0;
+ }
+
+ // Returns the index of the first set bit.
+ // (numbered 1 to n, with 0 meaning no bits were set)
+ int
+ fsb() const
+ {
+ int c, i, j;
+ c = 0;
+ for ( i = 0; i < m_iRacks; i++ )
+ {
+ j = m_pcRacks[i].fsb();
+ if ( j < FBV_BITS )
+ return c + j;
+ else
+ c += FBV_BITS;
+ }
+ return 0;
+ }
+
+
+ // Prefix decrement. Returns true if there
+ // was a carry, false otherwise.
+ bool
+ operator--()
+ {
+ int i = 0;
+ bool b;
+ while ( i < m_iRacks && (b = --m_pcRacks[i]) ) i++;
+
+ return b;
+ }
+
+
+ // 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);
+ }
+
+
+ // Gray Code Inverse
+ CBigBitVec &
+ grayCodeInv()
+ {
+ int i;
+ FBV_UINT s = 0;
+
+ for ( i = m_iRacks-1; i >= 0; i-- )
+ {
+ m_pcRacks[i].grayCodeInv();
+ if ( s ) m_pcRacks[i].complement();
+ s = m_pcRacks[i].rack() & 1;
+ }
+ return (*this);
+ }
+
+
+ // Complement
+ CBigBitVec &
+ complement()
+ {
+ int i;
+ for ( i = 0; i < m_iRacks; i++ )
+ m_pcRacks[i].complement();
+ return (*this);
+ }
+
+
+ // Returns the first rack.
+ FBV_UINT &
+ rack()
+ {
+ return m_pcRacks[0].rack();
+ }
+ FBV_UINT
+ rack() const
+ {
+ return m_pcRacks[0].rack();
+ }
+
+
+ // Returns the racks.
+ FBV_UINT *
+ racks()
+ {
+ return reinterpret_cast<FBV_UINT*>(m_pcRacks);
+ }
+ const FBV_UINT *
+ racks() const
+ {
+ return reinterpret_cast<FBV_UINT*>(m_pcRacks);
+ }
+
+
+ // Returns the number of racks.
+ int
+ rackCount() const
+ {
+ return m_iRacks;
+ }
+
+
+private:
+
+ // Right rotates entire racks (in place).
+ void
+ rackRotr(
+ int k
+ )
+ {
+ assert( 0 <= k && k < m_iRacks );
+
+ int c, v;
+ CFixBitVec tmp;
+
+ if (k == 0) return;
+
+ c = 0;
+ for (v = 0; c < m_iRacks; v++)
+ {
+ int t = v, tp = v + k;
+ 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;
+ }
+
+ return;
+ }
+
+
+ CFixBitVec *m_pcRacks;
+ int m_iRacks;
+};
+
+#endif
generated by cgit v1.2.1 (git 2.18.0) at 2024-09-09 20:29:14 +0000