Question

How can I convert the following subroutine into MIPS assembly:

search(Array, start, end, searchValue)

{

if (start > end) return false

mid = start + (end - start)/2;

if (array[mid] == searchValue) return true;

if (array[mid] > searchValue) return search(array, start, mid-1, searchValue);

return search(array, mid+1, end, searchValue);

}

Answer 1

search(int*, int, int, int):
addiu $sp,$sp,-40
sw $31,36($sp)
sw $fp,32($sp)
move $fp,$sp
sw $4,40($fp)
sw $5,44($fp)
sw $6,48($fp)
sw $7,52($fp)
lw $3,44($fp)
lw $2,48($fp)
nop
slt $2,$2,$3
beq $2,$0,$L2
nop

move $2,$0
b $L3
nop

$L2:
lw $3,48($fp)
lw $2,44($fp)
nop
subu $2,$3,$2
srl $3,$2,31
addu $2,$3,$2
sra $2,$2,1
move $3,$2
lw $2,44($fp)
nop
addu $2,$3,$2
sw $2,24($fp)
lw $2,24($fp)
nop
sll $2,$2,2
lw $3,40($fp)
nop
addu $2,$3,$2
lw $3,0($2)
lw $2,52($fp)
nop
bne $3,$2,$L4
nop

li $2,1 # 0x1
b $L3
nop

$L4:
lw $2,24($fp)
nop
sll $2,$2,2
lw $3,40($fp)
nop
addu $2,$3,$2
lw $3,0($2)
lw $2,52($fp)
nop
slt $2,$2,$3
beq $2,$0,$L5
nop

lw $2,24($fp)
nop
addiu $2,$2,-1
lw $7,52($fp)
move $6,$2
lw $5,44($fp)
lw $4,40($fp)
jal search(int*, int, int, int)
nop

b $L3
nop

$L5:
lw $2,24($fp)
nop
addiu $2,$2,1
lw $7,52($fp)
lw $6,48($fp)
move $5,$2
lw $4,40($fp)
jal search(int*, int, int, int)
nop

$L3:
move $sp,$fp
lw $31,36($sp)
lw $fp,32($sp)
addiu $sp,$sp,40
j $31
nop