CS61C: Machine Structures. Fall 2007, UC Berkeley
Patterson and Hennessey Kernighan and Ritchie
CS61C Fall 2007
MWF 3pm-4pm 2050 VLSB





CS 61C (Fall 2007)

Project 3

Submit as "proj3".  Due 7:45pm 10/24/2007.

This project is due October 24th, 2007. This is an individual assignment; you must work alone. Submit your solution, a file named proj3.c, as proj3.

Getting started

Copy the directory ~cs61c/files/proj/3 to your home directory and name it "proj3". It includes several files: sim.c, computer.h, computer.c, proj3.c, proj3.h, sample.s, sample.dump, sample.output, and makefile. These are described below.

Background

In this project, you will create an instruction interpreter for a subset of MIPS code. It will fetch, disassemble, decode, and execute MIPS machine instructions. You're creating what is effectively a miniature version of MARS! There is one important difference, though—MARS takes in assembly language source files, not .dump files, so it contains an assembler, too.

Project

The files sim.c, computer.h, computer.c, proj3.c and proj3.h comprise a framework for a MIPS simulator. Complete the program by adding code to proj3.c. Your simulator must be able to simulate the machine code versions of the following MIPS machine instructions:

	addu	Rdest, Rsrc1, Rsrc2
	addiu	Rdest, Rsrc1, imm
	subu	Rdest, Rsrc1, Rsrc2
	sll	Rdest, Rsrc, shamt
	srl	Rdest, Rsrc, shamt
	and	Rdest, Rsrc1, Rsrc2
	andi	Rdest, Rsrc, imm
	or	Rdest, Rsrc1, Rsrc2
	ori	Rdest, Rsrc, imm
	lui	Rdest, imm
	slt	Rdest, Rsrc1, Rsrc2
	beq	Rsrc1, Rsrc2, raddr
	bne	Rsrc1, Rsrc2, raddr
	j	address
	jal	address
	jr	Rsrc
	lw	Rdest, offset (Radd)
	sw	Rsrc, offset (Radd)

Once complete, your solution program will be able to simulate real programs that do just about anything that can be done on a real MIPS, with the notable exceptions of floating-point math and interrupts.

The framework code

The framework code begins by doing the following.

  1. It reads the machine code into "memory", starting at "address" 0x00400000. (In keeping with the MARS convention, addresses from 0x0000000 to 0x00400000 are unused.) We assume that the program will be no more than 1024 words long. The name of the file that contains the code is given as a command-line argument.

  2. It initializes the stack pointer to 0x00404000, it initializes all other registers to 0x00000000, and it initializes the program counter to 0x00400000.

  3. It provides simulated data memory starting at address 0x00401000 and ending at address 0x00404000. It stores instructions together with data in the same memory array.

  4. It sets flags that govern how the program interacts with the user.

It then enters a loop that repeatedly fetches and executes instructions, printing information as it goes:

Your job is to provide the code for the disassembled and simulateInstr functions, plus any auxiliary functions that are appropriate. You may assume that the simulated instructions will not address instruction memory illegally. If the program encounters an instruction that's not one of the ones just listed, it should quit.

The framework code supports several command line options:

  -i   runs the program in "interactive mode". In this mode, the program prints a ">" prompt and waits for you to type a return before simulating each instruction. If you type a "q" (for "quit") followed by a return, the program exits. If this option isn't specified, the only way to terminate the program is to have it simulate an instruction that's not one of those listed on the previous page.
  -r   prints all registers after the execution of an instruction. If this option isn't specified, only the register that was affected by the instruction should be printed; for a branch, a jump, or a store, which doesn't affect any registers, the framework code prints a message saying that no registers were affected. (Your code needs to signal when a simulated instruction doesn't affect any registers by returning an appropriate value in the changedReg argument to simulate and simulateInstr.)
  -m   prints all data memory locations that contain nonzero values after the execution of an instruction. If this option isn't specified, only the memory location that was affected by the instruction should be printed; for any instruction that's not sw, the framework code prints a message saying that no memory locations were affected. (Your code needs to signal when a simulated instruction doesn't affect memory by returning an appropriate value in the changedMem argument to simulate and simulateInstr.)
  -d   is a debugging flag that you might find useful.

Almost all the printing in the framework code is done in the printInfo function. Also printed is the output of the disassembled function, which requires some special attention. Although it just prints the instructions and its operands in text, we will be grading your project with automated scripts. Therefore, the output must follow this part of the specification exactly. Here are the details on the output format:

Here are examples of good instructions:

	addiu     $1, $0, -2
	lw        $1, 8($3)
	srl       $6, $7, 3
	ori       $1, $1, 0x1234
	lui       $10, 0x5678
	j         0x0040002c
	bne       $3, $4, 0x00400044

Here are examples of bad instructions:

	addiu     $1, $0, 0xffffffff     # shouldn't print hex for addiu
	sw        $1, 0x8($3)            # shouldn't print hex for sw
	sll       $a1, $a0, 3            # should use reg numbers instead of names
	srl       $6,$7,3                # no spaces between arguments
	ori       $1 $1 0x1234           # forgot commas
	lui       $t0, 0x0000ABCD        # hex should be lowercase and not zero extended
	j         54345                  # address should be in hex
	jal       00400548               # forgot the leading 0x
	bne       $3, $4, 4              # needs full target address in hex

The files sample.s and sample.output in the proj3 directory provide an example output that you may use for a "sanity check". We do not include any other test input files for this project. You must write the test cases in MIPS, use MARS (mars-cs61c) to assemble them, and then dump the binary code. See the "Hints" section for suggestions on how to do this.

Please don't change the framework code. If we find errors in it, we'll provide updates.

Hints

Most of you will be tempted to immediately write a first version of the entire project before properly testing. This will certainly complicate your debugging. We recommend the following procedure for approaching this project:

  1. Read and understand the project specification and source code.

  2. Before writing any C code, write a simple test in MIPS that tests just one particular instruction; assemble it to a binary using MARS (see below). Note that some of the instructions depend on far more code than others. For example, the lw and sw instructions require the memory code to work properly. Consider this when choosing your instruction.

  3. Code the minimal amount of C required to support the instruction that you selected in #2 and debug it using your test case. A first step might be to write the disassembly helper functions that your test case requires.

  4. Choose another instruction to test. It may make sense to choose a set of instructions that are similar to the first one that you chose to support. Write a second test file that only uses this set of instructions.

  5. Repeat steps 3 and 4 until all instructions are supported.

  6. Clean up your code.  Make sure to format it properly and add comments, this will help you debug and understand your own work better.

  7. Submit your solution.

Writing test cases

A first step in testing is to write test code in MIPS. Here are some important guidelines to consider as you write your MIPS test code:

Generating binary files

The procedure for generating input files for the simulator is straightforward. Here are the steps:

  1. Write your test program in MIPS. Make sure you only use supported instructions, and avoid assembler directives that set up .data memory. Suppose your test file is named test0.s. Terminate your program with a single unsupported instruction (e.g., slti). As mentioned previously, attempting to execute an unsupported instruction will cause the simulator to quit.

  2. Be sure to use mars-cs61c on the instructional machines or download ~cs61c/bin/mars/mars-cs61c.jar to your local machine.

  3. Debug your MIPS code with MARS.

  4. Dump the code from MARS using the Save Dump button in the lower left of the data segment window.  Be sure to select the .text segment in the dropdown before doing this, or you might accidentally dump the data memory. You should also select the Binary dump format for this project.  MARS will dump the binary instruction into a file of your choosing.

  5. Now, test0.dump is a valid input to the simulator. We recommend that you save all of your .s and .dump test files in an orderly fashion. This way, when you think you are done with the simulator, you will have a comprehensive battery of tests to put it through before submitting.

Additional pointers

To view a binary dump file in emacs, open it like you normally would and type M-x hexl-mode.

Use gdb. It can save you so much trouble. For example, you can type "make" at the gdb prompt and gdb will run the makefile for you. This is convenient because you don't have to quit out of gdb to recompile your code.



Site Maintained by: Greg Gibeling (gdgib <at> berkeley.edu)