Showing posts with label c. Show all posts
Showing posts with label c. Show all posts

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[16]'

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[16]' , 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[2]

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

which is exactly what we want.