Machine Problem 3, due at the end of Mar 4
Part of
the homework for CS:2630, Spring 2024
|
Framework: Your program must begin and end as follows:
TITLE "mp3.a by YOUR NAME HERE" USE "hawk.h" USE "stdio.h" EXT MP3DATA INT MAIN S MAIN ... your code here ... END
Obviously, where it says YOUR NAME HERE put your name, and where it says ... your code here ... put SMAL Hawk code to solve the problem.
Specification: The declaration, EXT MP3DATA defines the symbol MP3DATA as the address of the first word in an array of words, where each of the words in this array holds either the address of a character string or the address of a similar array of words. The last word in the array is a null pointer. As a result, the data structure is an n-ary tree, where each internal node contains zero or more pointers to subsidiary nodes, where character strings serve as leaf nodes.
Pointers to internal nodes in this tree hold word-aligned addresses. All leaf nodes begin at odd memory addresses so they are not aligned.
Your program should traverse the tree in order, printing the strings in leaf nodes as they are encountered and recursively descending into subtrees. All control characters for formatting the strings are included in the strings, so your program should not produce any additional output.
To run your program, you will have to link it with the object file that defines MP3DATA. Assuming that your source code is in a file named mp3.a, assembling this file will produce a file called mp3.o. To link this with the data, use this shell command:
hawklink mp3.o ~dwjones/mp3data.o
Once you do this, the object file link.o will contain both your code and the data structure that your code is responsible for interpreting.
Understanding the data structure: At an early stage in your debugging, it might be worthwhile to declare your own MP3DATA instead of using the larger data that your code must ultimately be able to process. In that case, replace:
EXT MP3DATA
MP3DATA:W HEL,SUB1,SPACE,SUB2,LD,0
SUB1: W LO,0
SUB2: W SUB3,SUB4,0
SUB3: W WOR,0
SUB4: W 0
B 066 ; make the address odd
HEL: ASCII "Hel",0
LO: ASCII "lo",0,066
SPACE: ASCII " ",0
WOR: ASCII "wor",0
LD: ASCII "ld!",LF,0
For a diagram of the above example input data, click here.
Given this input data, your program should produce the output "Hello world!" verbatim, with just one newline at the end. Notice that the order that the tree nodes are stored in memory is not important. What matters is the order of the pointers in MP3DATA.
We strongly recommend that you work out your algorithm in a high level language like C before trying to reduce it to assembly code. But note, forcing C data structures to begin at odd addresses is really difficult, so you will be forced to do your debugging in assembly language.
Grading: 5 points. Correct output is worth 2.5 points. The remaining credit will be offered only for those who have correct output.
Code that does not assemble will not earn any credit.
Stylistically clean code is important; that is why half the credit is reserved for style, but only if the code works. Awkward indenting will be penalized up to 1 point from the 2.5 style points. 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.
Note: Comments should not repeat the assignment. Assume that the reader of your code has read the assignment. Assume that the reader knows how to program, so commenting ADDSI R3,1 with increment R3 would be stupid. Comments should help the reader when the code is hard to follow.
Comments that give a high-level language equivalent for one or a small block of machine level statements are appropriate. If that style of commentary is used, please use sensible indenting and spacing rules for the "code" in the comments and use sensible variable names. So it might make very good sense to comment ADDSI R3,1 with counter++ because this explains that R3 is a counter and consistent use of high-level language code in the comments allows you to read the algorithm in the comment part of the assembly code. Of course, the high-level language code itself may still need comments. Don't omit those!
Note: As a general rule, the first lines of every file should identify that file. The TITLE in the code framework above does this. Please avoid using lines longer than 80 characters -- this is a common rule in the style guidelines of many employers. As a consequence, it is almost always a bad idea to maximize your editing window, since the default width of the window is 80 characters. Better to use the remainder of your screen realestate to open other windows for reference.
You can use the following tool flag many common file format problems such as overly long lines or invisible characters:
[HawkID@fastx?? ~]$ ~dwjones/format mp3.a
This format checker does not know anything about C or SMAL, it is looking for things that cause trouble with files imported from Windows systems, over-length lines, and non-printable characters.
Submission: To submit your work, it must be in a file named mp3.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 mp3.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. The completed dialogue on your screen will look like this when you are done:
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.
I'm getting some output but I'm having trouble getting the right output.
Try translating your code back to C-ish code an see if the C code you get makes any sense. It's much easier to identify logic errors at a high level than by looking at machine code.
I have taken your comments into consideration and edited my code. Can you look at it?
Your code had no comments at all, so I didn't even try to read it. Please translate your code back to a level comparable to C so I can see what it is trying to do.
I get the following output:
A poet from Hills was subversive To have sa Instruction Trap. Trap PC = #00001090
I can't figure out how to make sense of this.
Your code attempted to execute an instruction at address 1090 but that instruction was not a legal Hawk instruction. Because the Hawk has only a few illegal opcodes, your code may have successfully executed several nonsense instructions before it finally hit one that caused the trap. This makes it hard to work backward to where your code failed from this.
The address 109016 is in the region of memory allocated to your program, so if you subtract 100016 from 109016, you will get 9016. If your assembly listing (the mp3.l file) includes code or data at address 9016, that is where the CPU was trying to execute code when it died.
Looking at your program, it is not that big. The address 109016 is beyond your code, which puts it in the area where the Hawk linker put MP3DATA. So the question becomes, how did your program end up trying to execute the data structures and strings in MP3DATA? There are two possible ways this might happen?
First, it is possible that you left the return off of the last subrouting in your code. When the CPU got to the end of that subroutine, instead of returning, it simply continued to execute, working its way through pointers and character strings until it hit something that could not be interpreted as a legal instruction.
Second, your code loaded a nonsense value into PC. The most common place where your code loads a value into PC from RAM is in the return from a subroutine with the instruction LOADS&bsp;PC,R2. If R2 does not point to the return address, this will load a nonsense value. It is hard to solve this problem without storing pointers to parts of MP3DATA in local variables, so failing to adjust R2 correctly has a significant chance of leaving it pointing to a pointer to some part of MP3DATA. That kind of error would be highly likely to lead to the symptoms you reported.
