PROGRAMMING
Assembly line
A text enciphering program—Part 1.
by Douglas Weir
Although this is only the sixth installment of Assembly line, we've already managed to cover a large part of the 68000's instruction set, and almost all of its addressing modes. This time we'll meet the last of the latter—Address Register Indirect with Index; plus, one of the most complex of all the instructions, link.
Last time we learned a technique for passing parameters to subroutines, by pushing them on the stack, then using the Address Register Indirect with Displacement mode to read them from within the subroutine—without actually popping the values and disturbing the stack itself. The only difficulty with this, as used in the program, is that the displacement values have to be tediously recalculated for every subroutine, depending on how many registers the subroutine saves on the stack when it begins. However, there's an easier way to go about this.
The link instruction.
One of the nicest features of the so-called structured programming languages like Pascal or C is local variables. You can write a function or procedure with its own set of variables, some of which may have names identical to those in other subroutines, but which are active and accessible only within the subroutine to which they "belong." They exist only as long as the subroutine is active, and when it terminates, they do also.
This feature can be duplicated in assembly language; the 68000 implementation is founded on one instruction which handles practically everything. This instruction, link, is probably the single most complicated in the entire 68000 set. To make a long story short, it reserves a block of memory on the stack. This memory can then be used (via an address register used as a base pointer) as space for "local" variables just as if it had been reserved in your data segment. A second instruction, unlk (unlink), is used to de-allocate this space when you're finished with it.
The link instruction requires two operands, separated (as usual) by a comma. The first is an address register (usually not a7, for reasons which will become clear later). The second is an immediate value. Let's assume that a subroutine, which we'll call blop, begins with the following code:
| blop: | ||
| link | a6,#0 | |
| movem.l | d0-d4/a0-a5,-(a7) |
Here's what happens when the first instruction, link, is executed:
The contents of the address register specified, in this case a6, are saved on the stack. Then, the updated contents of the stack pointer, a7, are copied into a6. Finally, the immediate value specified as the second operand is added to the current contents of the stack pointer. In this case the value is 0, so the value of a7 remains the same.
So now the situation is as follows. Register a6 points to a constant location within the stack: in fact, it points to a copy of its own previous value, which was the last thing stored on the stack. Four bytes "up" from this value is the subroutine return address, which was automatically pushed when the bsr or jsr that got us here was executed. Beginning at an offset of 8 bytes from the current value of a6, we will find any parameters that were pushed just prior to the subroutine call. For example, suppose we call blop with the following sequence of instructions:
| move.I | d0,–(a7) | push a longword |
| move.w | d1,–(a7) | push a word |
| move.l | d2,–(a7) | push a longword |
| bsr | blop | branch to subroutine |
Within blop, after the link instruction has been executed, it's easy to access these parameters as follows:
| move.l | 8(a6),d7 | get 3rd parm pushed |
| move.w | 12(a6),d6 | get 2nd parm pushed |
| move.l | 14(a6),d5 | get 1st parm pushed |
Even though blop saves several registers on the stack immediately after the link is executed, the offsets to a6 remain the same. This is because the stack operations affect the value of a7, the stack pointer—not a6, the "link register" specified.
That's one feature of link: it sets up an address register as a useful marker into the stack, something like a book-mark. Just as important, however, is link's memory-allocation function.
The second operand to link, as mentioned, is an absolute value which is added to the contents of the stack pointer a7. If you consider what the stack looks like just after the execution of a bsr, it's clear that adding a value to a7 will probably result in the loss of the subroutine return address, which is the value currently at the top of the stack (before the link is executed). You'll recall that we've been adding values to a7 after the execution of subroutines, when the parameters had been pushed on the stack before the call. The result in those cases was that the stack was "cleaned up"; in other words, it was just as if we had laboriously popped all the values we had pushed before the call, and the stack pointer was restored to its original value. Who would want to do this to the stack pointer at the beginning of a subroutine?
The answer is, no one. The immediate value (if it's not 0) in a link is usually negative, which results in its being subtracted from the value of a7:
link a6, #-20 allocate stack space
Register a6 is saved, then loaded with the updated value of a7, just as before. The 20 is subtracted from the value of a7. This has the effect of reserving 20 bytes on the stack. The next data pushed on the stack after the link has been executed—if it's a word—will be written at an address 22 bytes "lower" than the last data pushed, which was the long-word value of a6. (Notice, I said 22 bytes, not 20. Remember, the stack pointer is decremented by an amount equal to the size of the data being written, before it is written.)
How do we access these 20 bytes? We could use positive offsets from a7. But if we wanted to use the stack for other miscellaneous purposes during the subroutine, we'd have to keep track of any operations that might affect the value of the stack pointer, because they would require the offsets to be changed. An easier way is to use negative offsets from the link register a6. For example:
move.l d0,-20(a6) write a longword
Now you can see how local variables in, say, C could be implemented on a 68000 machine. The number of local variables in a function would be calculated, and the total amount of memory space required would be allocated as a negative immediate value in a link instruction. The variable names could then be equated to negative offsets from the link register. Thus, if you had a variable named glop, it could be written to with the following instruction:
move.w d1, glop(a6)
...where something like the following data declaration appears elsewhere:
glop equ -16
In future installments of Assembly line, we'll come back to this use of link for memory allocation. Right now, we're interested in it mainly as a convenient way to set up a stack marker; when its second operand is 0, nothing is subtracted or added to a7, and it, and the designated link register, have the same value after the link is executed.
The effects of link are undone with unlk, which takes only one operand—namely, the link register. The stack pointer, a7, is loaded with the value from the link register. This restores the situation we had just after the link register was originally saved by link, and deallocates any memory then reserved. Then, the top longword of the stack is popped back into the link register, and everything is just as it was before the link was executed. Therefore, it goes without saying, that you should never alter the value of the link register between a link and unlk—at least, not without being extra careful to restore it before the unlk is executed.
Value-Added Addresses.
Our last addressing mode, Address Register Indirect with Index, is not really very different from the Displacement mode we learned last time. The concept is practically the same: a value is added to the contents of an address register, and the result is taken as the "effective address" of the operand. The difference is that the value added, instead of being an unalterable constant coded into the program, is instead contained in a designated data register. This allows you to implement assembly language versions of arrays, where the address register contains the base address of the array, and the contents of the data register—incremented or decremented as need be—are used as an index from the base. Hence, the mode's name.
The format of this mode is easily described. It's an expansion of the Displacement mode format. As before, the base (address) register is enclosed in parentheses; also within the parentheses, however, is the index (data) register, preceded by a comma. The data register is followed by a size specifier: "w" means that the contents of the low word of the register is to be used as the index value; "l" means that the entire longword contents of the register is to be used. You must also indicate a displacement in front of the parentheses, as before. You can specify a zero displacement if you want none. Any address register can be used as a base register, and any data register can be used to hold the index.
Here's how it looks. Suppose you've loaded the base address of a table of byte-size SAT scores into register aO. The following code will read the sixth element of this table into register d2:
move.w #5, d0 load index register move.b 0(a0, d0.w), d2 read sixth element
The index register is loaded with a 5 to get at the sixth element, because we're counting from offset 0, as with a C array. If you wanted to count from offset 1, you could specify a displacement of -1:
move.w #6, d0 move.b -1(a0, d0.w), d2
Note that the d0.w in the parentheses specifies what part of d0 is to be used as an index register; it has nothing to do with the size of the data read, which happens to be a byte here. If, by the way, our table had consisted of word-size elements, then an immediate value of 10 would have been required in d0 (in the first example, with 0 displacement). The technique of taking an ordinal subscript value, and generating from it an offset which can be used as an index into an array of multi-byte-size elements is known as "scaling," a technique we'll be using in the future.
Of course, the real power of this addressing mode is seen in loops, as we'll see in this month's program.
An enciphering program.
This month, I wanted to try something a bit different. The result is a program that enciphers text: that is, it inputs a line of characters you type, terminated by a carriage return, and outputs a line of unintelligible gibberish. The difference between this program and, say, advertising copy is that: (1) the program only does a line at a time; and (2) it follows a set of rules in its enciphering, thus allowing the text to be deciphered...I hope. We'll see if that's true in our next installment.
Instead of explaining what happens line by line—the program is really too long for that—I'll briefly describe how it behaves when run, then how it enciphers text—its algorithm, to use the technical term. Our new addressing mode, as well as link, unlk and a few other new (but not nearly so complicated) instructions are used.
The program begins by displaying a brief sign-on message, then waits for your input. It will allow you to type about a line's worth of characters. Hitting RETURN will end the input, or, if you type too many characters, the program will end it for you (that's to prevent the enciphered string from extending into forbidden memory). The TAB key works; BACKSPACE doesn't. This was the best way to keep the program simple, given that we're processing characters keypress by keypress. When input is concluded, the enciphered string will be written on the line below the input string, and the program then ends. To encipher another string, you have to run the program again. I got this dandy idea from my local bank's automatic teller machines.
The method of enciphering is as follows. The characters are input, of course, as ASCII codes. Alphabetic codes are converted into lower case—if necessary—and then, by subtracting the code for lower case "a" into a number from 0 to 25. (Non-alphabetic codes are passed through and not enciphered, to show how ranges of values can be checked for in assembly language.) The converted character code is now used as an index into a table of ASCII character codes (ciphers in the program's data segment).
The table consists only of all the lower-case ASCII codes, from a to z, in ascending order. Obviously, if we don't do any further converting, the result of indexing into this table of byte-size values will be that we'll simply get an element containing a code identical to the index.
So a fixed value is added to every index before the table is used. If, for example, the value is 2, then an "a" will be translated into a "c," a "g" into an "i," and so on. If the resulting index is larger than the size of the table (which happens if, say, a "z" is to be translated), then the size of the table is subtracted from the index, resulting in a "wraparound" effect ("z" is translated into "b," "x" is translated into "a").
However, anyone who's read Edgar Allan Poe's The Gold Bug knows that this kind of straight substitution cipher is ridiculously easy to break: you look for the most common letters (usually beginning with "e"), obvious combinations, and so on. Something more is needed.
Instead of having one constant add-in value, we'll use a table of them (incs). Each value will be used for a certain number of characters, then the next value will be used, and so on. When we reach the end of the table, we'll start at the beginning again. Not being a cipher expert, I have no idea how effective this ramshackle scheme really is, but I must admit to a certain satisfaction as I was testing the program whenever I noticed letter pairs that happened to be enciphered into non-matching letters.
Go for it.
Aside from mentioning the instructions and techniques that we haven't used before, that's as far as I'm going to explain the program for now. This is probably all you'll need, although I will go into more detail next time, when I'll also offer a deciphering routine. In the meantime, I think you can have some fun trying to sketch out how to implement the deciphering.
The first thing I want to discuss is how the character code ranges are checked. This occurs between the labels e__nxt0 and e__nxt2. The method is simple, and is used several times. To check if a code lies between, say, "A" and "Z" inclusive, I first compare the code for "A" to it. If the code is lower than "A," it can't possibly be within the range. If it's not lower than "A," I then compare the code for "Z," plus one, to it. If the code is lower than this value of ASCII "Z" plus one (which happens to be the code for "["), then I know that the code does fall within the A to Z range; otherwise, it doesn't.
As you might expect, a cmp instruction is used to implement these comparisons. However, we're not checking for simple equality of operands, as we were in previous programs; here, we're checking to see if the destination operand is less than the source operand (an immediate value, which explains the cmpi, "compare immediate value"). Checking the zero flag in the Condition Codes Register won't do us any good. Instead, we check the carry flag. It tells us whether or not the last instruction generated a "carry" or "borrow," which happens when a value is subtracted from a smaller value.
Suppose you wrote down on paper the simple subtraction of 9 from 10. Starting with the rightmost column, you find that 9 can't be subtracted from 0, so you borrow 10 from the left column, and 10 minus 9 is 1. In this case, the 10 was there to be borrowed. On the 68000, the carry flag would be set if 9 was subtracted from 0: a borrow was required, but was unavailable. Thus, the state of the carry flag after a compare or subtract will tell us if the value being subtracted was greater than the second operand. But, only if it was greater. That's why I check the top end of the range with an immediate value one greater than the range itself. If I used the ASCII value of "Z" to check the upper limit in the example above, the value of "Z" itself would never be detected as being in range. Subtracting ASCII "Z" from ASCII "Z" will set the zero flag, but clear the carry flag.
Thus, the cmpi instructions are followed by bcc (branch on carry clear), or bcs (branch on carry set) instructions, as appropriate. There are many other ways to check value ranges, using other CCR flags, but this seemed the simplest to me at the time. I'll have more to say about binary arithmetic in future installments.
Under label e__nxt2, you can see how I get the current increment from incs and add it to the ASCII code to be enciphered. If the result is greater than the size of the table, I just subtract (with a subi, "subtract immediate value" instruction) the size of the table from it. This results in the "wrap-around" effect I mentioned above. The technique is also used under e__raw on the index into incs itself. By the way, note how nice it is that our tables all have byte-size elements: each element's ordinal number is the same as its offset in the table. I must warn you, things won't always be this easy.
Finally, there are a couple of novelties in the data area at the bottom of the program. First, there are two "variables," space reserved to be written to as well as read from: last__ch and c__string. This space is reserved with the ds (define storage) directive, which is followed by a dot and a size specifier. Then, after at least one space, comes the number of elements to be reserved. One byte is reserved for last__ch (which always contains the last character typed; this allows me to override the action of BACKSPACE, by simply reprinting the last character), and 100 for c__string, where the enciphered string is written, prior to its being displayed on the screen. (One hundred is 20 too many, but I'm excessively cautious in these matters.)
The string and table size constants (S__SIZE, C__MAX and I__COUNT) are defined by having the assembler calculate the number of bytes between the current value of the assembler's location counter and the value of the table's base address (symbolized by its label—for example, ciphers). The nice thing about this is that you can change the size of the table simply by inserting or deleting values; the assembler will calculate the new size. Again, the operation is easy here because the elements are byte-size.
We'll continue with this project next time. Until then—uoou mcempun.