Due Sunday, July 1, 2012 @ 11:59pm
Updates
- June 30 @ 6:35PM - Clarifications for addTrain: Don't save the pointers to time structs as the values will change! Don't worry about duplicate station names.
- June 29 @ 4:20PM - Station names can be more than 1 character long
- June 29 @ 10:00AM - This was mentioned in lecture already. Do not leave extraneous prints (like from debugging); the autograder will fail you. Also, make sure to test on a machine in 200SD. Here is a list of machines. You don't have to physically be in the lab; you can ssh in. Ask us if you need help with that.
- June 25 @ 6:30PM - The comments for
printSchedule
is wrong. The file has been updated. Don't print the name of the src station first.
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
- a destination station,
- time of departure,
- and time of arrival.
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
trainSys_t* createSystem()
void deleteSystem(trainSys_t* s)
void addStation(trainSys_t* s, char* name)
station_t* getStation(trainSys_t* s, char* name)
void printStations(trainSys_t* s)
void printSchedule(station_t* s)
void addTrain(station_t* src, station_t* dst, timeHM_t* departure, timeHM_t* arrival)
bool getNextTrain(station_t* src, station_t* dst, timeHM_t* now, timeHM_t* departure, timeHM_t* arrival)
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 $raCreate 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."
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
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.