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.

Features

# 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