CS 270 Programming Assignment #6

Due Tuesday December 9th (by 11:59pm)

Introduction

Programming assignments are to be done individually. This programming assignment includes additional homework questions that should be answered in the README. Recall that for this assignment you need to include the final driver from PA5 (either MIPSdriver.s or LC3driver.asm). Indicate which one you are submitting in the README.

C-- can only print out strings that have been hard coded into the program. For example,

    cout << "Hello World!\n";

will print the string

    Hello World!

to standard out. For this assignment, you will be writing a MIPS routine, append_char_to_string(), that enables us to build a string in C--.

The goals for this assignment are as follows:

More practice with the LC3 calling convention. C-- and MIPS routines can call each other as long as the MIPS rountines follow the same calling convention as the C-- compiler.
Learn how to do some dynamic allocation.
Practice translating C code to MIPS assembly code.
Learn how C strings are constructed.

The Assignment

C-- does not have a character type. However, with the use of the void pointer type, dynamic memory allocation, and functions written in MIPS, we can write a C-- program that constructs and then prints out a string. The characters to be put in the string will be fed into the C-- program as ASCII codes through standard input. The C-- program will keep reading in integers as long as they are printable ASCII codes (32 through 126). For each printable ASCII code entered, the append_char_to_string() function will dynamically allocate space for a new string and copy the old string appended with the new ascii character into the newly allocated space. Upon reading in the first item that is NOT a printable ASCII code, the program will print the constructed string to the screen and then exit.

The main() (string-driver.cmm), print_string(), and strlen() functions have already been provided. Your assignment is to write the append_char_to_string function. The append_char_to_string function given to you allocates space in the heap for a bogus string ("NO"), initializes that space with the bogus string, and calls strlen on the string. Consider this original version to be an example of the various ways you can use the provided functions to rewrite append_char_to_string() so that it fits the following specification.

    void * append_char_to_string(int ascii_code, void * string)
        This MIPS routine will first call the C-- runtime library routine 
        sbrk() to allocate space on the heap for a new string that is the size
        of the current string plus one character and plus a null termination
        character. Then this routine copies the old string into the new string 
        and places the given ascii_code at the end of the new string.  Finally 
        the new string is null terminated and a pointer to it is returned.

We will provide you with the following functions:

    main()
    
    void print_string( void * )
        This routine uses the print string system call to print the 
        given string.
        
    
    int strlen( void * string )
        This function assumes that the string pointer points at the first
        character in a C string.  strlen will return the number of characters 
        in the C string NOT including the null termination character.

Getting Started

The following files have been provided in ~cs270/public/PA6-start for this assignment:

    Makefile
    Mars.jar
    append_char_to_string.s
    cmm.jar
    print_driver.s
    string-driver.c
    string-driver.cmm
    strlen.s

See SVN Notes for directions for setting up a subversion repository and working directory.

string-driver.c contains a full C version of the program. You can use the C source code to help guide your implementation of append_char_to_string.s. By typing "make" an executable called CstringDriver will be created.

    % make
    Compiling the C version of the program ...
    gcc -g -O0 -std=c99 -Wall  string-driver.c -o CstringDriver
    Done.

    Compiling the C-- version of the program ...
    java -jar cmm.jar --patt-mips string-driver.cmm string-driver.s
    cat string-driver.s append_char_to_string.s strlen.s print_string.s >
    CMMstringDriver.s
    Done.
    Now to run the C-- version, type 'java -jar Mars.jar CMMstringDriver.s'

Notice that "make" also executes commands that cause a CMMstringDriver.s file to be made. The CMMstringDriver.s file is a concatenation of the compiled string-driver.cmm and the functions written directly in MIPS.

The initial version of append_char_to_string() that you are given does not behave according to the PA6 specification, but it does contain some useful example MIPS code. Here is an example run where the '45' and '-1' numbers were entered by the user into standard input.

    % java -jar Mars.jar CMMstringDriver.s
    MARS 3.5  Copyright 2003-2008 Pete Sanderson and Kenneth Vollmar

    Enter decimal ASCII codes between 32 and 126 (anything else to stop): 45
    append_char_to_string needs to be implemented!
    NO
    2
    -1
    NO

We recommend that you step through the current append_char_to_string() MIPS code in the Mars debugger to see how things work. Finally, complete the implementation for append_char_to_string.s using the string-driver.c version of the same function as a guide. The following is an example of how your program should respond when your implementation is complete:

    % java -jar Mars.jar CMMstringDriver.s
    MARS 3.5  Copyright 2003-2008 Pete Sanderson and Kenneth Vollmar

    Enter decimal ASCII codes between 32 and 126 (anything else to stop): 45
    78
    89
    65
    1
    -NYA

Notes

Call the C-- runtime routine sbrk from within append_char_to_string() to create space for the new string, which is the old string appended with the new ascii code. The sbrk routine allocates space on the heap. The given version of the append_char_to_string code has an example of how to do this.
The cin in C-- does not work exactly like scanf. Most notably, each ASCII code must be on a separate line. Multiple numbers on the same line will cause something like the following error:
```
    Error in CMMstringDriver.s line 27: Runtime exception at 0x00400054:
invalid integer input (syscall 5)

    Processing terminated due to errors.
    
```

README and Homework Questions

For this assignment the README file should contain your name, userid, an indication as to whether you are submitting LC3driver.asm or MIPSdriver.s from PA5, a high-level description of the modifications you made to the given code for PA6 (5 sentences max), a description of how to compile and run the final program, an overview of how you tested the program (3 sentences max), and answers to the the following questions. COPY the question as it is shown in this writeup into the README file and then type in the answer directly after the copied question.

Draw the run-time stack for the PA5 MIPSdriver program when execution reaches the end of the sum(0) call but before the sum(0) epilogue has been executed. Assume the number 3 is provided as input. Use Figure 14.7 as an example for the level of detail the stack drawing should contain.

Draw the run-time stack for the PA6 MIPS CMMstringDriver.sprogram when execution reaches the "strlen_while" label. Use Figure 14.7 as an example for the level of detail the stack drawing should contain.

Draw the stack and the heap for the PA6 MIPS CMMstringDriver.s program when the main function is about to call print_string and the input is the following:
```
    70
    117
    110
    33
    -1
```
Also circle the memory locations that are no longer reachable and therefore in a Java program would be garbage collected. We will do an example similar to this in class.

Submitting your Assignment

Make sure your code follows the code style requirements (see http ://www.cs.colostate.edu/~cs270/Programs/code-requirements.html).
Put all of the required information in the README file.

The subversion.txt file should include output from the following commands:

    % svn log -r HEAD:1     // must be done in subversion working directory
    % svn info              // must be done in subversion working directory
    % svnlook tree REPOSITORY_PATH  // svnlook must be issued on the
machine where the repository is stored

We recommend copying the output of the above commands into an editor and saving the result as subversion.txt.

Do a "make clean" in PA6/ before creating the tar ball for the assignment.
Include all the source files, the README file, the Makefile, and a subversion.txt file in a tar file.
```
% cd ~/CS270/
```
```
% tar cvf PA6_userid.tar PA6
```

Submit assignment using checkin utility

% ~cs270/bin/checkin PA6 PA6_username.tar

Quick Sanity Check:

  % ~cs270/bin/SubmissionVerifier.sh PA6

Full Sanity Check (procedure we will use to grade your assignment):

    % cd ~/CS270/
    % cp PA6_username.tar ~/Temp
    % cd ~/Temp
    % tar xf PA6_username.tar
    % cd PA6
    % make all
    % java -jar Mars.jar CMMstringDriver.s

We will be reading through the code comments for the code style requirements portion of the grade.

Late Policy

Late assignments will be accepted up to 24 hours past the due date and time for a deduction of 20% and will not accepted past this period. One minute late is still late.

mstrout@cs.colostate.edu .... November 30, 2008