最快的方式转置4x4字节矩阵 [英] Fastest way to transpose 4x4 byte matrix

问题描述

我有一个4x4的字节块，我想使用通用硬件转置。换句话说，对于字节AP，我正在寻找从

开始的最有效的（在指令数量方面）

  ABCD 
 EFGH 
 IJKL 
 MNOP 
  

p>

  AEIM 
 BFJN 
 CGKO 
 DHLP 
  

我们可以假设我有有效的指针指向 A ， / code>， I 和 M （使得从A读取32位将获得我不是的重复。 /stackoverflow.com/questions/16737298/what-is-the-fastest-way-to-transpose-a-matrix-in-c \">这个问题，因为对大小和数据类型的限制。我的矩阵的每一行可以适合一个32位整数，我正在寻找可以使用通用硬件快速执行转置的解决方案，类似于实现的SSE宏 _MM_TRANSPOSE4_PS 便携式。然后：

  void transpose（uint32_t const in [4]，uint32_t out [4]）{
 // ABCDAEIM 
 // EFGHBFJN 
 // IJKLCGKO 
 // MNOPDHLP 
 
 out [0] = in [0]& 0xFF000000U; // 一个 。 。 。 
 out [1] = in [1]& 0x00FF 0000U; //。 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）& 0x00FF 0000U; // A E。 。 
 out [2] | =（in [1]<< 8）& 0x00FF 0000U; // C G K。 
 out [3] | =（in [1]<< 16）& 0x00FF 0000U; // 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; // CGKO 
} 
  

我看不到如何回答任何其他方式，因为那时你将依赖于一个特定的编译器以特定的方式编译它。

当然，如果这些操作本身可以被简化，帮帮我。这是这里唯一的进一步追求的途径。到目前为止，没有什么突出，但对我来说这是一个漫长的一天。

到目前为止，成本是12班，12个OR，16个AND。如果编译器和平台是任何好的，它可以在9 32位寄存器中完成。

如果编译器很伤心，或者平台没有桶移位器，那么一些转换可以帮助宣布移位和掩码只是字节提取的事实：

  void transpose（uint8_t const [16]，uint8_t out [16]）{
 // ABCDAEIM 
 // EFGHBFJN 
 // IJKLCGKO 
 // MNOPDHLP 
 
 out [0 ] = in [0]; // 一个 。 。 。 
 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]; // 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]）; 
} 
  

面向字节的版本可能会产生代码在现代平台上。只有基准可以告诉。

I have a 4x4 block of bytes that I'd like to transpose using general purpose hardware. In other words, for bytes A-P, I'm looking for the most efficient (in terms of number of instructions) way to go from

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

to

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

We can assume that I have valid pointers pointing to A, E, I, and M in memory (such that reading 32-bits from A will get me the integer containing bytes ABCD).

This is not a duplicate of this question because of the restrictions on both size and data type. Each row of my matrix can fit into a 32-bit integer, and I'm looking for answers that can perform a transpose quickly using general purpose hardware, similar to the implementation of the SSE macro _MM_TRANSPOSE4_PS.

解决方案

Let me rephrase your question: you're asking for a C- or C++-only solution that is portable. Then:

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
}

I don't see how it could be answered any other way, since then you'd be depending on a particular compiler compiling it in a particular way, etc.

Of course if those manipulations themselves can be somehow simplified, it'd help. So that's the only avenue of further pursuit here. Nothing stands out so far, but then it's been a long day for me.

So far, the cost is 12 shifts, 12 ORs, 16 ANDs. If the compiler and platform are any good, it can be done in 9 32 bit registers.

If the compiler is very sad, or the platform doesn't have a barrel shifter, then some casting could help extol the fact that the shifts and masks are just byte extractions:

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
}

If you really want to shuffle it in-place, then the following would do.

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

The byte-oriented versions may well produce worse code on modern platforms. Only a benchmark can tell.

这篇关于最快的方式转置4x4字节矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！