CS 270 Programming Assignment #3

Due Tuesday October 7th (by 11:59pm)

Introduction

Programming assignments and the associated homework questions are to be done individually. The homework questions listed in this assignment description should be answered in the README file.

For this assignment, you will be implementing and testing (1) some of the underlying functionality of an LC3 simulator, (2) simulation for three of the LC3 instructions, and (3) a program written in LC3 machine code.

The goals for this assignment are as follows:

Simulate execution of the LC3 machine code and through doing this work with the C implementation of a medium-sized finite state machine.
Learn how to grab a field of bits from a word and sign extend those bits if necessary.
Learn how to write some simple programs in LC3 machine code.

The Assignment

Part 1

You will be given the implementation for the following functions and their corresponding unit tests:

    void LC3state_init( ... )
    
    Word LC3state_read_reg( LC3state *m, unsigned int reg_num )

    void LC3state_write_mem( LC3state *m )

    void LC3state_dump( LC3state *m )
    
    void print_Instruction(Instruction)

Implement the following functions, each in a separate file named based on the function (e.g. decode.c).

    int LC3state_equal( LC3state *m1, LC3state *m2 )    
        Returns 1 if m1 and m2 are equal, otherwise returns 0.

    void LC3state_write_reg( LC3state *m, unsigned int reg_num, Word value )
        Writes the given value to the given register in LC3 machine state.
        Also set the N, Z, and P condition codes appropriately based on the 
        value being written to the register.  N is only one set if value is
        negative, Z is only one set if value is zero, and P is only one
        set if value is positive.  Should check that the register number is
        a valid register number.
    
    void LC3state_read_mem( LC3state *m )
        Read the value at address MAR in the simulated memory into the MDR
        register.  Should print an error to standard error if the address
        to read is outside of simulated memory.
        
    unsigned int 
    bit_field_to_unsigned( Instruction instr, 
                           unsigned int start, unsigned int end )
        Given an instruction, return the integer interpretation of the
        bit field starting at bit start and ending at bit end.
        An instruction is 16 bits.  The bits are numbered as follows:
            15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
        with 15 being the most significant bit and 0 being the least 
        significant bit.  The start position should be greater than or 
        equal to the end position.  See the unit test driver for some
        examples.

    int bit_field_to_int_sext( Instruction instr, 
                               unsigned int start, unsigned int end )
        Given an instruction, return the sign extended
        integer interpretation of the
        bit field starting at bit start and ending at bit end.
        The start position should be greater than or 
        equal to the end position.  

    Opcode decode( Instruction instr )
        Returns the Opcode for the given instruction.  The opcode is in 
        the first four bits of the instruction, bits 15 through 12.

    Word alu( ALUK op, Word B, Word A)
        Simulates the specified alu instruction on the given inputs and returns
        the results.

The prototypes for all of the functions are in a LC3.h file. Once you have implemented a function, add its source file, object file, and unit test name to the appropriate lists in the Makefile.

Each of the seven functions you are implementing will require a unit test driver. We provide you one test case within each unit test driver. For these functions, the possible set of inputs is quite large so you are not required to fully test the functions, but you will need to write at least two additional tests within each unit test driver for each of the functions listed above that you are writing. (Study Exercise: figure out exactly how large for some of the functions).

Since the functions in this assignment all return a value, your unit tests can check that the return value is the one expected and otherwise stop execution through the use of the C assert() function (see the provided test cases for examples).

Part 2: Implementing and testing some LC3 instructions

Once all of the above functions have been implemented, it will be possible to finish the LC3state_simulate function. The LC3state_simulate function takes the current state of an LC3 machine and simulates the LC3 instruction cycle until a HALT instruction is read. Implement the AND, ST, and JMP instructions. Use the implementation of similar instructions as a starting point. For example, AND is similar to ADD, ST is similar to LD, and JMP is similar to BR. Search for the phrase "IMPLEMENT ME" in the LC3state_simulate.c file to see where you need to do some implementation.

The unit test for LC3state_simulate already contains one test case for each opcode implemented in LC3state_simulate. You need to implement one additional test case for each opcode implemented in LC3state_simulate.

Part 3: Implementing a program in LC3

Once the LC3state_simulate function has been completed, you will be able to compile and run the LC3sim executable. Edit the Makefile and change the line that reads

all:		unit_test # $(EXE)

to read

all:		unit_test $(EXE)

Notice that the EXE variable is set to LC3sim earlier in the Makefile. The pound character (#) is the comment character in a Makefile, therefore up until you removed the # character, the LC3sim executable was not being built. Now type make on the command line to build the LC3sim executable.

The LC3sim executable reads memory addresses and values from a text file to initialize the state of an LC3 machine. It then uses that initial state to start the execution of an LC3 program. For example, assume the following text is in the file figure-5.10.asm:

0x30F6  0xE3FD  # R1 <- PC-3
0x30F7  0x146E  # R2 <- R1+14
0x30F8  0x35FB  # M[0x30F4] <- R2
0x30F9  0x54A0  # R2 <- 0
0x30FA  0x14A5  # R2 <- R2+5
0x30FB  0x744E  # M[R1+14] <- R2  
0x30FC  0xA7F7  # R3 <- M[M[0x3F04]]
0x30FD  0xF025  # HALT

If LC3sim is run given this file as input,

    % ./LC3sim figure-5.10.asm

then it will set the program counter (PC) to the first address it encounters in the program, which in this case is 0x30F6. It will then proceed to simulate the LC3 instruction cycle as described in the book. Execution will stop when the HALT trap is reached. LC3sim reads each line of the input file and assumes that the first hex number is a memory address, assumes the second hex number is the data at that memory address, and ignores anything after the # character.

LC3sim has a primitive debug mode, which can be activated by using the -debug command-line option.

    % ./LC3sim -debug figure-5.10.asm

The LC3sim debug mode enables single instruction stepping through the simulation and dumping of the simulated machine state (i.e. register values, memory, etc).

For the last part of this assignment, you will write an LC3 program that examines the 10 memory locations starting at address 0x3100 and stores a 1 in R0 if any of those 10 locations contain the number 5. The program should store a 0 in R0 if none of the locations contain the number 5. Put the program in a file called find-five.asm. Run the program with the following data at the specified addresses:

0x3100  0x0041     
0x3101  0x0042    
0x3102  0x0055    
0x3103  0x0005     
0x3104  0x0000     
0x3105  0x0005      
0x3106  0x0035     
0x3107  0x0525     
0x3108  0x5555      
0x3109  0xFF55

(Hint: Read Chapter 6)

Extra Credit: Bug Reports

Since we are not exhaustively test our functions for this assignment, there will probably be bugs in the provided code. If you are the first student to submit a valid bug report for a particular bug to the instructor and/or the TAs, then you will receive 5 extra points for this assignment. A valid bug report must include detailed instructions on how to reproduce the bug. For example, the code for a test within a unit test driver that causes the bug to show itself.

If you are the first to find inconsistencies with commenting, then you will be given 2 extra credit points.

README and Homework Questions

For this assignment the README file should contain your name, userid, a high-level description of what the functions in the assignment do, how to compile and run the unit tests and the LC3 simulator, an overview of how the functions were tested, and answers to the the following questions. COPY the question as it is shown in this writeup into the file and then type in the answer directly after the copied question.

What binary value does location 4 contain?
Interpret location 6 as a 2's complement integer.
Interpret locations 1 and 2 as an IEEE floating point number. Location 1 contains number [15:0] and location 2 contains number [31:16]. Do not translate to decimal fixed point. Instead just stop at the binary floating point representation. (for example, 1.1 x 2^(-3) )
Interpret location 2 as an LC3 instruction.
Problem 4.8 from book. (instruction design)
Problem 4.14 from book. (instruction cycle)
Problem 5.2 from book. (addressability)
Problem 5.4 from book. (Memory and PC relative)
Problem 5.10 from book. (BR versus JSR)
Problem 5.13 from book. (How to do various operations with limited LC3 instructions)
Problem 5.14 from book. (Implementing OR in LC3) (Hint: What is the relationship between AND and OR?)
Problem 5.24 from book. (LDR and sign extension)
If the condition codes have values N=0, Z=0, P=1 at the beginning of the execution of the following sequence of instructions, what will their values be at the end of the execution of the following sequence of LC-3 instructions?
```
        x3050 0000 0010 0000 0010
        x3051 0101 0000 0010 0000
        x3052 0000 1110 0000 0010
        x3053 0101 0000 0010 0000
        x3054 0001 0000 0011 1111
```
The resulting condition codes are N=1, Z=0, P=0.
Problem 5.40 from book.
Problem 6.14 from book.
Problem 6.16 from book.

Getting Started

The start of a Makefile, a doxygen configuration file (optional, try command make docs), and some of the functions and unit tests have been provided in the public directory (~cs270/public/PA3-start/). Let a copy of the PA3-start subdirectory become your initial PA3 subdirectory. To accomplish this do the following at the command prompt:

    % cd ~/CS270
    (Just to make sure you are in your home directory.)
    % cp -r ~cs270/public/PA3-start ~/CS270/PA3
    cp: cannot access `/s/bach/a/class/cs270/public/PA3-start/.svn': Permission denied

The above error about the .svn subdirectory is fine. Do an 'ls' in your PA3 directory and you should now see the following files:

find-five.asm
LC3.h                   test_LC3state_init.c
LC3sim.c                test_LC3state_read_mem.c
LC3state_dump.c         test_LC3state_read_reg.c
LC3state_init.c         test_LC3state_simulate.c
LC3state_read_reg.c     test_LC3state_write_mem.c
LC3state_simulate.c     test_LC3state_write_reg.c
LC3state_write_mem.c    test_alu.c
Makefile                test_bit_field_to_int_sext.c
cs270.doxygen.config    test_bit_field_to_unsigned.c
print_Instruction.c     test_decode.c
test_LC3state_dump.c    test_print_Instruction.c
test_LC3state_equal.c

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

We STRONGLY recommend that you implement one function and its corresponding unit test driver at a time. Write your file and function headers BEFORE you start implementing the function. Remember that each function and unit test driver should be in its own file.

Submitting your Assignment

Make sure there are the required number of unit tests for all of the functions in the 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 and answer the associated homework questions 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 PA3/ 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 PA3_userid.tar PA3
```

Submit assignment using checkin utility

% ~cs270/bin/checkin PA3 PA3_username.tar

Quick Sanity Check:
```
  % ~cs270/bin/SubmissionVerifier.sh PA3
  
```
Full Sanity Check (procedure we will use to grade your assignment):
```
    % cd ~/CS270/
    % cp PA3_username.tar ~/Temp
    % cd ~/Temp
    % tar xf PA3_username.tar
    % cd PA3
    % make all      // this should compile and run unit tests  
  
```
We will also be copying in our own unit tests for each function, and 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 .... October 6, 2008