c - 如何在位图中的位之间插入零？

Question

我有一些执行位操作的性能密集型代码。它可以简化为以下明确定义的问题:

给定一个 13 位位图，构造一个 26 位位图，其中包含在偶数位置间隔的原始位。

举例说明:

0000000000000000000abcdefghijklm (input, 32 bits)
0000000a0b0c0d0e0f0g0h0i0j0k0l0m (output, 32 bits)

我目前在 C 中以下列方式实现它:

if (input & (1 << 12))
    output |= 1 << 24;
if (input & (1 << 11))
    output |= 1 << 22;
if (input & (1 << 10))
    output |= 1 << 20;
...

我的编译器 (MS Visual Studio) 将其转换为以下内容:

test        eax,1000h
jne         0064F5EC
or          edx,1000000h
... (repeated 13 times with minor differences in constants)

我想知道我是否可以让它更快。我想用 C 语言编写代码，但可以切换到汇编语言。

• 我可以使用一些 MMX/SSE 指令一次处理所有位吗？
• 或许我可以使用乘法？ (乘以 0x11111111 或其他魔法常数)
• 使用条件设置指令 (SETcc) 代替条件跳转指令会更好吗？如果是，我怎样才能让编译器为我生成这样的代码？
• 关于如何让它更快的任何其他想法？
• 知道如何进行逆向位图转换(我也必须实现它，但它不太重要)？

Answer 1

有一个聪明的方法可以做到这一点，在这里可能会有帮助。它实际上解决了一个稍微更一般的位改组问题。你的问题有一个输入:

+---------------+---------------+---------------+---------------+
|0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|0 0 0 a b c d e|f g h i j k l m|
+---------------+---------------+---------------+---------------+

....但是让我们考虑所有的位:

+---------------+---------------+---------------+---------------+
|A B C D E F G H|I J K L M N O P|Q R S a b c d e|f g h i j k l m|
+---------------+---------------+---------------+---------------+

并尝试像这样交错它们:

+---------------+---------------+---------------+---------------+
|A Q B R C S D a|E b F c G d H e|I f J g K h L i|M j N k O l P m|
+---------------+---------------+---------------+---------------+

第一步，考虑输入的中间一半:

bit 31        24              16               8               0
 v             v               v               v               v
+---------------+---------------+---------------+---------------+
|               |I J K L M N O P|Q R S a b c d e|               |
+---------------+---------------+---------------+---------------+

构造8位值:{ I^Q, J^R, K^S, L^a , M^b, N^c, O^d, P^e }。

如果我们将这个 8 位值与 [15:8] 位进行异或，并且还进行异或与位 [23:16] 相同的 8 位值，我们将交换中间的两个字节:对于例如，第 23 位(最初是 I)将变为 I ^ (I^Q) = Q 和第 15 位(原本 Q) 会变成 Q ^ (I^Q) = I。

为此:tmp = (input ^ (input >> 8)) & 0x0000ff00;:

+---------------+---------------+---------------+---------------+
|A B C D E F G H|I J K L M N O P|Q R S a b c d e|f g h i j k l m| input
+---------------+---------------+---------------+---------------+
                            exclusive-OR with:
+---------------+---------------+---------------+---------------+
|0 0 0 0 0 0 0 0|A B C D E F G H|I J K L M N O P|Q R S a b c d e| input >> 8
+---------------+---------------+---------------+---------------+

                             -->|want these bits|<--

 mask (bitwise AND) with 0x0000ff00:
+---------------+---------------+---------------+---------------+
|0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|1 1 1 1 1 1 1 1|0 0 0 0 0 0 0 0| 0x0000ff00
+---------------+---------------+---------------+---------------+

现在我们需要的 8 位值在位 [15:8] 中，所有其他位都为 0。现在我们可以用

input ^= (tmp ^ (tmp << 8));

导致:

+---------------+---------------+---------------+---------------+
|A B C D E F G H|Q R S a b c d e|I J K L M N O P|f g h i j k l m| input
+---------------+---------------+---------------+---------------+

下一步，分而治之...进行类似的中间交换左手一半的位:

+---------------+---------------+---------------+---------------+
|A B C D E F G H|Q R S a b c d e|               |               |
+---------------+---------------+---------------+---------------+
             becomes
+---------------+---------------+---------------+---------------+
|A B C D Q R S a|E F G H b c d e|               |               |
+---------------+---------------+---------------+---------------+

...和右半边:

+---------------+---------------+---------------+---------------+
|               |               |I J K L M N O P|f g h i j k l m|
+---------------+---------------+---------------+---------------+
                                             becomes
+---------------+---------------+---------------+---------------+
|               |               |I J K L f g h i|M N O P j k l m|
+---------------+---------------+---------------+---------------+

我们可以使用与第一步完全相同的技巧，因为我们想要对 32 位字的两个 16 位半部分执行完全相同的操作，我们可以并行进行:

tmp = (input ^ (input >> 4)) & 0x00f000f0;

构造我们将用于交换的两对 4 位，然后

input ^= (tmp ^ (tmp << 4));

实际进行交换。

我们可以继续应用相同的原则，直到交换完成。每个点参与交换的比特用#标记:

+---------------+---------------+---------------+---------------+
|A B C D E F G H|I J K L M N O P|Q R S a b c d e|f g h i j k l m|
+---------------+---------------+---------------+---------------+
                 ###############/###############
+---------------+---------------+---------------+---------------+
|A B C D E F G H|Q R S a b c d e|I J K L M N O P|f g h i j k l m|
+---------------+---------------+---------------+---------------+
         #######/#######                 #######/#######
+---------------+---------------+---------------+---------------+
|A B C D Q R S a|E F G H b c d e|I J K L f g h i|M N O P j k l m|
+---------------+---------------+---------------+---------------+
     ###/###         ###/###         ###/###         ###/###
+---------------+---------------+---------------+---------------+
|A B Q R C D S a|E F b c G H d e|I J f g K L h i|M N j k O P l m|
+---------------+---------------+---------------+---------------+
   #/#     #/#     #/#     #/#       #/#   #/#     #/#     #/#
+---------------+---------------+---------------+---------------+
|A Q B R C S D a|E b F c G d G e|I f J g K h L i|M j N k O l P m|
+---------------+---------------+---------------+---------------+

代码:

tmp = (input ^ (input >> 8)) & 0x0000ff00;
input ^= (tmp ^ (tmp << 8));
tmp = (input ^ (input >> 4)) & 0x00f000f0;
input ^= (tmp ^ (tmp << 4));
tmp = (input ^ (input >> 2)) & 0x0c0c0c0c;
input ^= (tmp ^ (tmp << 2));
tmp = (input ^ (input >> 1)) & 0x22222222;
input ^= (tmp ^ (tmp << 1));                    /* = output */

---

可以通过向后运行4个步骤来执行反向操作:

tmp = (input ^ (input >> 1)) & 0x22222222;
input ^= (tmp ^ (tmp << 1));                    /* = output */
tmp = (input ^ (input >> 2)) & 0x0c0c0c0c;
input ^= (tmp ^ (tmp << 2));
tmp = (input ^ (input >> 4)) & 0x00f000f0;
input ^= (tmp ^ (tmp << 4));
tmp = (input ^ (input >> 8)) & 0x0000ff00;
input ^= (tmp ^ (tmp << 8));

尽管您可以针对您的特定应用对此进行改进，如果已知所有其他位都为零:请参阅我对另一个的回答问题 here .

---

最后一点，不要相信任何人关于相对性能的任何说法此处建议的任何方法都没有在您的中对其进行基准测试申请。 (特别是，大型查找表看起来会好得多在简单的微基准测试中，它们实际上在给定的真实环境中应用程序，由于从缓存中逐出大量其他数据，这会对外部循环产生负面影响。)