快速向后转动大块内存

Question

我需要以相反的顺序重写大约4KB的数据，在位级（最后一个字节的最后一位成为第一个字节的第一位），尽可能快。有没有聪明的小册子呢？

理由：数据是嵌入式设备中LCD屏幕的显示内容，通常以屏幕处于肩膀水平的方式定位。屏幕有“6点钟”的方向，可以从下面看 - 就像平躺或挂在眼睛上方。这可以通过将屏幕旋转180度来固定，但是我需要反转屏幕数据（由库生成），即1位= 1像素，从屏幕的左上角开始。 CPU功能不是很强大，设备已经有足够的工作量，加上一秒钟的几帧，所以性能是个问题。 RAM不是那么多。

编辑：单核，ARM 9系列。 64MB，（缩小到32MB以后），Linux。数据通过8位IO端口从系统存储器推送到LCD驱动器。

CPU为32位，在字长方面的性能要比字节级高得多。

Answer 1

这是一种经典的方法。假设unsigned int是你的32位字。我正在使用C99，因为restrict关键字允许编译器在此速度关键代码中执行额外的优化，否则这些代码将不可用。这些关键字通知编译器“src”和“dest”不重叠。这也假设你正在复制整数个单词，如果你不是，那么这只是一个开始。

我也不知道哪个位移/旋转基元在ARM上速度快，哪些速度慢。这是需要考虑的事情。如果您需要更高的速度，请考虑从C编译器中反汇编输出并从那里开始。如果使用GCC，请尝试使用O2，O3和Os来查看哪一个最快。您可以通过同时执行两个单词来减少管道中的停顿。

这每个单词使用23次操作，不计算加载和存储。但是，这23个操作都非常快，并且没有一个访问内存。我不知道查找表是否会更快。

void
copy_rev(unsigned int *restrict dest,
         unsigned int const *restrict src,
         unsigned int n)
{
    unsigned int i, x;
    for (i = 0; i < n; ++i) {
        x = src[i];
        x = (x >> 16) | (x << 16);
        x = ((x >> 8) & 0x00ff00ffU) | ((x & 0x00ff00ffU) << 8);
        x = ((x >> 4) & 0x0f0f0f0fU) | ((x & 0x0f0f0f0fU) << 4);
        x = ((x >> 2) & 0x33333333U) | ((x & 0x33333333U) << 2);
        x = ((x >> 1) & 0x55555555U) | ((x & 0x555555555) << 1);
        dest[n-1-i] = x;
    }
}

这个页面是一个很好的参考：http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious

最后注意：查看ARM程序集引用，有一个“REV”操作码，它反转一个字中的字节顺序。这将使上述代码的每个循环减少7次操作。

Answer 2

最快的方法可能是将所有可能的字节值的反转存储在查找表中。该表只需256个字节。

Answer 3

构建一个256元素的字节值查找表，它与索引位反转。

{0x00,0x80,0x40,0xc0等}

然后使用每个字节作为查找表的索引遍历您的数组复制。

如果您正在编写汇编语言，则x86指令集具有XLAT指令，该指令仅执行此类查找。虽然它实际上可能不比现代处理器上的C代码快。

如果从两端向中间迭代，则可以执行此操作。由于缓存效应，您可能会发现交换16字节块（假设16字节缓存行）更快。

这是基本代码（不包括缓存行优化）

// bit reversing lookup table
typedef unsigned char BYTE;
extern const BYTE g_RevBits[256];

void ReverseBitsInPlace(BYTE * pb, int cb)
{
    int iter = cb/2;
    for (int ii = 0, jj = cb-1; ii < iter; ++ii, --jj)
    {
        BYTE b1 = g_RevBits[pb[ii]];
        pb[ii] = g_RevBits[pb[jj]];
        pb[jj] = b1;
    }

    if (cb & 1) // if the number of bytes was odd, swap the middle one in place
    {
       pb[cb/2] = g_RevBits[pb[cb/2]];
    }
}

// initialize the bit reversing lookup table using macros to make it less typing.
#define BITLINE(n) \
   0x0##n, 0x8##n, 0x4##n, 0xC##n, 0x2##n, 0xA##n, 0x6##n, 0xE##n,\
   0x1##n, 0x9##n, 0x5##n, 0xD##n, 0x3##n, 0xB##n, 0x7##n, 0xF##n,

const BYTE g_RevBits[256] = {
  BITLINE(0), BITLINE(8), BITLINE(4), BITLINE(C), 
  BITLINE(2), BITLINE(A), BITLINE(6), BITLINE(E), 
  BITLINE(1), BITLINE(9), BITLINE(5), BITLINE(D), 
  BITLINE(3), BITLINE(B), BITLINE(7), BITLINE(F), 
  };

Answer 4

Bit Twiddling Hacks网站始终是解决这类问题的良好起点。看看qazxsw poi的快速反转。然后由您决定将其应用于内存块的每个字节/字。

编辑：

受到Dietrich Epps的回答和查看here的启发，有一个ARM instruction set操作码可以反转寄存器中包含的位。因此，如果性能至关重要，您可以考虑使用一些汇编代码。

Answer 5

循环遍历数组的一半，转换和交换字节。

RBIT

对于转换，使用预先计算的表 - 2CHAR_BIT（

for( int i = 0; i < arraySize / 2; i++ ) {
    char inverted1 = invert( array[i] );
    char inverted2 = invert( array[arraySize - i - 1] );
    array[i] = inverted2;
    array[arraySize - i - 1] = inverted1;
}

最有可能是8）元素的数组，其中在位置“I”处存储具有值“I”反转的字节的结果。这将非常快 - 一次通过 - 并且仅消耗表的2CHAR_BIT。

Answer 6

看起来这个代码在我的i7 XPS 8500机器上每位交换大约需要50个时钟。一百万次阵翻翻7.6秒。单线程。它根据1s和0s的模式打印一些ASCI艺术品。在使用图形编辑器反转位阵列后，我将图片旋转了180度，它们看起来与我相同。双反转图像与原始图像相同。

至于加号，它是一个完整的解决方案。它将位从位阵列的后面交换到前面，而不是在整数/字节上操作，然后需要在数组中交换整数/字节。

此外，这是一个通用的位库，因此您可能会发现将来解决其他更普通的问题很方便。

它和接受的答案一样快吗？我认为它很接近，但没有工作代码来进行基准测试就不可能了。随意剪切和粘贴此工作程序。

CHAR_BIT

下面是使用新缓冲区进行优化的代码清单，而不是交换字节。由于if（）测试只需要2030：4080 BitSet（），并且通过消除TEMP消除了大约一半的GetBit（）和PutBits（），我怀疑内存访问时间是一个很大的固定成本这些类型的操作，为优化提供了硬性限制。

使用查找方法，并且有条件地交换字节而不是位，将内存访问次数减少8倍，并且测试0字节将在8位而不是1中分摊。

同时使用这两种方法，在执行ANYTHING之前测试整个8位字符是否为0，包括表查找和写入，可能是最快的方法，但需要额外的512字节新的目标位数组，以及查找表的256个字节。尽管如此，表现回报可能非常显着。

// Reverse BitsInBuff.cpp : Defines the entry point for the console application.
#include "stdafx.h"
#include "time.h"
#include "memory.h"
//
//  Manifest constants
#define  uchar unsigned char
#define  BUFF_BYTES 510 //400 supports a display of 80x40 bits
#define  DW 80  //  Display Width
// ----------------------------------------------------------------------------
uchar   mask_set[] = { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 };
uchar   mask_clr[] = { 0xfe, 0xfd, 0xfb, 0xf7, 0xef, 0xdf, 0xbf, 0x7f };
//
// Function Prototypes
static void PrintIntBits(long x, int bits);
void    BitSet(uchar * BitArray, unsigned long BitNumber);
void    BitClr(uchar * BitArray, unsigned long BitNumber);
void    BitTog(uchar * BitArray, unsigned long BitNumber);
uchar   BitGet(uchar * BitArray, unsigned long BitNumber);
void    BitPut(uchar * BitArray, unsigned long BitNumber, uchar value);
//
uchar *ReverseBitsInArray(uchar *Buff, int BitKnt);
static void PrintIntBits(long x, int bits);
// -----------------------------------------------------------------------------
// Reverse the bit ordering in an array
uchar *ReverseBitsInArray(uchar *Buff, int BitKnt)  {
    unsigned long front=0, back = BitKnt-1;
    uchar temp;
    while( front<back ) {
        temp = BitGet(Buff, front);                 // copy front bit to temp before overwriting 
        BitPut(Buff, front, BitGet(Buff, back));    // copy back bit to front bit
        BitPut(Buff, back, temp);                   // copy saved value of front in temp to back of bit arra)
        front++;
        back--;
    }
    return Buff;
}
//  ---------------------------------------------------------------------------
//  ---------------------------------------------------------------------------
int _tmain(int argc, _TCHAR* argv[])    {
    int i, j, k, LoopKnt = 1000001;
    time_t start;
    uchar Buff[BUFF_BYTES];
    memset(Buff, 0, sizeof(Buff));
    //  make an ASCII art picture
    for(i=0, k=0; i<(sizeof(Buff)*8)/DW; i++)   {
        for(j=0; j<DW/2; j++)   {
            BitSet(Buff, (i*DW)+j+k);
        }
        k++;
    }
    //  print ASCII art picture
    for(i=0; i<sizeof(Buff); i++)   {
        if(!(i % 10)) printf("\n"); // print bits in blocks of 80
        PrintIntBits(Buff[i], 8);
    }
    i=LoopKnt;
    start = clock();
    while( i-- )    {
        ReverseBitsInArray((uchar *)Buff, BUFF_BYTES * 8);
    }
    //  print ASCII art pic flipped upside-down and rotated left
    printf("\nMilliseconds elapsed = %d", clock() - start);
    for(i=0; i<sizeof(Buff); i++)   {
        if(!(i % 10)) printf("\n"); // print bits in blocks of 80
        PrintIntBits(Buff[i], 8);
    }
    printf("\n\nBenchmark time for %d loops\n", LoopKnt);
    getchar();
    return 0;
}
// -----------------------------------------------------------------------------
//  Scaffolding...
static void PrintIntBits(long x, int bits)  {
    unsigned long long z=1;
    int i=0;
    z = z << (bits-1);
    for (; z > 0; z >>= 1)  {
        printf("%s", ((x & z) == z) ? "#" : ".");
    }
}
//  These routines do bit manipulations on a bit array of unsigned chars
//  ---------------------------------------------------------------------------
void BitSet(uchar *buff, unsigned long BitNumber)   {
    buff[BitNumber >> 3] |= mask_set[BitNumber & 7];
}
//  ---------------------------------------------------------------------------- 
void BitClr(uchar *buff, unsigned long BitNumber)   {
    buff[BitNumber >> 3] &= mask_clr[BitNumber & 7];
}
//  ---------------------------------------------------------------------------- 
void BitTog(uchar *buff, unsigned long BitNumber)   {
    buff[BitNumber >> 3] ^= mask_set[BitNumber & 7];
}
//  ---------------------------------------------------------------------------- 
uchar BitGet(uchar *buff, unsigned long BitNumber)  {
    return (uchar)  ((buff[BitNumber >> 3] >> (BitNumber & 7)) & 1);
}
//  ---------------------------------------------------------------------------- 
void BitPut(uchar *buff, unsigned long BitNumber, uchar value)  {
    if(value)   {   // if the bit at buff[BitNumber] is true.
        BitSet(buff, BitNumber);
    }   else    {
        BitClr(buff, BitNumber);
    }
}

Answer 7

要反转单个字节x，您可以一次处理一个位：

// -----------------------------------------------------------------------------
// Reverse the bit ordering in new array
uchar *ReverseBitsInNewArray(uchar *Dst, const uchar *Src, const int BitKnt)    {
    int front=0, back = BitKnt-1;
    memset(Dst, 0, BitKnt/BitsInByte);

    while( front < back )   {
        if(BitGet(Src, back--)) {   // memset() has already set all bits in Dst to 0, 
            BitSet(Dst, front);     // so only reset if Src bit is 1
        }
        front++;
    }
    return Dst;

您可以在数组中创建这些结果的缓存，这样您只需通过单个查找而不是循环即可快速反转字节。

然后你只需要反转字节数组，并在编写数据时应用上面的映射。反转字节数组是一个记录良好的问题，例如，

unsigned char a = 0;
for (i = 0; i < 8; ++i) {
   a += (unsigned char)(((x >> i) & 1) << (7 - i));
}

。

Answer 8

单核？

记忆多少钱？

显示屏是否在内存中缓冲并推送到设备，或者是屏幕内存中像素的唯一副本？

Answer 9

数据通过8位IO端口从系统存储器推送到LCD驱动器。

由于您将一次一个字节地写入LCD，我认为最好的想法是在将数据发送到LCD驱动器时执行位反转，而不是单独的预通过。沿着这些方向的东西应该比任何其他答案更快：

here

其中

void send_to_LCD(uint8_t* data, int len, bool rotate) {
  if (rotate)
    for (int i=len-1; i>=0; i--)
      write(reverse(data[i]));
  else
    for (int i=0; i<len; i++)
      write(data[i]);
}

是向LCD驱动器发送字节的函数，write()是其他答案中描述的单字节位反转方法之一。

这种方法避免了在ram中存储两个视频数据副本的需要，并且还避免了read-invert-write往返。还要注意，这是最简单的实现：它可以简单地适应从内存中一次加载4个字节，如果这样可以产生更好的性能。智能矢量化编译器甚至可以为您完成。