在位上旋转8x8块中的位的最快方法是什么？

Question

我不确定我正在尝试做什么的确切术语.我有一个存储8x8块,每个字节存储一行.当我完成后,我希望每个字节存储一列.bits8 bytes

例如,当我完成时:

Byte0out = Byte0inBit0 + Byte1inBit0 + Byte2inBit0 + Byte3inBit0 + ...
Byte1out = Byte0inBit1 + Byte1inBit1 + Byte2inBit1 + Byte3inBit1 + ...

在C中表现良好的最简单方法是什么？

Answer 1

这段代码直接来自"Hacker's Delight" - 图7-2转换一个8x8位矩阵,我不相信它:

void transpose8(unsigned char A[8], int m, int n, 
                unsigned char B[8]) {
   unsigned x, y, t; 

   // Load the array and pack it into x and y. 

   x = (A[0]<<24)   | (A[m]<<16)   | (A[2*m]<<8) | A[3*m]; 
   y = (A[4*m]<<24) | (A[5*m]<<16) | (A[6*m]<<8) | A[7*m]; 

   t = (x ^ (x >> 7)) & 0x00AA00AA;  x = x ^ t ^ (t << 7); 
   t = (y ^ (y >> 7)) & 0x00AA00AA;  y = y ^ t ^ (t << 7); 

   t = (x ^ (x >>14)) & 0x0000CCCC;  x = x ^ t ^ (t <<14); 
   t = (y ^ (y >>14)) & 0x0000CCCC;  y = y ^ t ^ (t <<14); 

   t = (x & 0xF0F0F0F0) | ((y >> 4) & 0x0F0F0F0F); 
   y = ((x << 4) & 0xF0F0F0F0) | (y & 0x0F0F0F0F); 
   x = t; 

   B[0]=x>>24;    B[n]=x>>16;    B[2*n]=x>>8;  B[3*n]=x; 
   B[4*n]=y>>24;  B[5*n]=y>>16;  B[6*n]=y>>8;  B[7*n]=y; 
}

我没有检查它是否按您所需的方向旋转,如果不是,您可能需要调整代码.

另外,记住数据类型和尺寸- int和unsigned (int)可能不是你的平台上32位.

顺便说一句,我怀疑这本书(Hacker's Delight)对于你正在做的工作至关重要......看看它,那里有很多很棒的东西.

Answer 2

如果您正在寻找最简单的解决方案:

/* not tested, not even compiled */

char bytes_in[8];
char bytes_out[8];

/* please fill bytes_in[] here with some pixel-crap */

memset(bytes_out, 0, 8);
for(int i = 0; i < 8; i++) {
    for(int j = 0; j < 8; j++) {
        bytes_out[i] = (bytes_out[i] << 1) | ((bytes_in[j] >> (7 - i)) & 0x01);
    }
}

如果您正在寻找最快的解决方案:

如何利用SSE2在程序集中转置位矩阵.