c-从UINT16到UINT8提取和组合比特的更快方式

Question

我正在为我所需的特殊提取和组合操作寻找一种更快的方法，如下所述：

+-------+-------+-------+-------+-------+-------+-------+-------+
| BIT 7 | BIT 6 | BIT 5 | BIT 4 | BIT 3 | BIT 2 | BIT 1 | BIT 0 |
+-------+-------+-------+-------+-------+-------+-------+-------+
|   D1  |  D0   |  C1   |  C0   |  B1   |  B0   |  A1   |   A0  |
+-------+-------+-------+-------+-------+-------+-------+-------+
A = A0 OR A1
B = B0 OR B1
C = C0 OR C1
D = D0 OR D1
+-------+-------+-------+-------+-------+-------+-------+-------+
| BIT 7 | BIT 6 | BIT 5 | BIT 4 | BIT 3 | BIT 2 | BIT 1 | BIT 0 |
+-------+-------+-------+-------+-------+-------+-------+-------+
|       |       |       |       |   D   |   C   |   B   |   A   |
+-------+-------+-------+-------+-------+-------+-------+-------+

为了简单起见，上面只是一个8位的例子，这同样适用于16位的值。它应该在dsPIC33F微控制器上尽可能快地实现。

C中最简单的方法是：

PairFlags |= (ChannelFlags & 0x0003) ? 0x0001 : 0;
PairFlags |= (ChannelFlags & 0x000C) ? 0x0002 : 0;
PairFlags |= (ChannelFlags & 0x0030) ? 0x0004 : 0;
PairFlags |= (ChannelFlags & 0x00C0) ? 0x0008 : 0;
PairFlags |= (ChannelFlags & 0x0300) ? 0x0010 : 0;
PairFlags |= (ChannelFlags & 0x0C00) ? 0x0020 : 0;
PairFlags |= (ChannelFlags & 0x3000) ? 0x0040 : 0;
PairFlags |= (ChannelFlags & 0xC000) ? 0x0080 : 0;

这将产生大约40条指令(含O3(，在我的情况下对应于1µs。

如果可能，应减少指令周期的数量。在C或内联汇编中有没有更快的方法？

Answer 1

以下操作应适用于将16位值减少到8位(每个输出位通过对输入位进行"或"运算形成(：

// Set even bits to bits in pair ORed together, and odd bits to 0...
PairFlags = (ChannelFlags | (ChannelFlags >> 1)) & 0x5555; // '0h0g0f0e0d0c0b0a'
// Compress the '00' or '01' bit pairs down to single '0' or '1' bits...
PairFlags = (PairFlags ^ (PairFlags >> 1)) & 0x3333; // '00hg00fe00dc00ba'
PairFlags = (PairFlags ^ (PairFlags >> 2)) & 0x0F0F; // '0000hgfe0000dcba'
PairFlags = (PairFlags ^ (PairFlags >> 4)) & 0x00FF; // '00000000hgfedcba'

注：对于相同的结果，可以将上述^替换为|。

Answer 2

假设我做得很好(没有测试(，这似乎至少在gcc和clang上为x86(-O3(生成了好的、无分支的代码：

uint8_t convert (uint8_t ChannelFlags)
{
return ( ((ChannelFlags & A1A0)!=0) << A_POS ) |
( ((ChannelFlags & B1B0)!=0) << B_POS ) |
( ((ChannelFlags & C1C0)!=0) << C_POS ) |
( ((ChannelFlags & D1D0)!=0) << D_POS ) ;  
}

这屏蔽了每个单独的位集，然后针对零进行检查，以在临时int中得到1或0。该值在结果中的位置发生了偏移，然后所有内容最终按位进行"或"运算。完整代码：

#include <stdint.h>
#define A1A0  (3u << 0)
#define B1B0  (3u << 2)
#define C1C0  (3u << 4)
#define D1D0  (3u << 6)
#define A_POS 0
#define B_POS 1
#define C_POS 2
#define D_POS 3
uint8_t convert (uint8_t ChannelFlags)
{
return ( ((ChannelFlags & A1A0)!=0) << A_POS ) |
( ((ChannelFlags & B1B0)!=0) << B_POS ) |
( ((ChannelFlags & C1C0)!=0) << C_POS ) |
( ((ChannelFlags & D1D0)!=0) << D_POS ) ;  
}

clang反汇编x86提供18条指令分支自由：

convert:                                # @convert
test    dil, 3
setne   al
test    dil, 12
setne   cl
add     cl, cl
or      cl, al
test    dil, 48
setne   al
shl     al, 2
or      al, cl
mov     ecx, edi
shr     cl, 7
shr     dil, 6
and     dil, 1
or      dil, cl
shl     dil, 3
or      al, dil
ret

Answer 3

不确定是否更有效，但与其使用三元if，为什么不只使用逐位运算呢？然后用位移算子来抵消它

PairFlags = ((ChannelFlags & (0b1 << 0)) | (ChannelFlags & (0b10 << 0))) << 0;
PairFlags = ((ChannelFlags & (0b1 << 2)) | (ChannelFlags & (0b10 << 2))) << 1;
PairFlags = ((ChannelFlags & (0b1 << 4)) | (ChannelFlags & (0b10 << 4))) << 2;
//...

Answer 4

这里有一个想法。在这里观察一件事：

A = A0 OR A1
B = B0 OR B1
C = C0 OR C1
D = D0 OR D1

您有4个或多个操作。你可以在一条指令中执行所有这些：

PairFlags = (PairFlags | (PairFlags >> 1))

现在你们的比特是这样排列的：

[D1][D1 or D0][D0 or C1][C1 or C0][C0 or B1][B1 or B0][B0 or A1][A1 or A0]

所以你只需要提取比特0，2，4，6就可以得到结果。

位0。已经可以了。

位1应设置为位2。

位2应设置为位4。

第3位应设置为第6位。

最终代码类似于：

PairFlags = (PairFlags | (PairFlags >> 1))
PairFlags = (PairFlags&1) | ((PairFlags&4)>>1) | ((PairFlags&16)>>2) | ((PairFlags&64)>>3)