## Tuesday, March 10, 2015

### 128 Bit bitmap operations

I had to maintain a '128 bit' bitmap with
• set
• clear
• is_set
operations , what came to my head was (128 / 8) = 16

ie if i declare

'unsigned char bitmap'

Q. Why didn't i choose (128 / 32) = 4 ?

A.  if the code  be portable across other platforms, '8 bit' should be a logical choice , as most lower ended arch at most 8 bit.

Now to the code .

//Version 1
void bitmap8_set_bit(unsigned char *bitmap, unsigned int bit)
{
*bitmap |= (1 << bit);
}

void bitmap8_clr_bit(unsigned char *bitmap, unsigned int bit)
{
*bitmap &= (0xff & ~(1 << bit));
}

int bitmap8_is_bit_set(unsigned char *bitmap, unsigned int bit)
{
return ( ( (*bitmap) & (1 << bit) ) ? 1 : 0 );
}


//Version 2
void bitmap8_set_bit(unsigned char *bitmap, unsigned int bit)
{
bitmap[bit / 8] |= (1 << (bit % 8));
}

void bitmap8_clr_bit(unsigned char *bitmap, unsigned int bit)
{
bitmap[bit / 8] &= (0xff & ~(1 << (bit % 8)));
}

int bitmap8_is_bit_set(unsigned char *bitmap, unsigned int bit)
{
return ( (bitmap[bit / 8] & (1 << (bit % 8)) ) ? 1 : 0 );
}

int bitmap8_next_free_bit(unsigned char *bitmap)
{
register int i;

for (i = 0;i < 128; i++) {
if (0 == is_bit_set(bitmap, i))
return i;
}
return i;
}


Q. What is the big deal in the Version 2 ?

Declared 'unsigned char bitmap' , i have to properly index the bitmap array to get the desired result, but the fundamental operation remains the same.

ie bitmap[bit / 8] -> would for bit = 16 would map to bitmap

(bit % 8) -> (16 % 8) = 0 ,

which is exactly what we want.

1. Good dispatch and this post helped me alot in my college assignement. Thank you seeking your information.

2. A little bit faster in certain cases:

int bitmap8_next_free_bit(unsigned char *bitmap)
{
register int i, j;

for (i = 0;i < 16; i++) {
if (bitmap[i] != 0xFF) {
for (j = 0;j < 8; j++) {
if (0 == bitmap8_is_bit_set(bitmap + i, j))
return i * 8 + j;
}
}
}
return i;
}

3. yea true, we could pre check the next byte.