向后快速地翻转一大块内存

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

我也不知道哪种位移动/旋转原语在手臂上速度快,哪种速度慢。这是需要考虑的事情。如果您需要更高的速度,可以考虑从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 网站一直是这些问题的良好起点。看一看 here 用于快速位反转。然后由您决定将它应用于内存块的每个字节/字。

编辑:

灵感来源于Dietrich EPPS的回答和观察 ARM instruction set 有一个 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 最有可能是8)个元素,其中在位置“i”处存储值为“i”的字节反转结果。这将非常快-一次通过-只消耗2 ^夏比特 为了桌子。

在我的i7 xps 8500机器上,这个代码每比特交换大约需要50个时钟。7.6秒,进行100万次阵列翻转。单螺纹。它基于1和0的模式打印了一些asci艺术。我使用图形编辑器反转位数组后将图片向左旋转180度,它们看起来和我一样。一个双反转的图像和原始图像一样。

至于优点,这是一个完整的解决方案。它将位从一个位数组的后面交换到前面,而不是在Ints/Bytes上操作,然后需要在数组中交换Ints/Bytes。

另外,这是一个通用的位库,所以将来您可能会发现它对于解决其他更普通的问题很方便。

它和公认的答案一样快吗?我认为这很接近,但是如果没有工作的代码来进行基准测试,就不可能说出来。请随意剪切和粘贴此工作程序。

//reverse bitsinbuff.cpp:定义控制台应用程序的入口点。
#包括“stdafx.h”
#包括“time.h”
#包括“memory.h”
/ /
//清单常量
#定义UChar无符号字符
#define buff_bytes 510//400支持80x40位的显示
#define dw 80//显示宽度
/————————————————————————————————————————————————————————————————————————————————————————————————————————————————————
uchar mask_set[]=0x01、0x02、0x04、0x08、0x10、0x20、0x40、0x80_
uchar mask_clr[]=0xfe,0xfd,0xfb,0xf7,0xef,0xdf,0xbf,0x7f_
/ /
//函数原型
静态void printintbits(long x,int bits);
空比特集(uchar*位数组,无符号长比特数);
void bitlr(uchar*位数组,无符号长位编号);
void bittog(uchar*位数组,无符号长位编号);
uchar bitget(uchar*位数组,无符号长位号);
空位输入(uchar*位数组,无符号长位数字,uchar值);
/ /
uchar*反向bitsinarray(uchar*buff,int bitknt);
静态void printintbits(long x,int bits);
/——————————————————————————————————————————————————————————————————————————————————————————————————————————————————
//颠倒数组中的位顺序
UChar*反向位数组(UChar*buff,int bitknt){
无符号长前=0,后=bitknt-1;
乌恰温度;
同时(前面和后面){
temp=bitget(buff,front);//覆盖前将前位复制到temp
位输入(buff,front,bitget(buff,back));//将位复制回前位
bitput(buff,back,temp);//将front-in-temp的保存值复制到bit-arra的后面)
前面+ +;
后背;
}
返回buff;
}
/————————————————————————————————————————————————————————————————————————————————————————————————————————————————---
/————————————————————————————————————————————————————————————————————————————————————————————————————————————————---
int _tmain(int argc,_tchar*argv[]){
int i,j,k,loopknt=1000001;
时间启动;
uchar buff[buff_字节];
memset(buff,0,sizeof(buff));
//制作ASCII艺术图片
对于(i=0,k=0;i<(sizeof(buff)*8)/dw;i++){
对于(j=0;j<dw/2;j++){
位集(buff,(i*dw)+j+k);
}
K++;
}
//打印ASCII艺术图片
对于(i=0;i<sizeof(buff);i++){
如果(!)(i%10))printf(“\n”);//以80块为单位打印位
printintbits(buff[i],8);
}
我= Loknt;
开始=时钟();
而(我--){
反向位数组((uchar*)buff,buff_bytes*8);
}
//print ascii art pic倒转左旋转
printf(“\nmilliseconds elaped=%d”,clock()-开始);
对于(i=0;i<sizeof(buff);i++){
如果(!)(i%10))printf(“\n”);//以80块为单位打印位
printintbits(buff[i],8);
}
printf(“\n \n为%d个循环标记时间\n”,loopknt);
getchar();
返回0;
}
/——————————————————————————————————————————————————————————————————————————————————————————————————————————————————
//脚手架…
静态void printintbits(long x,int位){
无符号长z=1;
int i=0;
Z=Z<<(位-1);
对于(;Z>0;Z>>=1){
printf(“%s”,((x&z)==z)?“”:“”
}
}
//这些例程对无符号字符的位数组执行位操作
/————————————————————————————————————————————————————————————————————————————————————————————————————————————————---
无效位集(uchar*buff,无符号长位号){
buff[bitnumber>>3]=mask_set[bitnumber&7];
}
/————————————————————————————————————————————————————————————————————————————————————————————————————————————————————
空比特lr(uchar*buff,无符号长比特数){
buff[bitnumber>>3]&=屏蔽\u clr[bitnumber&7];
}
/————————————————————————————————————————————————————————————————————————————————————————————————————————————————————
void bittog(uchar*buff,无符号长位号){
buff[bitnumber>>3]^=屏蔽设置[bitnumber&7];
}
/————————————————————————————————————————————————————————————————————————————————————————————————————————————————————
uchar bitget(uchar*buff,无符号长比特数){
返回(uchar)((buff[bitnumber>>3]>>(bitnumber&7))&1);
}
/————————————————————————————————————————————————————————————————————————————————————————————————————————————————————
空位输入(uchar*buff,无符号长位号,uchar值){
if(value)//如果buff[位号]处的位为真。
位集(buff,位号);
}否则{
bitlr(buff,位号);
}
}
< /代码> 

下面是使用新缓冲区进行优化的代码列表,而不是就地交换字节。由于if()测试只需要2030:4080位集(),并且通过消除temp消除了大约一半的getbit()和putbits(),我怀疑内存访问时间对于这些类型的操作来说是一个巨大的固定成本,为优化提供了一个硬限制。

使用查找方法,有条件地交换字节(而不是位),将内存访问数减少8倍,0字节的测试将分摊到8位,而不是1位。

同时使用这两种方法,在执行任何操作(包括表查找和写入)之前测试整个8位char是否为0可能是最快的方法,但对于新的目标位数组需要额外的512字节,而对于查找表则需要256字节。不过,业绩回报可能相当可观。

//————————————————————————————————————————————————————————————————————————————————————————————————————————————
//反转新数组中的位顺序
uchar*反向BitsInwarray(uchar*dst,const uchar*src,const int bitknt){
int front=0,back=bitknt-1;
内存集(dst,0,bitknt/bitsinbyte);

同时(前面和后面){
if(bitget(src,back--))//memset()已经将dst中的所有位设置为0,
bitset(dst,front);//所以只有当src bit为1时才重置
}
前面+ +;
}
返回DST;
< /代码> 


在我的i7 xps 8500机器上,这个代码每比特交换大约需要50个时钟。7.6秒,进行100万次阵列翻转。单螺纹。它基于1和0的模式打印了一些asci艺术。我使用图形编辑器反转位数组后将图片向左旋转180度,它们看起来和我一样。一个双反转的图像和原始图像一样。

至于优点,这是一个完整的解决方案。它将位从一个位数组的后面交换到前面,而操作的是Ints/字节,然后需要在一个数组中交换Ints/字节。

另外,这是一个通用的位库,所以将来您可能会发现它对于解决其他更普通的问题很方便。

它和公认的答案一样快吗?我认为这很接近,但是如果没有工作的代码来进行基准测试,就不可能说出来。请随意剪切和粘贴此工作程序。

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


下面是使用新缓冲区进行优化的代码列表,而不是就地交换字节。由于if()测试只需要2030:4080位集(),并且通过消除temp消除了大约一半的getbit()和putbits(),我怀疑内存访问时间对于这些类型的操作来说是一个巨大的固定成本,为优化提供了一个硬限制。

使用查找方法,有条件地交换字节(而不是位),将内存访问数减少8倍,0字节的测试将分摊到8位,而不是1位。

同时使用这两种方法,在执行任何操作(包括表查找和写入)之前测试整个8位char是否为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));
}

您可以在数组中创建这些结果的缓存,这样您就可以通过进行单个查找而不是循环来快速反转字节。

然后您只需要反转字节数组,当您编写数据时,应用上面的映射。反转字节数组是一个有良好记录的问题,例如 here .

单核?

有多少记忆?

显示器是在内存中缓冲并推送到设备上,还是屏幕内存中像素的唯一副本?

数据通过8位IO从系统内存推送到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<len; i++)
      write(data[i]);
}

在哪里? write() 是向LCD驱动程序发送字节的函数,并且 reverse() 其他答案中描述的单字节位反转方法之一。

这种方法避免了在RAM中存储两个视频数据副本的需要,也避免了读写往返。另外请注意,这是最简单的实现:如果要获得更好的性能,那么它可以非常适合从内存中一次加载4个字节。一个智能的矢量化编译器甚至可以为您做这件事。