Lab: MIPS Basics

Assigned

November 16, 2020

Due

November 20, 2020 by 8:00am Grinnell time

Collaboration

Complete this lab with your randomly-assigned group. You may ask the instructor or class mentor for help, but you should not discuss your work with students in other groups.

Submitting

Upload your mips-basics.asm and play-song.asm files to the appropriate assignment on Gradescope.

Preparation

Although we traditionally use a PIC32 microchip to execute MIPS machine code for this class, we can’t ship everyone a complete working development environment. Instead, we will simulate MIPS code in software using the MIPS Assembly and Runtime Simulator MARS, which is absolutely good enough for us to verify that you can think structurally about MIPS operations, even if we can’t wire it to external devices.

To launch MARS on the MathLAN, you can type

java -jar /home/weinman/shared/Mars4_5.jar

In addition, you may also copy the JAR (Java ARchive) file from that location or directly download it to your own computer and run it there, using a similar invocation of Java.

Basic Operation

Download the first starter file mips-basics.asm
Open the file in MARS.
To assemble your code, click “Assemble” under the Run menu (or the Screwdriver and Wrench icon in the toolbar).
You can step through your code line by line with the F7 key (or the green and white arrow button with a “1”), but this is tedious. A better way is to switch to the “Execute” pane, which shows your assembled code (along with the actual instructions, the machine version, and its address in the virtual machine). The left-most column allows you to set any breakpoints at which you may want to investigate behavior. If you just want to run the whole test program, the nop at the end of main is good point at which to stop. Other desirable breakpoints may arise as you wish to diagnose certain (mis)behaviors.

Broader MIPS Background

Before we proceed, we will unpack a few new bits of syntax and semantics it is helpful to understand.

Directives

In addition to the sequence of instructions you have seen (e.g., addi, lw), assembly files usually contain other important information. Like many assembly languages, directives to the MIPS assembler begin with a period and typically mark up regions and provide data,. You will see the following directives:

.globl

Precedes a list of symbols exported in the symbol table (with the symbol’s address in the final object) to be available for linking with other objects or use by the debugger.

.data

Marks the beginning of a data section of the assembly language file, for things like global variables.

.text

Marks the beginning of a text section of the assembly language file, where instructions are found.

.ent

Precedes a single label that marks the entry/starting point of the program for the loader. MARS ignores this directive and instead starts executing at the beginning of the text section, but it is important for reading general MIPS programs.

.word

Within the data section, followed by a label, reserves and initializes word-aligned, comma-separated blocks of data. For example, if you declared the following global variable in C,

int [] sloane211 = {4, 3, 5, 6, 9, 13, 20, 31, 49};

then you might end up with the following MIPS assembly line

sloane211: .word 4, 3, 5, 6, 9, 13, 20, 31, 49

A single global variable (rather than an array) would also be indicated the same way (though with only a single value, rather than a comma-separated list).

.byte

Similar to word, except that a sequence of bytes are specified. (Note they will be stored within words according to the endian-ness of the particular platform.) To load a single byte from memory (rather than a whole word) from an address, you would use either lb (load byte) or lbu (load byte unsigned), depending on the contextual need.

.asciiz

Within a data section, followed by a label, reserves space for and initializes a null-terminated ASCII string of bytes. For example,

message: .asciiz "Hello, world!"

There are other important directives, but these constitute the most important ones we will use this term.

To place the address of a label into a register (i.e., for issuing a load or store command), you use the la (load address) instruction. For example,

la $t0, sloane211  # Set $t0 to &sloane211[0] (address of the array's start)
lw $t1,0($t0)      # Dereference the pointer, i.e., put sloane211[0] into $t1

System Calls

Certain privileged operations or specialized on microprocessors are often accomplished by system calls. Toward the end of the term, we’ll revisit how those are implemented in hardware, but all you need to understand for now is that when a system call is invoked, control of the processor is transferred to a special program that enjoys certain elevated hardware permissions. When that special code concludes, control typically returns to your program just after the system call.

System calls in MIPS work by placing a specific integer (indicating the particular function) into the register $v0 and then invoking the syscall instruction.

For example, to terminate your program’s execution, you would invoke system call 10 as follows:

li $v0, 10  # Place the "exit" system call code in the appropriate register
syscall     # Invoke the system call
# No further instructions are reached or executed

Some system calls take arguments (in addition to specifying which specific system call is desired). To print a null-terminated string to the output terminal, one gives the address of the first byte of the string in argument register $a0. For example, if the string message were declared as above, you could print it in MIPS as follows anywhere in a text (program) region.

la $a0, message # Load the address of message into the argument register
li $v0, 4       # "Print string" system call
syscall
# Instructions here would continue executing after the printing has completed

For the curious, the MARS documentation gives the complete list of MIPS and MARS-specific system calls available in the MARS simulator.

Grading Guidelines

Note that the MARS simulator does not enable simulation of the branch/jump delay by default. Do not enable it; branch delays will not be activated during grading for correctness, so your program would likely fail many tests, leading to a poor grade.
The only pseudoinstructions you may use for completing the problems in this assignment are:
- move
- nop
- li
- beqz and bnez
In particular, you may NOT use ble, blt, etc.
Your grade on each problem will depend on its correctness. For Part A, I will use a test suite to validate your problem’s correctness, and the grade for each problem will be determined by how many tests each problem passes. For Part B, I will run your code to listen for overall correctness, giving credit for each of the steps (2–4) successfully completed.
In addition to being graded on correctness, your code will be evaluated on its clarity, organization, and overall efficiency with respect to the number of instructions required to complete any given task. In part that means i. ensuring comments clearly indicate the purpose of each instruction (or short set of instructions), rather than the literal interpretation, AND ii. nicely aligning the various labels, fields, and comments in your code.

Problems

Part A: Warm up Sequences

Problem 1: Register Swap

Write a sequence of MIPS instructions that transposes the values in registers $s0 and $s1. Your solution may only (if necessary) modify the contents of temporary registers ($t0–$t9).

For example, if $s0 contains 42 and $s1 contains -1 before your code runs, then after your code runs $s0 should contain -1 and $s1 should contain 42.

Problem 2: Memory Swap

Write a sequence of MIPS instructions that transposes the values at the memory addresses stored in registers $s0 and $s1. Your solution may only (if necessary) modify the contents of temporary registers ($t0–$t9).

Problem 3: Blefuscu to Lilliput

Occasions sometime arise when one needs to reverse the order of bytes presented to you by the host platform. This often happens when reading data produced by a platform with a different “endian-ness”.

Write a sequence of MIPS instructions that transposes the single 32-bit integer in register $s0 places the value in register $s1 with the bytes reversed. Your solution may only (if necessary) modify the contents of temporary registers ($t0–$t9). For example, if given the value 0xBA5EBA77, a byte flip would yield 0x77BA5EBA.

(Sadly, given 0xB7EF65C6 your procedure would not produce “Lilliput”.)

Problem 4: Product

Suppose your microchip’s ISA did not have an MDU that supported multiplication with a mult instruction. This can happen with extremely low cost devices that not only “make the common case fast” but pay very close attention to their minimal energy “budget”.

Write a sequence of instructions that multiplies the multiplicand value in register $s0 by the multiplier value in register $s1, using the elementary strategy of repeated addition. The result should be placed in register $s2. You should assume $s1 is non-negative. In addition to $s2, your solution may only (if necessary) modify the contents of temporary registers ($t0–$t9).

Part B: Play a Song

If we had a real microchip, we would use the signalling output pins of the device and its high-frequency clock to generate voltage wave forms that cause the magnetic cone in a speaker to oscillate at particular frequencies, thereby producing sound.

Since we’re using a simulation, we will have to fudge this capability somewhat. For now, it suffices to know that MARS supports a system call for generating MIDI sounds with particular a pitch, “instrument”, duration, and volume. One variant of the system call (33) returns after the duration has expired (the note has concluded), while the other (31) returns immediately so that other notes may be issued (nearly) synchronously.

We will use statically predeclared arrays in MIPS to store sequences of tones and durations. By iterating over these notes, your program will produce a song.

Unfortunately, the audio functionality will not transmit from MathLAN over FastX. Thus, to hear the audio you will need to copy the MARS Java Archive file to your own computer. (See the section Preparation above.) Please let the instructor know if you need any assistance with this.

The following steps will walk you through the tasks you will need to transform the starter file into a complete program for playing the song. When dealing with assembly code, it’s always good to make small changes (and also perhaps save your work in stages, so you can always revert to a previous known-working version). Thus, each step works you through a major change you’ll need to add for the final program to work correctly.

Step 1. Getting Started

Download the starter file play-song.asm and open it in MARS.
Assemble and execute the program.

If all worked well, you should hear the first few notes of a tune.

Taking a look at the code, the first thing you should observe at the top is the block of data labeled notes, which contains the full array of tones that specify the melody and some harmonies. Moving down to main in the text section, you’ll see the la (load address) instruction, which (unsurprisingly) tells the assembler to load the address of notes into register $s0. The assembler will know this address once it has translated all the text segments’ assembly instructions into machine language and concatenated the data segments’ data (converted into binary). (If you are curious, you can take a peek at Section 2.12 in our textbook.)

Step 2. Rolling the Loop

You’ll note the code is very repetitive in how it plays the first few notes of the song.

i. First, change the code so that it uses a simple loop to produce the first five notes. That is, instead of repeating the same basic block of instructions several times in the program text, the running program will run the same instructions, but the text should be a little bit more compact by using “instructions for making decisions”. ii. Next, generalize this so that it can play the entire sequence of notes. To do this, you’ll need to use the data at the label length. Note that this is a “variable” stored in memory, and length is its address. That means it’s something like a pointer to be dereferenced, but the easiest way to think about it, by way of analogy to what you’ve already seen in this program, is that it’s also like an array with only a single item in it.

When you have completed this step, you should be able to hear all the tones of the song in sequence, though they won’t yet have the right duration nor will their simultaneous playback work as intended. Those two steps are next.

Step 3. Multiplying Durations

So far each note is played by your program for the same duration (an eighth note in the original melody). In this step, you’ll add code to load the duration of each note, and scale the from the base duration accordingly.

i. Add code before your loop to initialize a pointer to durations (similar to the initialization for notes). Add code within your loop to load each duration corresponding to each note. Use a breakpoint in the debugger to stop after each load, and inspect the loaded value in the “Registers” view, making sure the numbers match the sequence given in the data section. ii. Finally, add code within your loop scale the original note time by the value duration value. Note you already wrote code in this assignment to accomplish that; you should use something like it here (do not use the mult instruction).

When you have completed this step, you should hear some longer notes. However, notes that are supposed to be played together still come in sequence. We’ll fix that in the next and final step.

Step 4. Playing Together

The preamble to this part mentioned that the MARS simulator has an option to return control to your program immediately after initiating a note play. In real hardware, such behavior can occur because there is independent hardware running to support the invoked command. Hard disk drives with spinning magnetic platters and moveable arms are a common example. A user program might ask the I/O controller to retrieve some data, but because we can often better utilize the computer’s time doing something else while the disk works to retrieve our data, the system returns control to us and promises to interrupt our processing when the data has arrived. We will return to the implementation of these notions in hardware toward the end of the semester; for now we will simply write a program that takes advantage of them.

In this step, you will enhance your program load the boolean values from yet another array that determine which sound system call should be invoked, the synchronous or aysnchronous version.

i. Add code before your loop to initialize a pointer to async. Add code within your loop to load each boolean value corresponding to whether the note is to be invoked asynchronously. BE CAREFUL! This is an array of bytes; not words. ii. Finally, modify the behavior within the loop so that when the boolean value loaded is 1 (true), the system call invoked is 31 (asynchronous), rather than 33 (synchronous). Note: Some particularly clever bit manipulation and arithmetic (with some correspondingly unclever comments) can make your code more concise and efficient by avoiding branching.

When you have completed this step, you should hear a complete and reasonably accurate rendition of the song.