c-如何有效地将两个16位字一位一位地组合成一个32位字

Question

我必须将两个16位的字组合成一个32位的字数百次，这需要大量的计算能力。我想找到一种更有效的方法来做这件事。

我有两个名为A和B的16位字。我想有一个名为C的32位字。A中的位应该复制到C中的偶数位。

我目前的解决方案如下：

for (i = 0; i < 32; i+=2)
{
C |=  (A & (1 << (i/2))) << (i/2);
C |=  (B & (1 << (i/2))) << (i/2 + 1);
}

当我有几百个C要处理时，这个解决方案花费了太多时间。我在找一个更好的！

添加：此程序在TriCore上运行。我别无选择，只能用这种方式处理数据，因为AB和C之间的关系是由协议定义的。

谢谢！

Answer 1

原来Tricore有一条BMERGE指令，它可以精确地执行您想要的操作——它采用两个16位值并交错这些位。如果您使用的是基于gcc的工具链，那么您应该能够使用单个内联asm语句——类似于：

asm("bmerge %0,%1,%2" : "=r"(C) : "r"(A), "r"(B))

还有一个BSPLIT指令可以执行相反的操作。

Answer 2

分组移位，而不是循环。

一些进一步的简化是可能的，但以下是它的要点。它是平均速度更快(还是最坏情况更快)？要了解的配置文件。

#include <inttypes.h>
#include <stdint.h>
uint64_t Merge(uint32_t a, uint32_t b) {
uint64_t A,B;
A = ((a & 0x00000000FFFF0000ull) << 16) | (a & 0x000000000000FFFFull);
A = ((A & 0x0000FF000000FF00ull) <<  8) | (A & 0x000000FF000000FFull);
A = ((A & 0xF0F0F0F0F0F0F0F0ull) <<  4) | (A & 0x0F0F0F0F0F0F0F0Full);
A = ((A & 0xCCCCCCCCCCCCCCCCull) <<  2) | (A & 0x0333333333333333ull);
A = ((A & 0xAAAAAAAAAAAAAAAAull) <<  1) | (A & 0x5555555555555555ull);
B = ((b & 0x00000000FFFF0000ull) << 16) | (b & 0x000000000000FFFFull);
B = ((B & 0x0000FF000000FF00ull) <<  8) | (B & 0x000000FF000000FFull);
B = ((B & 0xF0F0F0F0F0F0F0F0ull) <<  4) | (B & 0x0F0F0F0F0F0F0F0Full);
B = ((B & 0xCCCCCCCCCCCCCCCCull) <<  2) | (B & 0x0333333333333333ull);
B = ((B & 0xAAAAAAAAAAAAAAAAull) <<  1) | (B & 0x5555555555555555ull);
return A | (B << 1);
}
void MergeTest(uint32_t a, uint32_t b) {
uint64_t C = Merge(a,b);
printf("a:%08" PRIX32 " b:%08" PRIX32 " c:%016" PRIX64 "n", a,b,C);
}
void MergeTests(void) {
MergeTest(0x00000000L, 0xFFFFFFFFL);
MergeTest(0xFFFFFFFFL, 0x00000000L);
MergeTest(0x00000000L, 0x00000001L);;
MergeTest(0x00000000L, 0x00000010L);;
}
a:00000000 b:FFFFFFFF c:AAAAAAAAAAAAAAAA  
a:FFFFFFFF b:00000000 c:5555555555555555  
a:00000000 b:00000001 c:0000000000000002  
a:00000000 b:00000010 c:0000000000000200  

Answer 3

试试这个：

for (i = 0; i < 32; i+=2)
{
int i2 = i >> 1 ;
int andval = 1 << i2 ;
C |=  (A & andval) << i2;
C |=  (B & andval) << (i2 + 1);
}

但您的编译器可能已经进行了此优化。

Answer 4

在MCU上工作的最有可能的解决方案类型(可能是8位的，可能没有桶形移位器)是沿着这些线的手动编码组装(将A、B和CL/CH作为16位寄存器)：

LOOP:
MOV CNT, 16
RRC A     ; rotate A right through the carry
RRC CH    ; carry enters C at the top
RRC CL    ; continue roll through CL
RRC B
RRC CH
RRC CL
DJNZ CNT,LOOP

(显然，如果MCU是8位的，则每个RRC变成两个)。

这个解决方案将比特"混洗"在一起，同时每个周期只旋转一个比特，这是任何MCU都可以做到的。你可以尝试用C写这个，但你需要一个很好的优化器来从lsb = A & 1; A >>= 1; C >>=1; C |= lsb << 31;之类的东西中生成这个指令序列

编辑：使用32位CPU，您可以考虑bit Twiddling Hacks上列出的所有选项。

Answer 5

看起来快了40%，但这实际上取决于编译器的优化；-)

for (i=1, j=2, msk=1; i<0x100000000; i<<=2, j<<=2, msk<<=1) {
if (A & msk) C |= i;
if (B & msk) C |= j;
}

Answer 6

这个问题也被称为"Morton数编码"；即将2-D或3-D坐标平坦化为单个数字。

这篇博客文章总结了三种典型的方法：天真的循环、神奇的比特(如chux的回答)和查找表。基于LUT的方法显然是赢家。

基本上必须选择一次处理多少比特。通常，最佳点位于8->16位或4->8位LUT中，例如此处。

0001 --> 0 0 0 0 0 0 0 1
0010 --> 0 0 0 0 0 1 0 0
0011 --> 0 0 0 0 0 1 0 1  etc.

使用该表扩展两个uint8_t变量是通过以下公式实现的：

uint16_t ans =  LUT[a & 15]       + (LUT[b & 15] << 1) +
(LUT[a >> 4] << 8) + (LUT[b << 4] << 9);

同样，必须确定在给定位数的情况下，是否有4个不同的表更有效，每个表左移一个常数，或者手动执行移位。

Answer 7

下面使用两个遍历掩码，一个用于测试源数据位，另一个用于屏蔽到目的地。compileonline.com对1000万次迭代的测试给出了以下结果：

• 原始算法：1.14秒
• 此算法：0.81秒

尽管不要停止阅读-接下来会有显著的改进。

uint32_t C ;
uint16_t srcmask ;
uint32_t dstmask ;
for( C = 0, srcmask = 1u, dstmask = 1u; 
srcmask != 0; 
srcmask <<= 1 )
{
if( (A & srcmask) != 0 )
{
C |= dstmask ;
}
dstmask <<= 1 ;
if( (B & srcmask) != 0 )
{
C |= dstmask ;
}
dstmask <<= 1 ;
}

然而，理论上，性能可能会因1位的数量而异，但在我的测试中，这种差异是无法测量的，但不同的目标和编译器可能会产生不同的结果。

将循环展开到每次迭代4个源位具有边际效益(0.77秒)：

for( C = 0, srcmask = 1u, dstmask = 1u; 
srcmask != 0; 
srcmask <<= 1 )
{
// Unroll 1
if( (A & srcmask) )
{
C |= dstmask ;
}
dstmask <<= 1 ;
if( (B & srcmask) )
{
C |= dstmask ;
}
dstmask <<= 1 ;
// Unroll 2
srcmask <<= 1 ;
if( (A & srcmask) )
{
C |= dstmask ;
}
dstmask <<= 1 ;
if( (B & srcmask) )
{
C |= dstmask ;
}
dstmask <<= 1 ;
// Unroll 3
srcmask <<= 1 ;
if( (A & srcmask) )
{
C |= dstmask ;
}
dstmask <<= 1 ;
if( (B & srcmask) )
{
C |= dstmask ;
}
dstmask <<= 1 ;
// Unroll 4
srcmask <<= 1 ;
if( (A & srcmask) )
{
C |= dstmask ;
}
dstmask <<= 1 ;
if( (B & srcmask) )
{
C |= dstmask ;
}
dstmask <<= 1 ;
}

进一步展开会产生不利影响，但目标和编译器的结果可能会有所不同。

然后，我将C、srcmask和dstmask声明为register，而不期望有任何差异：

register uint32_t C ;
register uint16_t srcmask ;
register uint32_t dstmask ;

结果让我大吃一惊：

• 原始算法：1.19秒
• 此算法：0.29秒

展开的效果非常显著——如果没有它，时间将达到0.45秒，2次展开=0.33秒。进一步展开效果甚微。将A和B声明为寄存器会略微降低性能——只有这么多寄存器可供使用！。再次YMMV。

因此，得出的结论必须是，你需要尝试多种技术来确定什么对你的目标最有效。在这里，更好的算法、循环展开和寄存器变量的组合产生了巨大的影响。使用不同编译器优化设置进行实验也可能会产生影响，尽管改进代码的一个领域可能会损害其他领域，因此您可能不想对所有代码应用相同的优化。