CSE 220: Systems Fundamentals I
Stony Brook University
Homework Assignment #2
Fall 2018
Assignment Due: October 12, 2018 by 11:59 pm
Important Information about CSE 220 Homework Assignments
Read the entire homework documents twice before starting. Questions posted on Piazza whose answers are
clearly stated in the documents will be given lowest priority by the course staff.
When writing assembly code, try to stay consistent with your formatting and to comment as much as
possible. It is much easier for your TAs and the professor to help you if we can quickly figure out what your
code does.
You personally must implement homework assignments in MIPS Assembly language by yourself. You may
not write or use a code generator or other tools that write any MIPS code for you. You must manually write
all MIPS Assembly code you submit as part of the assignments.
Do not copy or share code. Your submissions will be checked against other submissions from this semester
and from previous semesters.
You must use the Stony Brook version of MARS posted on Piazza. Do not use the version of MARS posted
on the official MARS website. The Stony Brook version has a reduced instruction set, added tools, and
additional system calls you will need to complete the homework assignments.
For Homework Assignments #2 and later, do not submit a file with the functions/labels main or
start defined. You are also not permitted to start your label names with two underscores ( ). You
will obtain a zero for an assignment if you do this.
Submit your final .asm file to Blackboard by the due date and time. Late work will not be accepted or
graded. Code that crashes and cannot be graded will earn no credit. No changes to your submission will be
permitted once the deadline has passed.
How Your CSE 220 Assignments Will Be Graded
With minor exceptions, all aspects of your homework submissions will be graded entirely through automated
means. Grading scripts will execute your code with input values (e.g., command-line arguments, function ar-
guments) and will check for expected results (e.g., print-outs, return values, etc.) For Homework Assignments
#2 and later you will be writing functions in assembly language. The functions will be tested independently of
each other. This is very important to note, as you must take care that no function you write ever has side-effects
or requires that other functions be called before the function in question is called. Both of these are generally
considered bad practice in programming.
Some other items you should be aware of:
All test cases must execute in 10,000 instructions or fewer. Efficiency is an important aspect of program-
CSE 220 – Fall 2018 Homework Assignment #2 1
ming. This maximum instruction count will be increased in cases where a complicated algorithm might be
necessary, or a large data structure must be traversed.
Any excess output from your program (debugging notes, etc.) will impact grading. Do not leave erroneous
print-outs in your code.
We will provide you with a small set of test cases for each assignment to give you a sense of how your work
will be graded. It is your responsibility to test your code thoroughly by creating your own test cases.
The testing framework we use for grading your work will not be released, but the test cases and expected
results used for testing will be released.
Assignment Objectives
The primary objectives of this homework assignment are to continue mastering array processing in MIPS, to be
able to write functions in MIPS, and to apply MIPS register conventions.
Register Conventions
You must follow the register conventions taught in lecture and reviewed in recitation. Failure to follow them will
result in loss of credit when we grade your work. Here is a brief summary of the register conventions and how
your use of them will impact grading:
It is the callee’s responsibility to save any $s registers it overwrites by saving copies of those registers on
the stack and restoring them before returning.
If a function calls a secondary function, the caller must save $ra before calling the callee. In addition, if
the caller wants a particular $a, $t or $v register’s value to be preserved across the secondary function
call, the best practice would be to place a copy of that register in an $s register before making the function
call.
A function which allocates stack space by adjusting $sp must restore $sp to its original value before
returning.
Registers $fp and $gp are treated as preserved registers for the purposes of this course. If a function
modifies one or both, the function must restore them before returning to the caller. There is no reason for
your code to touch the $gp register, so leave it alone.
The following practices will result in loss of credit:
“Brute-force” saving of all $s registers in a function or otherwise saving $s registers that are not overwrit-
ten by a function.
Callee-saving of $a, $t or $v registers as a means of “helping” the caller.
Getting Started
Visit Piazza and download the file hw2.zip. Decompress the file and then open hw2.zip. Fill in the following
information at the top of hw2.asm:
1. your first and last name as they appear in Blackboard
2. your Net ID (e.g., jsmith)
CSE 220 – Fall 2018 Homework Assignment #2 2
3. your Stony Brook ID # (e.g., 111999999)
Having this information at the top of the file helps us locate your work. If you forget to include this information
but don’t remember until after the deadline has passed, don’t worry about it – we will track down your submission.
Inside hw2.asm you will find several function stubs that consist simply of jr $ra instructions. Your job in this
assignment is implement all the functions as specified below. Do not change the function names, as the grading
scripts will be looking for functions of the given names. However, you may implement additional helper functions
of your own, but they must be saved in hw2.asm.
If you are having difficulty implementing these functions, write out pseudocode or implement the functions in a
higher-level language first. Once you understand the algorithm and what steps to perform, then translate the logic
to MIPS assembly code.
Be sure to initialize all of your values (e.g., registers) within your functions. Never assume registers or memory
will hold any particular values (e.g., zero). MARS initializes all of the registers and bytes of main memory to
zeroes. The grading scripts will fill the registers and/or main memory with random values before calling your
functions.
Finally, do not define a .data section in your hw2.asm file. A submission that contains a .data section
will receive a score of zero.
Preliminaries
In this assignment, you will familiarize yourself with a feature of the C programming language known as structs.
A struct is a composite data type that is used to group variables under one name in a contiguous block of memory.
You will be reading and writing arrays of structs that represents cars and car repairs. The * notation used in
the struct definitions below is known as a pointer in C. A pointer is simply a memory address. The data type
associated with the pointer identifies how the data should be accessed at the memory location that is specified by
the pointer. For example, int * would signify the address of an integer located somewhere in memory.
The car Data Type
The car struct stores information about a particular car, identified by its 17-character VIN (vehicle identification
number):
struct car {
string vin; // 4 bytes
string make; // 4 bytes
string model; // 4 bytes
short year; // 2 bytes
byte features; // 1-byte bit vector
byte padding; // 1 byte of zero-padding
};
The meaning of each field:
vin: a pointer to the null-terminated string containing the car’s 17-character VIN.
make: a pointer to the null-terminated string containing the car’s make.
CSE 220 – Fall 2018 Homework Assignment #2 3
model: a pointer to the null-terminated string containing the car’s model.
year: a 16-bit integer (half-word) containing the car’s year of manufacture.
features: a bit vector that gives additional information about the car
bit 0: is it a convertible (1) or not (0)?
bit 1: is it hybrid (1) or not (0)
bit 2: are the windows tinted (1) or not (0)?
bit 3: is GPS built-in (1) or not (0)?
bits 4-7 are unused
Note that the car struct contains 16 bytes, including 1 byte of zero-padding.
Here is what a car struct might look like in MIPS:
# Data declarations from elsewhere in data.asm:
vin_03: .asciiz "1G1AK15F967719757"
make_E: .asciiz "Mersaydeez"
model_D: .asciiz "Road Hog"
# The car struct itself starts at label car_03:
car_03: .word vin_03 # vin_03 is the starting address of "1G1AK15F967719757"
car_03_make_addr: .word make_E # make_E is the starting address of "Mersaydeez"
car_03_model_addr: .word model_D # model_D is the starting address of "Road Hog"
car_03_year: .byte 175, 7 # the year of manufacture: 175 + 7*256 = 1967
car_03_features: .byte 10 # a bit-vector of features (binary 1010_2)
.byte 0 # one byte of zero-padding
See the included data.asm file for sample car structs.
While working on the homework you might find it helpful to write a function that prints the contents of a car
struct to give you a human-readable form. of the data structure.
The repair Data Type
struct repair {
car* car_ptr; // 4 bytes
string desc; // 4 bytes
short cost; // 2 bytes
short padding; // 2 bytes of zero-padding
}
The notation * indicates that the field is a pointer, i.e., the address of a car struct.
The meaning of each field:
car ptr: a pointer to the struct for the car that was repaired.
desc: a pointer to the null-terminated string containing the description of the repair.
CSE 220 – Fall 2018 Homework Assignment #2 4
cost: a 16-bit unsigned integer containing the cost of the repair.
Note that the repair struct contains 12 bytes of data, including 2 bytes of zero-padding.
Here is what a repair struct might look like in MIPS:
# A data declaration from elsewhere in data.asm:
repair_desc_A: .asciiz "fix cracked windshield"
# The car struct itself starts at label repair_05_car:
repair_05_car: .word car_03 # starting addr. of repaired car struct
repair_05_desc_addr: .word repair_desc_A # address of repair string
repair_05_cost: .byte 156, 1 # cost to repair the car: 156 + 1*256 = 412
.byte 0, 0 # two bytes of zero-padding
See the included data.asm file for sample repair structs.
How to Test Your Functions
Numerous .asm files have been provided to you for this assignment to help you test your work. However, note
the following:
These tests are not exhaustive. You will need to modify the provided “main” files to test your work more
thoroughly.
These test cases will not be used to grade your work.
The grading test cases will use different labels than the ones you will find in the data.asm file and similar
files.
Do not, under any circumstances, add a .data section to your hs2.asm file. Doing this will render your
submission ungradeable!
Using the provided main files is pretty simple. For example, suppose you wanted to test your index of car
function from Part I of the assignment. First, make sure that in the Settings menu in MARS the option Initialize
Program Counter to global ‘main’ if defined is checked. Then, open index of car main.asm,
assemble it, and then run it. The main file will load the contents of your hw2.asm file and call your implemen-
tation of the index of car function.
The main files will provide some basic output, but it is your responsibility to dig deeper into the function outputs
to make sure your implementations are correct. These main files will not be used in grading, and you should not
submit them for grading. Submit only your hw2.asm file to Blackboard.
Finally, make sure that all code required for implementing your functions is included only in the hw2.asm file.
To make sure that your code is self-contained, try assembling your hw2.asm file by itself in Mars. If you get any
errors (such as a missing label), this means that you need to refactor (reorganize) your code, possibly by moving
labels you inadvertently defined in a main file (e.g., a helper function) to hw2.asm.
Part I: Search for a Car by Year
int index of car(car[] cars, int length, int start index, int year)
CSE 220 – Fall 2018 Homework Assignment #2 5
This function searches an array of car structs starting at index start index and returns the index of the first
car it finds that was manufactured in the given year. (That is, when multiple cars of the given year are found,
the lowest index start index is returned.) Recall that each car struct is 16 bytes in size. Therefore,
the starting addresses of consecutive structs are 16 bytes apart. As an example, suppose that cars[] starts
at address 0x00100000. cars[0] begins at 0x00100000, cars[1] begins at 0x00100010, cars[2]
begins at 0x00100020, etc.
The function takes the following arguments, in this order:
cars: an array of car structs
length: the length of the cars array (i.e., how many structs are stored in the array)
start index: the index at which to start the search
year: the year of manufacture
Returns in $v0:
the index of the located car, as described earlier
Returns -1 in $v0 for error in any of the following cases:
length 0
start index length
Additional requirements:
You may assume that at least 16 bytes of memory has been set aside after the cars array to accommodate
the new car.
Do not modify the order of the cars in the array before and after the newly inserted car.
insert car() must call memcpy() to shift the cars in the array.
Examples:
Providing extensive examples in this document is not practical due to the nature of the array being manipu-
lated, so only return values are given in the table below. You are strongly urged to use (and modify!) the
insert car main.asm file provided with the homework materials to test your work. You will note that
one complete test case is given in that file. The array after insertion is called expected all cars. Use your
strcmp function from earlier in the assignment to compare the contents of all cars (from data.asm) with
expected all cars after the insert car() function has been called.
Function Call Return Value Explanation
insert car(cars array, 6, new car, 3) 0 new car inserted at index 3
insert car(cars array, 6, new car, 0) 0 new car inserted at start of array
insert car(cars array, 6, new car, 6) 0 new car appended to array
insert car(cars array, -1, new car, 3) -1 invalid array length
insert car(cars array, 6, new car, -1) -1 invalid insertion index
insert car(cars array, 6, new car, 8) -1 insertion index too large
Part V: Find the Most Damaged Car
(int, int) most damaged(car[] cars, repair[] repairs, int cars length,
int repairs length)
The most damaged() function finds the car in cars that has the highest total repair cost, returning both the
index of that car in cars and its total repair cost. If there are multiple cars with the same total repair cost,
the function returns the lowest of the indices. A particular VIN can appear in multiple repair structs in the
repairs array. (clarification added 10/7/2018)
The function takes the following arguments, in this order:
cars: an array of car structs
repairs: an array of repair structs
CSE 220 – Fall 2018 Homework Assignment #2 9
cars length: the number of elements in cars
repairs length: the number of elements in repairs
Returns:
$v0: the index of the car with the highest total repair cost, or -1 for an error case
$v1: the total repair cost for the car, or -1 for an error case
The following are error cases:
cars length 0
repairs length 0
Additional requirements:
Do not modify the contents of the cars or repairs arrays in memory.
This function must call strcmp() to compare VINs. (updated 10/3/2018)
Examples:
For the contents of the all cars array from data.asm, the returned index in $v0 should be 4 and the returned
total repair cost in $v1 should be 587. You are strongly encouraged to modify the all repairs array to make
additional examples yourself. This is very easy to do – simply change the cost of particular repair objects.
Some examples to consider making: what if the array of repairs has only one item? what if two or more cars have
the same total repair cost? what if all the cars have the same repair cost?
Part VI: Sort an Array of car Structs
int sort(car[] cars, int length)
The sort() function sorts an array of cars by year. The function must implement odd-even sort (which is a
stable sorting algorithm) according to the following pseudocode:
def sort(cars):
sorted = False
while !sorted:
sorted = True
for(i = 1; i cars[i + 1]:
swap cars[i] and cars[i + 1]
sorted = False
for(i = 0; i cars[i + 1]:
swap cars[i] and cars[i + 1]
sorted = False
CSE 220 – Fall 2018 Homework Assignment #2 10
The function must use the stack for temporary space when swapping cars in the array. Again, you must use the
stack for temporary space – do not add a .data section to your hw2.asm file. The following pseudocode can
be used to swap cars at indices i and j using the stack:
$sp -= 16 // make space on the stack for 1 car
memcpy(cars[i], $sp, 16) // copy cars[i] onto the stack
memcpy(cars[j], cars[i], 16) // copy cars[j] to cars[i]
memcpy($sp, cars[j], 16) // copy the temp car on the stack to cars[j]
$sp += 16
The function takes the following arguments, in this order:
cars: an array of cars
length: the number of elements in cars
Returns:
$v0: 0 if success, -1 if an error occurs.
Returns -1 for error in any of the following cases:
length 0
Additional requirements:
sort() must call memcpy() to swap cars in the array.
Example:
The all cars array given in sort data.asm contains the following cars, shown here in a more easily-
readable form.:
JTDKN3DU0D5614628 Fjord Wolfie-Z 2017 1000 Tinted windows > Hybrid > Convertible).
The examples given below will help to further clarify what this return value means.
Returns -1 for error in any of the following cases:
length 0
features not in range [1, 15].
CSE 220 – Fall 2018 Homework Assignment #2 12
All cars have no features from features (i.e. there is no favorite because the count is 0 for all features
that are being considered).
Additional requirements:
Do not modify the contents of the cars array in memory.
Examples:
Consider the following function call: most popular feature(all cars, 6, 7). The third argument,
01112 in binary, indicates that we will count how many cars are convertibles (bit 0 is 1), how many cars are
hybrid (bit 1 is 1), and how many cars have tinted windows (bit 2 is 1). We will not count cars that have a GPS
because bit 3 is 0. When we call the function with these arguments for the cars in data.asm, the return value
is 4, 01002 in binary. Bit 2 is associated with tinted windows. This means either that (1) of the three features we
considered, tinted windows was the most popular feature, or, (2) there was a tie in the counts for tinted windows
and some other feature, but we reported tinted windows as the “winner” because it has higher precedence than
hybrid engines or a convertible roof.
As another example, suppose we performed a search with 00112 as the feature vector, but no cars are hybrids or
have convertible roofs. In this case, both of those counts are zeroes, and so the function returns -1 to indicate an
error.
So to summarize, there are only 5 valid return values: -1, 1, 2, 4 or 8. Do you see why?
Function Call Return Value
most popular feature(all cars, 6, 15) 8
most popular feature(all cars, 6, 7) 4
most popular feature(all cars, 6, 3) 2
most popular feature(all cars, 6, 5) 4
most popular feature(all cars, 6, 1) 1
most popular feature(all cars, 6, 0) -1
most popular feature(all cars, -1, 14) -1
Part VIII: Compute a VIN’s Check Digit
char compute check digit(string vin, string map, string weights,
string transliterate str)
The compute check digit() function computes the check digit for a valid VIN according to the following
pseudocode:
def transliterate(ch, transliterate_str):
return transliterate_str.index_of(ch) % 10
def compute_check_digit(vin, map, weights, transliterate_str):
sum = 0
for (i = 0; i < 17; i++):
sum += transliterate(vin.charAt(i), transliterate_str) *
CSE 220 – Fall 2018 Homework Assignment #2 13
map.index_of(weights.char_at(i))
return map.char_at(sum % 11)
Implementing separate functions for transliterate, char at, and index of is not required, but is rec-
ommended to make your code easier to debug.
The function takes the following arguments, in this order:
vin: a VIN
map: the string "0123456789X", whose address is passed to the function via $a1
weights: the string "8765432X098765432", whose address is passed to the function via $a2
transliterate str: the string "0123456789.ABCDEFGH..JKLMN.P.R..STUVWXYZ", , whose
address is passed to the function via $a3
Returns:
$v0: The check digit of the VIN given as an ASCII character. You do not need to do any error-checking
for this function.
Additional requirements:
Do not modify vin in memory.
Examples:
In the table below, transliterate str has been abbreviated trs to save space.
Function Call Return Value
compute check digit("JTDKN3DU0D5614628", map, weights, trs) 0
compute check digit("1B4HR28N01F502695", map, weights, trs) 5
compute check digit("1HGEM1150YL037618", map, weights, trs) 9
compute check digit("1FTDF15N0KNB73611", map, weights, trs) 3
compute check digit("1M2P198C0JW002996", map, weights, trs) 5
Academic Honesty Policy
Academic honesty is taken very seriously in this course. By submitting your work to Blackboard you indicate
your understanding of, and agreement with, the following Academic Honesty Statement:
1. I understand that representing another person’s work as my own is academically dishonest.
2. I understand that copying, even with modifications, a solution from another source (such as the web or
another person) as a part of my answer constitutes plagiarism.
3. I understand that sharing parts of my homework solutions (text write-up, schematics, code, electronic or
hard-copy) is academic dishonesty and helps others plagiarize my work.
4. I understand that protecting my work from possible plagiarism is my responsibility. I understand the im-
CSE 220 – Fall 2018 Homework Assignment #2 14
portance of saving my work such that it is visible only to me.
5. I understand that passing information that is relevant to a homework/exam to others in the course (either
lecture or even in the future!) for their private use constitutes academic dishonesty. I will only discuss
material that I am willing to openly post on the discussion board.
6. I understand that academic dishonesty is treated very seriously in this course. I understand that the instructor
will report any incident of academic dishonesty to the College of Engineering and Applied Sciences.
7. I understand that the penalty for academic dishonesty might not be immediately administered. For instance,
cheating in a homework may be discovered and penalized after the grades for that homework have been
recorded.
8. I understand that buying or paying another entity for any code, partial or in its entirety, and submitting it as
my own work is considered academic dishonesty.
9. I understand that there are no extenuating circumstances for academic dishonesty.
How to Submit Your Work for Grading
To submit your hw2.asm file for grading:
1. Login to Blackboard and locate the course account for CSE 220.
2. Click on “Assignments” in the left-hand menu and click on the link for this assignment.
3. Click the “Browse My Computer” button and locate the hw2.asm file. Submit only that one .asm file.
4. Click the “Submit” button to submit your work for grading.
Oops, I messed up and I need to resubmit a file!
No worries! Just follow steps 4–6 again. We will grade only your last submission.
CSE 220 – Fall 2018 Homework Assignment #2 15