Subject Computer Science Assembly Language Programming

Question

The Program:
For this assignment, you will write a subroutine that performs a recursive binary search on an ordered array of 16 bit two's complement words. I have written all of the program for you except for the recursive binary search subroutine, which you must write.
This will copy the prog4.s file into the current working directory in your account. Since I have written much of the program for you, the files you should get are:
The program will prompt the user to enter an integer to search for. Output from the program will consist of either the logical position of the element in the array if found, or a "not found"
message if the element is not in the array.
binSearch.s Contains the recursive binary search subroutine, which you must write.

Subroutine Prototypes:
int getInput(char &buffer)
Action:
Reads input from the keyboard, validates that the input is a valid two's complement 16 bit integer, converts the input from ASCII to two's complement, and returns the converted integer. If the input entered is not valid, the V bit in the CCR is set, and the return value is undefined.
Load Point: $7000
int &binSearch(int key, int &low, int &hi)
Action:
Performs recursive binary search on the ordered array, and returns the address of the element in the array if it is found.
If the key is not in the array, then the subroutine sets the V bit in the CCR, and the return value is undefined.
Load Point: $8000

The "main" program (in prog4.s) does the following:
 Prints the title line.
 Prompts the user to enter an integer to search for.
 Calls getInput.
 Checks the CCR for valid input, and if V=1, then prints and error message and calls getInput until valid input is entered.
 Calls binSearch.
 If V=0, then the return value, which is the address of the found element, is used to determine the logical position of the element in the array, which is then printed.
 If V=1, then the program prints a "not found" message.

The datafile:
 Load Point: $6000
 The first word in the file is the number of elements in the array.
 following the count are the array elements, which are 16 bit two's complement integers.
Example:
ORG $6000
dc.w 10 *there are 10 elements in the array
dc.w 2,4,6,8,10,12,14,16,18,20
end
Note: The actual name of the data file is unimportant. Your program will be tested with a data file not available to you.

Sample Output:
Program #4, Main program by Alan Riggins
Enter the element to search for:
12
The element was found at position #6.
Program #4, Main program by Alan Riggins
Enter the element to search for:
15
The element was not found.

Recursive Binary Search Algorithm:
int &binSearch(int key, int &lo, int &hi) {
if(hi < lo)
return NOT_FOUND; //RETURN with V = 1
int mid = (lo+hi) / 2;
if(key == array[mid])
return mid;
else if(key < array[mid]) // go left
return binSearch(key, lo, mid-1); // left
else
return binSearch(key, mid+1, hi); // right
}

Additional Details:
 All code must obey structured programming principles.
 Registers may not be used to access parameters.
 All registers used in subroutines must be properly saved on the stack and restored on exit.
 The binSearch subroutine must be recursive.
 Subroutines may not use any storage allocation directives.
 Your program must load your binSearch subroutine at the addresses specified.
 Your program will be tested with an array not available to you.
 Your program must print the logical position of the array element if found. That is, if the element is located at array[0], then it is the first element in the array, and thus you will print
"The element is at position #1"
 Subroutines often use the CCR as a way to signal an error condition. When an error condition occurs, the V bit in the CCR is set to 1, and this serves as a flag to the calling program. This allows the programmer to do something that is impossible with many higher level languages--return two things from a function: the return value and the status. You can set the V bit
to 1 this way: move #2,CCR

Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

Recursive Binary Search In Assembly Language M68000

This is only a preview of the solution. Please use the purchase button to see the entire solution

Assisting Tutor

Related Homework Solutions

Get help from a qualified tutor
Live Chats