Rapid color replacement for in-memory BMP

Question

A function that relatively quick replaces one color with another, in a memory-buffered BMP. I am trying to improve the performance as much as it is possible. The previous implementation of this function was even faster.. but then I ran into some padding complications.

union
{
    unsigned long ulColor;
    unsigned char byteColor[4];
} oldColor;
union
{
    unsigned long ulColor;
    unsigned char byteColor[4];
} newColor;

typedef unsigned char BYTE;
typedef unsigned short int WORD;
typedef unsigned long int DWORD;
typedef unsigned long long int DDWORD;

DWORD
bitfox_find_xy
(DWORD WIDTH, DWORD xp, DWORD yp)
{
    DWORD w = WIDTH;
    DWORD channels = 3;
    DWORD bpp = 8;
    DWORD single = (channels*bpp)/8;
    DWORD offset = (2+sizeof(BMP)+sizeof(DIB));
    DWORD rowsize = w*single;

    DWORD pixAddress;

    if (rowsize % 4 != 0) rowsize += 4 - (rowsize % 4); // account for padding
    pixAddress = offset + yp*rowsize + xp*single; // finding the address
    return pixAddress;
}
DDWORD
bitfox_color_replace_data
(BYTE *buff, BYTE old_r, BYTE old_g, BYTE old_b, BYTE new_r, BYTE new_g, BYTE new_b)
{
    #define OFFSET_OF_SIZE      0x2
    #define OFFSET_OF_PIXELS    0xA
    #define OFFSET_OF_WIDTH     0x12
    #define OFFSET_OF_HEIGHT    0x16

    DWORD* buffSize     = (DWORD*)&buff[OFFSET_OF_SIZE];
    DWORD* buffPixels   = (DWORD*)&buff[OFFSET_OF_PIXELS];
    DWORD* buffWidth    = (DWORD*)&buff[OFFSET_OF_WIDTH];
    DWORD*  buffHeight  = (DWORD*)&buff[OFFSET_OF_HEIGHT];

    DDWORD pixels_replaced = 0;
    DDWORD ln, col;

    oldColor.byteColor[0] = old_b;  newColor.byteColor[0] = new_b;
    oldColor.byteColor[1] = old_g;  newColor.byteColor[1] = new_g;
    oldColor.byteColor[2] = old_r;  newColor.byteColor[2] = new_r;

    for(ln = 0; ln < *buffHeight; ln++)
    {
        for(col = 0; col <*buffWidth; col++)
        {
            DDWORD offset = bitfox_find_xy(*buffWidth, col, ln);

            if(!memcmp(buff + offset, oldColor.byteColor, 3))
            {
                memcpy(buff + offset, newColor.byteColor, 3);

                pixels_replaced++;
            }
        }
    }
    return pixels_replaced;
}

Answer 1

1. It seems weird to define the same union twice. Instead you can do

   union Color
   {
       unsigned long ulColor;
       unsigned char byteColor[4];
   };
   
   union Color oldColor;
   union Color newColor;
   

2. Your naming smells like hungarian notation (like ulColor or byteColor) - prefixing the variable with the type name has little benefits.

3. Again in consistent naming of function parameters like WIDTH should be width.

4. Use white spaces around operators (e.g. 2 + sizeof(BMP) + sizeof(DIB))

5. Use consistent bracing.

6. Instead of using all those typedefs for BYTE and WORD etc. you should use the types from stdint.h like int8_t, int16_t etc. which will make the code way more readable.

7. bitfox_find_xy can probably be made static (only visible to local C file) which would probably make it easier for the compiler to inline it.

8. There are a whole lot of local variables in bitfox_find_xy which can be made const:

   static uint32_t bitfox_find_xy(uint32_t width, uint32_t xp, uint32_t yp)
   {
       const uint32_t channels = 3;
       const uint32_t bpp = 8;
       const uint32_t single = (channels * bpp) >> 3;
       const uint32_t offset = 2 + sizeof(BMP) + sizeof(DIB);
       uint32_t rowsize = width * single;
   
       if (rowsize % 4 != 0) 
       {
           rowsize += 4 - (rowsize % 4); // account for padding
       }
       return offset + yp * rowsize + xp * single; // finding the address
   }
   

9. Also rowsize is actually constant for a given image so it should be computed once before the loop.

10. Not sure why you are obtaining the properties of the image as pointers rather than copying the values directly into local variable. This should save you a bunch of loads in the loop below. So instead of

    DWORD* buffSize     = (DWORD*)&buff[OFFSET_OF_SIZE];
    DWORD* buffPixels   = (DWORD*)&buff[OFFSET_OF_PIXELS];
    DWORD* buffWidth    = (DWORD*)&buff[OFFSET_OF_WIDTH];
    DWORD*  buffHeight  = (DWORD*)&buff[OFFSET_OF_HEIGHT];
    

    it should be:

    uint32_t buffSize    = *(uint32_t*)&buff[OFFSET_OF_SIZE];
    uint32_t buffPixels  = *(uint32_t*)&buff[OFFSET_OF_PIXELS];
    uint32_t buffWidth   = *(uint32_t*)&buff[OFFSET_OF_WIDTH];
    uint32_t buffHeight  = *(uint32_t*)&buff[OFFSET_OF_HEIGHT];
    

11. Rather than memcmp you should be able to use some masking to compare the color values directly:

    const uint32_t overlap_mask = 0xFF;
    const uint32_t color_mask = ~overlap_mask;
    
    for (ln = 0; ln < buffHeight; ln++)
    {
        for (col = 0; col < buffWidth; col++)
        {
            uint32_t offset = bitfox_find_xy(buffWidth, col, ln);
    
            uint32_t* pixel = (uint32_t *)&buff[offset];
            if ((*pixel & color_mask) == (oldColor.ulColor & color_mask))
            {
                *pixel = (*pixel & overlap_mask) | (newColor.ulColor & color_mask);
                pixels_replaced++;
            }
        }
    }
    

    Not sure if that will yield a speed up though.

---

You should be able to get rid of the call to bitfox_find_xy by inlining the call yourself. You just need to do some pre-computation (this time sticking with memcmp):

    const uint32_t overlap_mask = 0xFF;
    const uint32_t color_mask = ~overlap_mask;

    const uint32_t bytes_per_pixel = 3;
    const uint32_t header_offset = 2 + sizeof(BMP) + sizeof(DIB);

    uint32_t rowsize = bytes_per_pixel * buffWidth;
    if (rowsize % 4 != 0) 
    {
        rowsize += 4 - (rowsize % 4); // account for padding
    }

    for (ln = 0; ln < buffHeight; ln++)
    {
        for (col = 0; col < buffWidth; col++)
        {
            uint32_t offset = header_offset + col * bytes_per_pixel + ln * rowsize;

            if (!memcmp(buff + offset, oldColor.byteColor, 3))
            {
                memcpy(buff + offset, newColor.byteColor, 3);

                pixels_replaced++;
            }
        }
    }

Answer 2

Computing rowsize inside bitfox_find_xy (that is, for each and every pixel)seems wasteful: row size never changes during the bitfox_color_replace_data invocation, and shall only be computed once.