This program tests the function search(), which searches for an entry in an array. It illustrates subprograms, random access in arrays
The search_1.s program can be viewed as a text file by clicking here. After the file appears in a new tab or window it can be saved using your browser's file menu.
# This program tests the function search(), which searches for an
# entry in an array.
#
.globl main
.data
# Main program string constants
#
dataValueStr: .asciiz "Data value "
foundAtStr: .asciiz " found at index "
notFoundStr: .asciiz " not found"
endlineStr: .byte '.'
newlineStr: .asciiz "\n"
.text
# Main program.
#
# This program searches a dynamically allocated test array for
# data values from 0 to 20 and displays the search results.
#
# Register usage:
#
# $s0 - data value to be found (variable data)
# $s1 - index where it is found (variable index)
# $s2 - constant 20
# $s3 - base address of the test array
#
main:
jal createArray # create the test array
move $s3, $v0
li $s0, 0 # search for values from 0 to 20
li $s2, 20
b condTest
loop:
move $a0, $s3 # index = search(A, 10, data)
li $a1, 10
move $a2, $s0
jal search
move $s1, $v0
li $v0, 4 # print "Data value "
la $a0, dataValueStr
syscall
li $v0, 1 # print data as decimal digit string
move $a0, $s0
syscall
beq $s1, -1, notFound # if index is -1 print not found
li $v0, 4 # else print " found at index "
la $a0, foundAtStr
syscall
li $v0, 1 # and print index as decimal digit string
move $a0, $s1
syscall
b endLine
notFound:
li $v0, 4 # print " not found"
la $a0, notFoundStr
syscall
endLine:
li $v0, 4 # print ".\n"
la $a0, endlineStr
syscall
add $s0, $s0, 1 # increment data
condTest:
ble $s0, $s2, loop # continue loop if data <= 20
li $v0, 4 # print "\n"
la $a0, newlineStr
syscall
li $v0, 10 # terminate the program
syscall
# function createArray
#
# C synopsis:
#
# int[] createArray()
#
# Typical C call:
#
# A = createArray();
#
# Effect:
#
# Puts the address of a dynamically allocated array into A.
# The array has 10 entries.
# The values are the odd numbers from 1 to 19.
#
# MAL call sequence:
#
# jal createArray
# sw $v0, A
#
# Local variables:
#
# $t0 (addr) - entry address
# $t1 (val) - entry value
#
createArray:
li $v0, 9 # allocate an array with space for 10 ints
li $a0, 40
syscall
move $t0, $v0 # addr = array base address
li $t1, 1 # val = 1
b create_cond_test
create_loop:
sw $t1, 0($t0) # *addr = val
add $t0, $t0, 4 # addr++
add $t1, $t1, 2 # val += 2
create_cond_test:
blt $t1, 20, create_loop # continue loop if val < 20
jr $ra # return (array base address is still in $v0)
# function search
#
# C synopsis:
#
# int search(int A[], int numEntries, int searchVal)
#
# Typical C call:
#
# ind = search(A, numEntries, searchVal);
#
# Effect:
#
# Puts the index in A of the entry with value searchVal into ind.
# Puts -1 into ind if there is no such entry.
#
# Preconditions:
#
# The entries of A are in ascending numerical order.
#
# MAL call sequence:
#
# la $a0, A
# lw $a1, numEntries
# lw $a2, searchVal
# jal search
# sw $v0, ind
#
# Local variables:
#
# $t0 (lo) lowest possible index for searchVal
# $t1 (hi) highest possible index for searchVal
# $t2 (mid) index halfway between lo and hi
# $t3 (midAddr) address of A[mid]
# $t4 (midVal) A[mid]
#
search:
li $t0, 0 # lo = 0
sub $t1, $a1, 1 # hi = numEntries - 1
b searchLoopTest
searchLoop:
move $t2, $t0 # mid = (lo + hi)/2
add $t0, $t0, $t1
div $t0, $t0, 2
mul $t3, $t2, 4 # midAddr = mid*4 + address of A
add $t3, $t3, $a0
lw $t4, ($t3) # midVal = M[midAddr]
blt $a2, $t4, searchLower # if searchVal < midVal then
# search lower half of array segment
bgt $a2, $t4, searchHigher # if searchVal > midVal then
# search upper half of array segment
move $v0, $t2 # else found searchVal; return mid
jr $ra
searchLower:
sub $t1, $t2, 1 # try again with hi = mid - 1
b searchLoopTest
searchHigher:
add $t0, $t2, 1 # try again with lo = mid + 1
searchLoopTest:
ble $t0, $t1, searchLoop # continue loop if lo <= hi
li $v0, -1 # search failed; return -1
jr $ra