Horizontally Flip a One Bit Bitmap Line

Question

I'm looking for an algorithm to flip a 1 Bit Bitmap line horizontally. Remember these lines are DWORD aligned!

I'm currently unencoding an RLE stream to an 8 bit-per-pixel buffer, then re-encoding to a 1 bit line, however, I would like to try and keep it all in the 1 bit space in an effort to increase its speed. Profiling indicates this portion of the program to be relatively slow compared to the rest.

Example line (Before Flip):

FF FF FF FF 77 AE F0 00

Example line (After Flip):

F7 5E EF FF FF FF F0 00

Answer 1

Create a conversion table to swap the bits in a byte:

byte[] convert = new byte[256];
for (int i = 0; i < 256; i++) {
  int value = 0;
  for (int bit = 1; bit <= 128; bit<<=1) {
    value <<= 1;
    if ((i & bit) != 0) value++;
  }
  convert[i] = (byte)value;
}

Now you can use the table to swap a byte, then you just have to store the byte in the right place in the result:

byte[] data = { 0xFF, 0xFF, 0xFF, 0xFF, 0x77, 0xAE, 0xF0, 0x00 };
int width = 52;

int shift = data.Length * 8 - width;
int shiftBytes = data.Length - 1 - shift / 8;
int shiftBits = shift % 8;

byte[] result = new byte[data.Length];
for (int i = 0; i < data.Length; i++) {
  byte swap = convert[data[i]];
  if (shiftBits == 0) {
    result[shiftBYtes - i] = swap;
  } else {
    if (shiftBytes - i >= 0) {
      result[shiftBytes - i] |= (byte)(swap << shiftBits);
    }
    if (shiftBytes - i - 1 >= 0) {
      result[shiftBytes - i - 1] |= (byte)(swap >> (8 - shiftBits));
    }
  }
}

Console.WriteLine(BitConverter.ToString(result));

Output:

F7-5E-EF-FF-FF-FF-F0-00

Answer 2

The following code reads and reverses the data in blocks of 32 bits as integers. The code to reverse the bits is split into two parts because on a little endian machine reading four bytes as an 32 bit integer reverses the byte order.

private static void Main()
{     
    var lineLength = 52;

    var input = new Byte[] { 0xFF, 0xFF, 0xFF, 0xFF, 0x77, 0xAE, 0xF0, 0x00 };
    var output = new Byte[input.Length];

    UInt32 lastValue = 0x00000000;

    var numberBlocks = lineLength / 32 + ((lineLength % 32 == 0) ? 0 : 1);
    var numberBitsInLastBlock = lineLength % 32;

    for (Int32 block = 0; block < numberBlocks; block++)
    {
        var rawValue = BitConverter.ToUInt32(input, 4 * block);

        var reversedValue = (ReverseBitsA(rawValue) << (32 - numberBitsInLastBlock))  | (lastValue >> numberBitsInLastBlock);

        lastValue = rawValue;

        BitConverter.GetBytes(ReverseBitsB(reversedValue)).CopyTo(output, 4 * (numberBlocks - block - 1));
    }

    Console.WriteLine(BitConverter.ToString(input).Replace('-', ' '));
    Console.WriteLine(BitConverter.ToString(output).Replace('-', ' '));
}

private static UInt32 SwapBitGroups(UInt32 value, UInt32 mask, Int32 shift)
{
    return ((value & mask) << shift) | ((value & ~mask) >> shift);
}

private static UInt32 ReverseBitsA(UInt32 value)
{
   value = SwapBitGroups(value, 0x55555555, 1);
   value = SwapBitGroups(value, 0x33333333, 2);
   value = SwapBitGroups(value, 0x0F0F0F0F, 4);

   return value;
}

private static UInt32 ReverseBitsB(UInt32 value)
{
    value = SwapBitGroups(value, 0x00FF00FF, 8);
    value = SwapBitGroups(value, 0x0000FFFF, 16);

    return value;
}

It is a bit ugly and not robust against errors ... but it is just sample code. And it outputs the following.

FF FF FF FF 77 AE F0 00
F7 5E EF FF FF FF F0 00