我不知道有任何带有奇偶校验指令的 MIPS 变体,但是有一个小技巧可以比依次运行 32 位中的每一个的明显方法更快地计算奇偶校验。在 C 中:
result = in ^ (in >> 16);
result ^= (result >> 8);
result ^= (result >> 4);
result ^= (result >> 2);
result ^= (result >> 1);
result &= 1;
在第一步之后,结果的低 16 位包含输入的第 N 位和 N+16 位的奇偶校验 - 本质上,奇偶校验计算的 16 步已经一次执行。写作result{N}
表示“第 N 位result
”:
result{0} = in{0} ^ in{16}
result{1} = in{1} ^ in{17}
result{2} = in{2} ^ in{18}
...
result{7} = in{7} ^ in{23}
result{8} = in{8} ^ in{24}
...
result{15} = in{15} ^ in{31}
result
(现在可以忽略剩余的前 16 位;它们在剩余的计算中没有用处)。
在第二步之后,低 8 位result
包含原始输入的 N、N+8、N+16、N+24 位的奇偶校验:
result{0} = result{0} ^ result{8} = in{0} ^ in{8} ^ in{16} ^ in{24}
result{1} = result{1} ^ result{9} = in{1} ^ in{9} ^ in{17} ^ in{25}
...
result{7} = result{7} ^ result{15} = in{7} ^ in{15} ^ in{23} ^ in{31}
(同样,从这里开始可以忽略剩余的位)。
...依此类推,直到原始输入的所有位的奇偶校验最终位于 的底部位result
:
result{0} = in{0} ^ in{1} ^ in{2} ^ ... ^ in{30} ^ in{31}
这很容易直接转化为 MIPS 汇编;这是11条指令:
# input in $a0, output in $v0, $t0 corrupted
srl $t0, $a0, 16
xor $v0, $a0, $t0
srl $t0, $v0, 8
xor $v0, $v0, $t0
srl $t0, $v0, 4
xor $v0, $v0, $t0
srl $t0, $v0, 2
xor $v0, $v0, $t0
srl $t0, $v0, 1
xor $v0, $v0, $t0
and $v0, $v0, 1
一个可能的改进可能是使用查找表。例如,在前两个步骤之后,我们有:
result{0} = in{0} ^ in{8} ^ in{16} ^ in{24}
result{1} = in{1} ^ in{9} ^ in{17} ^ in{25}
...
result{7} = in{7} ^ in{15} ^ in{23} ^ in{31}
所以此时我们可以使用一个 256 字节的查找表。在 C 中:
result = in ^ (in >> 16);
result ^= (result >> 8);
result = lookup_table[result & 0xff];
lookup_table[n]
已预先计算的位置,例如:
for (i = 0; i < 256; i++) {
n = i ^ (i >> 4);
n ^= (n >> 2);
n ^= (n >> 1);
lookup_table[i] = n & 1;
}
这是 7 个 MIPS 指令,不包括将查找表基地址加载到寄存器中:
# input in $a0, lookup table address in $a1, output in $v0, $t0 corrupted
srl $t0, $a0, 16
xor $v0, $a0, $t0
srl $t0, $v0, 8
xor $v0, $v0, $t0
andi $v0, $v0, 0xff
addu $t0, $a1, $v0
lbu $v0, 0($t0)
但是,这是 7 条指令,其中包括内存访问,而 11 条指令是纯粹的寄存器操作;它可能会也可能不会更快。(这种微优化总是需要分析!)