bitstring.cpp #1

//========= Copyright  1996-2005, Valve Corporation, All rights reserved. ============//
//
// Purpose:		Arbitrary length bit string
//				** NOTE: This class does NOT override the bitwise operators
//						 as doing so would require overriding the operators
//						 to allocate memory for the returned bitstring.  This method
//						 would be prone to memory leaks as the calling party
//						 would have to remember to delete the memory.  Funtions
//						 are used instead to require the calling party to allocate
//						 and destroy their own memory
//
// $Workfile:     $
// $Date:         $
// $NoKeywords: $
//=============================================================================//

#include "cbase.h"

#include <limits.h>

#include "bitstring.h"
#include "utlbuffer.h"
#include "tier0/dbg.h"

// memdbgon must be the last include file in a .cpp file!!!
#include "tier0/memdbgon.h"

//-----------------------------------------------------------------------------
// Init static vars
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
// Purpose: Calculate a mask for the last int in the array
// Input  : numBits - 
// Output : static int
//-----------------------------------------------------------------------------

unsigned g_BitStringEndMasks[] = 
{
	0x00000000,
	0xfffffffe,
	0xfffffffc,
	0xfffffff8,
	0xfffffff0,
	0xffffffe0,
	0xffffffc0,
	0xffffff80,
	0xffffff00,
	0xfffffe00,
	0xfffffc00,
	0xfffff800,
	0xfffff000,
	0xffffe000,
	0xffffc000,
	0xffff8000,
	0xffff0000,
	0xfffe0000,
	0xfffc0000,
	0xfff80000,
	0xfff00000,
	0xffe00000,
	0xffc00000,
	0xff800000,
	0xff000000,
	0xfe000000,
	0xfc000000,
	0xf8000000,
	0xf0000000,
	0xe0000000,
	0xc0000000,
	0x80000000,
};

//-----------------------------------------------------------------------------
// Purpose: Print bits for debugging purposes
// Input  :
// Output :
//-----------------------------------------------------------------------------

void DebugPrintBitStringBits( const int *pInts, int nInts )
{
	for (int i=0;i<nInts;i++) 
	{
		for (int j =0; j<BITS_PER_INT;j++) 
		{
			Msg( "%d", (pInts[i] & (1<<j)) ? 1:0);
		}
	}
	Msg( "\n");
}

//-----------------------------------------------------------------------------
// Purpose: Saves a bit string to the given file
// Input  :
// Output :
//-----------------------------------------------------------------------------
void SaveBitString(const int *pInts, int nInts, CUtlBuffer& buf)
{
	for (int i=0;i<nInts;i++) 
	{
		buf.Printf("%d ", pInts[i]);
	}
	buf.Printf("\n");
}

//-----------------------------------------------------------------------------
// Purpose: Loads a bit string from the given file
// Input  :
// Output :
//-----------------------------------------------------------------------------

void LoadBitString(int *pInts, int nInts, CUtlBuffer& buf)
{
	for (int i=0; i<nInts; i++) 
	{
		buf.Scanf("%d", &pInts[i]);
	}
}


//-----------------------------------------------------------------------------

void CVariableBitStringBase::ValidateOperand( const CVariableBitStringBase &operand ) const
{
	Assert(Size() == operand.Size());
}

//-----------------------------------------------------------------------------
// Purpose: Resizes the bit string to a new number of bits
// Input  : resizeNumBits - 
//-----------------------------------------------------------------------------
void CVariableBitStringBase::Resize( int resizeNumBits )
{
	Assert( resizeNumBits >= 0 && resizeNumBits <= USHRT_MAX );

	int newIntCount = CalcNumIntsForBits( resizeNumBits );
	if ( newIntCount != GetNumInts() )
	{
		if ( GetInts() )
		{
			ReallocInts( newIntCount );
			if ( resizeNumBits >= Size() )
			{
				GetInts()[GetNumInts() - 1] &= ~GetEndMask();
				memset( GetInts() + GetNumInts(), 0, (newIntCount - GetNumInts()) * sizeof(int) );
			}
		}
		else
		{
			// Figure out how many ints are needed
			AllocInts( newIntCount );

			// Initialize bitstring by clearing all bits
			memset( GetInts(), 0, newIntCount * sizeof(int) );
		}
		m_numInts = newIntCount;
	} 
	else if ( resizeNumBits >= Size() && GetInts() )
		GetInts()[GetNumInts() - 1] &= ~GetEndMask();

	// store the new size and end mask
	m_numBits = resizeNumBits;
}

//-----------------------------------------------------------------------------
// Purpose: Allocate the storage for the ints
// Input  : numInts - 
//-----------------------------------------------------------------------------
void CVariableBitStringBase::AllocInts( int numInts )
{
	Assert( !m_pInt );

	if ( numInts == 0 )
		return;

	if ( numInts == 1 )
	{
		m_pInt = &m_iBitStringStorage;
		return;
	}

	m_pInt = (int *)malloc( numInts * sizeof(int) );
}


//-----------------------------------------------------------------------------
// Purpose: Reallocate the storage for the ints
// Input  : numInts - 
//-----------------------------------------------------------------------------
void CVariableBitStringBase::ReallocInts( int numInts )
{
	Assert( GetInts() );
	if ( numInts == 0)
	{
		FreeInts();
		return;
	}

	if ( m_pInt == &m_iBitStringStorage )
	{
		if ( numInts != 1 )
		{
			m_pInt = ((int *)malloc( numInts * sizeof(int) ));
			*m_pInt = m_iBitStringStorage;
		}

		return;
	}

	if ( numInts == 1 )
	{
		m_iBitStringStorage = *m_pInt;
		free( m_pInt );
		m_pInt = &m_iBitStringStorage;
		return;
	}

	m_pInt = (int *)realloc( m_pInt,  numInts * sizeof(int) );
}


//-----------------------------------------------------------------------------
// Purpose: Free storage allocated with AllocInts
//-----------------------------------------------------------------------------
void CVariableBitStringBase::FreeInts( void )
{
	if ( m_numInts > 1 )
	{
		free( m_pInt );
	}
	m_pInt = NULL;
}

//-----------------------------------------------------------------------------

#ifdef DEBUG
CON_COMMAND(test_bitstring, "Tests the bit string class")
{
	// This function is only testing new features (toml 11-10-02)

	int i, j;

	// Variable sized
	CBitString one, two, three;

	for ( i = 0; i < 100; i++ )
	{
		one.Resize( random->RandomInt(1, USHRT_MAX ) );
	}

	one.Resize( 0 );

	one.Resize( 2 );

	for ( i = 0; i < 14; i++ )
	{
		for ( j = 0; j < 64; j++)
		{
			int bit = random->RandomInt(0, one.Size() - 1 );
			Assert(!one.GetBit(bit));
			one.SetBit( bit );
			Assert(one.GetBit(bit));
			one.ClearBit( bit );
			Assert(!one.GetBit(bit));
		}
		one.Resize( one.Size() * 2 );
	}
	
	one.Resize( 100 );
	one.SetBit( 50 );
	one.Resize( 101 );
	Assert(one.GetBit(50));
	one.Resize( 1010 );
	Assert(one.GetBit(50));
	one.Resize( 49 );
	one.Resize( 100 );
	Assert(!one.GetBit(50));

	Assert( one.IsAllClear() );
	two.Resize( one.Size() );
	one.Not( &two );
	Assert( !two.IsAllClear() );
	Assert( two.IsAllSet() );

	// Fixed sized
	CFixedBitString<1> fbs1;	Assert( fbs1.GetEndMask() == GetEndMask( fbs1.Size() ) );
	CFixedBitString<2> fbs2;	Assert( fbs2.GetEndMask() == GetEndMask( fbs2.Size() ) );
	CFixedBitString<3> fbs3;	Assert( fbs3.GetEndMask() == GetEndMask( fbs3.Size() ) );
	CFixedBitString<4> fbs4;	Assert( fbs4.GetEndMask() == GetEndMask( fbs4.Size() ) );
	CFixedBitString<5> fbs5;	Assert( fbs5.GetEndMask() == GetEndMask( fbs5.Size() ) );
	CFixedBitString<6> fbs6;	Assert( fbs6.GetEndMask() == GetEndMask( fbs6.Size() ) );
	CFixedBitString<7> fbs7;	Assert( fbs7.GetEndMask() == GetEndMask( fbs7.Size() ) );
	CFixedBitString<8> fbs8;	Assert( fbs8.GetEndMask() == GetEndMask( fbs8.Size() ) );
	CFixedBitString<9> fbs9;	Assert( fbs9.GetEndMask() == GetEndMask( fbs9.Size() ) );
	CFixedBitString<10> fbs10;	Assert( fbs10.GetEndMask() == GetEndMask( fbs10.Size() ) );
	CFixedBitString<11> fbs11;	Assert( fbs11.GetEndMask() == GetEndMask( fbs11.Size() ) );
	CFixedBitString<12> fbs12;	Assert( fbs12.GetEndMask() == GetEndMask( fbs12.Size() ) );
	CFixedBitString<13> fbs13;	Assert( fbs13.GetEndMask() == GetEndMask( fbs13.Size() ) );
	CFixedBitString<14> fbs14;	Assert( fbs14.GetEndMask() == GetEndMask( fbs14.Size() ) );
	CFixedBitString<15> fbs15;	Assert( fbs15.GetEndMask() == GetEndMask( fbs15.Size() ) );
	CFixedBitString<16> fbs16;	Assert( fbs16.GetEndMask() == GetEndMask( fbs16.Size() ) );
	CFixedBitString<17> fbs17;	Assert( fbs17.GetEndMask() == GetEndMask( fbs17.Size() ) );
	CFixedBitString<18> fbs18;	Assert( fbs18.GetEndMask() == GetEndMask( fbs18.Size() ) );
	CFixedBitString<19> fbs19;	Assert( fbs19.GetEndMask() == GetEndMask( fbs19.Size() ) );
	CFixedBitString<20> fbs20;	Assert( fbs20.GetEndMask() == GetEndMask( fbs20.Size() ) );
	CFixedBitString<21> fbs21;	Assert( fbs21.GetEndMask() == GetEndMask( fbs21.Size() ) );
	CFixedBitString<22> fbs22;	Assert( fbs22.GetEndMask() == GetEndMask( fbs22.Size() ) );
	CFixedBitString<23> fbs23;	Assert( fbs23.GetEndMask() == GetEndMask( fbs23.Size() ) );
	CFixedBitString<24> fbs24;	Assert( fbs24.GetEndMask() == GetEndMask( fbs24.Size() ) );
	CFixedBitString<25> fbs25;	Assert( fbs25.GetEndMask() == GetEndMask( fbs25.Size() ) );
	CFixedBitString<26> fbs26;	Assert( fbs26.GetEndMask() == GetEndMask( fbs26.Size() ) );
	CFixedBitString<27> fbs27;	Assert( fbs27.GetEndMask() == GetEndMask( fbs27.Size() ) );
	CFixedBitString<28> fbs28;	Assert( fbs28.GetEndMask() == GetEndMask( fbs28.Size() ) );
	CFixedBitString<29> fbs29;	Assert( fbs29.GetEndMask() == GetEndMask( fbs29.Size() ) );
	CFixedBitString<30> fbs30;	Assert( fbs30.GetEndMask() == GetEndMask( fbs30.Size() ) );
	CFixedBitString<31> fbs31;	Assert( fbs31.GetEndMask() == GetEndMask( fbs31.Size() ) );
	CFixedBitString<32> fbs32;	Assert( fbs32.GetEndMask() == GetEndMask( fbs32.Size() ) );
	CFixedBitString<33> fbs33;	Assert( fbs33.GetEndMask() == GetEndMask( fbs33.Size() ) );
	CFixedBitString<34> fbs34;	Assert( fbs34.GetEndMask() == GetEndMask( fbs34.Size() ) );
	CFixedBitString<35> fbs35;	Assert( fbs35.GetEndMask() == GetEndMask( fbs35.Size() ) );
}
#endif