assembly - MIPS recursion: How to compute end result from stack -
my task implement egyptian multiplication in mips assembler recursively. think understood of relevant stuff, can't behind 1 thing: how end result computed? example in code(taken this question):
# int fact(int n) fact: subu sp, sp, 32 # allocate 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) stack lw v0, 0(fp) # load n v0 bgtz v0, l2 # if n > 0 jump rest of function li v0, 1 # n==1, return 1 j l1 # jump frame clean-up code l2: lw v1, 0(fp) # load n v1 subu v0, v1, 1 # compute n-1 move a0, v0 # move n-1 first argument jal fact # recursive call lw v1, 0(fp) # load n v1 mul v0, v0, v1 # compute fact(n-1) * n #result in v0, clean stack , 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 2 lines between
jal fact and
l2 ever reached? in understanding, either l1/l2 branched to, or fact called recursively...
/edit:
ok, seems figured out how implement recursively in mips. however, have 1 last problem: code below, program lacks 1 "turn", meaning last value isn't considered when computing final result.
pharao: li $t0, 2 #load imm division 2 lw $a0, fac_1 #load fac_1 $a0 lw $a1, fac_2 #load fac_2 $a1 li $t7, 0 #zero $t7 li $t6, 1 #load 1 $t6 jal egypt #jump egypt j end egypt: subiu $sp,$sp,16 #space on stack 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 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 2 mflo $a0 beq $a1, $t6, return #base case jal egypt #call egypt recursively addingup: lw $a0, 4($sp) #load values stack lw $a1, 8($sp) # " lw $a2, 12($sp) # " beqz $a2, return #jump on if remainder 0 addu $t7, $t7, $a0 #add if remainder 1 return: lw $ra, 0($sp) #restore return address addiu $sp, $sp, 16 #inc stackpointer jr $ra when try running program values 10 , 20, result (in $t7) 40, because last value, 160, isn't added. how can fix this?
thanks!
jal instruction jump , link, means stores next instruction's address in r31 , jumps label given. it's (one/the) way subroutine calls in mips assembler.
the jr $ra jumps address contained in r31, means returns instruction following jal. can see, that's done before .end.
in short, jal subroutine call, , when call returns, execute instructions following jal.
in edited question, check base case bit strangely, like;
a = n >> 1; b = n & 1; if(a == 0) return 0; ...do calculation... ...when better base case be;
if(n == 0) return 0; = n >> 1; b = n & 1; ...do calculation... the problem first base case b can still 1 , give result, return anyway without using value.
Comments
Post a Comment