|
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: IN389
Hi, for the bubble sort has been given, I just dont know what the "strs[i]" means in the outer for-loop.Thanks
It's the loop condition -- i.e. while that is not null/zero. The equivalent Java would probably be something like "strs[i] != null".
Keywords: mips-asm , mips-string-sorting
Submission reference: IN392
i'm looking at the semaphore assignment and I can't see how to define our own system call. I've looked through the spims documentation and can't see a mention of it. Could you please point me in the right direction?
The "system calls" here are not those involved with the "syscall" instruction. Implementing your own on that level would involve hacking the spim/xspim sources (it's only C, but ugly code..).
The systems calls that you have to add to are defined around line 718 in sema4.s, it's the array of addresses called "syscall_table". You just need to add to this mostly (and test that they work as expected). The "syscall_count" is worked out automatically in "setup_syscalls" (about line 135). Each of the entries in that table holds the address of some routine that actually implements the system-call, e.g. "sys_reschedule".
Keywords: mips-asm
Submission reference: IN394
probably a stupid question but the bubble sort you have given us sorts by the LENGTH of the two strings passed to it. So are we supposed to be sorting strings alphabetically or by length?
The code I've given for the bubble-sort does it by comparing strings alphabetically (well, by ASCII values, which is good enough) -- not by length! The C function "strcmp" takes two pointers to strings and compares them (which is approximately what you have to implement for your comparison routine here). E.g. "Ant" is less than "Zoology" is less than "bar" is less than "food". ASCII charts aren't hard to come by (google or "man ascii" on UNIX); you shouldn't need these though (except to verify the results maybe).
Keywords: mips-asm , mips-string-sorting
Submission reference: IN404
hi, my sorting program works fine now, apart from one point. in the new array 'all your MIPS' comes before 'all your base', presumably because capital letters preceed lower case in ASCII. just wanted to check that this is ok?
Yep, that's fine.
Keywords: mips-asm , mips-string-sorting
Submission reference: IN406
to implement the quicksort i'm declaring a new array to use a subarray, is this necessary and allowed?
I'm not sure it's necessary -- the string pointers already in an array, so probably best to sort them there. As for allowed, well, if it works then fine; but you may lose a few percent for implementing stuff that isn't clearly necessary.
Keywords: mips-asm
Submission reference: IN413
I'm having trouble figuring out how to store the strings back into the array, during the swap, how would I get the position to store the variables into the array, I'm guessing a backwards form of the loading from the array, but I don't know where to start, it's probably something simple that I have missed, or have I just missed the point?
In some sense it is the reverse of loading stuff from the array. You'll typically have code that looks like this for loading from the array:
#; scaled index in $s0, base address of array in $s1
addu $t0, $s0, $s1 #; address of $s0'th element
lw $t1, 0($t0) #; load address of string from the array
To store the same thing back in the array, you could just add:
sw $t1, 0($t0) #; store address of string back in the array
using the previously computed address in $t0. Unless you explicitly saved that address somewhere when you loaded things from the array, you'll need to recompute it (as in the "addu" line above).
Keywords: mips-asm , mips-string-sorting
Referrers: Question 78 (2005) , Question 85 (2005)
Submission reference: IN417
i'm having a similar problem as in Question 24 (2005), when loading a character of a string i use:
lbu $t1, 0($s0) #; $s0 being the string in the array
however this obviously only give me the first character, and i assume to load the next character would it be 1 instead of 0? how do i go about using a variable that will incremement within a loop? since lbu requires a constant offset and can't take a variable. Thanks
Getting variable indexes (rather than constant ones) is similar to how it's done when looping over the array of pointers (as "print_string" currently does, and as some of the short exercises do too). In fact it's a bit simpler (I think), because the increment is only 1, not 4. The answer to Question 21 (2005) might help a bit. There is a simpler implementation, however, based on something like:
lbu $t1, 0($s0) #; $s0 being the string in the array
lbu $t2, 1($s0) #; 2nd character
lbu $t3, 2($s0) #; 3rd character
being mostly the same as the following:
lbu $t1, 0($s0)
addiu $s0, $s0, 1 #; point at the next character
lbu $t2, 0($s0)
addiu $s0, $s0, 1 #; point at the next character
lbu $t3, 0($s0)
You shouldn't have duplicated code like this, but the point is that now the constant offsets are always zero, which makes things a bit simpler. However, it's only good if you don't mind the value of $s0 being changed (saving it somewhere else beforehand isn't much hastle if you do, though).
Keywords: mips-asm , mips-string-sorting
Submission reference: IN421
Regarding question 67:
lbu $t1, 0($s0)
addiu $s0, $s0, 1 #; point at the next character
lbu $t2, 0($s0)
addiu $s0, $s0, 2 #; point at the next character
lbu $t3, 0($s0)
Shouldn't the second addiu have a 1 insted of a 2? Ciao!
Erm, yes, I think it should have :-). Fixed it, cheers.
Submission reference: IN423
Hi. Could you please post java code for bubblesort if possible, as I tried to write mips from C code it was really challenging so i came up with my own java code but it fails somewhere that i cannot identify. thanks
Certainly, although the way that Java deals with strings is a bit peculiar -- C treats them in the assembler way (as simple arrays of byte-sized ASCII characters).
void bubblesort (String[] strs)
{
for (int i=1; strs[i] != null; i++) {
for (int j=0; j<i; j++) {
if (strs[i].compareTo (strs[j]) < 0) {
String temp = strs[i];
strs[i] = strs[j];
strs[j] = temp;
}
}
}
}
Keywords: mips-asm , mips-string-sorting
Submission reference: IN424
i have a working bubblesort and a quicksort that is far from working, should i still submit both files for the assessment and how should they be labelled?
It would be better to include the quick-sort code in the same file as the bubble-sort code; you could just give the relevant procedures different names (e.g. "do_quicksort_strings"). If you changed code elsewhere, include the changes but comment them out, e.g.:
la $a0, strs
jal do_sort_strings
#; BEGIN QUICKSORT CODE
#; la $a0, strs
#; jal do_quicksort_strings
#; END QUICKSORT CODE
Keywords: mips-asm , mips-string-sorting
Submission reference: IN425
For the sortstrings option, do we have to provide functionality to handle lists which contain no items and one item?
You're not sorting lists, you're sorting arrays -- there's a big difference! (unless you turned your array into a linked-list before sorting, and back again afterwards). The arrays can always be assumed to have at least one good item in them, followed by the null-terminator, otherwise this (Java) code would generate an "ArrayIndexOutOfBoundsException" (probably):
for (int i=1; (strs[i] != null); i++) {
...
}
Keywords: mips-asm
Referrers: Question 74 (2005)
Submission reference: IN427
I am not sure how to implement nested loops in the bubble sort by using assembly language.
Loops in assembly language tend to have the same structure applied to them. For instance, the C/Java style for() loop:
for (start; condition; end) {
... body
}
ends up in assembler as something like the following:
... start #; this happens before loopish things
lp0: #; label indicating start of loop
... condition #; do the loop-condition test
beq .., $zero, lp9 #; branch if condition false
... body #; do loop-body
... end #; do loop-end
j lp0 #; loop
lp9: #; label for end-of-loop
If you use this sort of structure, handling nested loops shouldn't be a problem -- it just becomes another loop in the "... body" of the above. Incidently, the C/Java for() loop is pretty general, in assembler the loop structure can usually be simplified a bit.
Keywords: mips-asm , mips-string-sorting
Submission reference: IN432
Hey, I wonder if you could help. I'm getting really confused with which registers to use for what, I was wondering if you could give me some hints, ie what to store the array as ($a0?), the addresses ($s0, $t0, or $a1), the individual characters($s0, $t0, $a1, $v0)? My assembly code is just a blur of numbers and letters at the moment and I keep changing the names of addresses etc to accommodate for the array, addresses, strings, constants, characters, loops etc! Please help as I have been working on this for 2 weeks now!
Before you start writing code out properly, it may be wise to figure out what registers you'll be using for what. Convention specifies how some of them should be used (e.g. $sp is the stack-pointer, $a0-$a3 are for argument passing, $v0-$v1 are for returned values, ...), the rest (mostly $s0-$s7 and $t0-$t7 are up to you).
For things that would be considered "variables" in C or Java, I'd probably use either the stack or the $s0-$s7 registers (stack only if I run out of registers usually). For values that are used during temporary evaluation I'd go for $t0-$t7 registers (since these probably won't need to be saved). E.g. given the C code:
int x = 0;
x = foo (42)
I'd write the assembler as:
#; NOTE: using $s0 for 'x'
move $s0, $zero #; set $s0 ('x') to zero (initialising declaration)
li $a0, 42 #; parameter (constant 42)
jal foo #; call "foo", result left in $v0
move $s0, $v0 #; move result into $s0 ('x')
I've not needed any temporary registers here, but might have done if the code was a little more complex, e.g.:
int x = 0;
int i = 4;
x = data[i];
which I would code in assembler as:
#; NOTE: using $s0 for 'x', $s1 for 'i'
move $s0, $zero #; set $s0 ('x') to zero (initialising declaration)
li $s1, 4 #; set $s1 ('i') to constant 4 (initialising declaration)
la $t0, data #; load address of "data" in temporary register
sll $t1, $s1, 2 #; multiply $s1 ('i') by 4 (scaling index to word-size), leave in $t1
addu $t2, $t0, $t1 #; add to get address of "data[i]"
lw $s0, 0($t2) #; load data and store in $s0 ('x')
Keywords: mips-asm
Referrers: Question 78 (2005)
Submission reference: IN428
Re Question 71 (2005), yes, I meant an array, thanks.
Good :-). Be aware that small mistakes like this can cost (not so much here, but in an exam it might).
Submission reference: IN426
Hi, I'm a bit confused as how to return to a method after a subroutine has been called, for example I have:
loop: lw $a1, 4($a2) #; loading 2nd address in array
... some code
j strcmp #; compare the two strings
blt $v0, 0, swap #; if r is < 0 ie neg, then swap
j loop #; jump back to x loop
strcmp: lbu $s0, 0($a0) #; load 1st char in 1st string
lbu $s1, 0($a1) #; load 1st char in 2nd
blt $s0, $s1, negative #; branch to nega routine
... some more code
j strcmp #; loop for next char
nega: subu $v0, $v0, 1 #; r = r - 1
jr $ra
after the "nega" method I want to jump back to loop so I can determine whether $v0 is < 1, and so I can jump to the swap method (not shown). Please help! (I know this is imcomplete but it is difficult to tell when I'm not sure which methods are being called when).
There are two kinda of "jump" in assembler (ish). The first is generally known as a plain "jump", and is roughly approximate to "goto" in C and Java (plus BASIC and any other languages that have it). The second is known as a "subroutine call", "function call", or for the more Java oriented, a "method call". The difference is that once we've jumped to a subroutine/function/method, we expect to come back. E.g. in the C/Java code "x = foo (y);", the code in "foo" gets called, runs for a bit, then returns back to the code that will assign it to "x". With a plain jump we don't ever expect to come back (at least not directly).
In your program, it's generally better to identify each type somehow. I do this with a convention like the following:
#; subroutine: strcmp -- description
#; inputs: ... input registers
#; outputs: ... output registers
strcmp:
... maybe save some stack space
... setup stack perhaps
sc_l3:
... code
j sc_l9 #; jump forward to end of subroutine
... more code
blt $v0, $zero, sc_l3 #; jump backward a bit if condition
... some more code
jal my_subroutine #; do subroutine call
... more code
sc_l9:
... restore some registers perhaps
... maybe restore stack
jr $ra #; return to caller
So, for labels that are definitely subroutines (and that when called, we expect to return), I've given sensible names ("strcmp", "do_sort_strings", "do_print_strings"). For ones that are not subroutines, but are just 'markers' for jumping around, I use abbreviated names ("sc_l1", "sc_l9", "dss_l4", "dss_l5", etc.). In your code above, the "strcmp" starts almost immediately after some other code -- not immediately clear that it's a separate subroutine (block-comments in front describing their operation will help :-)).
The "magic" of handling returning to somewhere once a subroutine call has finished depends on the jump instruction used. When jumping without the intention of returning, the "j" (jump) instruction should be used. The same applies to conditional branches, e.g. "beq", "blt", etc. When jumping to a subroutine with the intention or returning from it later, the "jal" (jump and link) instruction should be used. This causes the address of the instruction after the jump (i.e. the 'return-address') to be left in the $ra register. Hence, when a subroutine gets to the end, it executes "jr $ra", jumping back to the address held in the $ra register. But you can't conditionally branch to a subroutine like this.. However, getting around it isn't hard. E.g.:
blt $v0, $zero, foo #; call "foo" subroutine if ($v0 < 0) // BROKEN
can be written correctly as:
blt $v0, $zero, tmp_l1 #; jump forward a bit if ($v0 < 0)
j tmp_l2 #; jump forward to "tmp_l2" label
tmp_l1:
jal foo #; call "foo" subroutine if ($v0 < 0) // FIXED
tmp_l2:
the logical operation of the code is exactly the same (and there's a simpler way of doing this if you invert the test condition). Looking at your code, the most obvious error is that the jump from the sort to "strcmp" uses a "j" instruction, where it really should use "jal" (so that the subroutine can return). However, the "j" call inside "strcmp" going back to "strcmp" is correct -- this is not a subroutine call, it's looping code.
Keywords: mips-asm , mips-string-sorting
Submission reference: IN430
could you explain structs? i figure they are like small classes? in the sempahore assessment we are to pass an address of a "sema4_struct" to the semaphore methods but "sema4_struct" is commented out. uncommenting it stops the program compiling. im confused as to how to get about this problem?
You are right in that they are like small classes -- classes with no inheritance, no overloading, no polymorphism, no methods, no statics. All you're left with are "non-static attributes/fields". The "struct" I've defined in the template file is intended to be comment only. Because assembler has very little concept of types (beyond bytes, halfwords and words), the structures themselves are transparent. If you look at some of the other code in that file you'll see things like:
sw $v0, 24($a0) #; itask->sptr = $v0
The struct comment is what ties the constant offset "24" above to the "sptr" field in the structure. Things would get very confusing if you didn't have this. In some assemblers you can define constants, which can make the code a little cleaner, e.g.:
sw $v0, SPTR($a0) #; itask->sptr = $v0
exactly the same code (e.g. storing something in memory at offset 24 from $a0), but a bit more readable. I'm not sure to what extent spim/xspim support constants like these (not really tried).
Keywords: mips-asm , mips-semaphores
Submission reference: IN431
what's the difference between "b label" and "j label" ?
Generally, nothing as far as you're concerned :-). I.e. you can use one or the other interchangably. In actual fact there is a slight different, but nothing that should affect you in this assessment: the jump "j" instruction can jump further than a branch "b" instruction (should be fairly obvious if you look at the instruction encodings from Winston's architecture notes).
Keywords: mips-asm
Submission reference: IN433
Hi there, I am really stuck with swapping strings. I am not sure how to access the strings at random indices i and j? Can you drop me some hints, please? Thank you
See the answers to Question 66 (2005), Question 60 (2005) and Question 73 (2005). These should give you some clues about how to approach this.
Keywords: mips-asm , mips-string-sorting
Submission reference: IN434
Hi, is it right to use branch instruction to compare strings?
Yes, kind of. What you actually want to be comparing are the individual characters in the strings (i.e. the code that'll go in your string-comparison routine). The answers to Question 59 (2005) and Question 39 (2005) might be helpful.
Keywords: mips-asm , mips-string-sorting
Submission reference: IN436
In sorting strings how would you go by character comparisons? would you need the length of each string you are comparing with in order to compare all characters of that string?. I'm not sure how to get the length of a string if so, as they would not have a '0' at the end as a null terminator. thanks
Knowing the lengths of the strings before comparing might be useful, but isn't strictly necessary -- it mainly depends on how you program your string comparison routine. However finding out the lengths of strings is possible -- there is a null-terminator on the ends of these (a zero-byte actually, added automatically by the ".asciiz" directive, the 'z' meaning zero-terminated). Rather than discovering the lengths, it might be easier to write code that just stops comparing when it encounters this zero in either string. See the answer to Question 39 (2005) (and related questions).
Keywords: mips-asm , mips-string-sorting
|
Maintained by Fred Barnes, last modified Thu May 8 12:58:03 2014 |
