|
CO527 Anonymous Questions and Answers |
This page lists the various questions and answers. To submit a question, use the anonymous questions page. You may find the keyword index and/or top-level index useful for locating past questions and answers.
We have taken the liberty of making some minor typographical corrections to some of the questions as originally put. Although most of the questions here will have been submitted anonymously, this page also serves to answer some questions of general interest to those on the course.
Submission reference: IN331
Regarding the 's' and 't' registers, and Question 32 (2005).
Does this mean it doesn't matter which you use? Apart from the fact that you don't need to save any 's' registers to the stack before you call a subroutine versus having to save 't' registers that you've used and want to preserve, is there no diffence?
Effectively, yes, you can use either. Just that the $t0-$t7 registers won't be saved across calls, whereas $s0-$s7 will. However, saving $t0-$t7 registers before a subroutine call doesn't sound right. If you want their contents to be saved around the call, use $s0-$s7, not $t0-$t7. The only difference at the hardware level is a different register number. It'd be quite legitimate to re-assign registers numbers arbitrarily -- the only special one is register 0 ($zero).
Keywords: mips-asm
Referrers: Question 59 (2005)
Submission reference: IN334
Seeing as this isnt an algorithms module and we get more marks for doing a quicksort rather than a bubble sort, could you provide us with the C code for a quicksort? Thanks
The algorithm is readily available on the internet and in many textbooks. The wikipedia entry for quicksort gives a good description of the algorithm and implementation. My preferred C implementation is:
void quicksort (void **array, int first, int last, int (*cfcn)(void *, void *))
{
int i = first, j = last;
void *pivot = array[(first + last) >> 1];
while (i <= j) {
for (; cfcn (array[i], pivot) < 0; i++);
for (; cfcn (array[j], pivot) > 0; j--);
if (i <= j) {
void *tmp = array[i];
array[i++] = array[j];
array[j--] = tmp;
}
}
if (j > first) {
quicksort (array, first, j, cfcn);
}
if (i < last) {
quicksort (array, i, last, cfcn);
}
}
Keywords: mips-asm
Referrers: Question 45 (2005)
Submission reference: IN336
Do you want us to do all the questions that you have put up on the assessment2 sheet or just to choose one of them? How will you be setting your marking criteria for this assessment: code style, whether it works correctly, etc.? Will you be providing any points if the code is there but didn't compile without error? thanks
As the question page says, it's a choice -- i.e. choose one. The marking criteria are on the question page. If the code doesn't assemble (not actually compiling anything here) you'll lose as many marks as an equivalent broken but assembling implementation. I.e. I'm not going to give zero just for silly mistakes that stop it assembling -- that horribly unfair imo. However, you should aim to produce something that assembles correctly -- where it doesn't the assembler is pretty verbose about the problem (deal with the errors one at a time, starting at the first -- as with most assemblers/compilers, an early error can cause later ones).
Keywords: mips-asm
Submission reference: IN340
Where can I find SPIM on raptor?
You don't need to since it's in your path, but:
[raptor:501]:~:0$ type spim spim is /usr/local/bin/spim [raptor:502]:~:0$ type xspim xspim is /usr/local/bin/xspim
Keywords: mips-asm
Submission reference: IN343
would it be best to use a linked list for sorting strings? Can it be done without a linked list?
Erm, I don't think a linked-list would be best. Sure, you can do it with a linked list, but as the strings are already in an array it makes sense to sort that, rather than converting the array to a linked-list, sorting the list, then converting back into the array. For your second question, yes, it can be done without a linked list -- sorting an array perhaps ? :-). The code for a bubble sort is given on the page already; the code for a quicksort is given all over the place (and in Question 42 (2005)). Quicksort and bubble-sort work on arrays.. Mergesort works on linked-lists (and mergesort is more complicated than quicksort imo).
Keywords: mips-asm
Submission reference: IN349
Hello, In the part for sorting strings , there only seems to be one parameter available $a0, so in order to implement say quicksort which takes several parameters eg "void quicksort (void **array, int first, int last, int (*cfcn)(void *, void *))", can we assume values for 'first' , 'last' etc. based on the information given i.e the set of strings given to get these values.
Thank you for your help.
If you're doing a quicksort, you'll need to add extra parameters. You cannot and should not assume values for the 'first' and 'last' parameters -- the algorithm calls itself recursively and needs these! At the top-level, 'first' would be zero and 'last' would be N-1 (where N is the number of items in the array, which you would have to work out by counting them).
Keywords: mips-asm
Just a quick question, when the sys_malloc function allocates memory from a pointer location, does it allocate upwards or downwards? i.e. to work through the memory to test it, do I need to increment upwards from the pointer or decrement it?
As in general with memory allocation, the pointer you get back is at the base of the block (so the allocated bytes/words are at positive offsets, "above"/"up"/etc.). The stack is the only strange thing in that it grows downwards (but you don't need to worry about allocating stacks).
Keywords: mips-asm
Submission reference: IN351
Hi, I want to use the quicksort you provide,but I dont know what is the last parameter "int (*cfcn)(void *, void *)" in the method header. Thanks
This parameter is a function-pointer to something that does comparisons between array entries. You'll see it used as a normal function call in the C code (function-pointers are a little strange perhaps, but incredibly useful). The equivalent thing in Java would be something that implements a "Comparator", and have that passed as a parameter. For this exercise, you can remove it since you're only comparing strings (i.e. that function-pointer would always be the same function, something that compares strings).
Keywords: mips-asm
Submission reference: IN352
To save the $ra pointer to memory at the start of a subroutine do we need to first drop the stack pointer $sp by 8 bytes or can we just drop it by 4? I'm sure I read somewhere that you have to drop it in multiples of 8, although I can't seem to find it now....
4 bytes (1 32-bit word, size of $ra or most other registers) is fine. Real-world systems would probably do it in multiples of 8 ($ra still only needs 4 of those however) -- that way 64-bit sized things allocated on the stack will be well-aligned. You don't need to worry about this for the assessment however (because there isn't any 64-bit integer or floating-point stuff going on).
Keywords: mips-asm
Submission reference: IN353
Looking at your marking schemes, they add up to 65% what is the other 35% for? amusing code comments?
The other 35% is described in the common marking-scheme further up the page. It's for structuring and correct usage of instructions/registers (i.e. coding style, including indentation, commenting, etc.). Amusing comments probably won't affect your mark (depends what you consider "amusing" I guess .. ;-)), but may provide moments of relief in an otherwise arduous marking session :-).
Keywords: mips-asm
Submission reference: IN356
i'm really stuck on how to compare strings. should i be using the "read_string" system call to get the strngs from the array? if so how do i then compare them? if i read each character from a string as a byte, how can i cumulatively compare the string ? i.e. can i add all the bytes to a single register, and then compare?
Nope, you should not be using any system-calls in your code here. The strings are already in memory, defined in the assembler by things like:
.data #; data segment
s1: .asciiz "string one"
s2: .asciiz "another string"
.align 4 #; make sure words start on word-boundaries (missing from the
#; code provided, but didn't break it..)
strs: .word s1, s2, 0 #; array of addresses of string-starts
The sort routine is called with the address of "strs", as per:
la $a0, strs #; load address of "strs"
jal do_sort #; sort them
The address that is in $a0 when the sort routine is called points at some memory containing addresses of strings, followed by a null (zero) marking the end. So if your sort routine did this:
lw $t0, 0($a0) #; $t0 = strs[0] (load word)
it'd be left with the address of the first string ("s1") in $t0. This address points at the memory containing the strings themselves, so if the code subsequently did:
lbu $t1, 0($t0) #; $t1 = strs[0][0] (load byte)
it'd be left with the first character of the first string in $t1 ('s').
The intended approach involves writing a separate string-comparison routine. This should take two pointers to strings (in $a0 and $a1) and compare the strings, returning with a meaningful value in $v0. The addresses in $a0 and $a1 would be like those in $t0 above (containing the memory address of the string data itself).
The above fragments use constant-offsets to read fragments of memory, e.g. "strs[0]". To get variable-offsets requires a little more work, e.g. "strs[i]". The do_print_strings routine in the provided source does this, as do some of the assembler exercises on the assessment page. But briefly, instead of writing:
lw $t0, 0($a0) #; $t0 = strs[0] (load word)
lw $t1, 4($a0) #; $t1 = strs[1] (load word)
to load the first two strings from some array, you could write:
li $s0, 0 #; i = 0
li $s1, 1 #; j = 1
sll $s0, $s0, 2 #; i = (i * 4) (scale to word offset)
sll $s1, $s1, 2 #; j = (j * 4) (ditto)
addu $t2, $a0, $s0 #; $t2 = address of strs[i]
addu $t3, $a0, $s1 #; $t3 = address of strs[j]
lw $t0, 0($t2) #; $t0 = strs[i] (by dereference of $t2)
lw $t1, 0($t3) #; $t1 = strs[j] (by dereference of $t3)
Because 'i' and 'j' start in terms of array-indices (0 and 1 in this case), they must be scaled to word-sized quantities (*4). Shifting left by 2 does this (<<2). When getting elements out of strings, this scaling is not required (as each character is only a byte wide, not a word).
In response to your last point, no, you cannot compare strings by adding up their byte values -- strings like "beef" and "feed" would add up to the same value. You need to loop over the characters, comparing them as you go. The mechanisms that exist to turn strings into numbers for comparison are generally called hashes/hashing (and then can only tell you if they're the same string normally, not whether one is 'more' or 'less' than another).
Keywords: mips-asm
Referrers: Question 59 (2005) , Question 82 (2005)
Submission reference: IN357
does one byte represent a character in the string? and can i work out the address of the next byte/character in the string by adding 8 to the base address of the array?
Yes, each character is a byte (8 bits). But memory addresses work in bytes, so if you have the address of a character in $t0 say, you would get the address of the next character by adding 1 (not 8).
Keywords: mips-asm
Submission reference: IN358
Do we have to write the sortstrings.s in assembler or just the code to sort the strings? Thanx
Not quite sure I understand your question.. The file sortstrings.s is assembler; you have to modify it so that it sorts the strings successfully (and submit the modified file). Test by running it in spim/xspim -- the provided file prints the list before and after calling the sort routine, so initially you see exactly the same list.
Keywords: mips-asm
Submission reference: IN359
For sorting the given Strings (option 1), do we have to implement MIPS code that can deal with any list of array, or just deal with the given array only (stringsARRAY)?
It should cope with any list of strings, e.g. if you modify the given list it should still sort them correctly. The loss of marks for only dealing with the given array will depend on severity (e.g. assuming N items instead of counting will lose less marks than a sort that statically re-arranges the given items, to give extreme examples).
Keywords: mips-asm
Submission reference: IN363
when i save a return address to the stack, do i always decrement the pointer by 4 and place the new item at 0? whats the benefit of saving return addresses to stack and not to st registers, for example?
The stack is generally a better place to save it, but technically you could use one of the $s0-$s7 registers. The reason for using the stack is that it allows a debugger to extract the 'call trace' (backtrace) from the stack -- if return values are in registers it can't do this (however, it also needs the frame-pointer to do it properly). I'd recommend using the stack..
Keywords: mips-asm
Submission reference: IN369
i'm having trouble using the stack so, for the moment, am using the s registers to save between calls. will i be penalised if i don't have enough time to alter the code at the end to use the stack instead ?
Some marks would probably be lost, but not many in the scheme of things (depends how much it complicates the code).
Keywords: mips-asm
Submission reference: IN375
Hi, I am trying to find a way to find out the size of an array in MIPS, i'm not sure what to do. I am not sure how the "Count" method can be used in MIPS to find out the size of the array. Thanks in advance.
The way that arrays are defined should give you a clue, e.g.:
thestrings: .word s1, s2, s3, 0
i.e. there are obviously 3 things in this array (plus the null-terminator on the end). To count it in a program you can do two things: (1) loop over the array until you find the terminating null (zero); (2) place a label at the end of the array, and use the address difference between them (one of the exercises was doing this more or less).
Keywords: mips-asm
Submission reference: IN382
What is the convention for comments? should every line of code have a comment?
Maybe not every line, but probably most. The factorial example on the assessment page gives some idea of the sort of commenting I'd like. Remember that the comments should comment the program, not the code. E.g.:
lw $s0, 8($sp) #; load y
addi $s1, $s0, 24 #; x = y + 24
sw $s1, 4($sp) #; store x
and not:
lw $s0, 8($sp) #; load $s0 from position 8 on the stack
addi $s1, $s0, 24 #; $s1 = $s0 + 24
sw $s1, 4($sp) #; store $s1 at position 4 on the stack
The comments in the first case are much more meaningful (and helpful). :-)
Keywords: mips-asm
Submission reference: IN386
hi! i'm having some trouble with my code I enclosed it so you can see my problem i explain at the bottom...
do_sort_strings:
... initialisation code
li $t7, 4
li $t8, -4
do_sort_strings_loop:
#; LOADing the latest string to $a0
lw $t0, 0($sp)
addu $t1, $t0, $t7
lw $a0, 0($t1)
add $t7, 4 #incrementing counter...
#; the IF statement that allows the loop to continue
beq $a0, $zero, do_sort_strings_fin
nop
#; PRINTing first string so i can see if its all ok...
li $v0, 4 #; print_string syscall
syscall #; the end of the statement
#; LOAD second string...
lw $t2, 4($sp)
addu $t3, $t2, $t8
lw $a0, 4($t3) #; ~~change this~~
#; PRINTing second string
li $v0, 4 #; print_string syscall
syscall
add $t8, 4
#; blt $a0, $a1, do_sort_strings_2 #; skips swapping
there is more code later, but a few things: firstly in order to print both strings it only seems to work with $a0 which i quite annoying, so if i want to use the commented out branch statement (at the end) then i just alter the bit labeled "~~change this~~" and comment out the print code, and uncomment the last "blt" command.
what i want it for the blt to skip to "do_sort_strings_2" if $a0 is less than $a1, but it just always swaps them, yet i believe that the strings are correctly stored in $a0 and $a1, and the comparison should work. why does it always this the statement is false/true and not vary, it used to a little while ago!! now it doesn't work but nothing's changed.
I've been stuck on this for quite a few hours now, do you have any hints? thanks!! p.s. im starting to dislike assembler code!
For printing strings, yes, that particular system-call expects a pointer in $a0, to the string, and the value 4 in $v0 (meaning the "print-string" system-call). That's not a problem, however -- you could just store pointers to the strings in different registers, and "move" (copy) them into $a0 for printing. E.g.:
lw $t0, 0($sp) #; load saved array parameter
addu $t1, $t0, $s2 #; assuming $s2 has some scaled index in it,
#; add to get address of desired array element
lw $s0, 0($t1) #; load array element (address of the $s2'th string)
... do some other stuff
move $a0, $s0 #; load saved address of the $s2'th string (saved in $s0)
li $v0, 4 #; print_string
syscall
The "... do some other stuff" code can happily use $a0. In theory you could use $a1 and just not print the string.
At this point I'd suggest you read Question 51 (2005). The string comparison is not as trivial as your code suggests. You have this kind of thing:
blt $a0, $a1, dss_l2 #; skip swapping
What this actually does (and as you've kind of discovered) is compare the addresses of the strings -- not the contents of the strings themselves. As suggested in the question you should write a separate routine for comparing strings; instead of the "blt $a0, $a1, ..." you should be calling your string-comparison routine. $a0 and $a1 would be the correct registers to pass the addresses of the strings in though. Question 39 (2005) and Question 21 (2005) should give you some hints as to how to code this.
Incidently, your code uses the $t0-$t7 registers a bit liberally. Question 32 (2005) and Question 41 (2005) explain a bit about the difference between 's' and 't' registers. Basically you should not expect the contents of the 't' registers to be preserved across a subroutine call. system calls do not trash the 't' registers, but probably better to assume that they do (they might).
Assembler programming can get frustrating at times, but it should give you a useful insight into how computers actually work, and what anything written in another language (e.g. C, Java, C++, Haskell, etc.) ultimately gets reduced to. It's also a good experience of the sort of code that actually goes into operating-systems, e.g. if you were programming a boot-loader on the PC, you've only got 512 bytes to start with (no operating-system, no libraries, no anything else) -- assembler is the only option. Furthermore, many applications specifically use chunks of assembler (e.g. MP3 decoding) to get maximum performance from the hardware; games may also use chunks of assembler for implementing time-critical things (e.g. performing a set of rotations/scalings/translations on graphics vectors). On the fun side of assembler programming (yes, this exists!) you can make the average PC do some pretty impressive things in real-time. See the assembly (downloads mostly from scene.org) for examples. Keep meaning to show one of these in a lecture sometime..
Keywords: mips-asm
Referrers: Question 79 (2005) , Question 82 (2005)
Submission reference: IN387
hi, i'm doing the string sorting option (like everyone else it seems :/) and i'm having trouble figuring out how to swap the position of two strings in the array, for example in java to swap you could use a new variable z and do something like:
String z = array[0];
array[0] = array[1];
array[1] = z;
Is the same sort of thing done in mips? using another temporary register to store one of the variables while you switch them around?
Generally speaking, yes. However, the code that you have there is loading and storing values in the array as well. If the above were C, the literal assembler translation of it is only about 4-8 lines :-). The assembler code gets more complicated when variable indices are used (rather than constant 0 and 1). If the above were C, the assembler would probably look like:
la $t0, array #; temporary for address of "array"
lw $s0, 0($t0) #; load array[0], using $s0 for 'z'
lw $t1, 4($t0) #; load array[1]
sw $t1, 0($t0) #; store array[0]
sw $s0, 4($t0) #; array[1] = z
Keywords: mips-asm , mips-string-sorting
Referrers: Question 78 (2005)
|
Maintained by Fred Barnes, last modified Thu May 8 12:58:03 2014 |
