如何优化反转位组的顺序
How to optimize reversing the order of groups of bits
基本上，我有8条数据，每条2位（4个状态），存储在一个32位整数的低16位。我想颠倒数据片段的顺序来做一些模式匹配。
我得到了一个参考整数和 8 个候选人，我需要将其中一个候选人与参考相匹配。但是，匹配候选可能会以某种可预测的方式进行转换。
如果引用数据的形式是[0,1,2,3,4,5,6,7]，那么可能的匹配可以是这8种形式之一：
[0,1,2,3,4,5,6,7], [0,7,6,5,4,3,2,1]
[6,7,0,1,2,3,4,5], [2,1,0,7,6,5,4,3]
[4,5,6,7,0,1,2,3], [4,3,2,1,0,7,6,5]
[2,3,4,5,6,7,0,1], [6,5,4,3,2,1,0,7]
模式是数据总是有序的，但可以反转和旋转。
我正在用 C 和 MIPS 实现它。我都在工作，但它们看起来很笨重。我目前的做法是屏蔽掉原来的每一块，把它移到它的新位置，然后用新变量（初始化为0）或它。
我在 C 中做了更多硬编码：
int ref = 4941; // reference value, original order [1,3,0,1,3,0,1,0], (encoded as 0b0001001101001101)
int rev = 0;
rev |= ((ref & 0x0003) << 14) | ((ref & 0x000C) << 10) | ((ref & 0x0030) << 6) | ((ref & 0x00C0) << 2); // move bottom 8 bits to top
rev |= ((ref & 0xC000) >> 14) | ((ref & 0x3000) >> 10) | ((ref & 0x0C00) >> 6) | ((ref & 0x0300) >> 2); // move top 8 bits to bottom
// rev = 29124 reversed order [0,1,0,3,1,0,3,1], (0b0111000111000100)
我在 MIPS 中实现了一个循环来尝试减少静态指令：
lw , Reference([=12=]) # load reference value
addi , [=12=], 4 # initialize as Loop counter
addi , [=12=], 14 # initialize to hold shift value
addi , [=12=], 3 # initialize to hold mask (one piece of data)
# Reverse the order of data in Reference and store it in
Loop: addi , , -1 # decrement Loop counter
and , , # mask out one piece ( = Reference & )
sllv , , # shift piece to new position ( <<= )
or , , # put piece into ( |= )
sllv , , # shift mask for next piece
and , , # mask out next piece (#03 = Reference & )
srlv , , # shift piece to new position ( >>= )
or , , # put new piece into ( |= )
srlv , , # shift mask back
addi , , -4 # decrease shift amount by 4
sll , , 2 # shift mask for next loop
bne , [=12=], Loop # keep looping while != 0
有没有更简单或至少更少指令的实现方法？
对于一种非常简单有效的方法，使用 256 字节查找 table 并执行 2 次查找：
extern unsigned char const xtable[256];
unsigned int ref = 4149;
unsigned int rev = (xtable[ref & 0xFF] << 8) | xtable[ref >> 8];
xtable数组可以通过一组宏静态初始化：
#define S(x) ((((x) & 0x0003) << 14) | (((x) & 0x000C) << 10) | \
(((x) & 0x0030) << 6) | (((x) & 0x00C0) << 2) | \
(((x) & 0xC000) >> 14) | (((x) & 0x3000) >> 10) | \
(((x) & 0x0C00) >> 6) | (((x) & 0x0300) >> 2))
#define X8(m,n) m((n)+0), m((n)+1), m((n)+2), m((n)+3), \
m((n)+4), m((n)+5), m((n)+6), m((n)+7)
#define X32(m,n) X8(m,(n)), X8(m,(n)+8), X8(m,(n)+16), X8(m,(n)+24)
unsigned char const xtable[256] = {
X32(S, 0), X32(S, 32), X32(S, 64), X32(S, 96),
X32(S, 128), X32(S, 160), X32(S, 192), X32(S, 224),
};
#undef S
#undef X8
#undef X32
如果 space 并不昂贵，您可以对 128K 字节 table 进行一次查找，您可以在启动时计算或使用脚本生成并在编译时包含，但它有点浪费，而且对缓存不友好。
要反转您的位，您可以使用以下代码。
static int rev(int v){
// swap adjacent pairs of bits
v = ((v >> 2) & 0x3333) | ((v & 0x3333) << 2);
// swap nibbles
v = ((v >> 4) & 0x0f0f) | ((v & 0x0f0f) << 4);
// swap bytes
v = ((v >> 8) & 0x00ff) | ((v & 0x00ff) << 8);
return v;
}
MIPS 实现是 15 条指令。
rev: # value to reverse in
# uses reg
srli , , 2
andi , , 0x3333
andi , , 0x3333
slli , , 2
or , ,
srli , , 4
andi , , 0x0f0f
andi , , 0x0f0f
slli , , 4
or , ,
srli , , 8
andi , , 0xff
andi , , 0xff
slli , , 8
or , ,
# result in
请注意，只需将常量加倍（在 64 位机器上甚至是 4）即可同时反转 2x16 位。但我不确定它对你有用。
注意：小心手写优化汇编，如果您真的在紧密循环中与编译器生成斗争，确实有特定于处理器的优化保留它们。
您可以改进 pipeline, (if you code in C the compiler do it for you) and use the delay slot of the bne instruction. This will improve your instruction level parallelism。
假设您有类似 Mips 处理器的东西，带有 1 个延迟槽和 5 级流水线（指令获取、解码、执行、内存、写回）。
这个流水线引入了Read After Write数据依赖的危害大部分在</code>寄存器上。</p>
<p>RaW 故障导致您的流水线停滞。</p>
<pre><code># Reverse the order of data in Reference and store it in
Loop: and , , # mask out one piece ( = Reference & )
addi , , -1 # decrement Loop counter (RaW on )
sllv , , # shift piece to new position ( <<= )
sllv , , # shift mask for next piece
or , , # put piece into ( |= )
and , , # mask out next piece (#03 = Reference & )
srlv , , # shift mask back
srlv , , # shift piece to new position ( >>= )
addi , , -4 # decrease shift amount by 4
or , , # put new piece into ( |= )
bne , [=10=], Loop # keep looping while != 0
sll , , 2 # shift mask for next loop
如果您有超标量处理器，则解决方案需要进行一些更改。
基本上，我有8条数据，每条2位（4个状态），存储在一个32位整数的低16位。我想颠倒数据片段的顺序来做一些模式匹配。
我得到了一个参考整数和 8 个候选人，我需要将其中一个候选人与参考相匹配。但是，匹配候选可能会以某种可预测的方式进行转换。
如果引用数据的形式是[0,1,2,3,4,5,6,7]，那么可能的匹配可以是这8种形式之一：
[0,1,2,3,4,5,6,7], [0,7,6,5,4,3,2,1]
[6,7,0,1,2,3,4,5], [2,1,0,7,6,5,4,3]
[4,5,6,7,0,1,2,3], [4,3,2,1,0,7,6,5]
[2,3,4,5,6,7,0,1], [6,5,4,3,2,1,0,7]
模式是数据总是有序的，但可以反转和旋转。
我正在用 C 和 MIPS 实现它。我都在工作，但它们看起来很笨重。我目前的做法是屏蔽掉原来的每一块，把它移到它的新位置，然后用新变量（初始化为0）或它。
我在 C 中做了更多硬编码：
int ref = 4941; // reference value, original order [1,3,0,1,3,0,1,0], (encoded as 0b0001001101001101)
int rev = 0;
rev |= ((ref & 0x0003) << 14) | ((ref & 0x000C) << 10) | ((ref & 0x0030) << 6) | ((ref & 0x00C0) << 2); // move bottom 8 bits to top
rev |= ((ref & 0xC000) >> 14) | ((ref & 0x3000) >> 10) | ((ref & 0x0C00) >> 6) | ((ref & 0x0300) >> 2); // move top 8 bits to bottom
// rev = 29124 reversed order [0,1,0,3,1,0,3,1], (0b0111000111000100)
我在 MIPS 中实现了一个循环来尝试减少静态指令：
lw , Reference([=12=]) # load reference value
addi , [=12=], 4 # initialize as Loop counter
addi , [=12=], 14 # initialize to hold shift value
addi , [=12=], 3 # initialize to hold mask (one piece of data)
# Reverse the order of data in Reference and store it in
Loop: addi , , -1 # decrement Loop counter
and , , # mask out one piece ( = Reference & )
sllv , , # shift piece to new position ( <<= )
or , , # put piece into ( |= )
sllv , , # shift mask for next piece
and , , # mask out next piece (#03 = Reference & )
srlv , , # shift piece to new position ( >>= )
or , , # put new piece into ( |= )
srlv , , # shift mask back
addi , , -4 # decrease shift amount by 4
sll , , 2 # shift mask for next loop
bne , [=12=], Loop # keep looping while != 0
有没有更简单或至少更少指令的实现方法？
对于一种非常简单有效的方法，使用 256 字节查找 table 并执行 2 次查找：
extern unsigned char const xtable[256];
unsigned int ref = 4149;
unsigned int rev = (xtable[ref & 0xFF] << 8) | xtable[ref >> 8];
xtable数组可以通过一组宏静态初始化：
#define S(x) ((((x) & 0x0003) << 14) | (((x) & 0x000C) << 10) | \
(((x) & 0x0030) << 6) | (((x) & 0x00C0) << 2) | \
(((x) & 0xC000) >> 14) | (((x) & 0x3000) >> 10) | \
(((x) & 0x0C00) >> 6) | (((x) & 0x0300) >> 2))
#define X8(m,n) m((n)+0), m((n)+1), m((n)+2), m((n)+3), \
m((n)+4), m((n)+5), m((n)+6), m((n)+7)
#define X32(m,n) X8(m,(n)), X8(m,(n)+8), X8(m,(n)+16), X8(m,(n)+24)
unsigned char const xtable[256] = {
X32(S, 0), X32(S, 32), X32(S, 64), X32(S, 96),
X32(S, 128), X32(S, 160), X32(S, 192), X32(S, 224),
};
#undef S
#undef X8
#undef X32
如果 space 并不昂贵，您可以对 128K 字节 table 进行一次查找，您可以在启动时计算或使用脚本生成并在编译时包含，但它有点浪费，而且对缓存不友好。
要反转您的位，您可以使用以下代码。
static int rev(int v){
// swap adjacent pairs of bits
v = ((v >> 2) & 0x3333) | ((v & 0x3333) << 2);
// swap nibbles
v = ((v >> 4) & 0x0f0f) | ((v & 0x0f0f) << 4);
// swap bytes
v = ((v >> 8) & 0x00ff) | ((v & 0x00ff) << 8);
return v;
}
MIPS 实现是 15 条指令。
rev: # value to reverse in
# uses reg
srli , , 2
andi , , 0x3333
andi , , 0x3333
slli , , 2
or , ,
srli , , 4
andi , , 0x0f0f
andi , , 0x0f0f
slli , , 4
or , ,
srli , , 8
andi , , 0xff
andi , , 0xff
slli , , 8
or , ,
# result in
请注意，只需将常量加倍（在 64 位机器上甚至是 4）即可同时反转 2x16 位。但我不确定它对你有用。
注意：小心手写优化汇编，如果您真的在紧密循环中与编译器生成斗争，确实有特定于处理器的优化保留它们。
您可以改进 pipeline, (if you code in C the compiler do it for you) and use the delay slot of the bne instruction. This will improve your instruction level parallelism。
假设您有类似 Mips 处理器的东西，带有 1 个延迟槽和 5 级流水线（指令获取、解码、执行、内存、写回）。
这个流水线引入了Read After Write数据依赖的危害大部分在</code>寄存器上。</p>
<p>RaW 故障导致您的流水线停滞。</p>
<pre><code># Reverse the order of data in Reference and store it in
Loop: and , , # mask out one piece ( = Reference & )
addi , , -1 # decrement Loop counter (RaW on )
sllv , , # shift piece to new position ( <<= )
sllv , , # shift mask for next piece
or , , # put piece into ( |= )
and , , # mask out next piece (#03 = Reference & )
srlv , , # shift mask back
srlv , , # shift piece to new position ( >>= )
addi , , -4 # decrease shift amount by 4
or , , # put new piece into ( |= )
bne , [=10=], Loop # keep looping while != 0
sll , , 2 # shift mask for next loop
如果您有超标量处理器，则解决方案需要进行一些更改。