/*
 * 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));

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
	size()
	{
		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 &
	reset()
	{
		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
	test(
		int iIndex
	       ) const
	{
		assert( 0 <= iIndex && iIndex < FBV_BITS );
		return ( (m_uiRack & (FBV1<<iIndex)) > 0 );
	}

	// Sets the value of the nth bit.
	CFixBitVec &
	set(
		int iIndex,
		bool bBit = true
	       )
	{
		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 &
	toggle(
		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
	none() 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 &
	flip()
	{
		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_assert( 8*sizeof(FBV_UINT) == FBV_BITS, "" );
	static_assert( (sizeof(FBV_UINT) == 4) || (sizeof(FBV_UINT) == 8), "" );

	FBV_UINT	m_uiRack;
};


#endif