CS 270
CS 270 Documentation
Programming Assignment P6: CS 270 Computer Organization

Programming Assignment P6 - LC-3 String Library

See Progress page for due dates.

See the details of which subroutines must be implemented for P6A and P6B below.
This assignment has a number of objectives:
  • Writing a larger LC-3 assembly language program with subroutines.
  • Practice writing loops and conditionals in LC-3.
  • Learn how subroutines call other subroutines.
  • Learn how to use a register calling convention for subroutines.
  • Write some simple I/O in LC-3.
  • Give you a sense of how C stores and manipulates strings.
  • Learn how to use the LC-3 debugger to execute portions of your code.
You will complete an LC-3 assembly language program that implements a number of subroutines. Several of these subroutines are duplicates of C functions for strings. Subroutine parameters will be passed in register(s) R0/R1 and results will be returned in register(s). You may find that you do not have enough registers to keep all of your values in registers. In this case, you can create labels to hold them.

IMPORTANT:

  • Don't use registers R5 and R6 in this program (not even in comments). You may use R7 but be careful about its handling.
  • Don't change the reserved section of the code. The only exception to this is that you may change the .FILL values for Option, Value1 and Value2. This makes it easy to initialize the values in the program, so that you do not need to continually re-enter them every time you reset the simulator.
  • Never assume that registers are initialized to 0 by the time your subroutine starts. If you want a register to be initialized to 0, you must do it yourself in your code.

The following list is the set of subroutines you must implement.

Part A:

For testing purposes, it's useful to read and understand what each Test_ subroutine does in the reserved section. For example, the Test_pack subroutine loads the values of the Value1 and Value2 labels into R0 and R1 respectively. Then, it calls your pack subroutine. When your subroutine returns, it stores the value of R0 into the Result label. This tells you that to test your pack subroutine, you must enter the parameters in Value1 and Value2, and then check the result in the Result label.

  • pack(b1, b0) - Pack (combine) the lower 8 bits of R0 and the lower 8 bits of R1 and pack them into a single 16 bit quantity in R0. The lower 8 bits of R0 will be in the upper 8 bits of the result. Here is a visual example:

    pack

  • unpack(b) - Unpack the 16 bits in R0 into registers R0/R1 such that the upper 8 bits of R0 are stored in the lower 8 bits of R0 and the lower 8 bits of R0 are stored in the lower 8 bits of R1. The rest of R0 and R1 needs to be padded with 0's. Here is a visual example:

    unpack

  • printCC() - Print the word NEGATIVE, ZERO, POSITIVE depending on the value in register R0. At exit, register R0 must contain the original value. Each word is followed by a newline. Do not depend on the condition code being set to the correct value on entry. The test of strcmp() uses this subroutine. Notice that we have provided you with labels referring to the strings that you need to print (StringNEG, StringZERO, and StringPOS). The PUTS trap can be used to print a string value stored in memory to the LC3 console. PUTS prints the string beginning at the memory location contained in R0.

IMPORTANT: after your subroutine completes, control must return to the corresponding Test_ subroutine in the reserved section. For example, when your printCC subroutine gets to the RET, the program needs to return to right after JSR printCC in the Test_printCC subroutine. Otherwise, it means that you are not handling R7 correctly. This applies to both part A and part B.

Part B:

  • strlen(s) - On entry R0 contains the address of a valid (null terminated) C string. On exit, R0 contains the length. Note that the null terminator is not counted in the length.
  • strcpy(dest, src) - On entry R0 contains a pointer to the start of the destination string (dest), and R1 contains a pointer to the start of the null-terminated source string (src). On exit, the source string has been copied to the destination string (including the null terminator) and R0 contains a pointer to the start of the destination string.
  • strcat(dest, src) - On entry R0 contains a pointer to the start of the destination string (dest), and R1 contains a pointer to the start of the source string (src). On exit, the source string has been appended to the end of the destination string and R0 contains a pointer to the start of the destination string. For example, if "cdf" is to be appended to "abc", the destination string becomes "abccdf" and R0 is a pointer to the "a". The destination string must be null terminated.
  • strcmp(s1, s2) - On entry R0 contains a pointer to the start of a string (s1), and R1 contains a pointer to the start of another string (s2). On exit R0 contains a negative number if s1 < s2, zero if s1 == s2 and a positive number if s1 > s2, based on the lexicographic ordering using ASCII values: e.g., Z is less than a. In lexicographic ordering, we traverse the strings from left to right until the first difference is found. The differring characters tell us which string is greater. For example, abc < abde because the first difference is c vs. d and c < d. If we get to the end of both strings and no difference is found, the strings are equal. Experiment with the strcmp C function to see what should happen when one string is the prefix of another (for example, abc vs. abcd). Do not assume the strings have the same length (or even that the length is greater than 0).


Getting Started

Start with the file string.asm. You may assemble and run the program. For many of the subroutines you will be prompted to enter a string (see the blue "console"). Enter whatever you like (<256 chars). Your entry is terminated when you press the Enter key. As with any project, incremental development will improve your efficiency.

You might first write pseudo-code in a C or Java syntax to understand the algorithum for a subroutine. If your pseudo code uses variables, you may want to use labels for these variables. Create them before the start of the subroutine (not inside the subroutine). Although using labels may make your code a little longer, it is likely that you will get correct results more quickly if you use them. When you need a value, simply load it from the memory. When you update the value, write it back to memory. This is the load/store model.

When you write the LC-3 code for a subroutine, you may find it helpful if you add comments in each subroutine that explain how you are allocating the registers. For example, you might write ; R4 holds the count.

Testing/debugging each individual subroutines follows a pattern:

  1. Write/modify the code for a single subroutine.
  2. Assemble your program using lc3as.
  3. Load your program into the simulator/debugger.
  4. Set the variable Option to the index of the routine you wish to test. You may want to change the .FILL value so that you do not need to continually reset it as you write, and debug your subroutine.
  5. Set a break point at the entry of your subroutine, or wherever you would like to start your debugging.
  6. Continue the simulator/debugger. If you have set a breakpoint, it will stop when your program reaches that line. Use Step/Next to watch your code execute and examine registers and memory locations for correctness. You will want to use Next so that you do NOT step into traps like GETS or PUTS. You may step into them, but you will find them very tedious to step through.
  7. When the program halts, examine output and/or memory locations for results.
  8. Test your code with multiple test values and verify results.
When you have completed one subroutine, move on to the next one.

You may want to call one subroutine from another, or add subroutines to accomplish specific tasks. Recall that calling a subroutine from another subroutine requires careful handling of the return address (R7), and that registers from the calling routine may be overwritten.

Grading Criteria

Important: After your subroutine completes, control must return to the corresponding Test_ subroutine in the reserved section. For example, when your printCC subroutine gets to the RET, the program needs to return to right after JSR printCC in the Test_printCC subroutine. Otherwise, it means that you are not handling R7 correctly.

First installment of assignment (P6A):
  • Implement pack, unpack, and printCC.
  • Preliminary testing will verify that your program assembles without warnings (it will also test that you're not using R5 or R6 in your code) and it will test pack (40 points).
  • Final testing will verify unpack and printCC (60 points).
Second installment of assignment (P6B):
  • Implement strlen, strcpy, strcat, and strcmp.
  • Preliminary testing will verify that your program assembles without warnings (it will also test that you're not using R5 or R6 in your code) and it will test strlen and strcpy.
  • Final testing will verify strcat and strcmp.


Assignments Submission

Submit the single file string.asm using the Checkin tab of the course website.