Labs for The Most Complex Machine
xComputer Lab 2: Assembly Language Programming
THE MACHINE LANGUAGE FOR xComputer consists of thirty-one different instructions. Each instruction performs a very simple task. Nevertheless, very complex programs can be built up from these instructions. The previous lab introduced the xComputer applet and the basic xComputer machine language instructions. In this lab, you will learn more about programming the xComputer. Hopefully, you'll begin to appreciate how complex programs can be composed from very simple instructions.
Machine language consists of binary numbers, but it would be almost impossible for people to program if they had to write programs directly in binary. Instead, programmers use assembly language or high-level language. The programs they write in these languages are translated by assemblers and compilers into machine language. You'll use a high-level language called "xTurtle" in later labs. In this lab and the next, you'll use assembly language.
Assembly language is closely related to machine language, but has several features that make it much easier to use. You've already seen that assembly language uses meaningful instruction names, such as ADD-C, instead of numerical instruction codes. In this lab, you'll see how memory locations and data values can also be referred to by name rather than by number. Such names are called labels. You'll also learn about a few new machine language instructions, which use indirect addressing.
The material in this lab is based on Chapter 3 of The Most Complex Machine. Labels are introduced in the postscript to that chapter.
This lab includes the following sections:
Start by clicking this button to launch the xComputer applet in its own window:
(For a full list of labs and applets, see the index page.)
Labels and the Assembler
The previous lab introduced the xComputer applet and the most basic aspects of xComputer's assembly language. Here is an example repeated from that lab. This program simply counts forever by adding 1 to location 12 over and over in an infinite loop:
LOD-C 1 STO 12 LOD 12 INC STO 12 JMP 2The numbers 12 and 2 in this program are addresses of memory locations. While this short program is not terribly difficult to understand, it can be extremely tedious and error prone to keep track of the large number of numerical addresses that would be used by a complex program. For this reason, assembly language allows you to give names to memory locations, so that you can refer to the locations with meaningful names rather than meaningless numbers. Names used in this way are called labels.
To give a name to a memory location in an assembly language program, all you have to do is put the name, followed by a colon, before the contents of the memory location. For example, the line
Loop: LOD 12in a program would give the name "Loop" to the memory location that contains the LOD 12 instruction. Elsewhere in the program, you can use the word "Loop" to refer to that location, instead of using the numerical address. For example, you could jump to that location with the command JMP Loop.
Memory locations can be use to hold either instructions or data. Labels are useful in both situations. If "Num" is the label of a location that is used to hold data, then it would make sense to use "Num" in data-manipulation commands such as LOD Num, STO Num, and ADD Num. Labels for instructions, on the other hand, are mostly used in jump commands.
Here is a version of the counting program that uses labels. The name "Loop" is used for the instruction that begins the loop, and "Count" is used for the location that contains the value of the counter:
LOD-C 1 ; Set Count equal to 1 STO Count Loop: LOD Count ; Add 1 to Count INC STO Count JMP Loop ; Jump back to start of loop @12 Count: data ; Location to be used for countingThis example introduces two other features of xComputer's assembly language: "@" and "data". The word "data" is used as a place-holder for a memory location that is going to be used by the program to contain a data value. When the assembler translates the program into machine language and loads it into memory, it replaces "data" with a zero. (Actually, you could just use a 0 in the program, but "data" is more descriptive of your intentions.) The line "@12" is not translated into machine language. It is a directive to the assembler telling the computer to store the next item in location 12. In this case, it means that the Count will be stored in location 12. Without the "@12", it would be stored in location 6, the next sequential location after the JMP Loop instruction. If there were additional items after Count, they would be stored in locations 13, 14, and so on -- until the next "@" directive.
This program is one of the sample programs loaded by the xComputer applet that you launched above. Select the program "SimpleCounter.txt" from the pop-up menu at the top of the xComputer window. Load it into xComputer's memory by clicking on the "Translate" button. Once it is loaded, you can use the "Run," "Step," or "Cycle" button to execute the program. If you need more information about using the xComputer applet, please see the previous lab.
Loops and Decisions
Complex programs can be constructed using loops, decisions, and subroutines. All of these things become easier to use when labels are available. Subroutines will be introduced in the next lab. In this lab, you will work with loops and decisions.
Loops, of course, are implemented with jump commands, when the computer jumps back to a previous location in the program. Decisions are implemented with conditional jump instructions such as JMZ and JMN. When the computer executes one of theses instructions, it decides whether or not to jump, based on the current circumstances. When the computer encounters the instruction JMZ Loc, it checks the accumulator register. If the number in the accumulator is zero, then the computer jumps to location "Loc." Otherwise, the computer simply proceeds on to the next statement following the JMZ. The JMN instruction is similar, except that it checks whether the number in the accumulator is negative. Another conditional jump instruction, JMF, tests the value in the Flag register. It is described in one of the exercises at the end of the lab.
There are two sample programs for you to look at that make effective use of loops and decisions. Each of these programs is used in one of the exercises at the end of the lab.
The sample program "ThreeNPlusOne.txt" computes a "3N+1 sequence." (This is a problem that you will see several times in these labs.) Given a positive integer N, the program applies the rule: "If N is even, then replace N by N/2; if N is odd, then replace it by 3N+1." It applies this rule over and over until the number N becomes equal to 1. For example, if the starting value of N is 7, then the program generates the sequence of values: 7, 22, 11, 34, 17, 52, 26, 13, and so on.
Run the "ThreeNPlusOne.txt" program. To see the numbers as they are generated, watch memory location number 17, which contains the successive values of N starting with 7. You will probably want to bump the speed up to "Fast." You can run the program again with any other starting value of N. Modify the value of N in the assembly language program, and then reload it into memory with the "Translate" button. (You could also change the number in location 17 directly and then run the program. If you do this, don't forget to click the "Set PC=0" button to reset the Program Counter to zero.)
You should also read the program and note how it uses the five labels, "NextN," "Odd," "Even," "Done," and "N." (The label "Odd" is defined but is never referred to in the program. It is really just there for human readers.)
Another sample program, "MultiplyByAdding.txt" adds two numbers by adding one of the numbers to itself over and over. The program is set up to multiply 13 by 7. Read the program and try it out. Use it to multiply some other pairs of numbers.
Make sure that you understand these programs and the general ideas of loops and decisions. You will need to understand them to complete the exercises at the end of the lab.
Indirect Addressing
The next sample program is "ListSum.txt." This program illustrates a common type of processing where the computer processes a sequence of consecutive locations in memory. In "ListSum.txt", the computer adds up the numbers stored in consecutive locations. It stops when it gets to a location that contains a zero. In the exercises, you will write two programs based on this one. Before doing those exercises, you should read the sample program, run it, and try to understand how it works.
The "ListSum.txt" program uses indirect addressing to access numbers in the list. Indirect addressing is used in several assembly language instructions, including LOD-I, STO-I, ADD-I, and SUB-I. Recall that LOD-C XXX tells the computer to load the number XXX into the accumulator. LOD XXX, on the other hand, tells the computer to copy the contents of memory location XXX into the accumulator. This is known as direct addressing. In the LOD-I XXX instruction, XXX is the address of a memory location, but not of the memory location containing the data. Instead, memory location XXX contains another address, and that address specifies the location whose contents are to be loaded into the accumulator. For example, if location 17 contains the number 42, then LOD-I 17 will load the contents of memory location 42 into the accumulator.
Admittedly, this is confusing, but it turns out to be just what we need to do list processing. In fact, in that context, its not all that confusing after all. Consider the following program outline:
. . ; Set up . LOD ListStart ; Load Loc with the starting location of the list. STO Loc Loop: LOD-I Loc . . ; Process the number. . LOD Loc ; Add 1 to Loc. INC STO Loc JMP Loop ; Return to the start of the loop. Loc: data ; Location of next number to be processed. ListStart: 183 ; List of data to be processed. 72 902 164 . . .The first time LOD-I Loc is executed, it loads 183, the first number in the list, into the accumulator, since the value of Loc is ListStart. After processing the 183, the program adds 1 to the number in Loc and jumps back to the start of the loop. The value stored in Loc is now the address of the second number in the list, 72. So now when LOD-I Loc is executed, it loads 72 into the accumulator. The next time through the loop, it will load 902, then 164, and so on. So, each time through the loop a different location is processed, even though the instructions in the loop don't change.
"Loc" is said to be a pointer since the value stored in Loc is not really the number we are interested in. Instead, the value in Loc indicates where to go to find the number we want. It "points" to that value. Pointers and indirect addressing are used in various ways, even in high-level languages. In the next lab, you'll see how useful indirect addressing can be in a jump instruction.
Dancing Bits
There is another sample program that I've provided mostly for your amusement, but also because watching it run might just give you a better appreciation of what a computer is really doing as it computes. Select the sample program "PowersOfThree.txt," from the pop-up menu in the xComputer Window. Read the comments at the beginning of the file, and then load the program into xComputer's memory by clicking on the "Translate" button. Set the display style to "Graphics" and the run speed to "Fastest," and run the program. You will see the bits in xComputer's memory dance as a non-trivial computation is performed.
Exercises
Exercise 1: The sample program "SimpleCounter.txt" is a copy of the program that counts forever, which was discussed earlier in this lab. Modify this program so that it counts to 16 and then halts. (This was also an exercise in the previous lab, except that in that lab, you didn't use labels.) Add a HLT statement after the JMP statement. Use the name "Done" as a name for that statement. Jump to Done when the Count reaches 16.
Exercise 2: Here is a copy of the "CountAndStore" program that was used in the previous lab. (A copy was also loaded as one of the sample programs by the xComputer applet on this page.) Rewrite this program to use labels, instead of numerical addresses, for locations 2 and 4. Do you think the program is easier to understand with labels?
lod-c 1 ; Start with a 1 in location 12 sto 12 lod 12 ; This instruction is stored in location 2 inc sto 13 ; This instruction is stored in location 4 lod 2 ; Add 1 to the number in location 2 inc sto 2 lod 4 ; Add 1 to the number in location 4 inc sto 4 jmp 2 ; Go back to the instruction in location 2Exercise 3: Modify the "ThreeNPlusOne.txt" program so that it counts the number of steps it takes for N to become equal to 1. To do this, add another labeled location at the end of the program. Call it "Count". Change the program so that it starts by storing a zero in location Count. Each time through the loop, it should add 1 to Count. When the program ends, the value in Count is the number of times the program has gone through the loop. This is also the number of steps that were computed in the sequence. How many steps are there in the sequence that begins with N=7? How about N=27? Be sure to add comments to your program to explain how Count is being used.
Exercise 4: The assembly language instruction SHR shifts the number in the Accumulator one bit to the right. That is, each bit in the binary number is moved over one bit-position to the right. The leftmost bit-position, which would be left empty, is filled in with a zero. The rightmost bit, which has no other place to go, is placed into the Flag register. A JMF instruction can be used to test the contents of the Flag register. Suppose XXX is a label. If the Flag register contains a one, then JMF XXX causes a jump to location XXX. If the Flag register contains a zero, then JMF XXX has no effect.
Write a program that counts the number of 1's in a binary number. When the program begins, the number should be stored in a memory location labeled Num. There should also be a memory location named Count for counting the number of 1's in Num. The program begins by storing a zero in Count. It then goes into a loop that shifts Num one bit to the right. If the number that "falls off the end" into the Flag register is a 1, then the program should add 1 to Count. The loop continues until the value of Num becomes zero. At that point, Count contains the number of 1's that were in the original number.
Exercise 5: Just as it is possible to multiply by adding over and over, it is possible to divide by subtracting over and over. Suppose you want to know how many times N1 goes into N2. Start with N2 and subtract N1 repeatedly until the answer is less than N1. The number of subtractions you performed is the number of times that N1 goes into N2. For example, you can compute that 4 goes into 14 three times by computing 14 - 4 - 4 - 4 = 2 . (The number 2 that you end up with here is the remainder when 14 is divided by 4.)
Write a program to compute how many times a number N1 goes into another number N2. Your program will be somewhat similar to the sample program "MultiplyByAdding.txt." You still need a loop, and you still need to count how many times that loop is executed. However, the set-up before the loop, the action performed in the loop, and the test for ending the loop are different. Note that to test whether A < B, you can subtract B from A and test whether the result is negative. In the language of xComputer, you can use a JMN instruction to test whether a number is negative.
Exercise 6: The sample program "ListSum.txt" adds up a list of numbers. Modify this program so that instead of computing the sum of the numbers in the list, it will find the largest number in the list. Change the name of the memory location "Sum" to "Max". As the program runs, this memory location will hold the largest number seen so far in the list. When the program ends and the whole list has been examined, Max will hold the largest number in the entire list. (You can compare two numbers by subtracting one from the other, and using a JMN instruction to test whether the answer is negative.)
Exercise 7: Write another list-processing program that makes a copy of a list. You can model your program on "ListSum.txt." However, instead of adding up the numbers in the list, it should copy them to another part of memory. Use a label named "Copy" to indicate the location in memory where the copy of the list should begin.
Exercise 8: The "CountAndStore" program in Exercise 1 is a self-modifying program. That is, the machine language instructions in locations 2 and 4 change as the program is executed. Another way to write the program would be to use indirect addressing. Use a memory location labeled "Loc" to keep track of which location the program is currently working on. Use LOD-I Loc and STO-I Loc to load and store values in that memory location. To move on to the next consecutive memory location, add one to Loc.
Exercise 9: Write an essay explaining in detail how indirect addressing is used in the program you wrote for one of the exercises above (Exercise 5, Exercise 6, or Exercise 7).
Exercise 10: Write an essay explaining how labels are used in assembly language programming and why they are so important. Give examples of things that can be done with labels that would be much harder to do without them.
This is one of a series of labs written to be used with The Most Complex Machine: A Survey of Computers and Computing, an introductory computer science textbook by David Eck. For the most part, the labs are also useful on their own, and they can be freely used and distributed for private, non-commercial purposes. However, they should not be used as a formal part of a course unless The Most Complex Machine is also adopted for use in that course.--David Eck (eck@hws.edu), Summer 1998