快速向后转动大块内存

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

该位操作黑客网站alwas对于此类问题的一个很好的起点.看看这里的快速位反转.然后由您决定将其应用于内存块的每个字节/字.

编辑:

受到Dietrich Epps回答并查看ARM指令集的启发,有一个RBIT操作码可以反转寄存器中包含的位.因此,如果性能至关重要,您可以考虑使用一些汇编代码.