MIPS recursion: How to compute end result from stack

My task is to implement egyptian multiplication in MIPS assembler recursively. I think I understood most of the relevant stuff, but I just can't get behind one thing: How is the end result computed? For example in this code(taken from this question):

# int fact(int n)
fact:
subu    sp, sp, 32  # Allocate a 32-byte stack frame
sw  ra, 20(sp)  # Save Return Address
sw  fp, 16(sp)  # Save old frame pointer
addiu   fp, sp, 28  # Setup new frame pointer
sw  a0,  0(fp)  # Save argument (n) to stack

lw  v0, 0(fp)   # Load n into v0
bgtz    v0, L2      # if n > 0 jump to rest of the function
li  v0, 1       # n==1, return 1
j   L1      # jump to frame clean-up code

L2:
lw  v1, 0(fp)   # Load n into v1
subu    v0, v1, 1   # Compute n-1
move    a0, v0      # Move n-1 into first argument
jal fact        # Recursive call

lw  v1, 0(fp)   # Load n into v1
mul v0, v0, v1  # Compute fact(n-1) * n

#Result is in v0, so clean up the stack and return
L1:
lw  ra, 20(sp)  # Restore return address
lw  fp, 16(sp)  # Restore frame pointer
addiu   sp, sp, 32  # Pop stack
jr  ra      # return
.end    fact

How/ when are the two lines between

jal fact

and

L2

ever reached? In my understanding, either L1/L2 are branched to, or fact is called recursively...


/Edit:

Ok, it seems that I figured out how to implement something recursively in MIPS. However, I have one last problem: With the code below, my program lacks one "turn", meaning that the last value isn't considered when computing the final result.

pharao:
    li $t0, 2       #load imm for division by 2
    lw $a0, fac_1       #load fac_1 into $a0
    lw $a1, fac_2       #load fac_2 into $a1
    li $t7, 0       #zero $t7
    li $t6, 1       #load 1 into $t6

    jal egypt       #jump to egypt
    j end




egypt:      
    subiu $sp,$sp,16    #space on stack for 4 values
    sw $ra,0($sp)       #store return address
    sw $a0, 4($sp)      #store fac_1
    sw $a1, 8($sp)      #store fac_2
    divu $a1, $t0       #div fac_2 by 2
    mflo $a1        #store quotient in $a1
    mfhi $a2        #store remainder in $a2
    sw $a2, 12($sp)     #store remainder on stack


    multu $a0, $t0      #multiply fac_1 by 2
    mflo $a0

    beq $a1, $t6, return    #base case

    jal egypt       #call egypt recursively

addingup:       
    lw $a0, 4($sp)      #load values from stack
    lw $a1, 8($sp)      #   "
    lw $a2, 12($sp)     #   "

    beqz $a2, return    #jump on if remainder is 0

    addu $t7, $t7, $a0  #add if remainder is 1      
return:     

    lw $ra, 0($sp)      #restore return address
    addiu $sp, $sp, 16  #inc stackpointer
    jr $ra

When I try running the program with the values 10 and 20, the result (in $t7) is 40, because the last value, 160, isn't added. How can I fix this?

Thanks!

Answers


jal is the instruction JUMP AND LINK, which means it stores the next instruction's address in r31 and jumps to the label given. You could say it's (one/the) way to do subroutine calls in MIPS assembler.

The jr $ra jumps to the address contained in r31, which means it returns to the instruction following jal. As you can see, that's done just before the .end.

In short, jal is a subroutine call, and when the call returns, it will execute the instructions following jal.

In your edited question, you check the base case a bit strangely, something like;

a = n >> 1;
b = n & 1;
if(a == 0)
   return 0;
...do calculation...

...when a much better base case would be;

if(n == 0)
   return 0;
a = n >> 1;
b = n & 1;
...do calculation...

The problem with the first base case is that b can still be 1 and give a result, but you return anyway without using the value.


Need Your Help

CORBA : how does client poll from server?

c++ qt notifications polling corba

I am a total newbie in CORBA. I have written a simple c++ CORBA CLIENT and a CORBA SERVER. I would like the client to ask a status from time to time from the server. However, I have no idea how to do

Repeat CXF request in case of error

java web-services cxf

I have an OSGi service which I have exposed with CXF as a simple web service and for which I have created a client which invokes its methods. The methods of this service accept as one of their argu...

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.