CS61C Summer 2012 Homework 2

Due Sunday, July 1, 2012 @ 11:59pm

Updates

Goals

This assignment aims to give you a better understanding of C memory allocation and MIPS.

Submission

Submit your solution by creating a directory named hw2 that contains files trains.c, findMax.s, and TwoWaySubstringMatch.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 hw2. Partners are not allowed on this assignment.

To check whether you have submitted correctly, use glookup -t.

Setup

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

	$  cp -r ~cs61c/hw/02/ ~/hw2 

For testing problem 1, you'll need to use a tool called valgrind. It's not fully set up on the macs yet but you can ssh into a hive machine (any from hive1 to hive28) to use it:

	$  ssh hive10.cs.berkeley.edu 

You'll also need to use MARS for questions 2 and 4. We will introduce it in lab but it's basically a simulator that assembles and runs MIPS. You can download it here.

Exercises

Problem 1: C and Memory Allocation - 9pts

You will write some code to model a train system. RouteTime.c will use it to figure out when a route will complete given a starting time. Our model consists of stations, each with a schedule. Each schedule would have a list of entries of

For example, you can take a look at schedules.txt (you do not need to understand the format of the input files to complete the assignment though you might want to so you can write your own tests). "STATION: A" marks the beginning of the schedule for station A. Subsequent lines like "B 9:00 9:45" give the destination of a train, time of departure, and time of arrival.

In trains.c, define the structs trainSys and station, and implement the functions described in trains.c. You should only have to modify the file trains.c In particular, you'll have to write

timeHM_t is a struct defined in timeHM.h used to represent times in hours and minutes. You may need some of the functions described there.

You have the freedom to design the structs and the way you store the information however you like (so have fun!). However, your code must be able to handle an arbitrary number of stations and schedule entries; in other words, your data structures must be able to grow dynamically. You are not allowed to use a statically sized array. One possibility is linked list structures. Another is to use arrays but create larger ones to replace ones that are out of space (in which case you may find realloc useful). If you are out of memory (eg, malloc fails), call allocation_failed (given in trains.c).

You should comment your code so readers can give feedback and possibly partial credit easier.

All the required files are in the directory q1 but you only have to submit trains.c

Testing & Debugging

A Makefile is provided for you. The command "make" will produce the executable RouteTime. "make run" will do the same but also run it with the default arguments. The program takes 3 arguments, a file with a list of stations, a file with schedules, and routes. You can take a look at the ones provided to see their format. The stations file is a list of station names, one on each line. In the schedules file, each schedule starts with the "STATION: source_station_name" followed by lines of the format "destination_station departure_time arrival_time." In the routes file, each route begins with "ROUTE: a_name start_station time_now" and subsequent lines are station names in the route.

You should test each part individually as you go along. Once you have completed printStations, RouteTime should echo the stations listed in stations.txt correctly. Similarly, once you have completed printSchedule, the schedules in schedules.txt should be echoed. With getNextTrain completed, the program should be able to give the correct times for when routes should finish, or say that it's not possible. The correct output is given in trains.out.

Having just the correct output will not be enough though. We'll check that your code doesn't access memory it shouldn't be and that it doesn't leak any memory. We'll check with valgrind's memcheck tool. This is a tool that can help you catch memory problems too. "make trains-memcheck" will run the command. The tool will tell you where you are making invalid reads or writes and what memory is leaked (memory that you've lost all pointers to). The program should not have any of these errors nor leaked memory (don't worry about valgrind's report on "still reachable" or "suppressed").

If you run into bugs, try using gdb and valgrind. gdb will let you set breakpoints, step through your code, and check values of variables. valgrind's memcheck will help you catch bad reads and writes. If you run into a segfault, both gdb and valgrind can point you to exactly where it happened.

We will test your solution against other input files so you should test your code carefully.

Problem 2: From C to MIPS - 4pts

Translate the C code into MIPS. Make sure to follow all MIPS conventions. Put your answer in findMax.s after the label findMax. You must use recursion! Some code is already provided to test your solution. You should use run your solution with MARS to check. findMax.s should print "23 100".

Comment your code well as we will be looking at it to ensure all conventions are followed and that you used recursion.

/*
	x is a pointer to a linked list node and is not null.
	Return the max value stored in the linked list.
	
	Assume each node is stored in memory as an int (value) followed by a pointer to the next node (next), each a word wide.
	You must write it with recursion.
*/
int findMax(node *x) {
	if(x->next == NULL)
		return x->value;
	else {
		int max = findMax(x->next);
		if(max > x->value) 
			return max;
		else
			return x->value;
	}
}

Problem 3: Reading MIPS - 2pts

In this problem, $a0 is an integer argument while $a1 is a pointer to (ie: the address of) a large array. The value in $a0 can be any integer and the size of the array that $a1 points to is big enough (as long as you don't dereference memory before $a1, you won't be accessing memory that isn't yours) for the code to work correctly.

Think about what this does in C and briefly (a sentence or two will suffice) explain what it does. Specifically, what is in the array as the function returns?

	addi	$t1 $zero 31
	addi	$t0 $zero 31
loop:	srlv	$t3 $a0 $t1
	andi	$t3 $t3 1
	addi	$t3 $t3 48
	sub	$t4 $t0 $t1
	add	$t2 $a1 $t4
	sb	$t3 0($t2)
	beq	$t1 $zero done
	subi	$t1 $t1 1
	j	loop
done:	sb	$zero 1($t2)
	jr	$ra
Create a file called hw2q3.txt and put your answer in it.

Problem 4: Writing More MIPS - 5pts

You will write a program in MIPS that takes two strings, call them s1 and s2, and counts the number of times s2 occurs in s1 and the reverse of s1. Occurrences may overlap. For example, if s1 = "mirror" and s2 = "ro," the count is 2. Another example, if s1 = "mississippi" and s2 = "is," the count is two forwards and two backwards. Some code has already been provided for you in TwoWaySubstringMatch.s. Specifically, the functions strLen and reverseStr are given to you and you may find them useful.

We'll run your program on MARS. To run with arguments on the GUI, go to "Settings" and check "Program arguments provided to MIPS program." For those who can't get the program to start at main, there is an option under "Settings" for it. After you assemble, you'll see a space for program arguments in the "Text Segment" box.
You should also be able to run it from command line. It should work as follows:

	$ mars sm TwoWaySubstringMatch.s pa mississippi is
	forward matches: 2
	backward matches: 2
	$ mars sm TwoWaySubstringMatch.s pa missses
	wrong number of arguments
	

If you have trouble running the above commands remotely on 200SD machines, either try a hive machine or replace "mars" with "java -jar -Djava.awt.headless=true ~cs61c/bin/Mars.jar".

Your program should print the same as above(there's a newline at the end for both cases). The given code already handles the wrong number of arguments case for you. To print values, you'll have to use syscalls (go to 'Help' > 'Syscalls').

Comment your code well for possible partial credit and feedback.