CS 270 Programming Assignment #5

Due Friday November 21th (by 6:00pm, NOTE the different time)

Introduction

Programming assignments are to be done individually. This programming assignment does NOT include additional homework questions. Keep in mind that HW1 is due November 11th.

For this assignment, you will be implementing three different recursive functions (sum, countDownUp, and fib) in four different languages (C, C--, MIPS, and LC3). You will have one driver in each language that calls all three recursive functions. For testing, you will write unit tests for each of the functions in C and compare the output of your drivers with a provided reference driver (Cdriver.public). Your C driver must also perform some error checking.

The goals for this assignment are as follows:

Learn the calling convention for LC3.
See that the same calling convention can be used in other assembly languages.
Learn how C programs can receive command-line parameters.
Learn how to redirect files to standard in.

The Assignment

The following functions must be implemented with recursion.

    int fib( int n )
    
        This function returns the nth fibonacci number.  See 
	wikipedia
	for more information about the the fibonacci sequence.
	We are going to let fib(0)=0.
        Can assume that n is a non-negative number that is less than
        or equal to 9.
        

    int sum( int n )
        
        This function returns the sum of the numbers 0 through n.
        This function can assume that n is a non-negative number that 
        is less than or equal to 9.
        
        
    void countDownUp( int n )
        
        This function prints the integers n through 1 to standard out 
        and then prints the numbers 1 through n to standard out.
        This function assume that n is a non-negative number that is 
        less than or equal to 9.

All of the routines take a single integer in the range 0 to 9 as input so as to simplify input for LC3.

C driver

The C driver should receive a single non-negative integer parameter in the range 0 to 9. The C driver should have the following usage:

    % ./Cdriver -n 6
or
    % ./Cdriver -n6

The C version of all the recursive routines will help guide the development of the C--, MIPS, and LC3 drivers. As such it has more requirements than the other drivers.

The Cdriver should print an error message to standard error and return a 1, if ...
- the executable was called without command-line parameters or the wrong command line parameters.
- the number provided on the command-line does not fit within the required range.
The fib(), sum(), and countDownUp() functions should each have their own separate C file (fib.c, sum.c, and countDownUp.c). Both the fib() and sum() functions must have a corresponding unit test called test_fib.c and test_sum.c. It is possible to fully test fib() and sum(). There should also be a Cdriver.c file.

Here are some examples of the expected output:

    % ./Cdriver -n4
    fib(4) = 3
    sum(4) = 10
    4
    3
    2
    1
    1
    2
    3
    4
    
    % ./Cdriver -n-5
    ERROR: n = -5, n should be in range 0 to 9

    % ./Cdriver -h
    ./Cdriver: illegal option -- h
    
    % ./Cdriver blah
    Usage: ./Cdriver -n#
    
    % ./Cdriver -n 2
    fib(2) = 1
    sum(2) = 3
    2
    1
    1
    2

The output of your Cdriver executable will be compared with the output of the reference Cdriver.public executable, which is availabe in ~cs270/public/. (Note: You might find the getopt-example.c covered in recitation helpful).

C-- driver

C-- is a subset of C. The specific C-- compiler we will be using is a modified version of the Wisconsin C-- compiler (http://pages.cs.wisc.edu/~lenz/compiler.html), which we will call CMM. You can find the CMM jar file (cmm.jar) in the cs270 public directory (~cs270/public/).

CMM does not allow main() to take command-line arguments. Therefore, we will be redirecting a file into standard input. Assume that the file four.in contains the following:

This set of commands should be used to compile the CMMdriver.c file and run the resulting assembly code in the MARS simulator http://courses.missouristate.edu/KenVollmar/MARS/. A copy of the MARS simulator can be found in the cs270 public directory (~cs270/public/).

    % java -jar cmm.jar --patt-mips CMMdriver.c CMMdriver.s
    % java -jar Mars.jar nc CMMdriver.s < four.in
    fib(4) = 3
    sum(4) = 10
    4
    3
    2
    1
    1
    2
    3
    4

Note that your CMM driver should generate results identical to those generated by the Cdriver.public.

It is not too difficult to take the C code you have and translate it into C-- code. See (http://pages.cs.wisc.edu/~lenz/compiler.html) for a list of the C-- limitations. Here is a list of some of the things you need to do:

Put all of the C code into ONE source file and call it CMMdriver.c.

Change all of your multi-line comments to single-line comments. For example,

    /* Hello
       multi-line comment
    */

should be translated to the following:

    // Hello
    // multi-line comment
    //

Put the prototypes for fib, sum, and countDownUp at the top of the file.
The first funtion definition should be main().

Instead of printf, CMM uses cout and cin. For example,

    printf("fib(");
    printf("%d", n);

should become the following:

    cout << "fib(";
    cout << n;

Also to read in an integer from standard input, use the following:

    // Read in the input integer.
    cin >> n;

There is no "else if" in CMM.

Keep in mind that the CMM compiler is not nearly as robust as gcc. It is not going to catch many of your errors at compile time, so send email to the mailing list if you get stuck. We use the CMM compiler in this class so that in PA6 you can do a project where you have C-- code calling MIPS code and vice versa.

MIPS driver

Your MIPS driver will take the form of a single assembly file called MIPSdriver.s. The definition for all three recursive routines as well as the driver itself will be in the one assembly file. Make sure to follow the coding requirements for assembly code (http://www.cs.colostate.edu/~cs270/Programs/code-requirements.html).

We recommend that we implement your MIPSdriver.s after implementing the C and C-- drivers and before the LC3 driver. The MARS IDE is much more robust and useful than the LC3assem and LC3sim programs we developed this semester. It will be easier to debug your assembly versions of these recursive routines in MIPS and then do almost a line-by-line translation into LC3.

Do NOT attempt to pass off code generated by CMM as your own. Such actions are considered academically dishonest. Because of the way the CMM compiler generates code, it will be very easy to tell if that is what you are doing.

Here are some MIPS code segments to help get you started.

        .text
        .globl main
main:
    li      $v0, 5          # read an integer from stdin
    syscall                 # $v0 now contains read in integer
    move    $s0, $v0        # $s0 <- $v0


    
    la      $a0, SUMSTR     # print "sum(" to stdout
    li      $v0, 4          #
    syscall                 #
    
    
    # print n to stdout
    move    $a0, $s0        # $a0 <- $s0 <- input number
    li      $v0, 1          # indicate print_int syscall
    syscall

    la      $a0, NEWLINE    #  print "\n"
    li      $v0, 4          # indicate print_string
    syscall
   
    # HALT
    li      $v0, 10
    syscall

    
.data       
SUMSTR:      .asciiz "sum("
NEWLINE:     .asciiz "\n"

Also see notes from class (November 11 and 13) and Appendix A.

Here is how to run your MIPSdriver.s code.

    % java -jar Mars.jar nc MIPSdriver.s < four.in
    fib(4) = 3
    sum(4) = 10
    4
    3
    2
    1
    1
    2
    3
    4

Note that your MIPS driver should generate results identical to those generated by the Cdriver.public.

LC3 driver

Your LC3 driver will take the form of a single assembly file called LC3driver.asm. The definition for all three recursive routines as well as the driver itself will be in the one assembly file. Make sure to follow the coding requirements for assembly code (http://www.cs.colostate.edu/~cs270/Programs/code-requirements.html).

Your LC3 driver will receive the input number through standard input. For example, assume that the file LC3driver.in has the number 4 in it followed by a newline. The LC3 driver can be run as follows:

    % ./LC3assem.public LC3driver.asm LC3driver.LC3
    % ./LC3sim.public LC3driver.LC3 < LC3driver.in
    fib(4) = 3
    sum(4) = 10
    4
    3
    2
    1
    1
    2
    3
    4

The LC3 driver does NOT need to test that the number provided through standard input is provided in the correct format or is in the correct range.

The LC3 simulator written in this class is not as sophisticated as other simulators. The LC3 machine state starts out with nothing initialized and there is no start function that will be calling main. Therefore, you must initialize the stack pointer to point somewhere in memory before calling any of the recursive routines.

    LD      R6, SP_INIT     ; initialize the stack pointer
    ...
    
    SP_INIT     .FILL   x7000           ; initial address for stack pointer

Also, LC3 does not have any traps that input integers or output integers. You only need to be able to input integers in the range 0 through 9. However, you will need to output integers with more than one digit. We are providing the print_int, div10, and mod10 routines to help you print integers to the screen and as recursive examples in LC3. They will be available in ~cs270/public/PA5-start/LC3driver-start.asm.

README

For this assignment the README file should contain your name, userid, a high-level description of what the driver in each language does, how to compile and run the unit tests and the four drivers, and an overview of how the functions were tested (5 sentences max for testing overview). See http://www.cs.colostate.edu/~cs270/Programs/README.example for an example README.

Getting Started

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

    Cdriver.public
    cmm.jar
    Mars.jar
    LC3assem.public
    LC3sim
    PA5-start/LC3driver-start.asm

You can also copy and modify files such as the Makefile from previous assignments. You will have to take out the -std=c99 flag to make getopt work.

To figure out how to read input from the command line and from standard in see the examples given in recitation (~cs270/public/R9).

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

We STRONGLY recommend that you implement one function at a time. Start with the C functions and unit tests to ensure that the C functionality is working fully. Then complete each of the other drivers (CMMdriver, MIPSdriver, and LC3driver) one driver and one function at a time. Make sure that you can almost always compile and run something, and debug as you go.

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 PA5/ 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 PA5_userid.tar PA5
```

Submit assignment using checkin utility

% ~cs270/bin/checkin PA5 PA5_username.tar

Quick Sanity Check:
```
  % ~cs270/bin/SubmissionVerifier.sh PA5
  
```
Full Sanity Check (procedure we will use to grade your assignment):
```
    % cd ~/CS270/
    % cp PA5_username.tar ~/Temp
    % cd ~/Temp
    % tar xf PA5_username.tar
    % cd PA5
    % make all      // this should compile and run C unit tests  
  
```
We will also be testing the other drivers as specified above. 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 14, 2008