MIPS Programming

Preparation

To easily simulate MIPS code in software, separately from the PIC32 hardware, we will use the MIPS Assembly and Runtime Simulator MARS. We can’t make it beep and blink, but it will be good enough for us to verify that you can think structurally about MIPS operations.

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 to your own computer and run it there, using a similar invocation of Java.

  1. Download the starter file assignment4.asm

  2. Open the file in MARS.

  3. To assemble your code, click “Assemble” under the Run menu (or the Screwdriver and Wrench icon in the toolbar).

  4. 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 points may arise as you wish to diagnose certain behaviors.

Guidelines

  1. Note that the MARS simulator does not enable simulation of the branch/jump delay by default. Please do not enable it, because branch delays will not be activated during grading for correctness. However, you should keep the practice of minding the branch delay slot by including a nop statement wherever the delay slot would ordinarily occur.

  2. The only pseudoinstructions you may use for completing the procedures in this assignment are move and nop. You may use li for your testing in main, because that portion will not be graded.

  3. Your procedures must follow all MIPS calling conventions (see Figures 2.11, 2.12, and 2.14).

  4. 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 ensuring comments clearly indicate the purpose of each instruction (or short set of instructions), rather than the literal interpretation and nicely aligning the various labels, fields, and comments in your code.

Problems

Problem 1: 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”.

Complete a procedure byteflip that takes a single 32-bit integer in register $a0 and returns the value in register $v0 with the bytes reversed. For example, if given the value 0xBA5EBA77, a byte flip would yield 0x77BA5EBA.

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

Problem 2: Going to Extremes

Complete a procedure extremes that takes four 32-bit signed integers in registers $a0, $a1, $a2, and $a3 and returns the smallest of the four values in register $v0 and the largest of the four values in $v1.

Problem 3: The Remains of the Day

Branching gets more interesting when loops are involved.

Translate the following C procedure into MIPS to calculate the remainder of two 32-bit integers. We can consider them signed, but they should be positive.

// Repeatedly subtract (that's division after all) until we find the remainder
int
remainder(int a, int b)
{
  if (a < b)
    return a;
  int t;
  do
    t = a-b;
    if (t < 0)
      return a;
    else
      a = t;
  } while (1);
} // remainder

You may discover that MIPS has a rem instruction to do just this, but for now we’re practicing the translation process. (You can certainly use rem in your testing, but your procedure should not use it.)

Problem 4: Who is the Greatest?

Euclid’s algorithm for finding the greatest common divisor between two numbers can be elegantly expressed recursively as follows:

int
gcd(int m, int n) {
  if (n==0)
    return m;
  else
    return gcd(n, remainder(m,n));
} // gcd

  1. Translate this recursive function into MIPS “as is”, being sure to follow all the MIPS calling conventions. That is, you should use the stack and jal instructions to accomplish the recursion. You should use your remainder procedure, rather than the rem instruction.

  2. Write a version of the function in MIPS using tail recursion to accomplish the iteration. Call this version gcdtail.

Copyright © Jerod Weinman

CC-BY-NC-SA This work is licensed under a Creative Commons Attribution NonCommercial ShareAlike 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/4.0/ or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.