从 UINT16 到 UINT8 提取和组合位的更快方法
Faster way for extracting and combining bits from UINT16 to UINT8
我正在为我所需的特殊提取和合并操作寻找一种更快的方法,如下所述:
+-------+-------+-------+-------+-------+-------+-------+-------+
| 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 或内联汇编中有更快的方法吗?
不确定是否更有效但不是使用三元 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;
//...
假设我做对了一切(未测试),这似乎生成了良好的 branch-free 代码,至少在 x86 (-O3) 的 gcc 和 clang 上:
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
结束。在最终按位 OR:ed 在一起之前,这个值在结果中的位置发生了变化。完整代码:
#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
这是一个想法。
在这里观察一件事:
A = A0 OR A1
B = B0 OR B1
C = C0 OR C1
D = D0 OR D1
您有 4 个 or 操作。您可以在 1 条指令中执行所有这些操作:
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 即可得到结果。
Bit 0.已经OK了
位 1 应设置为位 2。
位 2 应设置为位 4。
第 3 位应设置为第 6 位。
最终代码类似于:
PairFlags = (PairFlags | (PairFlags >> 1))
PairFlags = (PairFlags&1) | ((PairFlags&4)>>1) | ((PairFlags&16)>>2) | ((PairFlags&64)>>3)
以下应该可以将 16 位值减少到 8 位(输出的每一位由一对输入位的 OR 运算形成):
// 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'
注:上面的^
可以换成|
,效果一样。
我正在为我所需的特殊提取和合并操作寻找一种更快的方法,如下所述:
+-------+-------+-------+-------+-------+-------+-------+-------+
| 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 或内联汇编中有更快的方法吗?
不确定是否更有效但不是使用三元 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;
//...
假设我做对了一切(未测试),这似乎生成了良好的 branch-free 代码,至少在 x86 (-O3) 的 gcc 和 clang 上:
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
结束。在最终按位 OR:ed 在一起之前,这个值在结果中的位置发生了变化。完整代码:
#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
这是一个想法。 在这里观察一件事:
A = A0 OR A1
B = B0 OR B1
C = C0 OR C1
D = D0 OR D1
您有 4 个 or 操作。您可以在 1 条指令中执行所有这些操作:
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 即可得到结果。
Bit 0.已经OK了
位 1 应设置为位 2。
位 2 应设置为位 4。
第 3 位应设置为第 6 位。
最终代码类似于:
PairFlags = (PairFlags | (PairFlags >> 1))
PairFlags = (PairFlags&1) | ((PairFlags&4)>>1) | ((PairFlags&16)>>2) | ((PairFlags&64)>>3)
以下应该可以将 16 位值减少到 8 位(输出的每一位由一对输入位的 OR 运算形成):
// 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'
注:上面的^
可以换成|
,效果一样。