# 程序代写代做代考 scheme c++ mips assembly SO

SO

LO

LA

B

CS233 Lab 7 Handout

“He who hasn’t hacked assembly language as a youth has no heart. He who does so as an adult has

no brain.” – John Moore

“Real programmers can write assembly code in any language.” – Larry Wall

Learning Objectives

This lab involves writing MIPS procedures. Specifically, the concepts involved are:

1. Arithmetic and logical operations in MIPS

2. Arrays and pointers in MIPS

3. MIPS control flow (conditionals, loops, etc.)

4. MIPS function calling conventions

Work that needs to be handed in (via SVN)

First deadline

1. detect_parity.s: implement the detect_parity function in MIPS. Run with:

QtSpim -file common.s detect_parity_main.s detect_parity.s

2. max_conts_bits_in_common.s: implement the max_conts_bits_in_common func-

tion in MIPS. Run with:

QtSpim -file common.s max_conts_bits_in_common_main.s max_conts_bits_in_common.s

3. twisted_sum_array.s: implement the twisted_sum_array function in MIPS. Run

with:

QtSpim -file common.s twisted_sum_array_main.s twisted_sum_array.s

Second deadline

1. accumulate.s: implement the accumulate function in MIPS. Run with:

QtSpim -file common.s accumulate_main.s accumulate.s detect_parity.s

max_conts_bits_in_common.s

2. calculate_identity.s: implement the calculate_identity function in MIPS. Run

with:

QtSpim -file common.s calculate_identity_main.s calculate_identity.s accumulate.s

twisted_sum_array.s max_conts_bits_in_common.s detect_parity.s

Important!

Unlike previous labs, this is a solo lab and you may not work with

anyone else on this lab.

We also cannot stress enough the importance of reading the entire

lab handout.

For Lab 7, we are providing all “main” files (e.g., detect_parity_main.s) and files for you to

implement your functions (e.g., detect_parity.s). We will need to load both of these files into

QtSpim to test your code.

We will only be grading the files you implement your functions in, and we will do so with our own

copy of the main files, so make sure that your code works correctly with original copies of those.

1

SO

LO

LA

B

CS233 Lab 7 Handout

Guidelines

• You may use any MIPS instructions or pseudo-instructions that you want.

• Follow all function-calling and register-saving conventions from lecture. If you don’t know

what these are, please ask someone. We will test your code thoroughly to verify that

you followed calling conventions.

• We will be testing your code using the EWS Linux machines, so we will consider what runs

on those machines to be the final word on correctness. Be sure to test your code on those

machines.

• Our test programs will try to break your code. You are encouraged to create your own

test programs to verify the correctness of your code. One good test is to run your procedure

multiple times from the same main function.

• We have a set of style guidelines for MIPS (https://wiki.illinois.edu//wiki/

display/cs233sp17/MIPS+style+guidelines). Assembly code can be close to impos-

sible to understand and debug without sufficient formatting and debugging, and doing so isn’t

an efficient use of our time in office hours. Therefore, we will only assist you in office

hours if your MIPS meets a certain standard of formatting and commenting. If

it doesn’t, we’ll ask you to format and comment it before we help you. Specifically, as far as

formatting is concerned, the first example on the linked page definitely won’t fly, the second

is iffy, and the third is really what you should be going for. For commenting, since we’re

translating C to MIPS, it should be immediately clear from your comments what C statement

each MIPS instruction is corresponding to; the commenting scheme on the linked page is one

way (but not the only one) to achieve this.

2

https://wiki.illinois.edu//wiki/display/cs233sp17/MIPS+style+guidelines

https://wiki.illinois.edu//wiki/display/cs233sp17/MIPS+style+guidelines

SO

LO

LA

B

CS233 Lab 7 Handout

Loops and Conditionals and Logic, Oh My! [30 points]

Detecting Parity [10 points]

This function determines if an integer’s number of 1 bits is even. It takes one input: an integer

number, and returns 1 if number has an even number of 1 bits (otherwise, returns 0). Similar

to count_ones from Lab2, this function counts the number of 1 bits in number. Then it uses

modulus 2 to check if bits_counted is even or odd.

The function below is an implemention of detecting parity.

int

detect_parity(int number) {

int bits_counted = 0;

int return_value = 1;

for (int i = 0; i < INT_SIZE; i++) {
int bit = (number >> i) & 1;

// zero is false, anything else is true

if (bit) {

bits_counted++;

}

}

if (bits_counted % 2 != 0) {

return_value = 0;

}

return return_value;

}

The C++ code and a test case for detect_parity() function are in the file named lab7.cpp.

You have to write a MIPS translation of this function in detect_parity.s. There are some

test cases in the assembly file named detect_parity_main.s, and you can compile and run the

C++ code and compare its output to your MIPS code to verify its correctness. Feel free to add

more test cases to both the C++ and detect_parity_main.s.

3

SO

LO

LA

B

CS233 Lab 7 Handout

Maximum Continuous Bits in Common [10 points]

This function extracts the maximum number of continous 1 bits that occur in the same indices in

two integers. It takes two inputs: an integer a and an integer b, and returns an integer max_seen.

The function below is an implemention of maximum continuous bits in common.

int

max_conts_bits_in_common(int a, int b) {

int bits_seen = 0;

int max_seen = 0;

int c = a & b;

for (int i = 0; i < INT_SIZE; i++) {
int bit = (c >> i) & 1;

if (bit) {

bits_seen++;

} else {

if (bits_seen > max_seen) {

max_seen = bits_seen;

}

bits_seen = 0;

}

}

if (bits_seen > max_seen) {

max_seen = bits_seen;

}

return max_seen;

}

The function ands the two input numbers together into a new integer c, and searches c for the

longest sequence of continuous 1 bits. It does this search by bit shifting each bit of c to the end of

the integer (i.e. to the LSB) and checking if it is equal to 1. It uses the integer bits_seen as a

counter, to keep track of the number of continuous 1 bits seen so far. If bits_seen is greater than

max_seen, it updates max_seen. For example, if a = 8b’10111111, b = 8b’10101111,

then max_seen = 4.

The C++ code and a test case for max_conts_bits_in_common() are in the file named

lab7.cpp. You have to write a MIPS translation of this function in max_conts_bits_in_common.s.

There are some test cases in the assembly file named max_conts_bits_in_common_main.s, and

you can compile and run the C++ code and compare its output to your MIPS code to verify its correct-

ness. Feel free to add more test cases to both the C++ and max_conts_bits_in_common_main.s.

4

SO

LO

LA

B

CS233 Lab 7 Handout

Twisted Sum Array [10 points]

This function sums all values of a 1D array together with a twist: the running sum is first divided

by 2 if the mirrored value of i in v is odd. It takes two inputs: an integer pointer v and an integer

length, and returns an integer sum.

The function below is an implemention of twisted sum of an array.

int

twisted_sum_array(int *v, int length) {

int sum = 0;

for (int i = 0; i < length; i++) {
if (v[length - 1 - i] & 1) {
sum >>= 1;

}

sum += v[i];

}

return sum;

}

The function iterates through the array and keeps a running total of the sum of values in the array.

But don’t forget the twist! If the mirrored value of a value in the array is odd, the running total is

divided by 2. For example:

1. Suppose v = [4, 3, 2]. We know that length = 3. We begin with sum = 0.

2. i = 0:

(a) First extract the mirrored value: v[length – 1 – i] = v[2] = 2

(b) Since the mirrored value, 2, is not odd, we do not divide the running sum by 2.

(c) Add v[i] to running sum: sum += 4. Then, sum = 4.

3. i = 1:

(a) First extract the mirrored value: v[length – 1 – i] = v[1] = 3

(b) Since the mirrored value, 3, is odd, we do divide the running sum by 2: sum /= 2.

Then, sum = 2

(c) Add v[i] to running sum: sum += 3. Then, sum = 5

4. i = 2:

(a) First extract the mirrored value: v[length – 1 – i] = v[0] = 4

(b) Since the mirrored value, 4, is not odd, we do not divide the running sum by 2.

(c) Add v[i] to running sum: sum += 2. Finally, sum = 7

The C++ code and a test case for twisted_sum_array() are in the file named lab7.cpp. You

have to write a MIPS translation of this function in twisted_sum_array.s. There are some test

cases in the assembly file named twisted_sum_array_main.s, and you can compile and run

the C++ code and compare its output to your MIPS code to verify its correctness. Feel free to add

more test cases to both the C++ and twisted_sum_array_main.s.

5

SO

LO

LA

B

CS233 Lab 7 Handout

Function Calls & Nested Loops [70 points]

In the second part of this lab, you will learn more about function calls and more complex loops.

Accumulate [35 points]

The first function will accumulate a value into a running total, based on some rules that will use

two of the functions you wrote in part 1 of this lab. It takes two inputs: an integer total that

represents a running total and an integer value. It returns an integer total.

The function below is an implemention of this accumulation process.

int

accumulate(int total, int value) {

if (max_conts_bits_in_common(total, value) >= 2) {

total = total | value;

} else if (detect_parity(value) == 0) {

total = total + value;

} else {

total = total * value;

}

return total;

}

If value and total have 2 or more continuous 1 bits in common, you will return the result of

value and total or’ed together. Otherwise, if value is odd, you will return the result of value

and total add’ed together. Finally, if neither of the above conditions are true, you will return the

result of value and total multiply’ed together.

Some examples:

• If total = 8b’10111111, value = 8b’10101111

There are 4 continuous 1 bits in common, so we should or.

8b’10111111 | 8b’10101111 = 8b’10111111

Then total = 8b’10111111.

• If total = 8b’00111111, value = 8b’01010101

There is only 1 continuous 1 bit in common, so we shouldn’t or.

value is odd, so we should add.

8b’00111111 + 8b’01010101 = 8b’10010100.

Then total = 8b’10010100.

• If total = 8b’00111111, value = 8b’00000010

There is only 1 continuous 1 bit in common, so we shouldn’t or.

value is even, so we shouldn’t add.

Therefore, we should multiply.

total = 8b’00111111 × 8b’00000010 = 8b’01111110.

Then total = 8b’01111110.

Your task is to translate this function to MIPS in accumulate.s. Some test cases are provided in

6

SO

LO

LA

B

CS233 Lab 7 Handout

accumulate_main.s, and you can compile and run the C++ from lab7.cpp and compare its

output to your MIPS code to verify its correctness. You’re encouraged to add more test cases to

both the C++ and accumulate_main.s.

Note that accumulate.s calls your detect_parity function from detect_parity.s and your

max_conts_bits_in_common function from max_conts_bits_in_common.s. You should

use jal to call these functions in your code. Do NOT inline max_conts_bits_in_common or

detect_parity. Also, do not include the max_conts_bits_in_common or detect_parity

functions in the accumulate.s file. Our tests will ensure that you’re actually calling the function.

We will release our own versions of detect_parity and max_conts_bits_in_common after the

first part of the lab is due. We recommend that you copy over our solutions into detect_parity.s

and max_conts_bits_in_common.s files so that you can test accumulate.s in the same

environment that we will run the autograder.

7

SO

LO

LA

B

CS233 Lab 7 Handout

Calculating Identity [35 points]

The second function you will need to write for Part 2 of this lab will calculate the secret identity

of a square array by accumulating the values in the array using the function accumulate that you

wrote previously. It takes in v (a 1D array with size × size values), size (the side length of v),

and returns the integer identity.

The function below is an implemention of calculating the secret identity of an array in C++.

int turns[4] = {1, 0, -1, 0}; // We take care of declaring this for you

int

calculate_identity(int *v, int size) {

int dist = size;

int total = 0;

int idx = -1;

turns[1] = size;

turns[3] = -size;

while (dist > 0) {

for (int i = 0; i < 4; i++) { for (int j = 0; j < dist; j++) { idx = idx + turns[i]; total = accumulate(total, v[idx]); v[idx] = total; } if (i % 2 == 0) { dist--; } } } return twisted_sum_array(v, size * size); } Your task is to translate this function to MIPS in calculate_identity.s. Some test cases are provided in calculate_identity_main.s, and you can compile and run the C++ from lab7.cpp and compare its output to your MIPS code to verify its correctness. You’re encouraged to add more test cases to both the C++ and calculate_identity_main.s. Note that calculate_identity.s calls your accumulate function from accumulate.s and your twisted_sum_array function from twisted_sum_array.s. You should use jal to call these functions in your code. Do NOT inline accumulate or twisted_sum_array. Also, do not include the accumulate or detect_parity functions in the calculate_identity file. Our tests will ensure that you’re actually calling the function. We will release our own version of twisted_sum_array after the first part of the lab is due. We recommend that you copy over our solution into your twisted_sum_array.s file so that you can test calculate_identity.s in the same environment that we will run the autograder. 8 SO LO LA B CS233 Lab 7 Handout Calling Conventions Remember about calling conventions; treat the functions that you call (e.g. detect_parity, twisted_sum_array, etc.) as black boxes (i.e., pretend that you don’t know how they are implemented), and make sure you’re correctly saving and restoring across the function call. We’ll test your code against our own versions of the called functions to ensure you’re following conventions. Suggestions Much of the course staff finds this code easier to write using the (callee-saved) $s registers! Using $s registers allows you to save registers once at the beginning of the function to free up the $s registers; you can then use $s registers for all values whose lifetimes cross function calls. We’ve posted videos in Piazza about using $s registers. There are also some helper functions for printing out values in common.s which you may find helpful for debugging purposes. 9