Department of Electrical and Computer Engineering

The University of Texas at Austin

EE 306, Fall 2009
Programming Assignment 3
Due: 8 November, 11:59 pm
Yale N. Patt, Instructor
TAs: Aater Suleman, Chang Joo Lee, Ameya Chaudhari, Antonius Keddis, Arvind Chandrababu, Bhargavi Narayanasetty, Eshar Ben-dor, Faruk Guvenilir, Marc Kellermann, RJ Harden

You must do the programming assignment by yourself. You are permitted to get help from ONLY the TAs and the instructor. The file you submit should be an assembly language file called directory.asm. This is the only file you need to submit.

Office Directory

Overview: You will design the user-interface of an office directory for the ENS building. Your program will prompt the user for a professor's last name and print the room number of that professor's office (only if it exists in the directory). For example, since Prof. Patt's office is located in room 541A, if the user types 'patt' at the prompt, your program will print 541A.

Your job: Write a program in LC-3 assembly language that will (1) prompt the user to type a professor's last name, (2) search the directory to find the room number of the professor's office, (3) print the room number of professor's office on the screen, and (4) halt the machine.

We now discuss each step in turn.

  1. Prompting for Last name: Your program will print on the screen the string "Type a last name and press Enter:" and wait for the user to input a string (followed by an <Enter>). Once the user has pressed the <Enter> key, your program will search the directory for the entered last name.
  2. Searching the directory: The directory stores for each professor the room number of his or her office. You will find a match for the last name if and only if the last name exists in the directory. Note that it is possible to not find a match in the directory.

    The directory is organized as a data-structure called a linked-list. The working of the linked-list is described below. The address of the first node of the directory is stored in memory location x3300 before the program is run.

  3. Printing the room number: If your program does not find a match for a last name in the directory, your program must EXACTLY print the string "No Entry" on the screen. If your program finds a match in the directory, your program will print the string containing the room number.
  4. Halting the machine: The machine halts after printing the room number or "No Entry."

The Linked-List

A linked-list consists of nodes which are linked with each other via pointers. Each node in a linked-list contains a pointer to the next node. This pointer is commanly known as the next-pointer. All nodes have a valid next-pointer except the last node. The last node is unique as it does not have a next node and its next-pointer is set to a NULL pointer (the value x0000).

Each node in a linked-list is comprised of k+1 words: one word containing the next-pointer (the pointer to the next node) and k words of data which are being stored by the node.

The directory of room numbers is implemented as a linked-list. Each node consists of three words in the following order:

1. The next-pointer.

2. A pointer to an ASCII string representing the professor's last name (in lower case).

3. A pointer to an ASCII string representing the room number of the professor's office.

Recall that a string consists of ASCII codes stored in consecutive memory locations, one ASCII code per location. The string is null-terminated, i.e., the end of a string is signified by the NULL character which is ASCII code 0.

Below we show an example directory implemented as a linked-list. This directory contains two nodes: the room numbers of professors patt (room 541A) and le (room 306).

Address Contents Description
x3300 x4000 Pointer to the first node
... ...
x4000 x4100 Next-pointer
x4001 x4025 Pointer to the first ASCII code of the last name
x4002 x4050 Pointer to the first ASCII code of the office location
... ...
x4025 x0070 ASCII code for "p"
x4026 x0061 ASCII code for "a"
x4027 x0074 ASCII code for "t"
x4028 x0074 ASCII code for "t"
x4029 x0000 NULL character which signifies the end of the last name
... ...
x4050 x0035 ASCII code for "5"
x4051 x0034 ASCII code for "4"
x4052 x0031 ASCII code for "1"
x4053 x0041 ASCII code for "A"
x4054 x0000 NULL character which signifies the end of the office location
... ...
x4100 x0000 Next-pointer, x0000 means there is no next node
x4101 x4200 Pointer to the first ASCII code of the last name
x4102 x4300 Pointer to the first ASCII code of the office location
... ...
x4200 x006c ASCII code for "l"
x4201 x0065 ASCII code for "e"
x4202 x0000 NULL character which signifies the end of the last name
... ...
x4300 x0033 ASCII code for "3"
x4301 x0030 ASCII code for "0"
x4302 x0036 ASCII code for "6"
x4304 x0000 NULL character which signifies the end of the office location
... ...

Below is a graphical representation of the linked-list.

To search the linked-list, your program will visit each node of the list and compare the last name stored at that node with the last name entered by the user. If a match is found, it will print the room number of the professor's office and terminate the search. If a match is not found, it will visit the next node and repeat the above process. It will continue to visit nodes until either a match is found or it reaches the last node (i.e., a node whose next pointer the next node is 0). Thus, if it reaches the last node, it implies that a match was not found.


Input/Output Requirements

Described below are detailed requirements about the Inputs and Outputs of your program. You should adhere to these guidelines to receive full credit for this assignment

Input:

Your program should prompt the user for the last name from the keyboard, as follows:

Hint: To continually read from the keyboard without first printing a prompt on the screen, use TRAP x20 (assembler name GETC). That is, for each key you wish to read, the LC-3 operating system must execute the TRAP x20 service routine. If you follow TRAP x20 with the instruction TRAP x21 (assembler name OUT), the character the user types will be displayed on the screen.

Output:

Your program should output one of two strings depending on the outcome of the directory lookup.


Hint: To output a string to the console display, use TRAP x22 (assembler name PUTS). What needs to go into R0 in order to use this TRAP instruction?

A sample of what your program will produce, when supplied with the input from users trying to look up a professor's office location, is shown below:

Type a last name and press Enter:patt
541A
----- Halting the processor -----
Type a last name and press Enter:suleman
No Entry
----- Halting the processor -----
Type a last name and press Enter:le
306
----- Halting the processor -----

Notes

  1. Your program must start at location x3000.
  2. The linked-list representing the directory is an input to your program. The directory is loaded in memory before your program begins to run. Your program will only search the directory, not modify it. You will lose points if you modify the directory.
  3. The pointer to the first node is stored in memory location x3300 before the program execution begins. Further, assume that all the nodes are stored between memory locations x4000 and xEFFF. Make no other assumptions about the location of the nodes. Note that the pointer to the first node may be set to NULL, indicating that there are no nodes in the list.
  4. Your program should NOT make any assumptions about the number of nodes in the list.
  5. The <Enter> key is the carriage return line feed which is the ASCII code x0D x0A .
  6. You can assume that the directory never contains two nodes with the same last name.


Submit your Program: The program you are to submit is the .asm file. Save your .asm file, and give it the name directory.asm. Follow the submission instructions for uploading your directory.asm file for grading.