lab02 : Binary Arithmetic, Bitwise Operators, and MIPS

num ready? description assigned due
lab02 true Binary Arithmetic, Bitwise Operators, and MIPS Thu 01/17 09:00AM Mon 01/21 11:59PM

Lab 2: Binary Arithmetic, Bitwise Operators, and MIPS

Due Monday, January 21st 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 ~zmatni/public_html/cs64w19/labs/2/*.txt ~zmatni/public_html/cs64w19/labs/2/*.h ~zmatni/public_html/cs64w19/labs/2/*.c ~zmatni/public_html/cs64w19/labs/2/mipsdemo.asm ~zmatni/public_html/cs64w19/labs/2/partner.txt ~zmatni/public_html/cs64w19/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).

You may need to change permissions on the files you just copied over (sometimes students have said that copying files over from other users only results in files that are read-only and thus not editable). You can do that with the UNIX command (done inside your lab2 subdirectory): 

chmod 664 *

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/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 are 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 might need to copy over QtSpim from csil. Check this out first and see if you can run QtSpim from the lab machine. Otherwise, to copy it over, do what is shown below, but substitute username with your username: 

scp username@csil-01.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 ~zmatni/public_html/cs64w19/resources/QtSpim .

If it still does not work, then download the source file from the program developer at: http://pages.cs.wisc.edu/~larus/spim.html

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 (OPTIONAL)

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:

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 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.

Copyright 2018, Ziad Matni, CS Dept, UC Santa Barbara. Adapted from work by Diana Franklin and Kyle Dewey. Permission to copy for non-commercial, non-profit, educational purposes granted, provided appropriate credit is given; all other rights reserved