aboutsummaryrefslogtreecommitdiffstats
path: root/Hilbert/FixBitVec.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'Hilbert/FixBitVec.hpp')
-rw-r--r--Hilbert/FixBitVec.hpp538
1 files changed, 538 insertions, 0 deletions
diff --git a/Hilbert/FixBitVec.hpp b/Hilbert/FixBitVec.hpp
new file mode 100644
index 0000000..84015cf
--- /dev/null
+++ b/Hilbert/FixBitVec.hpp
@@ -0,0 +1,538 @@
+/*
+ * Copyright (C) 2006-2007 Chris Hamilton <chamilton@cs.dal.ca>
+ * Copyright (C) 2015 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 _FIXBITVEC_HPP_
+#define _FIXBITVEC_HPP_
+
+
+#include <inttypes.h>
+#include <Hilbert/Common.hpp>
+
+
+// This must be an unsigned integer that is either
+// 32 or 64 bits. Otherwise, there are places in the
+// code that simply will not work.
+// For speed, this should be the native word size.
+typedef uint64_t FBV_UINT;
+#define FBV_BITS 64
+
+#define FBV0 ((FBV_UINT)0)
+#define FBV1 ((FBV_UINT)1)
+#define FBV1S (~FBV0)
+#define FBVN1S(n) (n==FBV_BITS?FBV1S:(FBV1<<n)-1)
+#define FBVMOD(i,m) if((i)>=(m))(i)-=(m)*((i)/(m));
+
+#define COMPILE_TIME_ASSERT(pred) switch(0){case 0:case pred:;}
+
+enum EBitVecType
+{
+ eFix,
+ eBig
+};
+
+
+class CFixBitVec
+{
+public:
+
+ static EBitVecType
+ type()
+ {
+ return eFix;
+ }
+
+ // Default constructor. The bits parameter
+ // is completely ignored, but accepted in order
+ // to look and feel the same as a BigBitVec.
+ CFixBitVec(
+ int iBits = FBV_BITS
+ )
+ {
+ return;
+ }
+
+ // Copy constructor.
+ CFixBitVec(
+ const CFixBitVec &cFBV
+ )
+ {
+ m_uiRack = cFBV.m_uiRack;
+ }
+
+ // Returns the current size in bits.
+ int
+ getSize()
+ {
+ return FBV_BITS;
+ }
+
+ // Sets the size. This is a dummy
+ // function just for BigBitVec compatibility.
+ CFixBitVec &
+ setSize(
+ int iBits
+ )
+ {
+ return (*this);
+ }
+
+ // Zeros the bit-vector.
+ CFixBitVec &
+ zero()
+ {
+ m_uiRack = 0;
+ 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=(
+ const CFixBitVec &cFBV
+ )
+ {
+ m_uiRack = cFBV.m_uiRack;
+ return (*this);
+ }
+
+ // Assignment operator.
+ CFixBitVec &
+ operator=(
+ FBV_UINT i
+ )
+ {
+ m_uiRack = i;
+ return (*this);
+ }
+
+ // Returns the value of the nth bit.
+ bool
+ getBit(
+ int iIndex
+ ) const
+ {
+ assert( 0 <= iIndex && iIndex < FBV_BITS );
+ return ( (m_uiRack & (FBV1<<iIndex)) > 0 );
+ }
+
+ // Sets the value of the nth bit.
+ CFixBitVec &
+ setBit(
+ int iIndex,
+ bool bBit
+ )
+ {
+ assert( 0 <= iIndex && iIndex < FBV_BITS );
+ FBV_UINT m = (FBV1<<iIndex);
+ m_uiRack |= m;
+ if ( !bBit ) m_uiRack ^= m;
+ return (*this);
+ }
+
+ // Toggles the value of the nth bit.
+ CFixBitVec &
+ toggleBit(
+ int iIndex
+ )
+ {
+ assert( 0 <= iIndex && iIndex < FBV_BITS );
+ m_uiRack ^= (FBV1<<iIndex);
+ return (*this);
+ }
+
+ // AND operation in place.
+ CFixBitVec &
+ operator&=(
+ const CFixBitVec &cFBV
+ )
+ {
+ m_uiRack &= cFBV.m_uiRack;
+ return (*this);
+ }
+ CFixBitVec &
+ operator&=(
+ FBV_UINT i
+ )
+ {
+ m_uiRack &= i;
+ return (*this);
+ }
+
+ // AND operation.
+ CFixBitVec
+ operator&(
+ const CFixBitVec &cFBV
+ ) const
+ {
+ CFixBitVec t(*this);
+ t &= cFBV;
+ return t;
+ }
+ CFixBitVec
+ operator&(
+ FBV_UINT i
+ )
+ {
+ CFixBitVec t(*this);
+ t &= i;
+ return t;
+ }
+
+ // OR operation in place.
+ CFixBitVec &
+ operator|=(
+ const CFixBitVec &cFBV
+ )
+ {
+ m_uiRack |= cFBV.m_uiRack;
+ return (*this);
+ }
+ CFixBitVec &
+ operator|=(
+ FBV_UINT i
+ )
+ {
+ m_uiRack |= i;
+ return (*this);
+ }
+
+ // OR operation.
+ CFixBitVec
+ operator|(
+ const CFixBitVec &cFBV
+ ) const
+ {
+ CFixBitVec t(*this);
+ t |= cFBV;
+ return t;
+ }
+ CFixBitVec
+ operator|(
+ FBV_UINT i
+ )
+ {
+ CFixBitVec t(*this);
+ t |= i;
+ return t;
+ }
+
+
+ // XOR operation in place.
+ CFixBitVec &
+ operator^=(
+ const CFixBitVec &cFBV
+ )
+ {
+ m_uiRack ^= cFBV.m_uiRack;
+ return (*this);
+ }
+ CFixBitVec &
+ operator^=(
+ FBV_UINT i
+ )
+ {
+ m_uiRack ^= i;
+ return (*this);
+ }
+
+ // XOR operation.
+ CFixBitVec
+ operator^(
+ const CFixBitVec &cFBV
+ ) const
+ {
+ CFixBitVec t(*this);
+ t ^= cFBV;
+ return t;
+ }
+ CFixBitVec
+ operator^(
+ FBV_UINT i
+ )
+ {
+ CFixBitVec t(*this);
+ t ^= i;
+ return t;
+ }
+
+ // Shift left operation, in place.
+ CFixBitVec &
+ operator<<=(
+ int iBits
+ )
+ {
+ m_uiRack <<= iBits;
+ return (*this);
+ }
+
+ // Shift left operation.
+ CFixBitVec
+ operator<<(
+ int iBits
+ ) const
+ {
+ CFixBitVec t(*this);
+ t <<= iBits;
+ return t;
+ }
+
+ // Shift right operation, in place.
+ CFixBitVec &
+ operator>>=(
+ int iBits
+ )
+ {
+ m_uiRack >>= iBits;
+ return (*this);
+ }
+
+ // Shift right operation.
+ CFixBitVec
+ operator>>(
+ int iBits
+ ) const
+ {
+ CFixBitVec t(*this);
+ t >>= iBits;
+ return t;
+ }
+
+ // Right rotation, in place.
+ CFixBitVec &
+ rotr(
+ int iBits,
+ int iWidth
+ )
+ {
+ assert( iBits >= 0 );
+ assert( iWidth > 0 );
+ assert( iBits < iWidth );//#D FBVMOD(iBits,iWidth);
+ m_uiRack &= FBVN1S(iWidth);
+ m_uiRack = (m_uiRack>>iBits) | (m_uiRack<<(iWidth-iBits));
+ m_uiRack &= FBVN1S(iWidth);
+ return (*this);
+ }
+
+ // Right rotation.
+ CFixBitVec
+ rotrCopy(
+ int iBits,
+ int iWidth
+ ) const
+ {
+ CFixBitVec t(*this);
+ t.rotr(iBits,iWidth);
+ return t;
+ }
+
+ // Left rotation, in place.
+ CFixBitVec &
+ rotl(
+ int iBits,
+ int iWidth
+ )
+ {
+ assert( iBits >= 0 );
+ assert( iWidth > 0 );
+ assert( iBits < iWidth );//#D FBVMOD(iBits,iWidth);
+ m_uiRack &= FBVN1S(iWidth);
+ m_uiRack = (m_uiRack<<iBits) | (m_uiRack>>(iWidth-iBits));
+ m_uiRack &= FBVN1S(iWidth);
+ return (*this);
+ }
+
+ // Left rotation.
+ CFixBitVec
+ rotlCopy(
+ int iBits,
+ int iWidth
+ ) const
+ {
+ CFixBitVec t(*this);
+ t.rotl(iBits,iWidth);
+ return t;
+ }
+
+ // Is the bit rack zero valued?
+ bool
+ isZero() const
+ {
+ return m_uiRack == 0;
+ }
+
+ // Returns the number of trailing set bits.
+ int
+ tsb() const
+ {
+ FBV_UINT i = m_uiRack;
+ int c = 0;
+
+#if FBV_BITS == 64
+ if ( i == FBV1S ) return 64;
+ if ( (i&FBVN1S(32)) == FBVN1S(32) ) { i>>=32; c^=32; }
+#elif FBV_BITS == 32
+ if ( i == FBV1S ) return 32;
+#endif
+ if ( (i&FBVN1S(16)) == FBVN1S(16) ) { i>>=16; c^=16; }
+ if ( (i&FBVN1S( 8)) == FBVN1S( 8) ) { i>>= 8; c^= 8; }
+ if ( (i&FBVN1S( 4)) == FBVN1S( 4) ) { i>>= 4; c^= 4; }
+ if ( (i&FBVN1S( 2)) == FBVN1S( 2) ) { i>>= 2; c^= 2; }
+ if ( (i&FBVN1S( 1)) == FBVN1S( 1) ) { i>>= 1; c^= 1; }
+
+ return c;
+ }
+
+ // Returns the index of the most significant bit
+ int
+ msb() const
+ {
+ FBV_UINT i = m_uiRack;
+ int c = 0;
+#if FBV_BITS == 64
+ if ( i == FBV0 ) return 0;
+ if ( i & (FBVN1S(32) << 32) ) { i >>= 32; c ^= 32; }
+#elif FBV_BITS == 32
+ if ( i == FBV0 ) return 0;
+#endif
+ if ( i & (FBVN1S(16) << 16) ) { i >>= 16; c ^= 16; }
+ if ( i & (FBVN1S( 8) << 8) ) { i >>= 8; c ^= 8; }
+ if ( i & (FBVN1S( 4) << 4) ) { i >>= 4; c ^= 4; }
+ if ( i & (FBVN1S( 2) << 2) ) { i >>= 2; c ^= 2; }
+ if ( i & (FBVN1S( 1) << 1) ) { i >>= 1; c ^= 1; }
+ return ++c;
+ }
+
+ // Returns the index of the first set bit, numbered from
+ // 1 to n. 0 means there were no set bits.
+ int
+ fsb() const
+ {
+ FBV_UINT i = m_uiRack;
+ int c = 0;
+
+#if FBV_BITS == 64
+ if ( i == FBV0 ) return 0;
+ if ( (i&FBVN1S(32)) == FBV0 ) { i>>=32; c^=32; }
+#elif FBV_BITS == 32
+ if ( i == FBV0 ) return 0;
+#endif
+ if ( (i&FBVN1S(16)) == FBV0 ) { i>>=16; c^=16; }
+ if ( (i&FBVN1S( 8)) == FBV0 ) { i>>= 8; c^= 8; }
+ if ( (i&FBVN1S( 4)) == FBV0 ) { i>>= 4; c^= 4; }
+ if ( (i&FBVN1S( 2)) == FBV0 ) { i>>= 2; c^= 2; }
+ if ( (i&FBVN1S( 1)) == FBV0 ) { i>>= 1; c^= 1; }
+
+ return ++c;
+ }
+
+ // Prefix decrement. Returns true if a carry
+ // was generated.
+ bool
+ operator--()
+ {
+ return ( m_uiRack-- == 0 );
+ }
+
+ // Calculates the Gray Code.
+ CFixBitVec &
+ grayCode()
+ {
+ m_uiRack ^= (m_uiRack>>1);
+ return (*this);
+ }
+
+ // Calculates the Gray Code Inverse
+ CFixBitVec &
+ grayCodeInv()
+ {
+ m_uiRack ^= (m_uiRack>>1);
+ m_uiRack ^= (m_uiRack>>2);
+ m_uiRack ^= (m_uiRack>>4);
+ m_uiRack ^= (m_uiRack>> 8);
+ m_uiRack ^= (m_uiRack>>16);
+#if FBV_BITS == 64
+ m_uiRack ^= (m_uiRack>>32);
+#endif
+ return (*this);
+ }
+
+ // Ones-complements the rack
+ CFixBitVec &
+ complement()
+ {
+ m_uiRack = ~m_uiRack;
+ return (*this);
+ }
+
+ // Returns the first rack.
+ FBV_UINT &
+ rack()
+ {
+ return m_uiRack;
+ }
+ FBV_UINT
+ rack() const
+ {
+ return m_uiRack;
+ }
+
+ // Return a pointer to the racks
+ FBV_UINT *
+ racks()
+ {
+ return &m_uiRack;
+ }
+ const FBV_UINT *
+ racks() const
+ {
+ return &m_uiRack;
+ }
+
+ // Returns the number of racks.
+ int
+ rackCount()
+ {
+ return 1;
+ }
+
+private:
+
+ static void
+ compileTimeAssertions()
+ {
+ COMPILE_TIME_ASSERT( 8*sizeof(FBV_UINT) == FBV_BITS );
+ COMPILE_TIME_ASSERT( (sizeof(FBV_UINT) == 4) || (sizeof(FBV_UINT) == 8) );
+ }
+
+ FBV_UINT m_uiRack;
+};
+
+
+#endif
generated by cgit v1.2.1 (git 2.18.0) at 2024-09-09 20:22:18 +0000