Reduced Machine Instruction Tutorial

Thomas Finley, September 2000

Contents and Introduction

This document is intended to provide examples of simple programs written in the RMI that demonstrate basic programming in RMI, as well as outline what you can and cannot do when programming with RMI. RMI is created by Professor Wagner, and serves as an example of an instruction set with minimal syntax, but potentially unlimited functionality. RMI serves the basis for problem P3.

How this "#define" Stuff is Supposed to Work

For the curious...

The definitions that pepper the program are what are called macros. Suppose we have this definition at the beginning of our source code.

#define SUB(X,A,B) \
        X = (A=A) - B; ICT++;

After that, supposing we had three variables "x", "y", and "z", we can subtract y from z and store the result in x through by inserting the following in our code.

SUB(x, y, z);

This looks similar to a function, and for most intents and purposes you can get away with treating it as such. However, it is not a function. What actually happens is that when you compile your code, something called the preprocessor goes through your code and looks for these macros. Suppose it runs into that SUB(x, y, z). It takes those codes, and since the x is in the X place, and the y is in the A place, and the z is in the B place, wherever in that definition there is an X you get an x, wherever there is an A you get a y, and wherever there is a B you get a z. This snippet of code then replaces the invocation of SUB in your source, and once all these macros have been replaced THEN the program is compiled. So, in the end, it's as though you typed in the following line of code:

x = (y=y) - z; ICT++;

Not that the X, A, B are not variables in themselves. They are merely "placeholders" that are replaced with whatever _text_ you pass them. It doesn't even have to be anything valid. If you say

SUB(and surely the future shall be better for thee than the past,
    and in the end shall your Lord be bounteous to thee, and thou
    be satisfied);

that will yield (if I'm not mistaken)

and surely the future shall be better for thee than the past = (and
in the end shall your Lord be bounteous to thee=and in the end shall
your Lord be bounteous to thee) - and thou be satisfied; ICT++;

The theological implications are enormous, I suppose, but what's important is that you see how macros in the preprocessor can be used (and misused), and also that these defined macros are not so much about passing values as they are about copying text.

About the "\"s, in case you wonder, this is taken from the assignment description for the RMI homework:

The "\" that terminates some lines in the #defines "continues" the
definition to another line of input; the"body" of a #define extends
to the end of the current logical line of text. To allow "define
bodies" of several input lines, the "\" is used to end intermediate
input lines that don't end the logical line.

But you already knew that, since you read the assignment description. Didn't you?


Setting Up your RMI Environment

Now, all of these examples suppose that you are sufficiently intelligent enough to have already "cut and pasted" the RMI instructions, and were also man (or woman) enough to implement the special shortcuts (ADD and BNZ). A short note you must heed...

#define BNZ(A,S) \
        BLTZ(A,S); \
        SUB(t,Zero,A);  \

The temp variable "t" that Prof. Wagner mentions in the description, which is necessary for this "BNZ" to work, is misrepresented as "T" in the last BLTZ instruction. Simply change "T" to "t", and it executes the intended function. "Which is?" We'll get to that.

Like the assignment description says, the ADD and BNZ quasi-instructions both make use of the variables "t" and "Zero", with the variable Zero always remaining 0; in order for the ADD nad BNZ instructions to work properly, these variables have to be declared. The assignment description also suggests setting up a variable "M1" to always hold -1.

About XIT()

There was some small confusion regarding XIT().

#define XIT() \
        printf("%d RMI Instructions executed.\n", ICT);

One person asked me during my office hours yesterday, "now, this XIT macro, HOW does it end the program?" It doesn't, really. All it does is print how many RMI instructions you used (if you'll notice, there are ICT++ in every basic RMI instruction, so the variable ICT keeps a running count). Technically speaking, you could insert XIT()s throughout your entire program.

However, since the idea is to see how many RMI instructions your program executes during the entire course of its execution, you'd better insert it right at the end of your program just before the end of the main() statement lest the grader suspect you of chicanery.

About Procedures

You're allowed to call procedures and pass values to them, but you can only return values from the procedure through use of a global variable. However, for P3 you really needn't use procedures, and just looking over my code for P3, I don't see how a procedure could have helped me out at all, really. However, your mileage may vary.

Stuff you CAN'T Do

Supposing you have the integer myInt, and you want to add it to itself. You CAN'T do something like

SUB(myInt, myInt, -myInt);

The reason is that when you write (-myInt), you're performing an operation on myInt. Basically, every variable you use in your program beyond the initial declaration of the variable must appear in an RMI instruction by itself, with no pendants or operators attached to it. All operations must be done using the RMI instructions.

However, that is not to say that you can't do something like the following:

SUB(myInt, myInt, -4);

-4 is just a simple constant, so you CAN do that.

BLTZ(-1, SomeLabel);

Whenever you use an RMI instruction, if the corresponding "placeholder" is an X or an A, you MUST use a variable in that place in order for it to be considered correct. However, if it's a B, feel free to use a constant.

Example Code

Okay, now that the preamble is done with, time for the good stuff... the meat and potatoes, if you will. In all of these examples, to save space I only include the "main()" function. I assume that "#include <stdio.h>" and the "#defines" Prof. Wagner provided and the global variables ICT, t, Zero, and M1 have all been implemented correctly. I'm not going to tell you outright how to put it together, and I don't provide it partly because it would take up so much room and partly becuase people would simply cut and paste if I did, and use that as a starting template for their code. First of all, setting it up is simple to do, and if you find it's NOT simple to do, that reveals a lack of understanding on your part of C convention, so it's good that you struggle to get it right so that you actually learn.

In many example I provide sample runs of the program from the command line. I always compile my programs as "tester".

Let's look at some simple programs.

The Idiotic Calculator

This is a simple calculator that only performs subtraction (and is hence idiotic). What it does is accepts two numbers, subtract the second from the first, and print the result.

main() {
  int operand1, operand2, result;

  R("%d", operand1);
  R("%d", operand2);
  SUB(result, operand1, operand2);
  P("%d-", operand1);
  P("%d=", operand2);
  P("%d\n", result);

After some integer variable declarations, R("%d", operand1) reads a number into "operand1", and R("%d", operand2) reads a number into "operand2". Then, we get "result=operand1-operand2" by executing SUB(result, operand1, operand2). After that, P("%d-", operand1) prints out the value of "operand1" plus a negative sign, P("%d=", operand2) prints out the value of "operand2" plus an equals sign, and P("%d\n", result) prints out the result of the subtraction, the variable "result", and tacks on a line feed. The program then calls XIT() to see how many RMI instructions were called, and the program terminates.

Some runs of this simple program are provided below.

[98] twf@teer15% tester
4 9
6 RMI instructions executed.
[99] twf@teer15% tester
100000 1 
6 RMI instructions executed.

Not a strenuous mental exercise by any stretch, but let's see if we can't make things a bit more interesting with discussion of elementary control flow.

Countdown Program (with simple control flow)

Remember when you were eight and first learning how to program, and your favorite program you created was the countdown program written on an Apple IIe in BASIC that read in a number and counted down from that mark? No? Well then, you had a deprived and sheltered childhood. I pity you and pray for your immortal soul.

The thing is, RMI is a lot like BASIC. Remember writing GOTO 10 and GOTO 495 and GOTO this and GOTO that, and each line of "code" you wrote was prefixed with a number? Well, unbeknownst to many novice programmers, that feature (albeit in a slightly more sophisticated form) survives in the modern programming languages to this day. It has great applications like breaking out of ugly nested loops and the like, but for our purposes we'll use it for simple control flow, just like BASIC did.

So now Although the R (read), P (print), ADD (uh, add), and SUB (subtract) have an obvious mnemonic name that gives away what they do, the instruction "BLTZ" and quasi-instruction "BNZ" are less obvious: they are "Branch if Less Than Zero" and "Branch if Not Zero."

Notice those lines in that code that are a single line ended with a colon (:). Shouldn't that be a semicolon (;), you ask? No. These things are called labels. Ignoring the RMI for a second, let's look at some straight C code.

#include <stdio.h>
main() {
  goto PastThePrintf;
  printf("Wah!  I'll never be printed!\n");

What this program does upon execution is, when it reaches the "goto PastThePrintf", it actually goes directly to the point in the code where it says "PastThePrintf:", and resumes execution from there. If you run it, you'll notice that "Wah! I'll never be printed!" is never printed.

In RMI you CANNOT use "goto" statements on their own, but must call them in the context of the RMI instruction BLTZ and quasi-instruction BNZ that use them.

Looking at the #define statement for BLTZ...

    #define BLTZ(A,S) \
            ICT++; if (A<0) goto S;

So, if whatever variable you give in place of A is less than zero, it goes to the label represented by S.

This functionality can be demonstrated in an example. So, without further ado, here is a countdown program that offers some simple control flow.

main() {
  int countDown;
  R("%d", countDown);
  BLTZ(countDown, JustExit);
  BLTZ(M1, DoCount);
  SUB(countDown, countDown, 1);
  P("%d...\n", countDown);
  BNZ(countDown, BeginLoop);
  P("BLAST OFF!\n", M1);


After the initial variable declaration of "countDown", the program reads a value into "countDown" using R("%d", countDown). It then tests this number to see if it's less than zero using BLTZ(countDown, JustExit) (that is, branch if less than zero).

If "countDown" is less than zero, the program jumps to "JustExit", where it runs into XIT(), which prints out the number of RMI instructions executed.

However, if "countDown" is not less than zero, it simply executes the next instructions, BLTZ(M1, DoCount). Since M1 == -1, and -1 < 0, it will jump to "DoCount:". The next instruction past "DoCount:" is P("%d...\n", countDown), which prints out the number of our countdown. The next instruction is BNZ... branch if not zero... of the form BNZ(countDown, BeginLoop). That is, if countdown != 0, then goto BeginLoop.

If we entered 10 for our "countDown" variable, since 10 != 0, we goto BeginLoop and the next instruction is SUB(countDown, countDown, 1). This merely decrements "countDown" by one. Then the P("%d...\n", countDown) instruction is executed again, etc etc etc.

Eventually, countDown WILL equal zero, and when that happens, BNZ(countDown, BeginLoop) will not jump to BeginLoop. It allows the program to continue working, and the next statement is P("BLAST OFF!\n", M1). Notice my use of M1 even though there is no conversion specifier for a number in the format string "BLAST OFF!\n". However, I need to put some variable in that second P argument, and so I just insert M1 as a "dummy" variable. I could have juts as well have used "countDown" or "Zero" or whatever.

Here are some sample runs of this program. Notice how when you insert a negative number (-10 is used in this example) the program does nothing.

[106] twf@teer15% tester
58 RMI instructions executed.
[107] twf@teer15% tester
2 RMI instructions executed.
[108] twf@teer15% tester
8 RMI instructions executed.

The Negative Tester

This program tests to see whether an input number is negative or not.

main() {
  int myInt;

  R("%d", myInt);
  BLTZ(myInt, IsNegative);
  P("It's not negative!\n", Zero);
  BLTZ(M1, PastNegativeTest);
  P("It IS negative!\n", Zero);

What this program does is read in a single number, and tell whether it is negeative or not. Tracing through the program, first we have the declaration of myInt. Then, we have R("%d", myInt), which reads in a number from stdin. Then, we have BLTZ(myInt, IsNegative).

If myInt is less than zero, then we branch to the label IsNegative. The next instruction is P("It IS negative!\n", Zero). This simply prints out "It IS negative!", as you might guess, but the reason I also include a Zero there is because the P RMI instruction requires that a variable be passed. Since I am not printing out a variable, simply a line of text, I just pass along Zero. I could just have easily passed along myInt, t, M1, or anything else you'd like, just so long as it is a variable. Once done with that, the next instruction executed is XIT(), which prints the number of RMI instructions used.

If myInt is not less than zero, that is, if the BLTZ(myInt, IsNegative) does not result in a branch to "IsNegative", the program continues on its merry way without interruption, arriving at the P("It's not negative!\n", Zero) statement. Note again that I used Zero as a "dummy" variable for P. The next line is BLTZ(M1, PastNegativeTest). Note that since M1 has been defined to be -1, this branch condition will ALWAYS be satisfied, so that it ALWAYS branches directly to PastNegativeTest. The reason why we want this is so that the P("It IS negative!", Zero) RMI instruction is skipped over and not executed. After all, it simply will not do to have the program saying that a number is both not negative and negative. After that, the XIT() instruction is executed, and the program terminates.

Here are some sample runs of the program.

[75] twf@teer15% tester
It's not negative!
4 RMI instructions executed.
[76] twf@teer15% tester
It IS negative!
3 RMI instructions executed.
[77] twf@teer15% tester
It's not negative!
4 RMI instructions executed.

The Imbecilic Calculator

Not quite as stupid as the idiotic calculator, but still pretty stupid, is the imbecilic calculator. It performs addition AND subtraction.

main() {
  int operand1, operand2, temp, result;
  char myOperator;
  R("%d", operand1);
  R("%c", myOperator);
  R("%d", operand2);

  SUB(temp, myOperator, '+');
  BNZ(temp, IsNotAddition);
  /* Now we know myOperator is '+', so we do addition */
  ADD(result, operand1, operand2);
  BLTZ(M1, ProduceOutput);
  SUB(temp, myOperator, '-');
  BNZ(temp, JustExit);
  /* Now we know myOperator is '-', so we do subtraction */
  SUB(result, operand1, operand2);

  P("%d", operand1);
  P("%c", myOperator);
  P("%d=", operand2);
  P("%d\n", result);

Rather than go through line by line, now that your understanding is somewhat more advanced, presumably, I'm going to simply give the gist of the program. After some int and char variable declarations, a number, a character, and another number is read in. That character is SUPPOSED to be either a "-" or a "+".

(Note that this input scheme is not robust: input MUST be of the form "5+3" and not something like "5 + 3" with spaces between the numbers and operators, because after reading the 5, the next char to be read will be a space, leading the program to not recognize that an operator was input. I could have designed a more robust income scheme, even with something as primitive as RMI, but that would take more time and would be confusing.)

The next thing is that '+', the ASCII value for the character +, is subtracted from "myOperator" and stored in "temp". If "myOperator" IS '+', then obviously temp will hold zero. We then branch to "IsNotAddition" if temp is not zero, and hence myOperator is NOT '+'.

However, if this branch is not satisfied and "temp" is zero, we know that the operator is '+', so we add "operand1" with "operand2", and store the result in "result". Then we jump to ProduceOutput. (More on this later.)

If the branch IS satisfied, we go to the "IsNotAddition" label. We then test to see if "myOperator" is '-' in the same way we tested to see if "myOperator" is '+'. If it isn't, then "myOperator" is neither '+' nor '-', so we jump to "JustExit", producing no output.

However, if we don't jump, then we know that "myOperator" is '-', so we subtract "operand2" from "operand1", and store the result in "result". Now, the portion of code that did the jump to "ProduceOutput" in our addition code was necessary, but since the code to produce output is right below the subtract code anyway, any jump is unnecessary.

The code following the "ProduceOutput" label simply prints out the expression the user gave on entering the program, and prints the result.

Here are some sample runs.

[89] twf@teer15% tester
7 RMI instructions executed.
[90] twf@teer15% tester
14 RMI instructions executed.
[91] twf@teer15% tester
16 RMI instructions executed.

That should just about do it.

Thomas Finley 2000