CS61C Summer 2014 Homework 3

Due Sunday, July 6, 2014 @ 11:59pm

Goals

This assignment is intended to give you practice with MIPS.

Submission

Submit your solution by creating a directory named hw3 that contains files named hw3.txt, and ll_anagram.s. (File names are case-sensitive and the submission program will not accept your submission if your file names differ at all from those specified.) From within that directory, type submit hw3.

Copy the contents of ~cs61c/hw/03 to a suitable location in your home directory to obtain files you will want for this homework.

$  cp -r ~cs61c/hw/03 ~/hw3 

Exercises

Problem 1: Get to Know Your MIPS Green Sheet

Your MIPS Green Sheet provides you with a wealth of information and will be extremely helpful to you during your exams.
In order to help you learn how to use it, answer the following using ONLY the MIPS Green Sheet.

Put your answers in hw3.txt for submission, including your name and login.

  1. Which instructions on the front page may cause overflow exceptions? List them all.
     
  2. What does R[rd] refer to in register transfer language (RTL)/Verilog?
     
  3. Which instructions on the front page use ZERO extended immediates? List them all.
     
  4. Find the hexadecimal representation for the ASCII character 'W'.
     
  5. At what address (in hex) does the dynamic data/Heap begin? Which way does it grow (increase or decrease)?
     
  6. Give the opcodes for the xor and xori instructions (xor stands for 'exclusive or'). Based on your earlier answers, is the immediate in xori sign or zero extended?
     
  7. What's the difference between a kibibyte and a kilobyte, if any?
     
  8. What is the name for register 7? Is it preserved across function calls in MIPS?

Problem 2: Reading MIPS

Consider the function fun below. $a0 contains an integer argument while $a1 is a pointer to an array. The value in $a0 can be any integer and the size of the array that $a1 points to is large enough that no overflow will occur.

Add comments to each line of code, and then explain what the function does in 1-2 sentences. Specifically, what is stored in the array as the function returns? (Hint: An ASCII table may help.)

fun:		addi 	$t0,$zero,32
		addi 	$t1,$zero,0
loop:		sub 	$t0,$t0,4
		srlv	$t2,$a0,$t0
		andi 	$t2,$t2,15
		slti 	$t3,$t2,10
		bne 	$t3,$zero,addLess
		addi 	$t2,$t2,7
addLess:	addi 	$t2,$t2,48
		add 	$t4,$a1,$t1
		sb	$t2,0($t4)
		beq 	$t0,$zero,done
		addi 	$t1,$t1,1
		j loop
done:		sb 	$zero,1($t4)
		jr $ra

Put your answers in hw3.txt.

Problem 3: MIPS Coding

Write a function called isAnagram that checks if two linked lists that stores ints (ranging from 0 to 9) are anagrams of each other. The two lists are anagrams if rearranging the order of one list can produce the other. For example, given the following linked lists:

listA: 1 -> 3 -> 5 -> 7 -> 9 -> NULL
listB: 1 -> 5 -> 9 -> 3 -> 7 -> NULL
listC: 1 -> 3 -> 3 -> 9 -> 7 -> NULL
listD: 1 -> 3 -> 5 -> 7 -> 9 -> 9 -> NULL

ListA and listB are anagrams because rearrangement of one can produce the other, but listA and listC are not because there is no way to produce listA from rearrangement of listC. ListA and listD are not anagrams either for the same reason.

Observe that in order for two lists to be anagrams, each list must contain the same number of each int as each other. ListA contains one of each odd int (1,3,5,7,9) and no even ints (0,2,4,6,8), and so does listB. This leads to a way to test whether two lists are anagrams:

  1. We iterate through each list and create an array of the counts of each int for each list.
  2. We compare the arrays, and if the arrays are equal, the lists are anagrams. Otherwise we conclude the lists are not anagrams.
As an example, suppose we perform this algorithm on listA and listB. We'll store the number of int n in array[n] (so the number of 0s go in array[0], number of 1s go in array[1], etc). After iterating through each list, our counts arrays looks like:

array_listA: [ 0 ][ 1 ][ 0 ][ 1 ][ 0 ][ 1 ][ 0 ][ 1 ][ 0 ][ 1 ]		// counts for listA
array_listB: [ 0 ][ 1 ][ 0 ][ 1 ][ 0 ][ 1 ][ 0 ][ 1 ][ 0 ][ 1 ]		// counts for listB

Since the arrays are equal, we know they are anagrams. Now suppose we do this on listA and listC:

array_listA: [ 0 ][ 1 ][ 0 ][ 1 ][ 0 ][ 1 ][ 0 ][ 1 ][ 0 ][ 1 ]		// counts for listA
array_listC: [ 0 ][ 1 ][ 0 ][ 2 ][ 0 ][ 0 ][ 0 ][ 1 ][ 0 ][ 1 ]		// counts for listC

Note that the arrays are unequal. We conclude that the lists cannot be anagrams of each other.

Your Assignment

Complete the implementation of countList and isAnagram, both located in ll_anagram.s.

countList traverses through a linked list stores the counts of each int into an array. It takes two parameters: $a0 is a pointer to the beginning of the linked list and $a1 is a pointer to a block of memory to put the array in. You may assume that the linked list only contains ints ranging from 0-9 and that there will be enough space in the memory block to fit your array. You do not need to return anything from this.

isAnagram checks if two linked lists are anagrams and takes three parameters: $a0 is a pointer to the beginning of the first linked list, $a1 is a pointer to the beginning of the second linked list, and $a2 is a pointer to a block of memory that you should create your arrays in. The function returns 1 if the linked lists given are anagrams and 0 if not. You should store your return value in $v0. Rough pseudocode has been provided for you in comments.

To compare two linked lists, you will need two arrays of counts. Since there are 10 possible values in our list, each array will need to contain 10 elements. The memory pointed to by $a2 contains enough space for 20 elements total, so it makes sense to use the first half for one array and the second half for another. While we do allocate the memory for you, the memory may contain garbage values, so you should zero out the memory first yourself. We have provided a function, zeroMem, that will set a block of memory to zero. zeroMem takes two parameters: $a0 is the beginning of the block you want to zero out, and $a1 is the number of words you want to set to zero.

A node in the linked list is made up of two successive words, 1) the value stored in the node, followed by 2) a pointer to the next node. Each pointer will point to the beginning of the next node, and unless it is the terminating node, in which case the pointer points to zero (NULL). You may also assume that each list will have at least one list node. However, you may NOT assume that successive list nodes are located next to each other in memory. You must obtain the address of the next node through the next pointer.

Make sure to respect MIPS conventions regarding function calls. If you need to save registers during a function call, you should save them onto the stack. Be sure to move the stack pointer correctly as well.

Before submitting, make sure your code runs correctly in MARS. A few test cases have been provided for you. If you have trouble debugging your code, it may help to set breakpoints or step through instructions slowly so that you can take a look at the values in memory/the registers.

Note: Depending on the version of MARS you have, you may need to make sure the "Initialize Program Counter to global main if defined" option under the Settings menu is checked before running the program.