?? bitarray.cpp
字號:
////////////////////////////////////////////////////////////////////////////
//
// 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;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -