快速向后转动大块内存
我需要以相反的顺序重写大约4KB的数据，在位级（最后一个字节的最后一位成为第一个字节的第一位），尽可能快。 有没有聪明的小册子呢？
理由：数据是嵌入式设备中LCD屏幕的显示内容，通常以屏幕位于肩膀上的方式定位。 屏幕有“6点钟”的方向，可以从下面看 – 像平躺或挂在眼睛上方。 这可以通过将屏幕旋转180度来固定，但是我需要从屏幕的左上角开始反转屏幕数据（由库生成），即1位= 1像素。 CPUfunction不是很强大，设备已经有足够的工作量，加上一秒钟的几帧，所以性能是个问题; RAM不是那么多。
编辑：单核，ARM 9系列。 64MB，（缩小到32MB以后），Linux。 数据通过8位IO端口从系统存储器推送到LCD驱动器。
CPU为32位，在字长方面的性能要比字节级高得多。
这是一种经典的方法。 假设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次操作。
最快的方法可能是将所有可能的字节值的反转存储在查找表中。 该表只需256个字节。
构建一个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), };
Bit Twiddling Hacks网站是解决这类问题的良好起点。 看看这里的快速位反转。 然后由您决定将其应用于内存块的每个字节/字。
编辑：
受到Dietrich Epps回答并查看ARM指令集的启发 ，有一个RBIT操作码可以反转寄存器中包含的位。 因此，如果性能至关重要，您可以考虑使用一些汇编代码。
循环遍历数组的一半，转换和交换字节。
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; }
对于转换，使用预先计算的表 - 2个CHAR_BIT （ CHAR_BIT最可能是8个）元素的数组，其中位置“I”存储具有值“I”反转的字节的结果。 这将非常快 - 一次通过 - 并且表格仅消耗2个CHAR_BIT 。
看起来这个代码在我的i7 XPS 8500机器上每位交换大约需要50个时钟。 一百万次阵翻翻7.6秒。 单线程。 它根据1s和0s的模式打印一些ASCI艺术品。 在使用图形编辑器反转位arrays后，我将图片向左旋转了180度，它们看起来与我相同。 双反转图像与原始图像相同。
至于加号，它是一个完整的解决方案。 它将位从位arrays的后面交换到前面，而不是在整数/字节上操作，然后需要在数组中交换整数/字节。
此外，这是一个通用的位库，因此您可能会发现将来解决其他更普通的问题很方便。
它和接受的答案一样快吗？ 我认为它很接近，但没有工作代码来进行基准测试就不可能了。 随意剪切和粘贴此工作程序。
// 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 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); } }
下面是使用新缓冲区进行优化的代码清单，而不是交换字节。 由于if（）测试只需要2030：4080 BitSet（），并且通过消除TEMP消除了大约一半的GetBit（）和PutBits（），我怀疑内存访问时间是一个很大的固定成本。这些类型的操作，为优化提供了硬性限制。
使用查找方法，并且有条件地交换字节而不是位，将内存访问次数减少8倍，对0字节的测试在8位而不是1中分摊。
一起使用这两种方法，在执行ANYTHING之前测试整个8位字符是否为0，包括表查找和写入，可能是最快的方法，但需要额外的512字节新的目标位数组，以及查找表的256个字节。 尽管如此，表现的回报可能非常大。
// ----------------------------------------------------------------------------- // 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;
要反转单个字节x，您可以一次处理一个位：
unsigned char a = 0; for (i = 0; i < 8; ++i) { a += (unsigned char)(((x >> i) & 1) << (7 - i)); }
您可以在数组中创建这些结果的缓存，这样您只需通过单个查找而不是循环即可快速反转字节。
然后你只需要反转字节数组，并在写入数据时应用上面的映射。 反转字节数组是一个记录良好的问题，例如这里 。
单核？
记忆多少钱？
显示屏是否在内存中缓冲并推送到设备，或者是屏幕内存中像素的唯一副本？
数据通过8位IO端口从系统存储器推送到LCD驱动器。
由于您将一次一个字节地写入LCD，我认为最好的想法是在将数据发送到LCD驱动器时执行位反转，而不是单独的预通过。 沿着这些方向的东西应该比任何其他答案更快：
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
其中write()是向LCD驱动程序发送字节的函数， reverse()是其他答案中描述的单字节位反转方法之一。
这种方法避免了在ram中存储两个video数据副本的需要，并且还避免了read-invert-write往返。 还要注意，这是最简单的实现：它可以简单地适应从内存中一次加载4个字节，如果这样可以产生更好的性能。 智能矢量化编译器甚至可以为您完成。