BINARY SEARCH IN MIPS ASSEMBLY Hi guys, i need some assistance with implementing
ID: 672748 • Letter: B
Question
BINARY SEARCH IN MIPS ASSEMBLY
Hi guys, i need some assistance with implementing a binary search on an array (Case 5 of my program). I have tried to write the code, but it keeps telling me bad address when I run this choice. Can someone please tell me what the problem can be and how to correctly implement a binary search in mips assembly. Here is my code:
###################################################################
# Program Name: Menu to either sort and or print array ints
# Programer: Babatunde Olaoye
###################################################################
# Pseudocode description of algorithm
# main:
# int array[20], i = 0;
# bool swap;
# cout << "1.)Insert numbers in array at most 20 ";
# cout << "2.)Sort the array ";
# cout << "3.)Print sorted array ";
# cout << "4.)Print unsorted array ";
# cout << "5.)Exit ";
# cin >> choice;
# if (choice 1)
# {
# while (i > 0 && i <= 20)
# {
# cin>> array[i];
# i++;
# }
# }
# if (choice 2){
# do{
# swap = false
# for(int i = 0; i < SIZE -1; i++){
# if (array[i] > array[i+1]){
# temp = array[i];
# array[i] = array[i+1];
# array[i+1] = temp;
# swap = true;
#
# }
# else{
# swap = false;
# i++;
# }}
# while(swap);
# }
# if (choice = 3){
# for (i =0; i < 20; i++)
# {
# cout<< sorted array;
# }}
# if (choice = 4){
# for (i =0; i < 20; i++)
# {
# cout<< unsorted array;
# }}
# if (choice = 5){
# exit(0);}
# return 0;
#
###################################################################
###################################################################
.data
.align 2
jumptable: .word top, case1, case2, case3, case4, case5, case6
Array: .space 80 #array for unsorted
Array1: .space 80 #array for sorted
menu: .ascii " 1.) Insert numbers in array (at most 20) "
.ascii "2.) SORT THE ARRAY "
.ascii "3.) PRINT THE SORTED ARRAY "
.ascii "4.) PRINT THE UNSORTED ARRAY "
.ascii "5.) SEARCH ARRAY FOR INTEGER "
.asciiz "6.) Exit "
insert: .asciiz " Please insert 20 numbers into the array "
unsorted: .asciiz " YOUR OUTPUT UNSORTED ARRAY IS: "
sorted: .asciiz " YOUR OUTPUT SORTED ARRAY IS: "
look: .asciiz " PLEASE ENTER AN INTEGER TO SEARCH FOR: "
found: .asciiz " INTEGER FOUND AT POSITION: "
blank: .asciiz " "
##############################################################################
.globl main
.text
main:
top:
li $t3, 20 #SIZE max
li $v0, 4 #Prompt to display menu
la $a0, menu
syscall
li $v0, 5 #Reads menu choice
syscall
blez $v0, top #go back to menu if choice is less than or equal zero
bgt $v0, 6, top #go back to menu if choice is greater than 5
la $a1, jumptable #read address for jumptable
sll $t0, $v0, 2 #word offset
add $t1, $a1, $t0 #pointer to jumptable
lw $t2, 0($t1) #load an address from jumptable
jr $t2 #jump to specified case
##############################################################################
case1:
li $t9, 0 #counter for loop display
li $t8, 0 #counter for loop display constant
li $s4, 0
la $t5, Array #address of array stored in t5
la $t6, Array1 #address of array1 stored in t6
li $v0, 4 #Prompt to display insert string
la $a0, insert
syscall
while:
li $v0, 5 #Get integer
syscall
beq $v0, -1, top #stop reading integers and go back to menu
sw $v0, ($t5) #array[i] = v0
sw $v0, ($t6) #array1[i] = v0
addi $t5, $t5, 4 #Shift by a word to make space for next input
addi $t6, $t6, 4 #Shift by a word to make space for next input
addi $t3, $t3, -1 #decrement space allowed
addi $t9, $t9, 4 #increment for loop display counter
addi $t8, $t8, 4
addi $s4, $s4, 4
bgtz $t3, while #if not max keep looping
##############################################################################
case2:
swap:
la $t4, Array1 #loads array to $t4
la $t1, Array1 #loads array to $t1
addi $t1,$t1,4 #add 4 to $t1, save to $t1
la $t0,Array1 #loads array to $t8
add $t0,$t8,$t0 #add $t8 to $t0, save to $t8
la $t5,Array1
add $t5,$t8,$t5 #add $t9 to $t0, save to $t9
addi $t5,$t5,-4 #subtracts 4 from $t9, save to $t9
loop:
lw $t2,($t4) #load input into $t2
lw $t3,($t1) #load input into $t3
blt $t2,$t3,loop1 #if $t2 < $t3, go to loops
sw $t3,($t4) #store $t3 in $t4
sw $t2,($t1) #store $t2 in $t1
loop1:
addi $t1,$t1,4 #add 4 to $t1, save to $t1
blt $t1,$t0,loop #if $t1<$t8, go to loop
addi $t4,$t4,4 #add 4 to $t4, save to $t4
move $t1,$t4
addi $t1,$t1,4 #add 4 to $t1, save to $t1
blt $t4,$t5,loop #if $t4<$t9, to go loop
b top
##############################################################################
case3:
print1:
la $a1,Array1 #loads array to $a1
li $v0, 4 #Prompt to display insert string
la, $a0, sorted
syscall
loop2:
blez $t8, done #if $t0<=0, go to done
li $v0, 1 #loads 1 into $v0
lw $a0, 0($a1) #load an inout into $a0
syscall
la $a0, blank #loads blank into $a0
li $v0, 4 #loads 4 into $v0
syscall
addi $a1, $a1, 4 #add 4 to $a1, save to $a1
addi $t8, $t8, -4 #subtracts 4 from #t0, save to $t0
j loop2
done:
add $t8, $s4, $0
b top #when counter is equal to 0 then go back to menu
##############################################################################
case4:
li $v0, 4 #Prompt to display insert string
la, $a0, unsorted
syscall
la $a3, Array #load base address of Array into $a3
print:
li $v0, 1 #get integer from output and put it into Array[i]
lw $a0, 0($a3)
syscall
li $v0, 4 #put spaces in between each integer when printed
la $a0, blank
syscall
addi $a3, $a3, 4 #adds 4 to go to next pos in Array
addi $t9, $t9, -4 #decrement loop counter
bgtz $t9, print #loop print while t9 i greater than 0
add $t9, $t8, $0 #reinitialize counter
b top #go back to menu when count is equal to 0
###############################################################################
case5:
li $v0, 4 #Prompt to display insert string
la, $a0, look
syscall
li $v0, 5 #get key
syscall
la $a3, Array1 #load base address of Array1 into $a3
sub $t9, $t9, 4 #Size = size-1
li $a1, 0 #a1 left postition
li $a2, 0
li $s2, 2
add $a2, $a2, $t9 #a2 right position
search:
add $t3, $a1, $a2 #calculate mid t3
div $t3, $s2 #mid = left+right/2
mfhi $t3 #ceiling of div
add $a3, $t3, 0
lw $s1, 0($a3) #put the value of mid in s1
beq $s1, $v0, foundit #if array1[mid] == key go to found
bgt $s1, $v0, left #if array1[mid] > key search left side of array
right:
addi $a2, $t3, -4 #right = mid -1
b search #go back to search
left:
addi $a1, $t3, 4 #left = mid +1
b search #go back to search
foundit:
li $v0, 4 #display found string
la $a0, found
syscall
li $v0, 1 #print out the position the key was found
move $a0, $t3
syscall
b top #go back to the menu
##############################################################################
case6:
li $v0, 10 #Exit program
syscall
Explanation / Answer
# Program 2: Bianry Search Tree in MIPS
.data
buffer: .space 4
space: .asciiz " "
println: .asciiz " "
i: .asciiz " is the number we want to insert. "
p: .asciiz "Print something "
d: .asciiz " is the number we want to delete. "
q: .asciiz "Quit "
CMD: .asciiz "Input command (I,P,D,Q,O): "
input: .asciiz "Input inputeger: "
result: .asciiz "The result is: "
error: .asciiz "Please input a valid command. "
.text
main:
li $s2, 0 # $s2 = the sentinel value.
move $a0, $s2 # value = $s2
li $a1, 0 # left = NULL
li $a2, 0 # right = NULL
jal node_create # call node_create
move $s0, $v0 # and put the result inpu to $s0.
input_loop:
li $v0, 4
la $a0, CMD
syscall
li $v0, 8
la $a0, buffer
li $a1, 4
syscall
lb $t1, 0($a0)
li $t3, 'O'
li $t4, 'D'
li $t5, 'I'
li $t6, 'P'
li $t7, 'Q'
beq $t1, $t4, input_integer
beq $t1, $t5, input_integer
beq $t1, $t6, print_input
beq $t1, $t3, print_input
beq $t1, $t7, exit
b err
input_integer:
li $v0, 4
la $a0, input
syscall
li $v0, 5
syscall
move $t2, $v0
beq $t1, $t4, delete
beq $t1, $t5, insert
delete:
li $v0, 1
move $a0, $t2
syscall
li $v0, 4
la $a0, d
syscall
#delete
b input_loop
insert:
# li $v0, 5 # read the input integer
# syscall
move $s1, $t2 # set $s1 as the integer inserted
# beq $s1, $s2, end_input # if $s2 is equal to $s1 then break the loop
# tree_insert (number, root);
move $a0, $s1 # number= $s1
move $a1, $s0 # root = $s0
jal tree_insert # call tree_insert.
b input_loop # repeat the input_loop.
err:
li $v0, 4
la $a0, error
syscall
b input_loop
print_input:
## Step 3: print out the left and right subtrees.
lw $a0, 4($s0) # print out the roots of the left child.
jal tree_print_input
lw $a0, 8($s0) # print out the roots of the right child.
jal tree_print_input
b input_loop # exit.
## end of main.
b input_loop
node_create:
# set up the stack:
subu $sp, $sp, 32
sw $ra, 28($sp)
sw $fp, 24($sp)
sw $s0, 20($sp)
sw $s1, 16($sp)
sw $s2, 12($sp)
sw $s3, 8($sp)
addu $fp, $sp, 32
# capture the parameters:
move $s0, $a0 # $s0 = value
move $s1, $a1 # $s1 = left
move $s2, $a2 # $s2 = right
li $a0, 12 # it needs 12 bytes for a new node.
li $v0, 9 # sbrk is syscall 9.
syscall
move $s3, $v0
beqz $s3, ERRORMEM
sw $s0, 0($s3) # node->number = number
sw $s1, 4($s3) # node->left = left
sw $s2, 8($s3) # node->right = right
move $v0, $s3 # put return value input into v0.
# release the stack frame:
lw $ra, 28($sp) # restore the Return Address.
lw $fp, 24($sp) # restore the Frame Poinputer.
lw $s0, 20($sp) # restore $s0.
lw $s1, 16($sp) # restore $s1.
lw $s2, 12($sp) # restore $s2.
lw $s3, 8($sp) # restore $s3.
addu $sp, $sp, 32 # restore the Stack Poinputer.
jr $ra # return.
## end of node_create.
## tree_insert (value, root): make a new node with the given value
## Register usage:
## $s0 - value
## $s1 - root node
## $s2 - a new node
## $s3 - a pointer for the root to the assigned value (root_value)
## $s4 - temporary pointer
tree_insert: # set up the stack frame:
subu $sp, $sp, 32
sw $ra, 28($sp)
sw $fp, 24($sp)
sw $s0, 20($sp)
sw $s1, 16($sp)
sw $s2, 12($sp)
sw $s3, 8($sp)
sw $s3, 4($sp)
addu $fp, $sp, 32
# grab the parameters:
move $s0, $a0 # $s0 = value
move $s1, $a1 # $s1 = root
# make a new node:
# new_node = node_create (value, 0, 0);
move $a0, $s0 # value = $s0
li $a1, 0 # left = 0
li $a2, 0 # right = 0
jal node_create # call node_create
move $s2, $v0 # save the result.
SLOOP:
lw $s3, 0($s1) # root_value = root->value;
ble $s0, $s3, SLEFT # if (valueue <= s3) goto SLEFT;
b SRIGHT # goto SRIGHT;
SLEFT:
lw $s4, 4($s1) # ptr = root->left;
beqz $s4, add_left # if (ptr == 0) goto add_left;
move $s1, $s4 # root = ptr;
b SLOOP # goto SLOOP;
add_left:
sw $s2, 4($s1) # root->left = new_node;
b end_SLOOP # goto end_SLOOP;
SRIGHT:
lw $s4, 8($s1) # ptr = root->right;
beqz $s4, add_right # if (ptr == 0) goto add_right;
move $s1, $s4 # root = ptr;
b SLOOP # goto SLOOP;
add_right:
sw $s2, 8($s1) # root->right = new_node;
b end_SLOOP # goto end_SLOOP;
end_SLOOP:
# release the stack frame:
lw $ra, 28($sp) # restore the Return Address.
lw $fp, 24($sp) # restore the Frame Pointers.
lw $s0, 20($sp) # restore $s0.
lw $s1, 16($sp) # restore $s1.
lw $s2, 12($sp) # restore $s2.
lw $s3, 8($sp) # restore $s3.
lw $s4, 4($sp) # restore $s4.
addu $sp, $sp, 32 # restore the Stack Pointers.
jr $ra # return.
## end of node_create.
## Do an inorder traversal of the tree, printing out each value.
## Register usage:
## s0 - the tree.
tree_print_input:
# set up the stack frame:
subu $sp, $sp, 32
sw $ra, 28($sp)
sw $fp, 24($sp)
sw $s0, 20($sp)
addu $fp, $sp, 32
# grab the parameter:
move $s0, $a0 # $s0 = tree
beqz $s0, tree_print_input_end # if tree == NULL, then return.
lw $a0, 4($s0) # recurse left.
jal tree_print_input
# prinput the value of the node:
lw $a0, 0($s0) # prinput the value, and
li $v0, 1
syscall
la $a0, println # also prinput a println.
li $v0, 4
syscall
lw $a0, 8($s0) # recurse right.
jal tree_print_input
tree_print_input_end: # clean up and return:
lw $ra, 28($sp) # restore the Return Address.
lw $fp, 24($sp) # restore the Frame Poinputer.
lw $s0, 20($sp) # restore $s0.
addu $sp, $sp, 32 # restore the Stack Poinputer.
jr $ra # return.
## end of tree_print_input.
tree_print_input2:
# set up the stack frame:
subu $sp, $sp, 32
sw $ra, 28($sp)
sw $fp, 24($sp)
sw $s0, 20($sp)
addu $fp, $sp, 32
# grab the parameter:
move $s0, $a0 # $s0 = tree
beqz $s0, tree_print_input_end # if tree == NULL, then return, if not conintue.
lw $a0, 8($s0) # recurse to the left of the tree.
jal tree_print_input2
# prinput the value of the node:
lw $a0, 0($s0) # prinput the value, and
li $v0, 1
syscall
la $a0, println # also prinput a println.
li $v0, 4
syscall
lw $a0, 4($s0) # recurse to the right of the tree.
jal tree_print_input2
tree_print_input_end2: # clean up and return:
lw $ra, 28($sp) # restore the Return Address.
lw $fp, 24($sp) # restore the Frame Pointer.
lw $s0, 20($sp) # restore $s0.
addu $sp, $sp, 32 # restore the Stack Pointer.
jr $ra
# end of tree_print_input.
# The routine to call when sbrk fails; It will jump to exit the program.
ERRORMEM:
la $a0, ERRORMEM_MSG
li $v0, 4
syscall
j exit
## The routine to call to exit the program.
exit:
li $v0, 10
syscall
## exit the program
## Here is where the data for this program is stored:
.data
ERRORMEM_MSG: .asciiz "Out of memory! "
## end of BinarySearchTree.asm
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.