转换4×4字节矩阵的最快方法
我有一个4×4字节块，我想使用通用硬件进行转置。 换句话说，对于字节AP，我正在寻找最有效的（就指令数量而言）的方式
ABCD EFGH IJKL MNOP 至
AEIM BFJN CGKO DHLP
我们可以假设我在内存中有指向A ， E ， I和M有效指针（这样从A读取32位将得到包含字节ABCD的整数）。
由于对大小和数据类型的限制，这不是此问题的重复。 我的矩阵的每一行都可以容纳32位整数，我正在寻找能够使用通用硬件快速执行转置的答案，类似于SSE宏_MM_TRANSPOSE4_PS 。
让我重新提一下你的问题：你要求的是只有C或C ++的便携式解决方案。 然后：
void transpose(uint32_t const in[4], uint32_t out[4]) { // ABCDAEIM // EFGHBFJN // IJKLCGKO // MNOPDHLP 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; // BF . . out[2] |= (in[0] << 16) & 0xFF000000U; // C . K . out[3] |= (in[0] << 24); // D . . P out[0] |= (in[1] >> 8) & 0x00FF0000U; // AE . . out[2] |= (in[1] << 8) & 0x00FF0000U; // CGK . out[3] |= (in[1] << 16) & 0x00FF0000U; // DH . P out[0] |= (in[2] >> 16) & 0x0000FF00U; // AEI . out[1] |= (in[2] >> 8) & 0x0000FF00U; // BFJ . out[3] |= (in[2] << 8) & 0x0000FF00U; // DHLP out[0] |= (in[3] >> 24); // AEIM out[1] |= (in[3] >> 8) & 0x000000FFU; // BFJN out[2] |= (in[3] << 8) & 0x000000FFU; // CGKO }
我不知道如何以任何其他方式回答它，因为那时你将依赖于特定的编译器以特定的方式编译它，等等。
当然，如果这些操作本身可以以某种方式简化，它会有所帮助。 所以这是进一步追求的唯一途径。 到目前为止，没有什么是突出的，但对我来说这是漫长的一天。
到目前为止，成本是12个class次，12个OR，16个AND。 如果编译器和平台有任何好处，可以在9个32位寄存器中完成。
如果编译器非常难过，或者平台没有桶形移位器，那么一些转换可以帮助推断移位和掩码只是字节提取这一事实：
void transpose(uint8_t const in[16], uint8_t out[16]) { // ABCDAEIM // EFGHBFJN // IJKLCGKO // MNOPDHLP out[0] = in[0]; // A . . . out[1] = in[4]; // AE . . out[2] = in[8]; // AEI . out[3] = in[12]; // AEIM out[4] = in[1]; // B . . . out[5] = in[5]; // BF . . out[6] = in[9]; // BFJ . out[7] = in[13]; // BFJN out[8] = in[2]; // C . . . out[9] = in[6]; // CG . . out[10] = in[10]; // CGK . out[11] = in[14]; // CGKO out[12] = in[3]; // D . . . out[13] = in[7]; // DH . . out[14] = in[11]; // DHL . out[15] = in[15]; // DHLP }
如果你真的想要在适当的位置进行随机播放，那么下面就可以了。
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]); }
面向字节的版本可能会在现代平台上产生更糟糕的代码。 只有一个基准可以告诉。
你想要适用性和效率。 那么你不可能两种方式。 你说你想用最少的指令来做这件事。 好吧，使用x86指令集中的pshufb指令（见下文），只能使用SSE3的一条指令执行此操作。
也许ARM Neon有同等的东西。 如果你想要效率（并且确定你需要它），那么学习硬件。
对于字节， _MM_TRANSPOSE4_PS的SSE等价物是使用带掩码的_mm_shuffle_epi8 （ _mm_shuffle_epi8的内在函数）。 在主循环外定义掩码。
//use -msse3 with GCC or /arch:SSE2 with MSVC #include #include //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 }
不确定速度，但这些都没关系。
template void Transpose(T (&Data)[Size][Size]) { for (int I = 0; I < Size; ++I) { for (int J = 0; J < I; ++J) { std::swap(Data[I][J], Data[J][I]); } } } template void Transpose(T (&Data)[Size * Size]) { for (int I = 0; I < Size; ++I) { for (int J = 0; J < I; ++J) { std::swap(Data[I * Size + J], Data[J * Size + I]); } } }
如果您接受，可以在64位机器上实现有效的解决方案。 首先将32位整数常量分别移位（0，）1,2和3字节[3 shitfs]。 然后屏蔽掉不需要的位并执行逻辑OR [12个带有常数，12个OR的AND]。 最后，转回32位[3个移位]并读出32位。
ABCD EFGH IJKL MNOP ABCD EFGH IJKL MNOP A--- E--- I--- MNOP ======= AEIMNOP AEIM AB-- -F-- -J-- -NOP ======= ABFJNOP BFJN ABC- --G- --K- --OP ======= ABCGKOP CGKO ABCD ---H ---L ---P ======= ABCDHLP DHLP
我在这里为SSE发布了这个相同问题的答案。
唯一需要添加的是矢量化加载/存储操作。
这个答案类似于Z boson对这个问题的回答 。 在那里可以看到加载/存储的示例。 这个答案不同，因为除了SSE3实现之外，还有一个SSE2实现，可以保证在任何x64处理器上运行。
值得注意的是，这两个解决方案都假设整个矩阵在内存中是行主要的，但是OP的问题表明每行可以拥有它自己的指针，这意味着arrays可能被分段。