1

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

devss
  • 145
  • 8
  • 1
    If you search for `5555` here: https://graphics.stanford.edu/~seander/bithacks.html You might find a pretty good clue. – Retired Ninja Jul 07 '19 at 22:12
  • @RetiredNinja thankyou, i trace and convert it to 1010 .. but what is the clue? – devss Jul 08 '19 at 03:39
  • Yup, looks like a popcount to me, 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. – Peter Cordes Jul 08 '19 at 05:47
  • @PeterCordes i dont know but my teacher said it is fibbonacci code(?) but imm cant see it why – devss Jul 08 '19 at 06:15
  • Perhaps there was a miscommunication with your teacher about which block of code you're discussing. This is very clearly *not* a Fibonacci implementation. There's no loop or Fib(0), 1 initializers, or fully-unrolled sequence of adds, and Fib(n) doesn't require any `and` or `srl`. (There is a closed-form solution for `Fib(n)` but it's pretty clearly not that either). – Peter Cordes Jul 08 '19 at 06:29
  • I looked at the operands for the instructions more carefully to make sure, and yes it is the familiar pattern of SWAR summing for popcount that I recognized from the masks and shift counts. As something of a bit-hack and assembly guru, I'm 100% confident about this (I edited my answer to remove the "I think" part now that I've taken extra time to be sure). Run it for some inputs if you're not convinced, or if you want to see it in action single-stepping and watching register values (I suggest using hex to see bit-groups in separate nibbles). – Peter Cordes Jul 08 '19 at 06:32
  • @PeterCordes i added picture, ther eseem pattern for fibbonaci if trace in binary.. im trying to trace it in paper, its really time consuming – devss Jul 09 '19 at 17:30
  • I don't know what you're seeing in that image that looks like Fibonacci. It's showing multiple *independent* 2-bit groups, exactly like I described. But there are some errors in the diagram: it shows the first `01` pair of input bits adding up to `1 + 1 = 10`. So it's like there was no attempt at consistency between the circles in the input row vs. the circles in row 3 (the first step of SRL + AND). There is consistency after that, though. – Peter Cordes Jul 10 '19 at 00:40
  • Oh, I think the diagram is showing a *left* shift for that step, like SLL + AND. But that wouldn't work because it would lose the carry from the top pair. So the diagram doesn't quite match the code you've shown. It's trying to explain the logic, but doing it wrong. There's still *nothing* Fibonacci-like here. Just binary addition of neighbouring bits then of 2-bit groups into 4-bit accumulators, etc. – Peter Cordes Jul 10 '19 at 00:42
  • @PeterCordes i added picture again, i try to trace it in hex but it seem the pattern only shown in binary(?) i really dont know popcount is, this is also introdcution to mips class maybe its not advanced(?) – devss Jul 10 '19 at 09:11
  • i really want to understand the code, in case you get find some pattern(?) – devss Jul 10 '19 at 09:20
  • I already linked to the wikipedia article about it in case you weren't familiar. But just now I edited my answer to explain that popcount is just counting the number of set bits. It's not a hard concept, but an optimized implementation like this uses tricks like doing addition where you care about multiple separate groups of bits in the same register. That's not specific to assembly language: it's usable with binary integers in other languages too, with shifting and masking. – Peter Cordes Jul 10 '19 at 09:38
  • Like I said before, single-step with a debugger and watch register values in hex or binary. It's a simple pattern that repeats for each step of 1, 2, 4, 8, and 16-bit groups. Notice the increasing shift counts with the same pattern of shift / 2x AND / add. You already have diagrams of it from your instructor; go ask them if you're still not getting it. – Peter Cordes Jul 10 '19 at 09:41
  • @PeterCordes thankyou i will try my best to understand the codes!! – devss Jul 11 '19 at 16:54

1 Answers1

1

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

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847