I am trying to practice converting C code to MIPS Assembly. How would I go about translating the following collatz function to MIPS?

Question

uint32_t collatz(uint32_t n, int d) {
  /*   printf("%d\n", n);*/
  if (n != 1) {
    if (n % 2)
      return collatz(3 * n + 1, d + 1);
    else {
      return collatz(n / 2, d + 1);
    }
  }

  return d;
}

This is the C function I am trying to rewrite in MIPS Assembly. I want to use recursion in my assembly version and I am really struggling with making the function work.

I have this driver for the assembly version of the function.

.data

arrow: .asciiz " -> "

.text

main:
    li      $sp,        0x7ffffffc      # initialize $sp

# PROLOGUE
    subu    $sp,        $sp,        8   # expand stack by 8 bytes
    sw      $ra,        8($sp)          # push $ra (ret addr, 4 bytes)
    sw      $fp,        4($sp)          # push $fp (4 bytes)
    addu    $fp,        $sp,        8   # set $fp to saved $ra

    subu    $sp,        $sp,        12  # save s0 and s1 on stack before using them
    sw      $s0,        12($sp)         # push $s0
    sw      $s1,        8($sp)          # push $s1
    sw      $s2,        4($sp)          # push $s2

    la      $s0,        xarr            # load address to s0

main_for:
    lw      $s1,        ($s0)           # use s1 for xarr[i] value
    li      $s2,        0               # use s2 for initial depth (steps)
    beqz    $s1,        main_end        # if xarr[i] == 0, stop.

# save args on stack rightmost one first
    subu    $sp,        $sp,        8   # save args on stack
    sw      $s2,        8($sp)          # save depth
    sw      $s1,        4($sp)          # save xarr[i]

    li      $v0,        1
    move    $a0,        $s1             # print_int(xarr[i])
    syscall 

    li      $v0,        4               # print " -> "
    la      $a0,        arrow
    syscall 

    jal     collatz                     # result = collatz(xarr[i])

    move    $a0,        $v0             # print_int(result)
    li      $v0,        1
    syscall 

    li      $a0,        10              # print_char('\n')
    li      $v0,        11
    syscall 

    addu    $s0,        $s0,        4   # make s0 point to the next element

    lw      $s2,        8($sp)          # save depth
    lw      $s1,        4($sp)          # save xarr[i]
    addu    $sp,        $sp,        8   # save args on stack
    j       main_for

main_end:
    lw      $s0,        12($sp)         # push $s0
    lw      $s1,        8($sp)          # push $s1
    lw      $s2,        4($sp)          # push $s2

# EPILOGUE
    move    $sp,        $fp             # restore $sp
    lw      $ra,        ($fp)           # restore saved $ra
    lw      $fp,        -4($sp)         # restore saved $fp
    jr      $ra                         # return to kernel

This was my expected output:

2 -> 1
4 -> 2
6 -> 8
8 -> 3
10 -> 6

This is my latest implementation of the function:

# collatz function in MIPS Assembly
# Assumes n is in $a0 and d is in $a1
# Returns the result in $v0

    .text
    .globl collatz
collatz:
    addi    $sp, $sp, -12    # Allocate stack space for local variables and return address
    sw      $ra, 8($sp)      # Save return address
    sw      $a0, 4($sp)      # Save n
    sw      $a1, 0($sp)      # Save d

    # Check if n is 1 (base case)
    li      $t0, 1
    beq     $a0, $t0, base_case

    # Check if n is even or odd
    andi    $t1, $a0, 1      # t1 = n % 2
    beqz    $t1, even_case

    # Odd case: 3n + 1
    li      $t2, 3
    mul     $t2, $a0, $t2    # t2 = 3 * n
    addi    $t2, $t2, 1      # t2 = 3 * n + 1

    j       recursive_call

even_case:
    # Even case: n / 2
    srl     $t2, $a0, 1      # t2 = n / 2

recursive_call:
    # Prepare arguments for recursive call
    lw      $a0, 4($sp)      # Restore n
    lw      $a1, 0($sp)      # Restore d
    addi    $a1, $a1, 1      # Increment d

    move    $a0, $t2         # Update n
    jal     collatz          # Recursive call

    # Returning from recursive call
    j       end_function

base_case:
    # Base case: n is 1, return d
    lw      $v0, 0($sp)      # Load d into return value register $v0

end_function:
    lw      $ra, 8($sp)      # Restore return address
    addi    $sp, $sp, 12     # Deallocate stack space
    jr      $ra              # Return to caller

This is the output I'm getting:

2 -> 2147476133
4 -> 2147476262
6 -> 2147476391
8 -> 2147476520
10 -> 2147476649

Other outputs I have been getting from previous versions I have written for this function include a large integer like the one above except its the same number for all inputs. I have also gotten outputs of all 0. I have also gotten arithmetic overflow errors.

Answer 1

You're not passing parameters from main to collatz properly.  The value in $a0, the first parameter register, is a reference to the string "->", hardly what you want.

To illustrate:

li      $v0,        4               # print " -> "
la      $a0,        arrow
syscall 

jal     collatz                     # result = collatz(xarr[i])

The last value put in $a0 is arrow, not xarr[i].  You need to be careful of $a0 and $v0 and some others when inserting syscalls for printing output in the middle of your code.  Worse even, if using other like printf (not available on MARS/QtSpim) because these are less friendly to preserving registers than syscalls.

---

Let's also note that you're assuming collatz to be called with one parameter in usage as follows:

jal     collatz                     # result = collatz(xarr[i])

However, it is declared as

# collatz function in MIPS Assembly
# Assumes n is in $a0 and d is in $a1
# Returns the result in $v0

and in C, uint32_t collatz(uint32_t n, int d);

In summary, that code is passing a string address for n and nothing for d.  Fix those and things should get better.

---

Otherwise, your code looks mostly right but has a lot of unnecessary transfers to/from the stack.  For the most part, could have used more values from the registers.

---

Single step debugging will highlight the main to collatz parameter passing problem.  During single stepping, check each instruction for its own correctness, but also, at the beginning of a function call and at function return, these are good points to check larger program state validity, such as parameters, return values, and expectations on call-preserved registers.  Most instructions only involve modification of one register or memory location, but some, like syscalls and function calls may have more side effects, so at their transitions are good points to do additional verification.