University of California at Berkeley

College of Engineering

Department of Electrical Engineering and Computer Science

EECS 61C, Fall 2003

Lab 2-1: Malloc and MIPS Introduction

Goals

This lab will give you practice working with the malloc function and an introduction to MIPS.

Initial preparation

Read sections 6.1–6.5 in K&R and 3.1-3.3 in P&H.

Copy the contents of the directory ~cs61c/labs/lab2-1 to your home directory.

Exercise 1

The code in lists.c supplies a partial implementation of a data type representing a list of names; its corresponding header file is lists.h. (Note that the #include statements surround the file name with double quotes rather than brackets.) A program that tests the list functions is provided in listtest.c. Compile the pair of .c files into a program with the command:

gcc lists.c listtest.c

The listtest.c program reads successive lines from the input without prompting, replacing the terminating newline with a '\0'. Each input string should be added to the front of the list being accumulated. The program doesn’t prompt you individually for the names to add to the list -- simply type each name (followed by return), then type ^D (control-D, which means end-of-input) at the start of a line to indicate that no more strings are to be added to the list. The names should be printed one per line in reverse order that they appear in the list.

Part a

Define struct ListNode. Your solution should not limit the length of a name, even though the listtest.c program does.

Part b

Complete the cons function. Your solution should use malloc to allocate space on the heap.

Part c

Complete the print function and test it with the listtest.c code. Don't change anything else in any of the files.

Contents of ~cs61c/labs/lab2-1

lists.h

struct ListNode;

struct ListNode * newList ( );

struct ListNode * cons (char *, struct ListNode *);

void print (struct ListNode *);

lists.c (to which you add code)

#include <stdio.h>

#include <stdlib.h>

#include <strings.h>

#include "lists.h"

struct ListNode ... /* You supply this definition. */

/* Return an empty linked list. */

struct ListNode * newList ( ) {

return 0;

}

/* Return the result of adding the given string to the front of the given list. */

struct ListNode * cons (char * s, struct ListNode * list) {

/* You supply the body of this function. */

}

/* Print the names in the given linked list, one per line. */

void print (struct ListNode * list) {

/* You supply the body of this function... use recursion. */

}

listtest.c

#include <stdio.h>

#include "lists.h"

int main ( ) {

char word[100];

printf ("Collecting names into a list.\n");

struct ListNode * list = newList ( );

while (gets(word)) {

list = cons (word, list);

}

printf ("Printing the names in the list.\n");

print (list);

return 0;

}

Exercise 2: Simple MIPS program.

Write a piece of MIPS code that takes values in $s0 and $s1 and puts the value fib(i) into register $ti (for 0 <= i <= 7). For example, if $s0 contains the value 1 and $s1 contains the value 1, then after running your code, registers $t0 through $t7 should contain these values:

$t0 = 2 ($s0 + $s1)

$t1 = 3 ($s1 + $t0)

$t2 = 5 ($t0 + $t1)

...

$t7 = 55 ($t5 + $t6)

You should not set the value of $s0 or $s1 in your code. Learn how to set it manually within XSpim. Assembly programs are written in files with a .s extension. The program must start with the label "__start:" (two underscores) and end with the instruction "done". In order to run your program, run "spim" or "xspim" and consult P&H for commands in Spim.

Using XSpim

XSpim is a version of Spim that has an X-interface, as opposed to Spim's console interface. To run XSpim at home, you will need to download support for X-interface (such as Exceed for Windows). To run XSpim in the labs, simply run "xspim". To run your program in XSpim, use the "Load" button to load your .s file. You should see the instructions of your .s file appear in the "Text Segments" frame. Set the $s0 register using the "Set Value" button. Then use the "Run" or "Step" button to execute your program. You should see the registers change in the top frame.