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.