Homework 5 (120 points; 60 points each part)
Implementing C's strcmp (using LC-3 assembly language and subroutines)
Due in two parts:
Part 1 due Friday, October 10, 2003 at 11:59 pm
Part 2 due Tuesday, October 14, 2003 at 11:59pm
Outcomes
After successfully completing this assignment, you will
be able to...
- Edit, assemble, debug, and execute a program written in LC-3 assembly
language that utilizes subroutines
- Add a new trap routine to the LC-3
- Write LC-3 code that does device-level I/O
- Simulate one of C's string-processing routines
Before Starting
Read Chapters 8 and 9.
Description of Problem
In this assignment you will implement the C string-processing function called
strcmp (string compare). strcmp compares two strings and
returns
- a negative integer if the first string is less than the
second string
- a zero if the two strings are equal
- a positive integer if the first string is greater than the second
string
The comparison is done lexicographically. When comparing two strings
lexicographically, there are three possibilities:
- the strings have the same length, and the characters in the two
strings are identical in every position (eg. "dog" == "dog")
- the strings have different lengths, and each character in the shorter
string is identical to the corresponding character in the longer string
(eg. "cat" < "catnip")
- the strings have same or different lengths, and, in doing a left-to-right
scan, at some position
the characters in the two strings differ. The order of the strings is
determined by the character at that position (eg. "black" < "block", and
"Hamilton" < "hamel")
strcmp assumes that each string terminates with an ASCII zero.
The only difference between your implementation of strcmp and C's
implementation is that you should assume the characters of the string
are stored one per word (in bits [0:7] of each word), rather than two per word,
as they are in C.
In addition to implementing strcmp, you will also implement a new
trap that allows the user program to input a string. That way, you
will be able to write a program that can easily test strcmp.
Design Requirements
You must implement the string input routine as a trap, and the
strcmp routine as a subroutine. Here are the requirements
for each:
- trap x30 This trap inputs a string from the keyboard.
The trap service routine expects register R0 to contain the address of the
buffer
that will hold the string. The routine accepts characters typed at
the keyboard, and stores them one character per word in the buffer. The
characters in the string are echoed as they are typed in. Use device-level
I/O to read and echo the characters.
Input is terminated when the user types the enter key. The enter
is not stored in the buffer, rather a terminating zero is stored instead.
The trap routine
returns the number of characters in the string (not counting the
terminating zero) in register R1.
The trap routine assumes that there is enough room in the buffer to hold
the entire string.
- strcmp This subroutine compares two strings lexicographically,
as described above. Upon entry to the subroutine, R0 contains the address
of the first string, and R1 contains the address of the second string.
strcmp returns its integer result in R2.
Design program in two parts
Part 1
Note: Pregrading will be available for hw5Part1 for assignments turned
in by 11:59pm on Tuesday, October 7. The pregrading will be done in lab
on Wednesday, October 8.
You will be developing this program in two parts. For Part 1, you
should get trap x30 working. You will need to write two files for Part 1. One of the files contains
your trap code (the string input routine). Name the file
trap30.asm. The trap service routine should begin at
location x0530.
The other file contains the user program that calls the trap. Name this file
hw5Part1.asm. hw5Part1.asm uses trap x30 to read two strings into two
different buffers (use 80 (decimal) as the maximum buffer length). The program will then use puts to display the two strings. Output for Part 1 should look like this:
Enter two strings terminated with newlines:
An apple sat on the railroad tracks, feeling blue and cross,
Around the bend came Number 10, toot, toot, applesauce!
Here are your two strings
An apple sat on the railroad tracks, feeling blue and cross,
Around the bend came Number 10, toot, toot, applesauce!
----- Halting the processor -----
Part 2
(I will provide a working version of Part 1 of this assignment once the
due date for Part 1 has passed.)
Name the user program for Part 2 hw5Part2.asm.
This program will start by doing the same thing as
Part 1 (read in two strings using trap x30 and output them using puts). Then it will call strcmp, which you should code as
a subroutine. Based on the output from
strcmp, your program should print out one of the following messages:
- First string is less than the second string
- First string equals the second string
- First string is greater than the second string
A sample output for Part 2 would look like this:
Enter two strings terminated with newlines:
hamel
Hamilton
Here are your two strings
hamel
Hamilton
First string is greater than the second string
----- Halting the processor -----
One last design restriction...the LC-3 Simulator does not provide the
capability to define a subroutine as .EXTERNAL,
but you should try to develop subroutines as self-contained units as
much as possible. There are two things you can do to help encapsulate
a subroutine -
the first is to put all
of the code and the data for a single subroutine together in contiguous
lines in the
source file, and the second is to make sure
that a subroutine does not access by name any labels defined in the
main program or in other subroutines. With a single copy and
paste you should be able to copy an entire subroutine from one
file to another, to be used by a different main program.
Documentation Guidelines
You will be using the LC3Edit program to create your assembly language
source file. Follow the same formatting and documentation guidelines
as you did for Homework 4. In addition, subroutines should come with their
own documentation. Each subroutine should be clearly separated from the
main program and
from other subroutines by comment lines, such as this:
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; subroutine strcmp
;;
You should also include as part of the documentation of each subroutine
a brief description of the purpose of the subroutine, and a list of
the inputs to and the outputs from the subroutine.
Deliverables
You must use turnin
to submit your LC-3 source files.
Here are the Unix commands you should use to submit your files:
for Part 1 (due Oct 10):
/cs/bin/turnin submit cs2011 hw5Part1 hw5Part1.asm trap30.asm
for Part 2 (due Oct 14):
/cs/bin/turnin submit cs2011 hw5Part2 hw5Part2.asm trap30.asm