Lab 2: Binary Arithmetic, Bitwise Operators, and MIPS

Due Friday, January 22 at 11:59:59 PM

Goals for This Week

By the time you have completed this work, you should be able to:

Provided files: Documentation:

Step by Step Instructions

There are four tasks that you need to complete for this week, each with multiple steps. You may complete them in any order, though you should start with the task you feel you will have the most questions on. The tasks are listed below:

The initial step below describes how to get the files you will need into the appropriate place. These files are used for all the different tasks.

Initial Step: Create a Directory for This Lab and Copy Over the Files

After you log in, go into your cs64 directory that you created last time:

cd cs64

Then create a new directory for this lab: lab2:

mkdir lab2

Then go into that directory.

Now copy over all of the files necessary for this week's tasks:

cp ~kyledewey/public_html/cs64/labs/2/*.txt ~kyledewey/public_html/cs64/labs/2/*.h ~kyledewey/public_html/cs64/labs/2/*.c ~kyledewey/public_html/cs64/labs/2/mipsdemo.asm ~kyledewey/public_html/cs64/labs/2/partner.txt ~kyledewey/public_html/cs64/resources/QtSpim .

Note the use of the trailing . in the above command, which stipulates that the specified files should be copied into the current directory. Also note the use of a glob (*), which specifies that all files of a given form should be chosen (e.g., *.txt stipulates all files that end in .txt).

Now you need to decide what task to begin in lab. If you understand binary addition and bitwise operators, it is recommended to begin with task 2 or 3. If you want extra practice with those concepts, you should start with task 1.

Task 1: Binary Addition and Bit-Level Operations

This task entails answering a series of questions focused on bit-level operations.

Open the file lab2problems.txt using an editor and answer the questions, just as with Lab 1.

Task 2: Bitwise Operations in C

In this task, you will write some random code as well as useful code that appears in a common MIPS processor simulator.

Step 1: Familiarizing Yourself With the Files and Compilation Process

There should be three files in your directory starting with the word Random. List just those files: 

ls Random*

Those three files contain a single program. If you have not taken CS24 before, you might not know how this works. RandomCode.h contains the prototypes for the functions you are going to implement. RandomCode.c contains the definitions or implementations of those functions. That is where you are going to add your code. I have also provided a handy test file with which you can test your code. This is RandomMain.c.

The way this works is that after the usual #include files, there is a line: 

#include "RandomCode.h"

This tells RandomMain.c to read in RandomCode.h for the function prototypes. This allows us to compile them separately. To compile them, do the following: 

gcc RandomCode.c RandomMain.c

Another way you could do this, utilizing the * to avoid typing as much, is:

gcc Random*.c

Step 2: Implementing Bit-Level Manipulation Routines

You will only be turning in RandomCode.c - we are going to provide the .h file and any test files for our test cases. I have provided the main so that you can test your files individually. Make sure you do not edit RandomCode.h. If you edit that file, then your solution will not work with our test cases.

Your assignment is to look at the functions in RandomCode.c and fill in the several lines necessary for each one. Each one should perform a series of bitwise operations (usually just one) on an integer, and return the resulting integer. The functions are roughly ordered easiest to hardest. The idea is to take what you understand about bitwise operations and apply it to high-level code.

You should use only bitwise operations, except for the following functions where you may also use if:

For the if functions, you may need to utilize the fact that in C, “true” is non-zero and “false” is zero. So this means that if you want to return true, you can return any number other than 0. For the functions that return signed results, be sure that sign extension is performed!

Here is a little sample to see how it might look. This does not match the main code provided for you - this is for illustrative purposes in the description only.

FunctionInputOutput
multiplyBy8756
setBit6to10x010x41
setBit3to00xffff0xfff7
flipBit50x010x21
ifBit7is00x77nonzero
ifBit3is10x770
unsignedBits0through50x3350x35
unsignedBits6through90x3b40xe
signedBits0through50x3fa0xfffffffa
signedBits6through90xcf70x03
signedBits0through50x38f0xf
signedBits6through90x38f0xfffffffe
setBits4through9(0xffffffff, 0x23)0xfffffe3f

The function that needs the most explanation is setBits4through9. You can think of this as replacing bits 4-9 (inclusive) with the second input's lowest bits. Leave the rest of the input's bits unchanged.

Any extracted bits should be returned in the lowest bits of the return value. For example, in unsignedBits6through9, if bits 0110 were extracted from the value, then 0110 with 28 leading zeros should be returned (we are working with 32-bit integers).

Specifically for this portion, we have also provided RandomCodeTester.c, which contains a small test suite which may be of interest to you. Instructions for compiling with the test suite, along with running it, are directly in RandomCodeTester.c. Note that this is not intended as a comprehensive test suite, but is instead there to make sure you are on the right track. You are encouraged to add your own tests to this suite.

Step 3: Instruction Decoding

Now you are ready to use bitwise operators to do something useful as a programmer. Processor simulators are used to evaluate implementation ideas long before processors are fabricated. These simulators read in compiled programs and execute them, performing the functions and reporting performance statistics for the theoretical processor. They are written in high-level languages such as C and C++.

You are going to write one function in DecodeCode.c - a function that divides an instruction into its parts. An instruction is a single 32-bit value in which many smaller values have been packed together. The instruction format is in your textbook. You do not need to read any of the text around it - all we care about is extracting fields opcode, rs, rt, rd, immediate, and funct (function code). Bit positions are expressed in an inclusive manner (e.g., bits 0 - 5 mean that all 6 bits are in the field).

You can look at your code that you wrote in RandomCode.c - this will be very useful to you. Fill in the lines of code in DecodeCode.c that extract each set of bits. Be mindful of whether it wants the answer expressed as a signed integer or an unsigned integer.

The setup for this task is similar to the last one. I have provided three files, only one of which you will turn in. You are free to edit either .c file, but you may not change the .h file (for if you do, it will not compile when it gets turned in).

Once again, list the files you will be using.

ls Decode*

You should see three files: DecodeCode.c, DecodeCode.h, and DecodeMain.c.

To compile this code, you do the following:

gcc DecodeCode.c DecodeMain.c

Another way you could do this, utilizing the * to avoid typing as much, is: 

gcc Decode*.c

Now you're ready to fill in the code! Edit DecodeCode.c.

Remember that you are only allowed to use bitwise operations to extract bits. You may not use multiplication or division. You may use an if statement for signed operations.

Specifically for this portion, we have also provided DecodeCodeTester.c, which contains a small test suite which may be of interest to you. Instructions for compiling with the test suite, along with running it, are directly in DecodeCodeTester.c. In addition, DecodeMain.c contains code for testing with more tests; see DecodeMain.c for details. Note that this is not intended as a comprehensive test suite, but is instead there to make sure you are on the right track. You are encouraged to add your own tests to this suite.

Task 3: QtSpim Tutorial

You are now ready for MIPS! We will use a simulator QtSpim to run our MIPS programs in this class. For this task, you will need to fill out the spimtutorial.txt questions. You may want to take a look at these questions before you start running the simulator, just to get a handle on exactly what it is you will need to learn.

Step 1: Get QtSpim

Assuming you are on one of the lab machines, then you will need to copy over QtSpim from csil. This can be done as shown below, substituting username with your username: 

scp username@csil.cs.ucsb.edu:/usr/bin/QtSpim .
<<enter password at the prompt>>

In case you have an issue with the above command, a version of QtSpim can also be copied directly from the course webpage, like so: 

cp ~kyledewey/public_html/cs64/resources/QtSpim .

Step 2: Load the Demonstration Program

Type: 

./QtSpim

...to begin the simulator. Once that is loaded, go to File->Load File to load the demo program mipsdemo.asm.

Understanding the Screens

The left box shows the values in the registers at any given time. So, when you are asked what value was in a certain register at a certain time, you can advance to that instruction using breakpoints and stepping, and when it gets to the right instruction, look at the register in question.

The right box shows the text segment, which contains all of the program instructions. As you are stepping along, you can see what instruction is executing. This is also how you can see where the program starts. The left column of that screen tells the address of the instruction. The next column shows the hexadecimal representation of the actual instruction. The 3rd column shows what the machine receives as the instruction, and the fourth column shows what the original MIPS instruction was. We will learn more about these parts in class later.

The right box also shows the data segments if you choose the Data tab. Here you can see the global variables that were declared in the data segment. The left-hand column shows the address of the beginning of that set of data. If you click on Data now, you will recognize all of the strings that are being used to print out data.

Step 3: Set a Breakpoint

First, make sure the Text tab is highlighted. Look at the instruction that says: 

jal 0x00400024 [main]

This means that the first instruction of main is located at address 0x00400024. The left-hand column shows the address of each instruction. Locate the one with that address (ori $2, $0, 4). Right click on it and choose Set Breakpoint. If it works, a red indicator will show up to the left of the address.

Step 4: Step Through Code

Click on the green arrow (the “play” button) to start running the code.

When it gets to the breakpoint you set in the previous step and asks if you want to continue, cluck Single Step.

To advance a single single instruction, click the 1-2-3 numbered list, or press F10 on your keyboard. Do this to confirm the answers you get from inspecting the code.

Step 5: Answer Questions About the Code

Answer the questions in spimtutorial.txt. You may find it helpful during this process to use breakpoints and to step through individual instructions, and watching what happens to both the registers and to the Console screen. The Console screen acts as an input/output terminal to your program. Just as with a normal terminal, if it is waiting for input, it will not continue until you type something into that screen and press return.

You are being exposed to a lot of new material in a very short amount of time here, and it can be quite overwhelming at first. Keep in mind that you are learning not only a new language, but a new way of thinking, along with a new tool (QtSpim). Most of all, you have been doing this for only around a week - if this feels difficult, it is because it is difficult. If you want to read more, or just have more potentially helpful information in your grasp, the links below may be of some assistance:

Task 4: First MIPS Program

The purpose of this task is to gain more familiarity with QtSpim, and to get used to programming in assembly. For this task, you will write code that performs a series of numeric transformations on some input number. An example session follows, where the user typed in 805 after the program prompted “What are the first 3 digits of your phone number? ”. Other than the initial input 805 which is on the same line as the prompt, all text was produced by the program. 

What are the first 3 digits of your phone number? 805
805
Add it to itself
1610
Multiply by 80
128800
Add 450
129250
Divide by 5
25850
Subtract 10
25840
Divide by 4
6460
Subtract 20
6440
Divide by 8
805

Write a program in MIPS assembly that performs the above numeric transformations, and describes it to the user in the same way as the session above. You may assume that the user will input a valid non-negative three-digit number that will not entail a division by zero with respect to the numeric transformations. For full credit, your program must produce the exact same output, including prompts. For this reason, we recommend copying and pasting the above prompts into your code rather than trying to retype them, so as to avoid any typos.

Save your code in a file called MagicMathTricks.asm.

We have repeated the operations you need to perform below, and annotated where you should use bitwise operations as opposed to performing division directly. In these operations, “it” refers to the running result as it is being computed, and generally refers to the result of the last operation.

  1. Get the digits from the user. You may assume they form a valid non-negative three-digit number which will not cause a division by zero to occur downstream.
  2. Add it to itself
  3. Multiply it by 80
  4. Add 450 to it
  5. Divide it by 5
  6. Subtract 10 from it
  7. Divide it by 4 (use bitwise operations)
  8. Subtract 20 from it
  9. Divide it by 8 (use bitwise operations)

For full credit, your code must exit gracefully. This means that at the end of your program, you should use the syscall instruction to exit. A code snippet that performs this correctly is shown below: 

li $v0, 10
syscall

You may use any MIPS instructions or psuedoinstructions you want in order to implement this task. However, you will be somewhat restricted on exams. You may want to read the grading policies regarding MIPS assembly instructions for more information.

Grading for the Code

For the commenting, try to describe higher-level ideas, as opposed to merely saying what the instruction does (which will quickly become second-nature). For example, instead of saying something like “shift left by 1”, say something like “multiply by 2”. As another example, instead of saying “move 4 into register $vo”, say something like “prepare to print”. For now, we are going to be fairly lenient on commenting, and mostly just check to see if something is commented. This is to give you an opportunity to get some feedback on your commenting before things really get underway. Later on, the grading for commenting will get more strict, and may be weighted more heavily.

Turn in Everything Using turnin

If you partnered with someone, record the email address they are using for the class in partner.txt. For example, if your partner had the email address foo@bar.com, then the contents of partner.txt should be the following (and only the following): 

Partner: foo@bar.com

If you did not partner with anyone, you do not need to (and should not) edit partner.txt.

Assuming you are in the cs64/lab2 directory you created at the beginning, you can send in your answers via the following command:

turnin lab2@cs64 lab2problems.txt RandomCode.c DecodeCode.c spimtutorial.txt MagicMathTricks.asm partner.txt

You may turn in the same assignment up to 100 times, which is useful if you are working on it incrementally. Note that only the last version you submitted will be graded.

Even if you did not partner with anyone, should should still turn in partner.txt, which should not have been modified.

Note that the above turnin command does not ask for all files to be submitted. This is intentional. The rest of the files (e.g., RandomCode.h) should not have been modified, and so they do not differ from what was distributed. That said, if you did modify these files, please make sure that they work correctly with the original unmodified files. We will test with the original files on our end, so if they do not work with the original files, then they might as well not work at all.

Prepared for Computer Science 64 by Diana Franklin, with slight adaptation by Kyle Dewey.