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.

3 comments :

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

    ReplyDelete
  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;
    }

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

    ReplyDelete