Essentials

Due:
Key: Use the key UTIL for checkin

Goals of Assignment

In this short assignment you will write some utility routines for the lc3 assembler. This assignment serves several purposes:

Learn about C structures (struct) and how to initialize structures at compile time.
Learn how to use C pointers and the address-of operator &
Learn how to use data strucutres for searching.
Build a module that will be resused in the assembler assignment.

Overview

In writing large projects, it is convenient to build utility routines that support the completion of the larger project. These utilities are in separate files so that they may be written and thorought tested independently of the project as a whole. Also, by splitting up the work, it can be spread over a team of programmers working in parallel. This assignment is an example of a set of utility routines for the assembler.

One of the taks required in the assembler is converting symbolic names that are used in an assembly language program to their underlying representation. For example the word "ADD" needs to be converted to the numeric code that the LC3 uses for the operation. Assemblers for other assembly lanuages will also have the name "ADD", but will likely have a different numeric code.

One way to convert words to values is to have a long sequence of statements like:


   if (strcmp(name, "ADD") == 0)
     code = OP_ADD;
   else if (strcmp(name, ".FILL") == 0)
     code = OP_FILL
   ...

An alternative this is to search a data structure. The advantage of this is two fold. First the search code is written once and resused multiple times. Secondly, the contents of the data structure could actually be read from a file, thus changing the behavior of the program without changing the program itself. This is exactly what happens in program like lex which take a textual description of a language and automatically produces a lexical analyzer for it. If you ever take a compiler course (e.g. cs453), you will learn to use these tools.

In this assignment there are three functions for converting names to values:

Converting LC3 operators (e.g. "ADD") to a numerical value.
Converting LC3 conditional branch code (e.g. "N") to a numerical values
Convering a register name (e.g. "R3") to its numerical value. There are other ways of doing this easily, but since you have written the search code, it is convenient to take advantage of it.

The fourth function analyzes a string and determines if it is a valid label.

Getting Started

Create a directory for this assignment and cd to it
Copy the following files to the directory you created. It is easiest to right click on the link, and do a Save Target As.. for each of the files.
- Debug.h (do no modify)
- Debug.c (do no modify)
- lc3.h (do no modify)
- util.h (do no modify)
- util.c (complete this file)
- testUtil.c (do not modify)
- Makefile (do not modify)
Build the excutable by typing make
You now have a functional program, but it will not produce the corrrect results
Enter ./testUtil. You will see a usage message which tells you how to use the program.
You are now ready to begin implementation. You have four functions to implement. In addition, you must intialize two data arrays and two int variables. Implement functions one at a time and test as you go.

Implementing `util_bin_search()`

This function is used three places in your code. Its purpose is to search a sorted array and to find a name. If that name is found, it returns a pointer to the structure containing that name. It is used is to lookup a name like ADD or .FILL and determine the opcode associated with that name.

You have learned how to write binary search in your previous courses. Build on your knowlegde and complete this implementation on C. To test your code, use the reg option in testUtil. This will use you binary search code using the provided code for the function util_get_reg().

Initializing the `cond_code_map[]`

Study the provided code for initializing register_map[]. Then add code to intialize cond_code_map[]. It should have eight entries. To determine what numeric value goes with each "name", think of the bits nzp as a three bit binary number. Once you have initialized cond_code_map[], initialize the variable numCondCodes following the pattern of the code for initializing numRegisters. Lastly, complete the routine util_parse_cond() following the pattern of the code for util_get_reg(). You may test your function using the ccode option of testUtil.

Implementing the remaining functions and initializations

Implement the remaining functions one by one and test them as you go.

Add code for function util_get_opcode() and initalizing the variables numOps and lc3_instruction_map[]. Test by using the option op in testUtil.
Implemet the function util_is_valid_label(). Test by using the option label in testUtil.

Checking in Your Code

You will submit the single file util.c using the checkin program. Use the key UTIL. At the terminal type:

    ~cs270/bin/checkin UTIL util.c