ASL/LSL -- more defense of the obvious...

In the previous post, I explained the difference of intent between "logical" and "arithmetic" shift operations in assembly language. I also demonstrated that for two's complement binary numbers, the bitwise effects of logical-shift-left and arithmetic-shift-left are actually identical. This makes the choice to implement a single physical instruction that covers both operations a completely legitimate option, which explains why that choice was made for x86, Z80, MIPS, ARM, SPARC, RCA1802, CP1610, and of course the various Motorola 68xx CPUs.

The previous post would seem to be an unnecessary defense of the obvious truth, except that it was a response to a statement made on a podcast by someone operating in a teaching capacity. Random statements are easy to ignore, but authoritative claims can pollute conversations for long afterward. So, I posted my correction in hopes of clearing the air. Alas, so far all indications are that the errant speaker remains unabashed. Given the situation, perhaps a bit more discussion is in order?

Overflow Example

It is important to consider what happens when values grow beyond the capacity of a single byte to store them. An arithmetic-shift-left is a multiplication by a factor of two, and there are only so many bits in a byte. Let's look at a couple of examples...

First, let's look at a 16-bit value, say the equivalent of decimal 32. The values in the A and B registers are shown below. The states of the Carry and oVerflow flags are unknown at the start of the example, but they will be shown in the indicated places as the example continues below.

          A Reg.   B Reg.   C   V
          ------   ------   -   -
         00000000 00100000  X   X

We will now perform a left-shift operation across the 16-bit value held in the A and B registers. This must be done 8 bits at a time, therefore two instructions are used. Since we are shifting left, we must first shift from B (with the highest bit of B going to the Carry flag) and then rotate into A (with the value of the Carry flag rotated into the lowest bit of A).

ASLB --> 00000000 01000000  0   0
ROLA --> 00000000 01000000  0   0

The value is exactly as expected: instead of 10 zeros, a single 1, and 5 more zeros, we now have 9 zeros, a single 1, and 6 more zeros. The left most bit (i.e. bit 7) in B was a zero, so now the Carry flag is zero. The two's complement sign of B was unchanged, so the oVerflow flag was zero after each of the two instructions.

Let's do another round!

ASLB --> 00000000 10000000  0   1

Here again, the leftmost bit (i.e. bit 7) in B was a zero, so now the Carry flag remains zero. Also, we see that the two's complement sign of B changes, which causes the oVerflow bit to be set. If we were confined to signed, 8-bit numbers then we could check for the V flag here and then branch to some error handling code. But since we are dealing with a 16-bit value we just continue the operation we already started.

ROLA --> 00000000 10000000  0   0

With the Carry flag as zero, the ROLA shifts the bits in A to the left and rotates the zero from Carry into the rightmost bit.

Let's try one more round...

ASLB --> 00000000 00000000  1   1

Now the leftmost bit in B was a one, so the Carry flag becomes a one. The two's complement sign of B changed, so the oVerflow flag is also a one. Again, if we were dealing with an 8-bit number then we could branch to some error handling code at this point. But since we are dealing with a 16-bit value...

ROLA --> 00000001 00000000  0   0

...we continue with the ROLA. This instruction again shifts the bits in A to the left, but in this case a one is rotated from Carry into the rightmost bit.

Hopefully the above demonstrates that while the arithmetic-left-shift may seem to do funny things at first glance when viewed only in terms of an 8-bit number, the truth is that a) the behavior is advantageous when dealing with 16-bit (or larger) numbers; and b) the flags indicate when the 8-bit results become problematic and therefore the flags can be used for handlilng those situations as required.

But...you may ask about negative numbers! Let's try another (hopefully less verbose) example. Let's start with the equivalent of decimal - 96:

          A Reg.   B Reg.   C   V
          ------   ------   -   -
         11111111 10100000  X   X

ASLB --> 11111111 01000000  1   1
ROLA --> 11111111 01000000  1   0

ASLB --> 11111111 10000000  0   1
ROLA --> 11111110 10000000  1   0

Unsurprisingly, after two ASLB/ROLA combinations (i.e. two left shifts within a 16-bit value) then the -96 value has become -384 (i.e. "4 time -96"). Also, please note that the oVerflow bit is always clear after the final rotate instruction in these examples. The value of the V bit after the first ASLB instruction is irrelevant for the overall 16-bit value being computed. Obviously this behavior is only guaranteed if proper two's complement encoding is observed across an entire 16-bit value.


Multiplication or Addition

So it seems reasonable to demand that if an arithmetic shift to the left is equivalent to multiplication by two, then the result of such an operation should be the same as the result of adding the starting value to itself:

          A Reg.                      A Reg.
         --------                    --------
         00001000                    00001000
ASLA --> 00010000        ADDA #8 --> 00010000

Another example, this time with a negative value:

          A Reg.                      A Reg.
         --------                    --------
         11000000                    11000000
ASLA --> 10000000    ADDA #(-64) --> 10000000

I'll stop here because to be honest, it is tiresome to continue thinking-up examples that are interesting enough to be worth typing. ASL as implemented on the 6809 "just works". Anyone that still needs convincing is either being dishonest or just plainly doesn't understand two's complement binary math.

That's Enough

As if the first blog post wasn't already too much time wasted on such a stupid controversy, I've now burnt another one. My original hope was that by illustrating the mathematical facts involved, we might avoid spreading misinformation among those in the retrocomputing community that were honestly trying to learn something about assembly language for the 6809. Consequently, the facts have been presented, demonstrated, and even illustrated across two different postings to this blog.

If you want to learn the truth, it's all here for you. Really, there isn't much more to say...keep hope alive!

Yes, LSL and ASL really are the same operation...

Recently I was listening to a retrocomputing-themed podcast, as I am often wont to do... This particular podcast has a recurring segment wherein a game developer from the good old days is presenting some relatively simple lessons on programming in assembly language for the Motorola 6809. This particular lesson was about shift and rotate instructions, which are used both for manipulation of data bits within a data byte and for performing the fundamental operations of multiplication and/or division by exact powers of the number 2.

I do not intend to critique the presentation as a whole. But there was one bit of misinformation presented that I feel the need to address. During the talk, the fact was mentioned that when designing the instruction set for the 6809, Motorola had chosen to implement both logical-shift-left (LSL) and arithmetic-shift-left (ASL) with the same physical machine instruction. The assertion was that this was wrong, that LSL and ASL are different operations, and that due to Motorola's failure to recognize such, one should never use that instruction. This assertion being made by one acting in a teaching capacity is so clearly wrong that I feel compelled to clarify the record.

Did the CPU architects at Motorola get it wrong? Spoiler alert: No! Neither did architects for Intel, MIPS, Sparc, ARM, or any of the other CPUs that similarly implement a single instruction for both operations. The fact is that when operating on two's-complement numbers, logical-shift-left and arithmetic-shift-left are, in fact, exactly the same operation.

Signed Binary

This (supposed) controversy is rooted in how negative numbers are represented in digital computers. As you are probably aware, digital computers represent numbers using binary numbers. For positive, whole numbers the mapping to representation in binary is obvious. But there is no obvious extension to binary numbers to account for either fractional or negative numbers. (Fractional numbers are outside this particular conversation...)

Negative numbers can be represented in binary in at least three ways: two's complement (which nearly every digital computer uses), one's complement, and signed magnitude, among others. Two's complement encoding has the advantage that basic operations like addition and subtraction between signed and unsigned values "just work" with the same hardware that is already needed for unsigned operations. Plus, two's complement does not suffer from having multiple ways of encoding the number zero. Consequently, two's complement is the encoding system used by Motorola on the 6809 (and most other designers on most other digital computers up to this day and beyond).

One point to note: although for human communication we usually do not write leading zeros on numbers, most of us are at least vaguely aware of the idea of them. More importantly, computers tend to have fixed-width places to store numbers, like registers or bytes in memory. In those cases, every bit (leading or otherwise) is either a zero or a one. For the discussion below, it is important to realize that positive numbers will start with one or more (i.e. possibly several) leading zeros while negative numbers will start with one or more (i.e. possibly several) leading ones.

Logical vs. Arithmetic

As noted above, shift operations can be used to manipulate isolated bits of information stored within a larger byte. But they can also be used for power-of-2 multiplication and division. The former of those two categories is called logical shifting, while the latter is called arithmetic shifting. The appropriate handling of the leading zeros and ones in two's complement numbers accounts for the differences between the two type of shifting.

In logical shifting, the bits in a byte are shifted left or right as a group like beads on an abacus. Bits farthest in the direction of the shift effectively "fall off" that edge, and they are replaced by zeros entering from the opposite side. This mechanical manipulation of bits can be quite useful when converting small data values embedded in "bit fields" to and from actual register values usable for math operations on the CPU. Nevertheless, careless application of logical shifts could prove quite destructive to a two's complement number where adding a zero at the wrong end could drastically change the meaning of the binary value.

Arithmetic shifting preserves the sign (i.e. positive or negative) aspect of a two's complement number while still transforming its magnitude. Right shifts reduce magnitude (i.e. numbers get closer to zero), while left shifts increase magnitude. So, how is this magic performed?

For a shift to the right, the rightmost bit is dropped leaving the leftmost bit temporarily vacant. For a logical shift, the vacant leftmost bit is filled with a zero -- but this would be wrong for a two's complement number. For example, -128 shifted right would become 64!

10000000 --> _1000000 (left bit vacated) 
         --> 01000000 (filled with zero -- wrong!) 

In order to maintain the sign of the shifted value, an arithmetic shift to the right will replicate the value of the leftmost bit. This yields correct values for both positive and negative two's complement values.

10000000 --> _1000000 (left bit vacated)
         --> 11000000 (filled with one -- correct!)

Notice how continued shifts will increase the number of leading ones as the magnitude of a negative number decreases (i.e. gets closer to zero):

         --> 11100000 (-32)
         --> 11110000 (-16)
         --> 11111000 (-8 )
         --> 11111100 (-4 )
         --> 11111110 (-2 )
         --> 11111111 (-1 )

So we see now that the sign must be preserved while shifting. So what does an arithmetic shift to the left do to preserve the sign? Let's visualize by implementing the above table in reverse:

             11111111 (-1  )
         --> 11111110 (-2  )
         --> 11111100 (-4  )
         --> 11111000 (-8  )
         --> 11110000 (-16 )
         --> 11100000 (-32 )
         --> 11000000 (-64 )
         --> 10000000 (-128)

As you can see, the arithmetic left shift is done by dropping the leftmost bit, shifting every other bit to the left, and filling the vacated bit on the right with a zero. While no action is taken to preserve the sign bit, it is nevertheless maintained at the same value by subsequent leading ones. Positive values are handled the same way, with equally correct results. In either case, the magnitude of the result (i.e. the distance from zero) is increased.

With that explained, please demonstrate for me how an arithmetic left shift on a two's complement binary number differs in any way from a logical left shift. I'll wait...hopefully we now agree that arithmetic left shift and logical left shift are the same operation!

Carry and Overflow

By now, some of you will have had an "a ha!" moment...what happens when a value is such that the leftmost (i.e. sign) bit isn't re-filled properly by the following bit in the left shift? This can happen, but only for values between -65 and -128 -- feel free to do some two's complement encoding exercises to convince yourself of this fact, if necessary. Multiplying those values by two (i.e. the purpose of the arithmetic left shift) would yield values that are too large to fit in a byte anyway. At that point, no amount of maintaining the sign would undo the fact that the resulting value would still be wrong.

So what is done in this case? Well for one thing, the bit that gets dropped off the left of the value is retained in the Carry flag, where it can be retrieved by a following rotate operation. This facility can be used to shift the "lost" bit onto the right side of the next byte in a multi-byte value. This operation is quite common when handling multi-byte values.

The other thing that happens when a "too negative" value (i.e. a negative value with too large a magnitude) is shifted left is that the oVerflow flag is set. By checking the V flag after a left shift, one can determine whether or not the sign of the value is changed by the shift. At that point, the programmer can take whatever action is deemed appropriate either to fail the operation or to correct the apparent error.

Above I have demonstrated that for two's complement binary numbers, the mechanics of a logical left shift and an arithmetic left shift are exactly the same. This is not controversial, and would never have been in question had it not been for some random comments on a podcast. Given that the comments in question amount to misinformation and that said podcast has an audience which significantly overlaps with my own podcast, I felt it necessary to provide a defense of the facts with the demonstration above. Feel free to do your own research, but what I have presented above is absolutely true.

For further reference:

https://en.wikipedia.org/wiki/Bitwise_operation

https://open4tech.com/logical-vs-arithmetic-shift/

http://teaching.idallen.com/dat2343/09f/notes/04bit_operations_shift.txt

Hopefully that proves the point...Q.E.D.

Z Intepreter Source for CoCo Recovered

In November 2017, The CoCo Crew Podcast interviewed Brian Moriarty. Professor Moriarty (a.k.a. the Professor) was not only an author of several well-known games both at Infocom and elsewhere, but in particular he was the author and maintainer of some of Infocom's Z interpreter software used on a variety of microcomputers. In particular, that includes the Z interpreter software for the Tandy Color Computer. During the interview, the Professor hinted that he might have preserved the source code for that software in some form.

One of our listeners, Carlos Camacho, contacted the Professor in pursuit of that software. This eventually resulted in an email message to the CoCo mailing list indicating that Carlos was in possession of Infocom source code. As of this writing, that sourcecode is now available at the TRS-80 Color Computer Archive website.

(NOTE: What follows should be taken as pursuit of an academic/educational interest and an investigation into a historical aspect of the history of Infocom and the Tandy Color computer. The intellectual property of Infocom belongs to Infocom's legal heirs, and I am not in any way advocating otherwise.)

Preparations to Build

Let's begin by creating a fresh code repository in git and extracting the Infocom source into it:

mkdir coco_infocom
cd coco_infocom/
git init .
unzip ../Infocom\ Adventure\ Games\ Interpreter\ Source\ Code\ \(Infocom\).zip
chmod 644 *
git add *
git commit -m 'Initial commit of pristine CoCo ZIP source from Infocom'

At this point, we are mostly ready to build the code with lwasm or some other assembler. For fun, lets go ahead and try to build the boot track for use with the DOS command:

lwasm -9 -l -f raw -o boot.trk boot.src

That didn't work! Instead we see a bunch of ouput like this:

boot.src(105) : ERROR : Bad opcode
boot.src:00105 ERRM:    DB    $0D

What's going on? Well...unfortunately, many assemblers take some liberties with the naming of pseudo-ops. The assembler used by Infocom does exactly that, and at least lwasm is unsure what to do with a number of those pseudo-ops as they are used in the pristine code from Infocom. In the error shown above, lwasm needs to see ".DB $0D" (or certain other variants) instead of "DB $0D".

Fortunately, some simple transliterations in the source code are sufficient to make lwasm happy. Rather than describe them all here, I have provided a patch that can be applied to your local git tree:

wget http://www.tuxdriver.com/download/coco_infocom_patches/lwasm-compat.patch
git am lwasm-compat.patch
lwasm -9 -l -f raw -o boot.trk boot.src

You will now see a 597-byte file named boot.trk. The binary data in that file matches what you will find on the boot track of the Infocom diskette images in the Color Computer Archive with the Version C interpreter.

Make Things Easier

Many people do not like typing command lines to use a computer for anything. Even those that don't mind typing a few commands can tire of typing long command lines over and over again. As you can see above, the lwasm command line can be a bit complicated. Serious developers tend to use some sort of build script or a tool like make to control their software builds. To that end, I have provided a patch that adds a Makefile to the repository as well:

wget http://www.tuxdriver.com/download/coco_infocom_patches/add-makefile.patch
git am add-makefile.patch
make

You will now also see a 5824-byte file named cocozip.img. The binary data in that file matches what you will find on the first several tracks of the Infocom diskette images in the Color Computer Archive with the Version C interpreter.

On to Version D

One of the interestings that I noted in an earlier blog entry is that there are different versions of the Infocom Z interpreter represented among the various Infocom diskette images in the Color Computer Archive. The newly recovered Infocom source matches Version C of the interpreter. But what about the (apparently) later version D?

The ability to build the Version C source and compare the results to the various binaries made a reasonable task out of isolating the differences between the Version C and Version D binaries. I patched the code with the binary differences, then I disassembled those differences to reveal reasonable interpretations of what the original source must have been doing. This was a non-trivial effort, but it is already done! I am making those patches available too:

wget http://www.tuxdriver.com/download/coco_infocom_patches/remove-tandy-bit.patch
git am remove-tandy-bit.patch
wget http://www.tuxdriver.com/download/coco_infocom_patches/update-to-version-D.patch
git am update-to-version-D.patch

Why two different patches? Well, the first patch simply removes the part of the interpreter that sets the "Tandy bit". This little piece of censorship/marketing from Tandy is an interesting historical footnote. Some may choose to apply this single patch but otherwise use the version C interpreter for whatever reason suits them. Others may choose to use version D but otherwise omit that single patch in order to preserve the experience Tandy would have preferred to give them. That change is given its own identity to enable such choices or for further investigation.

The bulk of the version D update is contained in the second patch. With both patches applied, the resulting binaries from the build will match the corresponding bits from those Infocom diskette images in the Color Computer Archive that have the Version D interpreter.


Questions Raised or Answered?

For the record, the Professor seems to have been unaware of the existence of version D of the interpreter. This raises the question of whether version D might have been the work of some lone hacker or whatever. The fact that most of the version D changes seem to be simple features and bug fixes suggests that this is the sort of mundane work that we might expect from a typical software house as it continues to operate its business. That coupled with the several copies of version D in the repository being identical leads me to believe that version D was simply a maintenance update from Infocom.

However, the removal of the "Tandy bit" in version D seems noteworthy. Why would Infocom simply remove this piece of the Z interpreter? Was there some change in the corporate relationship between Infocom and Tandy that made Infocom want to revert this piece of Tandy-specific functionality? Or perhaps that unknown Infocom maintenance programmer was offended by this single bit (literally) of censorship, and simply removed it to soothe his own conscience? We may never know.

Having access to the source for this historic piece of software has been amazing. Interesting code structures and techniques and tantalizing comments abound. Beyond that, I have identified a number of places to make code changes for certain fixes and enhancements, like support for lowercase characters, different text screen dimensions, Drivewire support, etc. I plan to have more patches before long, but CoCoFEST! is coming...you'll just have to stay tuned!