Inverting an image

Question

The problem is that I am trying to modify the code to invert the image in C and optimize it to make it run faster than the original by any method I could think of. After tried to use blocking and loop unrolling, it still does not seem to speed up. Maybe I did it in a wrong way as I'm not really fully understanding these methods.

void invert(int width, int height, char *code)
{
  int x, y, z;
  int i, n;
  char RGB[4]="RGB";

  for (z=0; z<3; z++)
    for (y=0; y<width; y++)
      for (x=0; x<height; x++)
      {
        b[x][y][z] = a[x][y][z];
        n = strlen(code);
        for(i=0; i<n; i++)
        {
          if (code[i]==RGB[z])
          {
            b[x][y][z] = 255 - a[x][y][z];
          }
        }
      }
  return;
}

void invert_optimized(int width, int height, char *code)
{
  int x, y, z , xx , yy;
  int i, n;
  char RGB[4]="RGB";

  for (z=0; z<3; z++)
    for (xx=0; xx<height; xx+=4)
        for (yy=0; yy<width; yy+=4)
        for (x=xx; x<4+xx; x++)
            for (y=yy; y<4+yy; y++)
              {
                c[x][y][0] = a[x][y][0];
                c[x][y][1] = a[x][y][1];
                c[x][y][2] = a[x][y][2];
                n = strlen(code);
                for(i=0; i<n; i++)
                {
                  if (code[i]==RGB[z])
                  {
                    c[x][y][z] = 255 - a[x][y][z];
                  }
                }
              }
  return;
}

I also was thinking about inline, but the problem is that I don't know how to implement it for this code and I don't think it will work for this either.

Answer 1

I rewrote your function so the main loop didn't have to loop against code at all. I did that by preprocessing the code string. I also reordered the loops so that the array would be traversed in the same order as memory (good for cache hits). It ran about 39x as fast as the original function, using a 5000 x 5000 array.

void invert(int width, int height, char *code)
{
    int x, y, z;
    int i, n;
    int doInvert[3] = {0};

    n = strlen(code);
    for (i=0;i<n;i++) {
        switch (code[i]) {
            case 'R': doInvert[0] = 1; break;
            case 'G': doInvert[1] = 1; break;
            case 'B': doInvert[2] = 1; break;
            default : break;
        }
    }
    for (x=0; x<height; x++) {
        for (y=0; y<width; y++) {
            for (z=0; z<3; z++) {
                if (doInvert[z])
                    b[x][y][z] = 255 - a[x][y][z];
                else
                    b[x][y][z] = a[x][y][z];
            }
        }
    }
}

Answer 2

1. You can move the `strlen` call to outside all of the loops since that is loop invariant.
2. You can store the "RGB" char value at the outer for loop so that you aren't looking it up inside the for loops. I would assume a good compiler would do that, but due to the nesting it might miss it and so you can just code it up yourself that way.
3. Just kind of brainstorming, but it might be better to figure out which bits you need to flip, memcpy the whole array, and then just flip those specific bits. (see invert2) This turned out to be a bad idea

Just as an aside, my C is rusty and I did not compile this, but the concept should still come through clearly.

void invert(int width, int height, char *code)
{
  int x, y, z;
  int i, n;
  char RGB[4]="RGB";
  char rgb;

  n = strlen(code);

  for (z=0; z<3; z++)
  {
    rgb = RGB[z];
    for (y=0; y<width; y++)
      for (x=0; x<height; x++)
      {
        b[x][y][z] = a[x][y][z];
        for(i=0; i<n; i++)
        {
          if (code[i]==rgb)
          {
            b[x][y][z] = 255 - a[x][y][z];
          }
        }
      }
  }
  return;
}