Home    News    Components    Get ViTooKi    Documentation    Community    Developers    @sf.net  

Info

Last update:
12 Feb 2007

Documentation

Doxygen LXR

BitField.cpp

 /***********************************************************************
 *                                                                      *
 * ViTooKi                                                              *
 *                                                                      *
 * title:       BitField.cpp                                                  *
 *                                                                      *
 *                                                                      *
 *                                                                      *
 * ITEC institute of the University of Klagenfurt (Austria)             *
 * http://www.itec.uni-klu.ac.at                                        *
 *                                                                      *
 *                                                                      *
 * For more information visit the ViTooKi homepage:                     *
 * http://ViTooKi.sourceforge.net                                       *
 * vitooki-user@lists.sourceforge.net                                   *
 * vitooki-devel@lists.sourceforge.net                                  *
 *                                                                      *
 * This file is part of ViTooKi, a free video toolkit.                  *
 * ViTooKi 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.                                                 *
 *                                                                      *
 ***********************************************************************/

 /***********************************************************************
 *                                                                      *
 *  REVISION HISTORY:                                                   *
 *                                                                      *
 *                                                                      *
 *                                                                      *
 ***********************************************************************/

#include "BitField.hpp"
#include <assert.h>

BitField::BitField(char* data, u32 size)
{
        assert(data);
        maxSize=size;
        bits=(u32*) data;
};


BitField::BitField(u32 size, bool initToValue)
{
        dprintf_full("BitField::BitField(size:%u, initVal %i)\n",size,(int)initToValue);
        maxSize=size;
        u32 newSize=(maxSize+(sizeof(u32)*8-1))/(sizeof(u32)*8);
        this->bits=new u32[newSize];
        assert(bits);
        u32 setToVal=0;
        if(initToValue)
                setToVal=0xffffffff;
        for(u32 i=0;i<newSize;i++) {
                bits[i]=setToVal;
        }
};

BitField::~BitField() 
{
        delete[] bits;
}

void BitField::clearBit(u32 pos) 
{
        if(pos>=maxSize)
                return;
        //dprintf_full("BitField::clearBit(u32 %u) first u32 is %u\n",pos,bits[0]);
        u32 posInArray=pos/(sizeof(u32)*8);
        u32 bitInPos=pos%(sizeof(u32)*8);
        bits[posInArray]&=(((u32)0xffffffff)-(1<<bitInPos));
};

void BitField::setBit(u32 pos)
{
        if(pos>=maxSize)
                return;
        //dprintf_full("BitField::setBit(u32 %u) first u32 is %u\n",pos,bits[0]);
        u32 posInArray=pos/(sizeof(u32)*8);
        u32 bitInPos=pos%(sizeof(u32)*8);
        bits[posInArray]|=(1<<bitInPos);
};

bool BitField::getBit(u32 pos) const
{
        if(pos>=maxSize)
                return false;

        u32 posInArray=pos/(sizeof(u32)*8);
        u32 bitInPos=pos%(sizeof(u32)*8);
        return bits[posInArray]&(1<<bitInPos);
};

void BitField::invert()
{
        bool val;
        for(u32 i=0;i<maxSize;i++) {
                val=getBit(i);
                if(val) // if true set to false
                        clearBit(i);
                else    // if false set to true
                        setBit(i);      
        }               
};

BitField* BitField::createWithNewSize(u32 size, bool initValueForMissing)
{

        BitField* b=new BitField(size,initValueForMissing);

        // copy full bytes with normal memcopy
        u32 posInArray=size/(sizeof(u32)*8);
        if(size>maxSize) //prevent buffer overflow
                posInArray=maxSize/(sizeof(u32)*8);

        memcpy(b->bits,bits,posInArray*sizeof(u32));

        // copy the remaining bits (up to 31) manually
        u32 startPosRemaining=posInArray*(sizeof(u32)*8);
        u32 endPos=MIN(size,maxSize);
        for(u32 i=startPosRemaining;i<endPos;i++) {
                if(getBit(i))
                        b->setBit(i);
                else
                        b->clearBit(i);
        }
        return b;
};

const char* BitField::toBinaryString(u32* sizeInU32) const
{
        *sizeInU32=(maxSize+(sizeof(u32)*8-1))/(sizeof(u32)*8);
        return (const char*)bits;
};

char* BitField::toAsciiString() const
{
        char* temp=new char[maxSize+1];
        for(u32 i=0;i<maxSize;i++)
                temp[i]=( getBit(i) ? '1' : '0');

        temp[maxSize]='\0';
        return temp;
};

bool BitField::isAllSet() const
{
        u32 lastFullU32=maxSize/(sizeof(u32)*8);
        u32 restBits=lastFullU32*(sizeof(u32)*8);
        u32 i;

        for(i=0;i<lastFullU32;i++) {
                if( (bits[i] & 0xffffffff)!=0xffffffff)
                        return false;
        }
        // check the rest
        for(i=restBits;i<maxSize;i++) {
                if(!getBit(i))
                        return false;
        }
        return true;
};

bool BitField::isAllCleared() const
{
        u32 lastFullU32=maxSize/(sizeof(u32)*8);
        u32 restBits=lastFullU32*(sizeof(u32)*8);
        u32 i;

        for(i=0;i<lastFullU32;i++) {
                if( (bits[i] | 0x00000000)!=0x00000000)
                        return false;
        }
        // check the rest
        for(i=restBits;i<maxSize;i++) {
                if(getBit(i))
                        return false;
        }
        return true;
};

float BitField::getPercentageSetBits() const
{
        float res=0;
        int count=0;
        for(u32 i=0;i<maxSize;i++) {
                if(getBit(i))
                        count++;
        }
        if(count>0) // thus maxSize > 0
                res= (float)((double)count)/((double)maxSize);
        return res;
};

BitField* BitField::fromAsciiString(const char* str)
{
        if(str==NULL)
                return NULL;

        u32 sizeStr=strlen(str);
        BitField* b=new BitField(sizeStr,true);
        // only check for 0 and just hope that the string is valid
        // init to 1 because hopefully we will have more 1 than 0
        // in the string
        for(u32 i=0;i<sizeStr;i++) {
                if(str[i]=='0')
                        b->clearBit(i);
        }
        return b;       
};

BitField* BitField::fromBinaryString(const char* bin, u32 numBits) {
        BitField* b=new BitField(numBits,false);
        u32 bytes=(numBits+sizeof(char)-1)/sizeof(char);
        memcpy(b->bits,bin,bytes);
        return b;
};

BitField* BitField::fromBinaryString(char* bin, u32 numBits)
{
        return new BitField(bin,numBits);
};

char* BitField::toHexString() const
{
        // one char represents 4 bits 0111 -> 7
        int size=(maxSize+3)/4;
        // add 9 Byte header (32bit size in Hex + _)
        size+=9;
        char* result=new char[size+1];
        // write header
        sprintf(result,"%8X_",maxSize);
        int cnt=0;
        
        for(u32 i=0;i<maxSize;i+=4) {
                cnt=(getBit(i) ? 1 : 0);
                cnt+=(getBit(i+1) ? 1 : 0)<<1;
                cnt+=(getBit(i+2) ? 1 : 0)<<2;
                cnt+=(getBit(i+3) ? 1 : 0)<<3;
                if(cnt>9) {
                        cnt-=10;
                        cnt+='A';
                }
                else
                        cnt+='0';
                result[9+i/4]=cnt;
        }
        result[size]='\0';
        return result;
};
BitField* BitField::fromHexString(const char* bin)
{
        assert(bin);
        const char* payload=strchr(bin,'_');
        if(!payload) {
                dprintf_err("BitField::fromHexString: invalid header\n");
                return NULL;
        }
        payload++; // skip '_'  
        u32 maxSize=0;
        if(0==sscanf(bin,"%x",&maxSize))
                return NULL;
        if( strlen(payload) != ( (maxSize+3)/4)) {
                dprintf_err("BitField::fromHexString invalid header or incomplete data: >%s<\n",bin);
                return NULL;
        }
        const char* lBin=payload;
        BitField* b=new BitField(maxSize,true);
        char t='\0';
        u32 i=0;
        for(u32 j=0;j<maxSize;j+=4) {
                t=lBin[j/4];
                if(t>='A' && t <= 'F')
                        i=t-'A'+10;
                else if(t>='0' && t<='9')
                        i=t-'0';
                else if(t=='\0')
                        return b; //should be impossible
                else {
                        dprintf_err("BitField::fromHexString Invalid char in hex string >%i<\n",t);
                        delete b; return NULL;
                }
                // valid i
                // extract 4 bits from i, loop unrolling :-))))
                // no need to handle last iteration specially, clearBit takes care of that
                if(!(i & 1u))
                        b->clearBit(j);
                if(!(i & 2u))
                        b->clearBit(j+1);
                if(!(i & 4u))
                        b->clearBit(j+2);
                if(!(i & 8u))
                        b->clearBit(j+3);
        };
        dprintf_full("BitField::fromHexString: Successfully created bitfield\n");
        return b;
};

u32 BitField::getBitRange(u32 startPos, int* nrBits, bool littleEndian)
{
        assert(nrBits);
        if( (*nrBits)==0 || (*nrBits)>32 || startPos+(*nrBits)>maxSize) {
                (*nrBits)=-1;
                return 0;
        }
        // everything is valid
        u32 result=0;
        u32 shamt=0; //shift amount
        u32 i=0;
        if(!littleEndian) {
                shamt=(*nrBits)-1;
        }
        for (i=startPos;i<startPos+(*nrBits);i++) {
                result+=(getBit(i)?1:0)<<shamt;
                if(littleEndian)
                        shamt++;
                else
                        shamt--;
        }       
        
        return result;  
};

/* writes @param nrBits of @param value starting with @param startBit at position @param startPos.
 * returns false if startBit+nrBits is greater 32, if nrBits is not in range 1..32,
 * if startBit is not in range 0..32-nrBits, or startPos+nBits is greater than maxSize
 * @param littleEndian specifies endianness. When set to true the decimal value for the
 * requested bitrange is calculated as if the first bit has the lowest value.
 * e.g.: Bit 0 1000 Bit 3 -> littleEndian=true --> 1 littleEndian=false --> 8
 */
bool BitField::writeBitRange(u32 startPos, int nrBits, u32 value, u32 startBit, bool littleEndian)
{
        if(startBit+nrBits>32 || nrBits<1 || nrBits>32 || startPos+nrBits>maxSize)
                return false;
        
        // write bits startBit..startBit+nrBits-1 from value to the bitfield according to endianness
        // little endianness: pos startBit equals to startPos
        // big endianness: pos startBit+nrBits-1 equals to startpos
        u32 shamt=0;
        u32 i=0;
        u32 val=0;
        if(!littleEndian) {
                shamt=nrBits-1;
        }

        for(i=startPos;i<startPos+nrBits;i++) {
                val=(value>>(startBit+shamt))&1;
                if(val==1)
                        setBit(i);
                else
                        clearBit(i);
                if(littleEndian)
                        shamt++;
                else
                        shamt--;
        }
                        
        return true;    
};

void BitField::doTest()
{
        u32 i=0;
        BitField b(128,false);
        assert(b.getPercentageSetBits()<0.0001f);
        assert(b.isAllCleared());
        b.setBit(128); //should be ignored
        assert(b.isAllCleared());
        float f=b.getPercentageSetBits();
        for(i=0;i<128;i++) {
                b.setBit(i);
                assert(f<b.getPercentageSetBits());
                f=b.getPercentageSetBits();
        }
        assert(b.isAllSet());
        b.invert();
        assert(b.isAllCleared());
        b.invert();
        assert(b.isAllSet());
        char* tmp=new char[33];
        char* tmp2=new char[33];
        strcpy(tmp,"10000000000000011111111001111111");
        BitField* b2=BitField::fromAsciiString(tmp);
        char* t2=b2->toAsciiString();
        printf("X%sX\n",t2);
        assert(strcmp(tmp,t2)==0);
        delete[] t2;
        for(i=0;i<32;i++)
                tmp2[i]= (b2->getBit(i)?1:0)+'0';
        tmp2[32]='\0';
        printf("X%sX\n",tmp2);
        assert(strcmp(tmp,tmp2)==0);

        delete[] tmp2;
        
        assert(b2->getBit(33)==false);

        int nrBits=8;
        assert(1==b2->getBitRange(0,&nrBits,true));
        assert(nrBits==8);
        assert(128==b2->getBitRange(0,&nrBits,false));
        assert(nrBits==8);
        assert(128==b2->getBitRange(8,&nrBits,true));
        assert(nrBits==8);
        assert(1==b2->getBitRange(8,&nrBits,false));
        assert(nrBits==8);
        nrBits=0;
        assert(0==b2->getBitRange(0,&nrBits,false));
        assert(nrBits==-1);
        nrBits=16;
        assert((127+254*256)==b2->getBitRange(16,&nrBits,true));
        assert(nrBits==16);
        assert((127+254*256)==b2->getBitRange(16,&nrBits,false));
        assert(nrBits==16);
        nrBits=32;
        printf("%x\n",b2->getBitRange(0,&nrBits,true));
        assert(0xfe7f8001==b2->getBitRange(0,&nrBits,true));
        assert(nrBits==32);
        printf("%x\n",b2->getBitRange(0,&nrBits,false));
        assert(0x8001fe7f==b2->getBitRange(0,&nrBits,false));
        assert(nrBits==32);
        assert(0==b2->getBitRange(1,&nrBits,true));
        assert(nrBits==-1);
        nrBits=1;
        assert(1==b2->getBitRange(31,&nrBits,true));
        assert(nrBits==1);
        assert(0==b2->getBitRange(32,&nrBits,true));
        assert(nrBits==-1);

        BitField* b3=new BitField(32,false);
        nrBits=32;
        u32 val=b2->getBitRange(0,&nrBits,true);
        b3->writeBitRange(0,nrBits,val,0,true);
        char* b3Tmp=b3->toAsciiString();
        printf("X%sX\n",b3Tmp);
        assert(strcmp(tmp,b3Tmp)==0);
        delete[] b3Tmp;

        val=b2->getBitRange(0,&nrBits,false);
        b3->writeBitRange(0,nrBits,val,0,false);
        b3Tmp=b3->toAsciiString();
        printf("X%sX\n",b3Tmp);
        assert(strcmp(tmp,b3Tmp)==0);

        delete b2;delete[] tmp;
        delete b3; delete[] b3Tmp;

        // Test 4 hex
        const char* t4="A_FF0";
        BitField* b4=BitField::fromHexString(t4);
        assert(b4);
        char* t4_1=b4->toHexString();
        assert(strstr(t4_1,t4));
        delete[] t4_1;

};

© ViTooKi 2003 :: [Lite version] Created with Doxygen