CS50 - Section 11

Section Information


ANT

For assignment 9, you need to write a small amount of ANT assembly language. At first, the programs may seem daunting, but if you approach it methodically and carefully, it should not present any major difficulties.

Professor Kernighan has made several remarks about how unpleasant assembly programming can be, and in the general case he is right- it's not something that you want to do forever. However, it can be an interesting thing to do, and a lot of fun in the short run (sort of like camping is something that people enjoy doing on the weekends, but not many people want to live their lives in a tent).

The Ellard Guide to Writing in Assembly

  1. Define your algorithm.

    For this assignment, we give you the precise algorithms for the code you need to write, so this shouldn't be a problem. You may find it useful to modify these algorithms slightly, in order to express them in ANT, but make sure that you have the basic ideas totally nailed down before diving into the code.

  2. Write your program in C (or at least in pseudo-C).

    If you can't precisely specify what it is that your algorithm is supposed to do and how to do it, then there's little chance you'll get it right be tinkering with it in assembly language. Since the beginning of the semester, you have been learning how to express algorithms precisely by writing them in C. Use this experience!

    Note that the most appropriate or elegant algorithms in C may not be the most appropriate or elegant algorithms in ANT. Think about what's going to be easiest to express in ANT; it may change your algorithm.

  3. Study the ANT references and look over the examples from lecture and the course notes.

    If you don't know how to express yourself in ANT, then even the best algorithm is doomed to failure.

  4. Divide the algorithm into smaller and smaller pieces.

    Eventually, each piece of the algorithm should start to look like something that you can easily convert into a sequence of ANT instructions and/or data declarations.

  5. Decide what temporary variables you need, choose registers to keep them all in, and document this.

    Do this before you write any code, and once you start to write code be very reluctant to change the register allocations without good reason! If you change the meaning of a register in one part of your code, you may need to change many other parts of your code in order to avoid clobbering something else.

  6. Don't try to write everything at once.

    Write small pieces that you can check and test carefully. An example of this in included later in this handout.

    Make use of the ANT debugger (ad) to test your code. You can execute your code line by line, checking to make sure that what is in the registers and data memory is what you expect after each step.

  7. Learn the debugger.

    ANT comes with a decent debugger. Learn your way around it! You will not be able to debug your programs by staring at them- most people find the debugger invaluable (the rest find ANT programming impossible, because they can't find their bugs without using the debugger).

    The debugger takes five minutes to learn and can save you hours.

  8. Use checkin early and often, and use scratch files.

    Make sure you keep track of what each scratch file is used for (i.e. what idea you were experimenting with in it) so you can pick out the good stuff later. There's no reason why the programs you need to write for this assignment should be the only ANT programs you ever write!

Arrays in ANT

In assembly, arrays are just a pointer to the first element in the array. If you want to get at the nth item in an array, you'll need to compute the address of that item. The general calculation, in C-like notation is:

	/* Address calculation in assembler:		*/
	/* NOTE: this is different from address		*/
	/*	calculation in C!			*/
	&A [x] == &A [0] + (x * sizeof (each element of A));

In ANT, this all greatly simplified by the fact that the size of each element (at least for arrays of bytes, which are all you need to worry about for this assignment) is exactly one. Therefore, this reduces to the following more C-like expression:

	&A [x] == &A [0] + x;
		/* or just */
	&A [x] == A + x;

So, let's imagine that you need to get at the nth element of A, where the address of the first element of A is stored in r2 and n is stored in r3, and put it into r4.

	lc	r2, $A		# r2 = &A [0];
	ld	r4, r2, r3	# r4 = A [x];

There are a few examples of strolling through arrays in the code we offer as examples: reverse.asm is pretty clear, and of course there is always the silly bigadd.asm.


Creating Your Very Own ANT

With any luck, this will be the most rewarding and fun assignment of the semester. You will implement most of the important aspects of a realistic virtual machine. At the beginning of the semester, you may have known nothing about computers, but now you know enough to create your own! (You might find this boring, but to me this seems extremely cool.)

Some guidelines that you might find useful:

Random Implementation Notes

  1. There are a lot of things that can go wrong with the get_int syscall. That's why the spec is so shaky- if the user types in a valid integer in the range from -128 to 127, your ANT should be able to deal with it, but if they type in some garbage, or something too large or too small, or any other sort of nonsense, then the results are undefined. This was done to make your life easier.

  2. There are a few errors that you need to check for over and over again, on most of the instructions. Perhaps you should make a function to do this error check.


Please bring any errors or inconsistencies in this document to the attention of the author.

Dan Ellard - (ellard@deas.harvard.edu)