Отразить по горизонтали одну битовую строку

Question

Я ищу алгоритм для переворачивания 1-битной строки растрового изображения по горизонтали. Помните, что эти строки выровнены по DWORD!

В настоящее время я декодирую поток RLE в буфер 8 бит на пиксель, затем перекодирую в 1-битную строку, однако я хотел бы попытаться сохранить все это в 1-битном пространстве в попытке увеличить его скорость. Профилирование указывает, что эта часть программы относительно медленная по сравнению с остальными.

Пример строки (перед переворотом):

FF FF FF FF 77 AE F0 00

Пример строки (после переворачивания):

F7 5E EF FF FF FF F0 00

Answer 1

Следующий код считывает и переворачивает данные в виде блоков по 32 бита в виде целых чисел. Код для обращения битов разделен на две части, потому что на машине с прямым порядком байтов, считывающей четыре байта как 32-битное целое число, меняет порядок байтов.

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

Это немного некрасиво и не устойчиво к ошибкам ... но это всего лишь пример кода. И выводит следующее.

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

Answer 2

Создать таблицу преобразования для замены битов в байте:

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

Теперь вы можете использовать таблицу для замены байта, тогда вам просто нужно сохранить байт в нужном месте в результате:

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));

Выход:

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