c - MIPS 汇编代码——试图找出这段代码的内容

Question

我正在学习汇编代码，鉴于此代码，我需要找到此代码的内容。但是我正在尝试使用 qtspim 进行调试。我知道每个寄存器中的值是什么，但我仍然不明白这段代码是关于什么的。

如果您找到了该模式以及这段代码的内容，您能告诉我您是怎么做到的吗？您知道该模式在哪一行？谢谢!

.text
.globl main


.text
main:
li $s0, 0x00BEEF00 ##given $s0= 0x00BEEF00

Init:
li $t0, 0x55555555
li $t1,0x33333333
li $t2,0x0f0f0f0f
li $t3,0x00ff00ff
li $t4,0x0000ffff
Step1: and $s1, $s0, $t0

srl $s0,$s0,1
and $s2,$s0,$t0
add $s0,$s1,$s2

Step2: and $s1,$s0,$t1

srl $s0,$s0,2
and $s2,$s0,$t1
add $s0,$s1,$s2


Step3: and $s1,$s0,$t2
srl $s0,$s0,4
and $s2,$s0,$t2
add $s0,$s1,$s2

Step4: and $s1,$s0,$t3
srl $s0,$s0,8
and $s2,$s0,$t3
add $s0,$s1,$s2

Step5: 
and $s1,$s0,$t4
srl $s0,$s0,16
and $s2,$s0,$t4
add $s0,$s1,$s2

End:
andi $s0,$s0,0x003f

enter image description here

enter image description here

mips explain

Answer 1

这是一个 population count, aka popcount, aka Hamming Weight 。最终结果在$s0是1的数量输入中的位。这是一个优化的实现，它给出的结果与将每个位分别移到寄存器的底部并将其加到总数中相同。参见 https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

此实现的工作原理是使用 SWAR 从 2 位累加器构建到 4 位、8 位和 16 位累加器| 做多个不与一个 add 相互携带的窄加法说明。

注意它是如何屏蔽每隔一个位，然后是每对位，然后是每组 4 位。并使用轮类让另一对排队等待 add .喜欢C
(x & mask) + ((x>>1) & mask)

用更大的移位和不同的掩码重复此操作最终会得到所有位的总和(将它们都视为位值为 1)，即输入中设置位的数量。

所以这个的 GNU C 表示是 __builtin_popcnt(x) .

(除了编​​译器实际上会使用更高效的 p​​opcnt:每个字节单独的字节查找表，或者以这种方式开始的 bithack，但使用乘以像 0x01010101 这样的数字来水平求和 4 个字节结果的高字节。因为乘法是一个移位加指令。How to count the number of set bits in a 32-bit integer? )

---

但这有问题:它需要使用 addu避免出错；如果你尝试 popcnt 0x80000000 , 第一个 add将有两个输入 = 0x40000000 ，从而产生有符号溢出和故障。

IDK 为什么有人使用 add MIPS 指令。正常的二进制加法指令称为 addu .

add-with-trapping-on-signed-overflow 指令是 add ，这很少是您想要的，即使您的号码已签名。您不妨忘记它的存在并使用 addu/addui