MIPS - Binary Search

[Dr.Fuzzy]

Παίδες λίγο βοήθεια στο παρακάτω πρόγραμμα assembly (MIPS) που υλοποιεί ένα αναδρομικό binary search σε sorted array. Μου επιστρέφει πάντα a στον $v0, ασχέτως τιμής που ψάχνω ($a0) και αδυνατώ να βρω τι πάει λάθος. Το τρέχω σε xspim.

 

> .data first: # sorted array of 32 bit words.word 2, 3, 8, 10, 16, 21, 35, 42, 43, 50#, 64, 69#.word 70, 77, 82, 83, 84, 90, 96, 99, 100, 105, 111, 120last: # address just after sorted array .text.globl mainmain: # binary search in sorted array#   input:  search value in $a0#    base address of array in $a1#    last address of array in $a2#   output: address of needle in $v0 if found,#    0 in $v0 otherwiseli $a0, 35 # search valuela $a1, first # address of first array entryla $a2, last - 4 # address of last array entryjal binsearch # perform binary search li $v0, 10syscall binsearch:subu $sp, $sp, 4 # allocate 4 bytes on stacksw $ra, 4($sp) # save return address on stack subu $t0, $a2, $a1 # $t0 <- size of arraybnez $t0, search # if size > 0, continue search move $v0, $a1 # address of only entry in arraylw $t0, ($v0) # load the entrybeq $a0, $t0, return # equal to needle value? yes => returnli $v0, 0 # no => needle not in arrayb return # done, returnsearch:sra $t0, $t0, 3 # compute offset of middle entry m:sll $t0, $t0, 2 # $t0 <- ($t0 / 8) * 4addu $v0, $a1, $t0 # compute address of middle entry mlw $t0, ($v0) # $t0 <- middle entry mbeq $a0, $t0, return # m = needle? yes => returnblt $a0, $t0, go_left # needle less than m? yes =># search continues left of mgo_right:addu $a1, $v0, 4 # search continues right of mjal   binsearch # recursive callb return # done, returngo_left:move $a2, $v0 # search continues left of mjal binsearch # recursive callreturn:lw $ra, 4($sp) # recover return address from stackaddu $sp, $sp, 4 # release 4 bytes on stack j $ra # return to caller