Posted: May 4, 2002

Additions

• (5/9) Version 2 now posted. Contains information about software interrupts.
• (5/5) Changed static_cast to reinterpret_cast when casting pointer from one type to another (in C++). In C, the casting is done the old fashioned way (with parentheses, indicating the new type).

Primary

Primary Link

If you pass primary, you can get at least 70 points out of 100 points.

Purpose

What Might Have Been

In case you were wondering where the projects would have gone:

• Project 2 (this project)

  Store the program in some sort of data structure (an array of instructions). Have a variable keep track of the current instruction being run. However, keep the data in "memory" and registers in an array of int values.

• Project 3

  Convert the program to binary and save it to memory and to a binary file and be able to read from that binary file too.

• Project 4

  Write implementations of various instructions using microcode and a simulated CPU which fetches and decodes instructions, etc.

At least you get to project 2 where the assembly language program begins to run.

Academic Integrity Statement

Please note that *all* programming projects in this course (including this one) are to be done independently or with the assistance of the instructional staff of this course only, unless otherwise specified IN PRINT by official webpages.

Please review the policies outlined on the class syllabus concerning the use of class computer accounts and concerning the University's Code of Academic Integrity. The instructors of this course will review the programs submitted by students for potential violations of the Code of Academic Integrity and if it is believed that a violation has occurred it will be referred to the Office of Judicial Programs and the Student Honor Council.

Hardcoding is considered a violation of academic integrity

Reminder

I thought this was obvious, but perhaps I should repeat it again. Each memory address stores one byte. A word (32 bits) occupies 4 consecutive meomry addresses. The first byte of that address must be word-aligned (in an address divisibly by 4).

Running Code

In Project 1, you had two parts of the input: data and text. They had very little to do with each other. This time, the two parts are going to be run together.

The output of Project 2 can simply be the output of Project 1, followed by the output of one run of the program.

Here's what you need to do:

• Find some way to store the program. One suggestion is a vector of Instruction, and a variable keeping track of the current instruction being run.

• The registers should be some sort of array of integers. As long as you have some reasonable representation of the registers, that's fine (for example, you could create a Register object that stores 32 bits).

• Memory should be some sort of array of bytes. Assume the array will not have to exceed 3000 elements (bytes). If you are using C++, you can use an array of characters. If you're clever with the indexing, you can use arrays of integers (which would store 4 bytes).

• The assembly language program is not stored in memory.

Furthermore:

• Initialize all registers to 0.

• Initialize register 29 (the stack pointer) to address 2996 (which is the bottom of memory).

• Initialize all of memory to 0.

• From part 1, put all the data into memory. This may be a little tricky because some data are characters and some are integers. Integers should be stored in big-endian format.

  Here's a way to handle it using C/C++, assuming you use a character array to represent memory.

    int val = -10 ;   // want to store this in memory
  
    // Woops, HTML inteprets < and > as tags, so this
    // didnt show up properly...
    char * ptr = reinterpret_cast<char *>( & val ) ; 
  
    // now store at address 1003
    mem[ 1003 ] = *ptr ;
    ptr++ ;
    // now store at address 1002
    mem[ 1002 ] = *ptr ;
    ptr++ ;
    // now store at address 1001
    mem[ 1001 ] = *ptr ;
    ptr++ ;
    // now store at address 1001
    mem[ 1000 ] = *ptr ;
  

  Here's what's happening. You are putting a character pointer to the address of an int value. An int value should be 4 bytes (it is on the OIT class cluster). The reason you store the first byte in 1003 instead of 1000 is because the OIT machines are little endian, so we are converting it to big endian. Thus, ptr initially points to the least significant byte, and now it's store in the most significant byte.

  In Java, the technique is a little more complicated, but not that bad. In Java, you should be able to do two operations. First, you can cast an int to a byte. This SHOULD truncate the upper bits, leaving only the lower bits.

  Then, you can use the bitshift operator >> to shift by 8 bits to the right, and again, cast to a byte. Do this two more times, and you have all 4 bytes. Again, since you are getting the bytes starting at the least significant end, you will need to save this to memory starting at address + 3 and working down to address where address stores the first byte (the most significant byte).

At this point, you can run the program.

Commands to Support

The following are a list of assembly language commands to support.

Command	Explanation
add $rd, $rs, $rt	$rd = $rs + $rt
addi $rd, $rs, immed	$rd = $rs + immed where immed is 16 bit 2-complement
sub $rd, $rs, $rt	$rd = $rs - $rt
and $rd, $rs, $rt	$rd = $rs & $rt (bitwise and)
andi $rd, $rs, immed	$rd = $rs & immed where immed is 16 bit 2-complement, sign extended
or $rd, $rs, $rt	$rd = $rs | $rt (bitwise and)
ori $rd, $rs, immed	$rd = $rs | immed where immed is 16 bit 2-complement, sign extended
xor $rd, $rs, $rt	$rd = $rs & $rt (bitwise xor)
xori $rd, $rs, immed	$rd = $rs & immed where immed is 16 bit 2-complement, sign extended
andi $rd, $rs, immed	$rd = $rs & immed where immed is 16 bit 2-complement, sign extended
beq $rd, $rs, LABEL	Jump to LABEL if $rd == $rs, otherwise next instruction
bne $rd, $rs, LABEL	Jump to LABEL if $rd != $rs, otherwise next instruction
slt $rd, $rs, $rt	If $rs < $rt, then $rd = 1 else $rd = 0
slti $rd, $rs, immed	(CORRECTION: slt was replaced with slti on 5/13) If $rs < immed then $rd = 1 else $rd = 0
jr $rd	Jump to address in $rd
j LABEL	Jump to LABEL
jal LABEL	Jump to LABEL, storing address after this instruction in $r31
lw $rd, offset($rs)	Compute address by $rs + offset (sign extended) and load word to $rd
lb $rd, offset($rs)	Compute address by $rs + offset (sign extended) and load byte to $rd (upper 24 bits are 0)
sw $rd, offset($rs)	Compute address by $rs + offset (sign extended) and store word at address in $rd
sb $rd, offset($rs)	Compute address by $rs + offset (sign extended) and store byte to $rd (upper 24 bits are 0)
lui $rd, immed	Load upper 16 bits of $rd with immed and lower 16 bits with 0.

• subi does not really exist, so it has been removed. Only addi actually exists.

Software Interrupts

In order to print information to the screen, you will implement fake software interrupt. There are two kinds of interrupts: external (hardware) interrupts and software interrupts.

A hardware interrupt usually occurs from an external device such as a mouse, keyboard, printer, etc. One mechanism for handling, say, mouse movements is called polling. This is where the CPU repeatedly checks to see if the mouse is doing anything. This can be wasteful use of CPU resources if the mouse isn't doing anything.

The other approach is to use hardware interrupts. This is an external signal (for example, a 0 to 1 transition) to the CPU, indicating an interrupt has occurred. Typically, the CPU completes the current instruction it is working on, then handles the interrupt.

The interrupt typically saves registers on the stack (although this isn't absolutely necessary), determines what interrupt has occurred (each interrupt has a special number), then runs the appropriate interrupt handling routine.

Once the interrupt handling routine is done, the program that was interrupted is restarted. The interrupt handling routine needs to be "programmed" ahead of time and can be altered to use routines that the user has developed (if the user is "trusted").

An interrupt is similar to a function call, but is less predicatable.

This mechanism can also be used like a function call. In the old days, IBM had something called BIOS which were a series of routines stored in, say, ROM. You invoked the routines using software interrupts.

The software interrupt is much closer to a function call. It uses a similar technique to invoke the interrupt handling routine, and then the routine runs under "supervisor" or "kernel" mode, which is a privileged mode of operation.

You need to support the following software interrupts.

• Print an int stored at a word-aligned address
• Print a character stored at any address
• Print the hexadecimal value at a range of addresses
• Print a null-terminated string starting at some address
• Print the contents of a range of register values.

Hopefully, this won't be too bad.

How the interrupts work

The name of the command for an software interrupt is swi (this is stolen from ARM---the version in MIPS is really syscall, but I prefer swi, which stands for software interrupt--duh).

Interrupt number	Registers used	Purpose
1	$r26 stores 1 $r27 stores address	Prints integer at address in $r27 in base 10
2	$r26 stores 2 $r27 stores address	Prints integer at address in $r27 in base 16
3	$r26 stores 3 $r27 stores address	Prints byte at address in $r27 in base 16
4	$r26 stores 4 $r27 stores address of string	Prints string starting at register $r27
5	$r26 stores 5 $r27 stores register number	Prints integer value stored at register $r27 in base 10
6	$r26 stores 6 $r27 stores register number	Prints integer value stored in register $r27 in base 16
7	$r26 stores 7 $r27 stores low register $r28 stores high register	Does a register "dump", printing contents of registers from $r27 to $r28, inclusive.

Some notes:

• $r26 stores the interrupt number
• You may assume that only valid addresses with valid data will be called.
• You may assume the integer is word-aligned (at an address divisible by 4).
• When printing an integer in base 10 (interuupt 1 and 5), print as signed value. Don't add a newline at the end.
• When printing an integer in base 16 (interuupt 2 and 6), print as unsigned using 8 hex digits (e.g. 1A 23 09 22). Recall each hex digit is 4 bits. Put a blank space between every pair of hex digits. Do not add a newline at the end.
• When printing a string, print the ASCII character at address $r27 and keep printing characters until you reach a null character (whose byte value is 0).
• A byte can be printed at any valid address (including a byte from a string or integers). This will be used to check whether your integers are stored in big-endian.
• When printing a byte (interrupt 3), print two hex digits (e.g. 1A). Don't add a newline at the end.
• When printing the contents of a register (interrupt 5 and 6), you can assume $r27 stores a valid register number (from 0 to 31). Use same format as for interrupt 1 and 2.
• When doing a register "dump", print in base 10 (signed). For example, if $r27 stores 9 and $r28 stores 12, you would print:

   9: -10
  10: 14
  11: 1003
  12: -2101
  

• Assume that when swi is called, $r26 and $r27 have been filled with correct values.

Assumptions about registers

Assumptions:

• $r0 is hardwired to 0. No matter what operation you do, it should leave this register with a value of 0.
• $r29 is the stack pointer
• $r31 is used by the jump-and-link (jal) instruction to store the return address (the address just after the jump and link). This address is an absolute address.
• It may be useful to represent registers as an array of signed int. That way, you can do normal addition, subtraction, etc. without much work. For bitwise operations, it's often better to cast the contents of the register to unsigned int and use the bitwise operators available in C++ and Java. If you prefer to do more work, you can represent registers as an array of 32 boolean values. However, you can't use bitwise operators from C++/Java, and must implement something that behaves like them.

Submitting

"Primary" posted soon!

See the class syllabus for policies concerning email Last Modified: Sun Mar 3 22:54:00 EST 2002

Web Accessibility