转换4x4字节矩阵的最快方法

Question

我有一个4x4字节块,我想使用通用硬件进行转置.换句话说,对于字节AP,我正在寻找最有效(就指令数量而言)的方式

A B C D
E F G H
I J K L
M N O P

至

A E I M
B F J N
C G K O
D H L P

我们可以假设,我有有效指针指向A,E,I,并M在内存中(这样从读取32位将让我的包含整数字节ABCD).

由于对大小和数据类型的限制,这不是此问题的重复.我的矩阵的每一行都可以适合32位整数,我正在寻找可以使用通用硬件快速执行转置的答案,类似于SSE宏的实现_MM_TRANSPOSE4_PS.

Answer 1

你想要适销性和效率.那么你不可能两种方式.你说你想用最少的指令来做这件事.好吧,使用x86指令集中的pshufb指令(见下文),只能使用SSE3的一条指令执行此操作.

也许ARM Neon有同等的东西.如果你想要效率(并确定你需要它),那么学习硬件.

_MM_TRANSPOSE4_PS用于字节的SSE等价物是使用_mm_shuffle_epi8(带有掩码的pshufb的内在函数).在主循环外定义掩码.

//use -msse3 with GCC or /arch:SSE2 with MSVC
#include <stdio.h>
#include <tmmintrin.h> //SSSE3
int main() {
    char x[] = {0,1,2,3, 4,5,6,7, 8,9,10,11, 12,13,15,16};
    __m128i mask = _mm_setr_epi8(0x0,0x04,0x08,0x0c, 0x01,0x05,0x09,0x0d, 0x02,0x06,0x0a,0x0e, 0x03,0x07,0x0b,0x0f);

    __m128i v = _mm_loadu_si128((__m128i*)x);
    v = _mm_shuffle_epi8(v,mask);
    _mm_storeu_si128((__m128i*)x,v);
    for(int i=0; i<16; i++) printf("%d ", x[i]); printf("\n");
    //output: 0 4 8 12 1 5 9 13 2 6 10 15 3 7 11 16   
}

Answer 2

让我重新提一下你的问题:你要求的是只有C或C++的便携式解决方案.然后:

void transpose(uint32_t const in[4], uint32_t out[4]) {
  // A B C D    A E I M
  // E F G H    B F J N
  // I J K L    C G K O
  // M N O P    D H L P

  out[0] = in[0] & 0xFF000000U; // A . . .
  out[1] = in[1] & 0x00FF0000U; // . F . .
  out[2] = in[2] & 0x0000FF00U; // . . K .
  out[3] = in[3] & 0x000000FFU; // . . . P

  out[1] |= (in[0] <<  8) & 0xFF000000U; // B F . .
  out[2] |= (in[0] << 16) & 0xFF000000U; // C . K .
  out[3] |= (in[0] << 24);               // D . . P

  out[0] |= (in[1] >>  8) & 0x00FF0000U; // A E . .
  out[2] |= (in[1] <<  8) & 0x00FF0000U; // C G K .
  out[3] |= (in[1] << 16) & 0x00FF0000U; // D H . P

  out[0] |= (in[2] >> 16) & 0x0000FF00U; // A E I .
  out[1] |= (in[2] >>  8) & 0x0000FF00U; // B F J .
  out[3] |= (in[2] <<  8) & 0x0000FF00U; // D H L P

  out[0] |= (in[3] >> 24);               // A E I M
  out[1] |= (in[3] >>  8) & 0x000000FFU; // B F J N
  out[2] |= (in[3] <<  8) & 0x000000FFU; // C G K O
}

我不知道如何以任何其他方式回答它,因为那时你将依赖于特定的编译器以特定的方式编译它,等等.

当然,如果这些操作本身可以以某种方式简化,那么它会有所帮助.所以这是进一步追求的唯一途径.到目前为止,没有什么是突出的,但对我来说这是漫长的一天.

到目前为止,成本是12个班次,12个OR,16个AND.如果编译器和平台有任何好处,可以在9个32位寄存器中完成.

如果编译器非常难过,或者平台没有桶形移位器,那么一些转换可以帮助推断移位和掩码只是字节提取这一事实:

void transpose(uint8_t const in[16], uint8_t out[16]) {
  // A B C D    A E I M
  // E F G H    B F J N
  // I J K L    C G K O
  // M N O P    D H L P

  out[0]  = in[0];  // A . . .
  out[1]  = in[4];  // A E . .
  out[2]  = in[8];  // A E I .
  out[3]  = in[12]; // A E I M
  out[4]  = in[1];  // B . . .
  out[5]  = in[5];  // B F . .
  out[6]  = in[9];  // B F J .
  out[7]  = in[13]; // B F J N
  out[8]  = in[2];  // C . . .
  out[9]  = in[6];  // C G . .
  out[10] = in[10]; // C G K .
  out[11] = in[14]; // C G K O
  out[12] = in[3];  // D . . .
  out[13] = in[7];  // D H . .
  out[14] = in[11]; // D H L .
  out[15] = in[15]; // D H L P
}

如果你真的想要在适当的位置进行随机播放,那么以下内容就可以了.

void transpose(uint8_t m[16]) {
  std::swap(m[1], m[4]);
  std::swap(m[2], m[8]);
  std::swap(m[3], m[12]);
  std::swap(m[6], m[9]);
  std::swap(m[7], m[13]);
  std::swap(m[11], m[14]);
}

面向字节的版本可能会在现代平台上产生更糟糕的代码.只有一个基准可以说明.