CODEWITHSUNDEEP
cassemblymipsreverse-engineeringhammingweight
devss
devss

Reputation: 145

MIPS assembly code - trying to find out what this code's about

I'm learning assembly code, and given this code, I need to find what this code is about. However I am trying to debug using qtspim. I know what the value inside each register, but I still don't get what is this code about.

If you find the pattern and what this code about, can you tell me how can you do it, and in what line you know the pattern? thanks!

.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

Upvotes: 1

Views: 687

Answers (1)

Peter Cordes
Peter Cordes

Reputation: 363980

This is a population count, aka popcount, aka Hamming Weight. The final result in $s0 is the number of 1 bits in the input. This is an optimized implementation that gives the same result as shifting each bit separately to the bottom of a register and adding it to a total. See https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

This implementation works by building up from 2-bit accumulators to 4-bit, 8-bit, and 16-bit using SWAR to do multiple narrow adds that don't carry into each other with one add instruction.

Notice how it masks every other bit, then every pair of bits, then every group of 4 bits. And uses a shift to bring the other pair down to line up for an add. Like C
(x & mask) + ((x>>1) & mask)

Repeating this with a larger shift and a different mask eventually gives you the sum of all the bits (treating them all as having place-value of 1), i.e. the number of set bits in the input.

So the GNU C representation of this is __builtin_popcnt(x).

(Except that compilers will actually use a more efficient popcnt: either a byte lookup table for each byte separately, or a bithack that starts this way, but uses a multiply by a number like 0x01010101 to horizontal sum 4 bytes into the high byte of the result. Because multiply is a shift-and-add instruction. How to count the number of set bits in a 32-bit integer?)

But this is broken: it needs to use addu to avoid faulting; if you try to popcnt 0x80000000, the first add will have both inputs = 0x40000000, thus producing signed overflow and faulting.

IDK why anyone uses the add instruction on MIPS. The normal binary add instruction is called addu.

The add-with-trapping-on-signed-overflow instruction is add, which is rarely what you want even if your numbers are signed. You might as well just forget it exists and use addu / addui

Upvotes: 1

Related Questions