Machine Problem 5, due at the end of Oct 30
Part of
the homework for CS:2630, Fall 2023
|
Top Level Specification: Your program should read text from an external source MP5DATA and write it out to the screen. This sounds just like MP1, except:
MP5DATA consists of a sequence of "words" separated by NUL characters, and the component "words" must be output in alphabetical order. A component "word" of length zero indicates the end of the data. NUL characteres are the only ones with special meaning. Spaces and punctuation within the "words" are treated the same as letters or digits.
If MP5DATA were to be declared in C, you might see something like this:
const char const * mp5data = "fortnight.\0came \0eve"
"ry \0down \0bug \0A \0";
Note that:
The expected output from processing this example would be:
Spaces in the input data are
A bug came down every fortnight.
Pragmatic detail: Your program will have to declare MP5DATA as follows:
EXT MP5DATA
MP5DATA is defined in its own object file, so to use this data, you will have to tell the linker where to look for it. The following link command does this:
hawklink count.o ~dwjones/mp5data.o
Some thoughts on the problem: Your program will have to gather all of the "words" (which might contain spaces and punctuation) into a data structure of some kind, then extract them from the data structure in alphabetical order for output.
In reading MP5DATA, you can measure the length of each "word" with STRLEN and then advance the pointer by that much (perhaps plus a bit) to find the next "word."
You could copy "words" with STRCPY, but there is no need to do so, because you can just work with pointers to each "word." (That is, the addresses of the first character of each "word.")
You can put out each "word" with PUTSTR.
What kind of data structure should you use to hold (pointers to) all of the "words?" Nothing in the assignment tells you how many "words" there will be. There could be two, there could be thousands. This means that you should probably think in terms of a dynaic data structure, using MALLOC go grab memory for (the pointer to) each "word" as you discover there is one. Obvious data structures include:
The final step, in either case, is to traverse the structure in the right order to output the "words."
Of course, you could also count the strings in MP5DATA and then allocate an array big enough to hold that much, then scan MP5DATA again to extract (pointers to) the "words," before sorting the array.
This is a hard enough problem that solving it in assembly language without a clear idea of how to solve it in a high level language like C is going to be futile. Even before you start coding in a high level language, you need to make strategic decisions about what data structure and what algorithm you want to use.
We strongly suggest that you work on an incremental solution. First, just work on picking apart MP5DATA into component "words" and output them directly. Only after you have success with that should you try building a data structure that you can then traverse to output the "words." If you plan well, you should be able to build the data structure without alphabetizing before you finally tackle that detail.
Grading: 5 points. Correct output is worth 2.5 points. The remaining credit will be offered only for those who have reasonably correct output.
Code containing assembly errors will not earn any credit.
Your program must be written in SMAL Hawk assembly language, and it it must be formatted so that it does not trigger warnings when you run
[HawkID@fastx?? ~]$ ~dwjones/format mp5.a
The final 2.5 points of the score will be based on program organization. Stylistically clean code is important; that is why half the credit is reserved for style, but only if the code works. Bad indenting of the assembly code itself will be penalized up to 1 point from the 2.5 style points. The use of indenting to improve comment readability is equally important. Excessive or inadequate white space within and between lines will be penalized, again, up to 1 point. Excessive or inadequate comments will be judged similarly.
Comments must show clear evidence of planning. Clear comments in a notation similar to C are very valuable. If the code does not do what the comments say, that will be penalized. Control structures in your code that cannot be expressed in a readable high-level language style of commentary will be penalized. Comments that do not reflect the actual control structure of your code will be penalized. When you edit your code, don't forget to update the comments.
Function headers are important. Do not deviate from the standard Hawk calling sequence rules. Document your activation records! Document the registers you use (but note: everyone should know that R1 and R3 are locally available between calls to functions.
Do not put off commenting your code! If you ask for help with your code and it is not properly commented, you will be told to write good comments first! This is because the exercise of writing good comments frequently helps you find out what your code really does, and even when it does not, the comments tell us what you thought your code was supposed to do.
If you base your code on examples from the notes, code distributed in previous course offerings, code distributed with lecture notes, or any source other than your own brain, say so! Cite your sources! Failure to cite sources will be penalized.
Submission: To submit your work, it must be in a file named mp4.a in your current directory on the CLAS Linux system, and you must know your section number. In the following, what you type is shown in bold face. Begin at the linux command-line prompt:
[HawkID@fastx?? ~]$ ~dwjones/submit 0A0X mp5.a
Note: The ~dwjones must be verbatim, do not substitute another name. Also, use your section number (one of 0A01 to 0A05).
The submission script will copy your code and, after the copy is made, it will output a message saying "successful submission." You may resubmit as many times as you want; each time you resubmit, your previous submission of that file will be replaced, so we will only see your final submission.
In the event of insurmountable trouble, do not delete or edit files you have submitted until the graded work is returned. The operating system record of the last edit time and date and the backups maintained by the operating system are proof of what you did and when, and they allow us to investigate what happened. until your graded work is returned. This way, the time stamp marking the time of last edit is a trustworthy indicator of whether you did the work on time.
Having heard no questions yet, I thought it might be helpful to comment on my experience solving the problem:
First, if I'd started in assembly language, I don't think I'd have gotten it done very quickly. I did it in C first, and thinking through the logic for insertion in a sorted data structure took half of the time it took me to solve the problem. My C solution was 67 lines of moderately well commented code.
Useful fragments of C code, out of context:
struct node {
const char * str; // the string this node refers to
struct node * nameofthisfield;
... more fields if needed ...
}
struct node * n = malloc( sizeof( struct node * ) );
n->str = s;
fputs( n->str, stdout );
Translating it to assembly code was an interesting exercise. With reasonably good comments that preserved the C code (sometimes expanded a bit because of things that were one-liners in C took a few instructions in assembly code), the code came to 167 lines, including many blank lines.
As is typical of such exercises, mistakes cost me some time. Some things I learned:
It is frequently easier to use put local variables in the activation record. To do this, just add code in your receiving sequence to save the subset of registers in R8 to R15 than that you want to use. Save them in the activation record; using field names in the AR such as R8SV is helpful.
Having done this, it is easy to forget to restore the registers you saved as part of the return sequence. Once you get this right, though, you will find that the only references to R2 between your routine's receiving return sequences are the places where it is incremented and decremented around calls. This leads immediately to a trivial optimization: Just increment once at the end of the receiving sequence and decrement once before the return sequence.
Forgetting to set pointers in newly allocated tree or linked-list nodes is an easy mistake. Remember to do this!
I was working on writing the code in C, and it works, but I'm not sure if I did it correctly.
Some things I noticed in the code I was shown:
int compare_words(void *a, void *b) {
return strcmp(*(char **)a, *(char **)b);
}
Why not just call strcmp() directly? And why take a parameter that was a pointer to a string and pass it in such an awkward way, casting it through void on the way back to being a pointer to a string?
The code used the classic quicksort algorithm, which is a really odd choice of sorting algorithm. Quicksort is famous for being slow, but it's far from the simplest sorting algorithm.
Also, array-based solutions require that you know how big the array will be. You can dynamically allocate an array on the heap, but to do so, you need to count the "words" in mp5data before you allocate the array. That means iterating through the string twice, once before and once after a call to malloc. Linked list and tree solutions are probably easier.
The program I was shown tried to dynamically allocate an array of strings like this:
char * words[] = malloc( sizeof( char * ) );
The program actually worked, but that was misleading because it is very wrong. The call to malloc allocates enough space for a one-word array, and then the program used it as if it was bigger. To demonstrate the error, all you have to do is add some more use of the heap:
int * guard1 = malloc( sizeof( int ) ); char * words[] = malloc( sizeof( char * ) ); int * guard2 = malloc( sizeof( int ) ); *guard1 = *guard2 = 0;
Now, put this code any time after filling the array before printing it:
if ((*guard1 | *guard2) != 0) {
printf( "A guard was clobbered.\n" );
*guard1 = *guard2 = 0;
}
It is highly probable that one or both guards will be allocated adjacent to or very near the array of words, there are two likely results:
Running the code on my laptop, I didn't even need to try this trick with the guards. The default setting on my C compiler seems to have automatically put in some guards and checked them.
And, I'm not sure if I'm fully understanding the part where I need to declare EXT MP5DATA. Do you mean that I need to declare right away in the beginning of the code (e.g., after USE "stdio.h" ...)
Exactly. My solution begins like this:
TITLE "mp5.a by Douglas Jones, using a binary tree"
USE "hawk.h"
USE "stdio.h"
USE "stdlib.h"
USE "string.h"
EXT MP5DATA ; the data we are to process
I had to use stdlib.h for MALLOC and string.h for STRLEN.
and when I test out the code I need write in my case, hawklink mp5.o ~dwjones/mp5data.o?
Exactly. The full sequence of commands to assemble and test your code will be:
smal mp5.a hawklink mp5.o ~dwjones/mp5data.o hawk link.o
You are welcome to construct a makefile to automate this sequence, or just rely (as I did) on the fact that the up arrow key (when running the shell) digs into the history of recently used shell commands so you don't have to type commands more than once.
I would like for R9 to be the address of the string, as it is encountered during the traversal of MP5DATA.
There is nothing at all wrong with using R9 (or any other high register) so long as you save R9 in your activation record on entry to the routine where you need it, and then restore R9 before return. This allows any subroutine to conform to the standard Hawk calling sequence.
There is just one exception. Your MAIN routine can use R9 with impunity because its caller (the Hawk monitor) doesn't make any assumptions about register contents surviving a call.
Typical code to save and retore R9 would look like this:
; fields of AR ;RETAD = 0 R9SV = 4 ; save R9 ... ARSIZE = ... ENTRY: STORES R1,R2 STORE R9,R2,R9SV ... LOAD R0,R2,R9SV LOADS PC,R2 ; return
Even further, I still cannot reason with why it is printing, as even if I edit out the line that calls my TRAV function, it still prints.
There are two ways for control to enter any bit of code: First, you can branch to, jump to or call that code, or second, you can fall into it from above.
By commenting out the call, you eliminated the first alternative. That leaves the second alternative. So, the thing to do is look at how the subroutine immediately before your TRAV code ended. Did it have a well formed return? (I checked, it didn't.)
I’ve tried various alternatives for loading the addresses of the strings. I’ve attempted to use LOAD, which results in a trap on the Hawk. I’ve also tried variations of STORE.
Take a look at the code presented in class on Oct. 25, indexed here:
http://homepage.cs.uiowa.edu/~dwjones/assem/notes/
The code is broken up into multiple source files, but you can ignore that and focus on the data structures. The code uses a linked list of nodes to represent a stack. These have fields defined as follows:
STR = 0 ; pointer to this node's string NEXT = 4 ; pointer to the next node NODESIZE= 8
STORE R4,R3,STR ; n->str = s LOAD R4,R3,STR ; s = n->str
You can take one step down the linked list as follows (assuming the same register assignments):
LOAD R3,R3,NEXT ; n = n->next
I hope that helps. To use a tree instead of a linked list, you need to replace NEXT in each node with LEFT and RIGHT but all the mechanisms for accessing and updating fields of the nodes stay the same.
I managed to make what I thought was a spectacular refactoring, but unfortunately my struggles with understanding the maintenance of return addresses led to catastrophic failure.
I looked at your code and found a classical programming error. Everyone seems to be prone to confuse the address of a variable with its contents.
Here's your code to create the array:
SL R3,2 ; -- parameter = string_count*4
LIL R1,MALLOC
JSRS R1,R1
LIL R5,ARR
STORES R3,R5 ; arr = malloc( string_count * 4 )
That stores, in a global variable (COMMON block) named ARR a pointer to the correct size array. But then look how you use it:
LIL R15,ARR
MOVE R5,R9
ADDSL R5,R15,2
STORES R11,R5 ; arr[i] = *word
This uses the global variable ARR as the array itsel and not as the address of the array. The declaration was COMMON ARR,4 allowing only 4 bytes, but the array, depending on what limerick was loaded at the time, is about 16 words (64 bytes).
On the Hawk, commons are all put in RAM below the stack, so overrunning the end of a common block clobbers the stack.
I am still not sure why my program is only printing "bd".
I looked at your code, and found this call to your tree-traversal routine:
LIL R3,ROOT
ADDI R2,R2,ARSIZE
LIL R1,TRAVERSE
JSRS R1,R1
ADDI R2,R2,-ARSIZE
ROOT is the name of the global variable holding a pointer to the root node of your tree. You are passing the address of this variable.
Then, I looked at your traversal subroutine, tracing how the parameter in R3 gets used:
TRAVERSE:
... ... other instructions
MOVECC R8,R3
... ... other instructions
LOAD R3,R8,LEFT
Here, the parameter passed in R3 is being used as a pointer to the root node in the tree. It is not being used as the address of the variable holding that pointer!
This is exactly the same error that wrote on Oct. 29, 8:51 PM. That student made the error with an array, this example is dealing with a binary tree. Programmers have been making this error from the first time a computer was built that allowed programs to manipulate both the addresses of data and the values of that data.
A student came to my office hours with a remarkably complex solution to MP5 in C. The solution invoved calling strcat() repeatedly during the traversal of the tree of strings in order to concatenate all of the strings into one big string, and then at the very end, just one call to puts() to output the result.
Certainly, that solution can be made to work, but it is very complicated! My estimate is that it just about doubles the complexity of the problem, and you certainly don't want to do that.
In summary: This machine problem can be solved with calls to just three library routines, malloc() to allocate an array or to allocate nodes in linked data structures, strcmp() to order the strings, putstr() to output the "words" in sorted order. You should not need to call strcpy() to make copies of any strings, nor to call strcat() to put them together.
I've declared EXT MP5DATA but haven't been able to access any data within it. Any help with this problem would be greatly appreciated.
This would have been a great question a week before the due date but it is a very disturbing one 6 hours before the due date. Here some example code in C to just print the "words" in in mp5data:
int main() {
stringptr p = mp5data;
while (*p != '\0') { /* how many "words" are there? */
puts( p ); /* output one "word" -- followed by newline */
p = p + strlen( p ) + 1;
}
}
You'll have to add the C definition of mp5data from the assignment, along with the appropriate #include files. I've translated the first half of this loop to SMAL Hawk assembly language:
; activation record for MAIN
;RETAD = 0
ARSIZE = 4
MAIN: ; expects nothing
; returns nothing
; uses R8 = p, the pointer into the string
STORES R1,R2
ADDSI R2,ARSIZE
LIL R8,MP5DATA ; p = mp5data;
MAINLP:
LOADS R3,R8
EXTB R3,R3,R8
BZS MAINLPQ ; while (*p != '\0') {
MOVE R3,R8 ; -- parameter
LIL R1,PUTS
JSRS R1,R1 ; puts( p )