Systems Architecture
121 Assignment 2
DUE 6pm Friday 9th March 2012, end of week 8
Rules
- The course rules on own work and plagiarism apply to this assignment.
See the subject outline page
for details. Your submission will be cross-compared to other
student submissions to ensure that answers have not been shared.
- The due date for the assignment is a hard date. You will
need to supply a good reason if an extension is required. Unless you
have given me your written request for extension, and I have approved
an extension (along with my signature), late submissions will
not be accepted. This assignment is worth 15% of your final mark
in this course.
Submission
Your answer to the assignment must be submitted electronically through
the iLearn portal as a Zip or tar file containing all of the source
code files: no other submission will be accepted. Instructions
on how to create a Zip or tar file are given somewhere.
Please submit your Zip or tar file for the assignment through the
iLearn submission area.
Introduction
The C programming language is a much lower level language than Java.
In Java, you get a reference to an object, but you cannot find where
in memory that object is stored.
In C, you can find the actual memory location for ints, characters,
arrays, strings etc. The language provides pointers, which
are variables that hold the memory address of another data structure.
There is a specific pointer value, NULL, which means that the pointer
is not pointing at anything. In most implementations NULL is the value
0, and any access of memory location 0 will cause a program to crash.
A string in C is a sequence of bytes stored in memory starting at
a specific address. C marks the end of a string with a byte whose
value is 0, i.e. the 8-bit value 0x00. Confusingly, this is known
as the NUL character. This means that, to find the length of a string,
you need to count the number of non-NUL bytes from the beginning of
the string.
The C library provides many functions that manipulate strings and
memory areas. In this assignment you will implement some of these
functions.
Task 1: malloc() - 2 marks
The malloc()
function in C takes a single integer length as its argument
and returns the first address of an unused area of memory which is
length bytes long. Write a MIPS function which implements the
malloc() function.
Hint: investigate the sbrk syscall. I am happy for
you to implement a naive version of malloc(). A proper version
of malloc() has to keep track of all the memory allocated,
as well as those areas which are released by calls to the free()
function. Your function does not have to keep track of allocated or
released memory.
Task 2: memcpy() - 5 marks
The memcpy()
function in C takes two pointers to locations in memory and an integer
length argument. The function copies length bytes of
data from one of the pointer locations (the source) to the other pointer
location (the destination). Write a MIPS function which implements
the memcpy() function.
You will be marked based on three criteria:
- The function works correctly and doesn't crash. No input to the function
should cause it to crash. Arguments which don't make sense should
be rejected.
- The function deals with the situation when the source region overlaps
the destination region. In this situation, the contents of the source
region before memcpy() starts must be
copied into the destination region.
Task 3: strlen() - 4 marks
The strlen()
function in C takes a pointer to a string and returns the length of
the string in bytes, not including the NUL byte which terminates the
string. Write a MIPS function which implements the strlen()
function.
You will receive full marks if you implement a function that works
correctly and which is also recursive. An implementation which is
not recursive will receive fewer marks. Arguments which don't make
sense should be rejected.
Task 4: strcmp() - 2 marks
The strcmp()
function in C takes two pointers to two strings and returns a value
that indicates if they are the same string, if the first comes before
the second or if the second comes before the first. Write a MIPS function
which implements the strcmp() function. Arguments which don't
make sense should be rejected.
Task 5: strdup() - 2 marks
The strdup()
function in C takes a pointer to an existing string and returns a
pointer to a newly-allocated area of memory where the original string
has been copied. Write a MIPS function which implements the strdup()
function. You should use the functions that you have already written
to implement this function. Arguments which don't make sense should
be rejected.
Hints, Tips, Constraints
Make sure that all functions use the argument registers $a0,
$a1, $a2 and $a3 to receive their arguments,
and that any return value is returned in the $v0 register.
Make sure that all functions have exactly the names given above.
Testing
I will use a test rig to stress test each function that you implement:
- Each function name is correct.
- Each function receives its arguments correctly and returns its value
correctly.
- Each function works correctly when given a variety of sensible inputs.
- Each function deals with bad inputs correctly.
- No function crashes when given bad input.
You should do your own stress testing on your functions to ensure
that they work as specified. I would like to see your test rig included
as part of your answer.
Update
Here is my test rig as two versions:
- testrig.asm, the one you can feed into MARS
- testrig.wasm, the version I wrote which I convert
into the above version
To use the test rig, keep your code in a separate file, i.e. I want
you to submit your library functions in a file by themselves.
Take my test rig, and copy/paste your library functions to the bottom.
Now run it in MARS and see what it does. The program should not crash
at any stage.
Here are the results when I run the test rig on my answer:
MARS 4.1 Copyright 2003-2011 Pete Sanderson and Kenneth Vollmar
Malloc 20 gives 268697600
Malloc 19 gives 268697620
Malloc 18 gives 268697640
Malloc 17 gives 268697660
Malloc 16 gives 268697680
Malloc 15 gives 268697696
Malloc 14 gives 268697712
Malloc 13 gives 268697728
Malloc 12 gives 268697744
Malloc 11 gives 268697756
Malloc 10 gives 268697768
Malloc 9 gives 268697780
Malloc 8 gives 268697792
Malloc 7 gives 268697800
Malloc 6 gives 268697808
Malloc 5 gives 268697816
Malloc 4 gives 268697824
Malloc 3 gives 268697828
Malloc 2 gives 268697832
Malloc 1 gives 268697836
Malloc 0 gives 0
Malloc -27 gives 0
Strlen strlen test string #1 is 21
Strlen is 0
Strlen on NULL is 0
Strcmp string1 string2 gives 1
Strcmp string2 string1 gives -1
Strcmp string1 string1 gives 0
Strcmp string1 string3 gives 1
Strcmp string3 string1 gives -1
Strcmp NULL string3 gives -2
Strcmp string1 NULL gives -2
Memcpy string1 buf1 gives abcdefghijklmnopq
Memcpy string1 buf2 gives abcdefghijklmnopq
Memcpy overlap buf3 buf4 gives 0123456789abcde
Memcpy overlap buf7 into buf6 gives 0123456789
Memcpy overlap buf7 into buf6 size 0 gives 0123456789
Memcpy overlap buf7 into buf6 size -5 gives 0123456789
Strdup string1 gives abcdefghijklmnopq
Strdup string3 gives abcd
Strdup empty string gives
Strdup NULL pointer gives 0
File translated from
TEX
by
TTH,
version 3.85.
On 9 Mar 2012, 10:33.