bitarray.cpp

The Bit Array structure provides a compacted arrays of Booleans, with one bit for each Boolean value

////////////////////////////////////////////////////////////////////////////
//
//	Inventor Name: Hatem Mostafa
//	Creation date: 15/1/2003
//
////////////////////////////////////////////////////////////////////////////
// BitArray.cpp : implementation of the CBitArray class
//

#include "stdafx.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

#define 	SEG_COUNT		10240

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CBitArray::CBitArray(bool bCompressed /*= false*/)
{
	InitValues();
	m_bCompressed = bCompressed;
}

CBitArray::CBitArray(CBitArray &src)
{
	InitValues();

	*this = src;
}

CBitArray::CBitArray(BYTE* pBuffer, int nLength, bool bCompressed /*= false*/)
{
	InitValues();

	m_bCompressed = bCompressed;
	Init(pBuffer, nLength);
}

void CBitArray::InitValues()
{
	m_pBuffer = NULL;
	m_nLength = m_nAllocLength = 0;
	m_nCount = -1;
	m_nIndexes = NULL;
	m_bModified = false;
	m_nBitSeg = 1;
	m_bCompressed = false;
}

CBitArray::~CBitArray()
{
	if(m_pBuffer)
		FreePtr(m_pBuffer);
	if(m_nIndexes)
		free(m_nIndexes);
}

void CBitArray::FreeBuffer()
{
	if(m_pBuffer)
		FreePtr(m_pBuffer);
	if(m_nIndexes)
		free(m_nIndexes);
	m_nIndexes = NULL;
	m_pBuffer = NULL;
	m_nLength = m_nAllocLength = 0;
	m_nCount = -1;
}

int CBitArray::GetCount()
{
	if(m_nCount == -1)
	{	// (^_^) 19/2/2004 hmh
//		static BYTE bitCount[16] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 };
		static BYTE bitCount[256] = { 
			0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
			1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
			1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
			2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
			1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
			2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
			2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
			3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8 };
		BYTE by;
		m_nCount = 0;
		for(int nByte = 0; nByte < m_nLength; nByte++)
			if(by = m_pBuffer[nByte])
//				m_nCount += by == 0xff ? 8 : bitCount[by&0x0f] + bitCount[(by&0xf0) >> 4];
				m_nCount += bitCount[by];
	}
	return m_nCount;
}

int CBitArray::GetRangeCount(int nStartBit, int nEndBit)
{	// (^_^) 6/3/2004 hmh
	static BYTE bitCount[16] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 };

	int nCount = 0;
	BOOL bFirstByte = (nStartBit&7) != 0;
	if(bFirstByte)
		for(int nBit = nStartBit; nBit < (nStartBit/8+1)*8; nBit++)
			if(GetAt(nBit))
				nCount++;
	int nEndByte = nEndBit/8;
	BYTE by;
	for(int nByte = nStartBit/8+bFirstByte; nByte < nEndByte; nByte++)
		if(by = m_pBuffer[nByte])
			nCount += by == 0xff ? 8 : bitCount[by&0x0f] + bitCount[(by&0xf0) >> 4];
	for(int nBit = nEndByte*8; nBit <= nEndBit; nBit++)
		if(GetAt(nBit))
			nCount++;

	return nCount;
}

void CBitArray::Index()
{	// (^_^) 21/2/2004 hmh
	if(GetLength() == 0)
		return;
	// calculate number of ones that will be include in each index
	m_nBitSeg = GetCount()/SEG_COUNT + 1;
	if(m_nIndexes)
		free(m_nIndexes);
	// allocate buffe of the indices array
	m_nIndexes = (int *)malloc(sizeof(int)*(m_nCount/m_nBitSeg+1));
	m_nIndexesCount = m_nCount = 0;
	BYTE by;
	// loop in the bitmap buffer to index '1's locations
	for(int nBit, nByte = 0; nByte < m_nLength; nByte++)
		// copy buffer byte into by and check if it is not 0
		if(by = m_pBuffer[nByte])
		{	// get bit number by multiply by 8 (or left shift by 3)
			nBit = nByte<<3;
			while(by)
			{	// if the first bit in the byte is '1'
				if(by&1)
					// check if the bit in the head of the index
					if(m_nCount++ % m_nBitSeg == 0)
						// add this bit to the indices
						m_nIndexes[m_nIndexesCount++] = nBit;
				// shift right to move second bit to the byte head
				by >>= 1, nBit++;
			}
		}
}

void CBitArray::SetLength(int nLength)
{
	if(nLength == 0)
		FreeBuffer();
	else	if(nLength > m_nAllocLength)
	{
		m_nAllocLength = nLength+(m_bCompressed?0:100);
		if(m_pBuffer == NULL)
			m_pBuffer = (BYTE*)AllocPtr(m_nAllocLength);
		else
			m_pBuffer = (BYTE*)ReAllocPtr(m_pBuffer, m_nAllocLength);
	}
	m_nLength = nLength;
	m_bModified = true;
}

BYTE *CBitArray::Detach()
{
	BYTE * p = m_pBuffer;
	m_pBuffer = NULL;
	FreeBuffer();
	
	return p;
}

void CBitArray::Attach(BYTE* pBuffer, int nLength)
{
	FreeBuffer();
	if(nLength > 0)
	{
		m_pBuffer = pBuffer;
		m_nLength = m_nAllocLength = nLength;
	}
	m_bModified = true;
}

void CBitArray::SetRange(int nStartBit, int nEndBit)
{
	if(nEndBit >= m_nLength*8)
		SetLength(nEndBit/8+1);
	for(int nBit = nStartBit; nBit <= nEndBit; nBit++)
		SetBit(m_pBuffer, nBit);
	SetModified();
}

void CBitArray::ResetRange(int nStartBit, int nEndBit)
{
	if(nEndBit >= m_nLength*8)
		nEndBit = m_nLength*8-1;
	for(int nBit = nStartBit; nBit <= nEndBit; nBit++)
		ResetBit(m_pBuffer, nBit);
	SetModified();
}

void CBitArray::ResetAt(CBitArray *pBitArray)
{
	int nLength = min(m_nLength, pBitArray->GetLength())*8;
	for(int nBit = 0; nBit < nLength; nBit++)
		if(pBitArray->GetAt(nBit))
			ResetBit(m_pBuffer, nBit);
	SetModified();
}

void CBitArray::XOrRange(int nStartBit, int nEndBit)
{
	if(nEndBit >= m_nLength*8)
		SetLength(nEndBit/8+1);
	for(int nBit = nStartBit; nBit <= nEndBit; nBit++)
		XOrBit(m_pBuffer, nBit);
	SetModified();
}

void CBitArray::CopyRange(const CBitArray& src, int nStartBit, int nEndBit)
{
	if(nStartBit >= src.m_nLength*8)
		return;
	nEndBit = min(nEndBit, src.m_nLength*8-1);

	if(nEndBit >= m_nLength*8)
		SetLength(nEndBit/8+1);

	BOOL bFirstByte = (nStartBit&7) != 0;
	int nStartByte = nStartBit/8+bFirstByte, nEndByte = max(nStartByte, nEndBit/8);
	if(bFirstByte)
		for(int nBit = nStartBit; nBit < nStartByte*8; nBit++)
			GetBit(src.m_pBuffer, nBit) ? SetBit(m_pBuffer, nBit) : ResetBit(m_pBuffer, nBit);
	if(nEndByte > nStartByte)
		memcpy(m_pBuffer+nStartByte, src.m_pBuffer+nStartByte, nEndByte-nStartByte);
	for(int nBit = nEndByte*8; nBit <= nEndBit; nBit++)
		GetBit(src.m_pBuffer, nBit) ? SetBit(m_pBuffer, nBit) : ResetBit(m_pBuffer, nBit);
	SetModified();
}

void CBitArray::Compress()
{
	if(m_bCompressed || m_nLength == 0)
		return;
	m_bCompressed = true;

	int nLength = m_nLength;
	BYTE *p = new BYTE[m_nLength];
	memcpy(p, m_pBuffer, m_nLength);
	FreeBuffer();
	Compress(p, nLength, m_pBuffer, m_nLength);
	delete p;
}

void CBitArray::Decompress()
{
	if(!m_bCompressed || m_nLength == 0)
		return;
	m_bCompressed = false;

	Decompress(m_pBuffer, m_nLength);
}

#define COMPRESS_TYPE	WORD//BYTE
#define COMPRESS_SIZE	2//1
#define COMPRESS_COUNT	65535//255

void CBitArray::Compress(BYTE *src, int nSrcLen, BYTE *&des, int &nDesLen)
{
	nDesLen = 1;	// keep first byte for compression info
	while(nSrcLen && src[nSrcLen-1] == 0)
		nSrcLen--;
	if(nSrcLen == 0)
	{
		des = NULL;
		nDesLen = 0;
		return;
	}
	int nLength = nSrcLen;
	if(nLength)
		des = (BYTE*)AllocPtr(nLength);
	des[0] = 1;	// COMPRESS_TYPE	WORD
	int nByte = 0, nRunLength;
	BYTE byType;
	while(nByte < nSrcLen)
	{
		if(nDesLen+5 > nLength)
		{
			nLength += 1024;
			des = (BYTE*)ReAllocPtr(des, nLength);
		}
		byType = des[nDesLen++] = src[nByte++];
		if(byType == 0 || byType == 0xff)
		{
			nRunLength = 1;
			while(nRunLength < COMPRESS_COUNT && nByte < nSrcLen && src[nByte] == byType)
				nRunLength++, nByte++;
			*(COMPRESS_TYPE*)(des+nDesLen) = nRunLength;
			nDesLen += COMPRESS_SIZE;
		}
	}
}

void CBitArray::Decompress(BYTE *&src, int &nSrcLen, int nMaxLen /*= -1*/)
{
	if(nSrcLen == 0)
		return;
	int nDesLen = 0;
	int nLength = nSrcLen, nRunLength;
	BYTE* des = (BYTE*)AllocPtr(nLength);
	int nByte = 1;	// first byte kept for comprerssion info
	BYTE byType;
	while(nByte < nSrcLen && (nMaxLen == -1 || nDesLen < nMaxLen))
		if(src[nByte] == 0 || src[nByte] == 0xff)
		{
			byType = src[nByte++];
			nRunLength = *(COMPRESS_TYPE*)(src+nByte);
			nByte += COMPRESS_SIZE;
			if(nDesLen+nRunLength+10 >= nLength)
			{
				nLength = nDesLen+nRunLength+1024;
				des = (BYTE*)ReAllocPtr(des, nLength);
			}
			if(byType)	
				memset(des+nDesLen, byType, nRunLength);
			nDesLen += nRunLength;
		}
		else
		{
			if(nDesLen+10 >= nLength)
			{
				nLength = nDesLen+1024;
				des = (BYTE*)ReAllocPtr(des, nLength);
			}
			des[nDesLen++] = src[nByte++];
		}
	FreePtr(src);
	nSrcLen = nDesLen; 
	src = (BYTE *)ReAllocPtr(des, nSrcLen);
}

bool CBitArray::SetAt(BYTE *&src, int &nSrcLen, int nBit)
{
	int nDesLen = 0;
	int nDesByte = nBit/8;
	if(nSrcLen > 0)
	{
		int nByte = 1;	// first byte kept for comprerssion info
		int nRunLength = 0, nAddedSize;
		BYTE byType = 0;
		while(nByte < nSrcLen)
			if(src[nByte] == 0 || src[nByte] == 0xff)
			{
				byType = src[nByte++];
				nRunLength = *(COMPRESS_TYPE*)(src+nByte);
				if(nDesLen+nRunLength > nDesByte)
				{
					if(byType == 0xff)
						return false;
					// current buffer (0|count) and nByte points to count
					if(nRunLength > 1)
					{	//  (0|count-1|byte) OR (0|count1|byte|0|count2) OR (byte|0|count-1)
						nAddedSize = 1;
						if(nDesByte == nDesLen+nRunLength-1)
						{	// (0|count-1|byte) last byte
							// change the run length
							*(COMPRESS_TYPE*)(src+nByte) = nDesByte-nDesLen;
							// increment buffer index after the old run length
							nByte += COMPRESS_SIZE;
						}
						else	if(nDesByte > nDesLen)
						{	// (0|count1|byte|0|count2) middle byte
							nAddedSize += 1+COMPRESS_SIZE;
							// change the run length
							*(COMPRESS_TYPE*)(src+nByte) = nDesByte-nDesLen;
							// increment buffer index after the old run length
							nByte += COMPRESS_SIZE;
						}
						else	// (byte|0|count-1) frist byte
						{
							*(COMPRESS_TYPE*)(src+nByte) -= 1;
							nByte--;
						}
						// increment buffer size to have new byte(one) + Zero byte + reminder run length
						src = (BYTE*)ReAllocPtr(src, nSrcLen+nAddedSize);
						// move the buffer after the old run length bytes
						memmove(src+nByte+nAddedSize, src+nByte, nSrcLen-nByte);
						memset(src+nByte, 0, nAddedSize);
						// increment buffer size new byte(one) + Zero byte + reminder run length
						nSrcLen += nAddedSize;
						if(nAddedSize > 1)	// save the reminder run length
							*(COMPRESS_TYPE*)(src+nByte+2) = nRunLength-1-(nDesByte-nDesLen);
					}
					else
					{	// remove the zero count 
						memmove(src+nByte, src+nByte+COMPRESS_SIZE, nSrcLen-nByte-COMPRESS_SIZE);
						// decrement buffer size by COMPRESS_SIZE
						nSrcLen -= COMPRESS_SIZE;
						// reset buffer tail
						memset(src+nSrcLen, 0, COMPRESS_SIZE);
						// back to point to the zero byte
						nByte--;
					}
					// set the target bit
					SetBit(src+nByte, nBit&7);
					return true;
				}
				nDesLen += nRunLength;
				nByte += COMPRESS_SIZE;
			}
			else
			{
				if(nDesLen++ == nDesByte)
				{
					if(GetBit(src+nByte, nBit&7))
						return false;
					SetBit(src+nByte, nBit&7);
					if(src[nByte] == 0xff)
						if(nRunLength != COMPRESS_COUNT && byType == 0xff)
						{	// increment previous runlength only
							memmove(src+nByte, src+nByte+1, nSrcLen-nByte-1);
							src[--nSrcLen] = 0;
							*(COMPRESS_TYPE*)(src+nByte-COMPRESS_SIZE) = nRunLength+1;
						}