Introduction to Byte Arithmetic
on the 6800, 6801, and 6809
In the last four chapters, we reused the Hello World example to introduce and demonstrate the use of a separate parameter stack, first, synthesizing the parameter stack in software on the 6800, and 6801, then using the advanced addressing capabilities of the 6809 and 68000 to directly implement the parameter stack using the CPU's own instructions.
It may have been a little deep.
It's okay. It just gets deeper. But in this chapter, we're going to relax a bit and get a better feel for some of the fundamentals of arithmetic on digital logic processors.
8-bit CPUs generally work on data in 8-bit bytes. (Other size bytes have existed.)Just as a reminder, the word "byte" is a pun. This is bite-sized data, so to speak. But you knew that. You also knew that there are other byte sizes than 8 bits, right?
The 6800, 6801, and 6809 all have 8-bit bytes. So do the members of the 68000
family, although their natural integer width is 16 or 32 bits. They address memory in 8-bit bytes.
Eight bits (binary digits) in a latch yield 256 discrete values. These values can represent, among many other things, up to 256 states in a control system, up to 256 characters (as in ASCII or EBCDIC text) in a small character set, or small integers. One common thing to have them represent is the unsigned small integers 0 to 255ten.
Eight bits could also represent signed small integers, such as -128ten to +127ten, or -127ten to -0 and +0 to +127ten, but we'll set signed integers aside for a moment. (Sort-of. Just a moment.)
Let's take a closer look at adding small unsigned integers.
One question that arises when you know you can only represent numbers from 0 to 255 is what happens when you go over 255?
What happens when you go over nine in a column when adding decimal (base ten)
numbers by hand? Let's see if we can remember:
34
+66
---
???
First column adds up to ten. Write down your zero, carry your one to the next
column:
1 (carries)
34
+66
---
__0
Nine and the carried one makes ten in the second column, write down the zero,
carry the one:
11 (carries)
34
+66
---
_00
And so forth.
11 (carries)
34
+66
---
100
Let's replay that in hexadecimal:
22
+42
---
???
Two and two is four, no carry:
0 (carries)
22
+42
---
__4
Two and four is six, no carry:
00 (carries)
22
+42
---
_64
Interesting. 64sixteen is 100ten. I wonder what 64ten
is in hexadecimal. :)
How would this sum look in binary?
00100010
+01000010
---------
?????????
0 (carries)
00100010
+01000010
---------
________0
10 (carries)
00100010
+01000010
---------
_______00
010 (carries)
00100010
+01000010
---------
______100
0010 (carries)
00100010
+01000010
---------
_____0100
... and a few more uninteresting columns without carries until we get:
00000010 (carries)
00100010
+01000010
---------
_01100100
Bit serial CPUs actually do that one bit at a time. But none of the processors we are working with are bit serial. The 8-bit processors all do eight bits in parallel. And the 68000 does sixteen bits in parallel.
So, what happens when you get a carry from the highest bit in a byte?
Consider a byte to be a column in base 256, and it is plain. You get a carry
to the next byte.
Just like carries from column to column in base ten never exceed 1, and carries from column to column in hexadecimal never exceed 1, carries from column to column in binary never exceed 1, and carries in base 256 never exceed 1.
So, when you go over 255 in unsigned byte additions in a CPU, you have a carry, of course. And the CPU, if it's a 6800, 6801, or 6809, records it in the (C)arry flag.
There are other ways to do this, but most 8-bit CPUs do it this way.
So let's look at some code.
We've done 8-bit additions before, using immediate constants. This time, we'll
separate the numbers from the code and put them in global constants and
variables (even though I've said global constants and variables are not what
we generally want to do). Also, I'll be showing several different approaches, rather than just showing you some "optimal" subroutine. And we'll do something so we don't lose the Carry flag:
* Add two 8-bit numbers in memory and store them in memory:
*
ENTRY JMP ADDM8
*
NL1 FCB 34 ; just an arbitrary small number
NR1 FCB 66 ; another arbitrary small number
C1 RMB 1 ; To hold one bit of carry from the sum.
R1 RMB 1 ; To hold the eight bit sum.
*
NL2 FCB 132 ; Somewhat larger arbitrary number
NR2 FCB 188 ; And another
C2 RMB 1 ; carry from 2nd sum
R2 RMB 1 ; 2nd sum
*
*
ADDM8 CLR C1 ; clear storage for the carry bit
LDAB NL1 ; Get the augend (left side addend).
ADDB NR1 ; Add the addend (right side addend).
* Result is safely in B.
ROL C1 ; Save the carry bit away.
STAB R1 ; Save the sum itself.
*
CLR C2 ; 2nd carry bit
LDAB NL2 ; 2nd augend (left side addend)
ADDB NR2 ; 2nd addend (right side addend)
STAB R2 ; 2nd sum, 8 bits
* ST and LD do not alter C, carry still safe.
ROL C2 ; 2nd carry bit
NOP
NOP
Assemble that and step through it on EXORsim running a 6800 instance:
$ ./exor --mon
Load facts file 'facts'
'exbug.bin' loaded.
EXBUG-1.1 detected
'mdos.dsk' opened for drive 0 (double sided)
OSLOAD...
Hit Ctrl-C for simulator command line. Starting simulation...
> 0 A=00 B=00 X=0000 SP=00FF ------ 0020: B6 E8 00 LDA E800
6800 Monitor: Ctrl-C to exit, 'c' to continue, or type 'help'
% a 2000
2000: * Add two 8-bit numbers in memory and store them in memory:
2000: *
2000: ENTRY JMP ADDM8
2003: *
2003: NL1 FCB 34 ; just an arbitrary small number
2004: NR1 FCB 66 ; another arbitrary small number
2005: C1 RMB 1 ; To hold one bit of carry from the sum.
2006: R1 RMB 1 ; To hold the eight bit sum.
2007: *
2007: NL2 FCB 132 ; Somewhat larger arbitrary number
2008: NR2 FCB 188 ; And another
2009: C2 RMB 1 ; carry from 2nd sum
200a: R2 RMB 1 ; 2nd sum
200b: *
200b: *
200b: ADDM8 CLR C1 ; clear storage for the carry bit
Address at 2001 set to 200B
200e: LDAB NL1 ; Get the augend (left side addend).
2011: ADDB NR1 ; Add the addend (right side addend).
2014: * Result is safely in B.
2014: ROL C1 ; Save the carry bit away.
2017: STAB R1 ; Save the sum itself.
201a: *
201a: CLR C2 ; 2nd carry bit
201d: LDAB NL2 ; 2nd augend (left side addend)
2020: ADDB NR2 ; 2nd addend (right side addend)
2023: STAB R2 ; 2nd sum, 8 bits
2026: * ST and LD do not alter C, carry still safe.
2026: ROL C2 ; 2nd carry bit
2029: NOP
202a: NOP
202b:
% u 2000
2000: 7E 20 0B JMP $200B
2003: 22 42 BHI $2047
2005: 00 ???
2006: 00 ???
2007: 84 BC ANDA #$BC
2009: 00 ???
200A: 00 ???
200B: 7F 20 05 CLR $2005
200E: F6 20 03 LDB $2003
2011: FB 20 04 ADDB $2004
2014: 79 20 05 ROL $2005
2017: F7 20 06 STB $2006
201A: 7F 20 09 CLR $2009
201D: F6 20 07 LDB $2007
2020: FB 20 08 ADDB $2008
2023: F7 20 0A STB $200A
2026: 79 20 09 ROL $2009
2029: 01 NOP
202A: 01 NOP
202B: 00 ???
202C: 00 ???
202D: 00 ???
% s 2000
0 A=00 B=00 X=0000 SP=00FF ------ ENTRY 2000: 7E 20 0B JMP 200B EA=200B(ADDM8)
> 1 A=00 B=00 X=0000 SP=00FF ------ ADDM8 200B: 7F 20 05 CLR 2005
6800 Monitor: Ctrl-C to exit, 'c' to continue, or type 'help'
% s
1 A=00 B=00 X=0000 SP=00FF ------ ADDM8 200B: 7F 20 05 CLR 2005 EA=2005(C1)
> 2 A=00 B=00 X=0000 SP=00FF ---Z-- 200E: F6 20 03 LDB 2003
6800 Monitor: Ctrl-C to exit, 'c' to continue, or type 'help'
% s
2 A=00 B=00 X=0000 SP=00FF ---Z-- 200E: F6 20 03 LDB 2003 EA=2003(NL1) D=22
> 3 A=00 B=22 X=0000 SP=00FF ------ 2011: FB 20 04 ADDB 2004
6800 Monitor: Ctrl-C to exit, 'c' to continue, or type 'help'
% s
3 A=00 B=22 X=0000 SP=00FF ------ 2011: FB 20 04 ADDB 2004 EA=2004(NR1) D=42
> 4 A=00 B=64 X=0000 SP=00FF ------ 2014: 79 20 05 ROL 2005
6800 Monitor: Ctrl-C to exit, 'c' to continue, or type 'help'
% s
4 A=00 B=64 X=0000 SP=00FF ------ 2014: 79 20 05 ROL 2005 EA=2005(C1)
> 5 A=00 B=64 X=0000 SP=00FF ---Z-- 2017: F7 20 06 STB 2006
6800 Monitor: Ctrl-C to exit, 'c' to continue, or type 'help'
% s
5 A=00 B=64 X=0000 SP=00FF ---Z-- 2017: F7 20 06 STB 2006 EA=2006(R1) D=64
> 6 A=00 B=64 X=0000 SP=00FF ------ 201A: 7F 20 09 CLR 2009
6800 Monitor: Ctrl-C to exit, 'c' to continue, or type 'help'
% s
6 A=00 B=64 X=0000 SP=00FF ------ 201A: 7F 20 09 CLR 2009 EA=2009(C2)
> 7 A=00 B=64 X=0000 SP=00FF ---Z-- 201D: F6 20 07 LDB 2007
6800 Monitor: Ctrl-C to exit, 'c' to continue, or type 'help'
% s
7 A=00 B=64 X=0000 SP=00FF ---Z-- 201D: F6 20 07 LDB 2007 EA=2007(NL2) D=84
> 8 A=00 B=84 X=0000 SP=00FF --N--- 2020: FB 20 08 ADDB 2008
6800 Monitor: Ctrl-C to exit, 'c' to continue, or type 'help'
% s
8 A=00 B=84 X=0000 SP=00FF --N--- 2020: FB 20 08 ADDB 2008 EA=2008(NR2) D=BC
> 9 A=00 B=40 X=0000 SP=00FF H---VC 2023: F7 20 0A STB 200A
6800 Monitor: Ctrl-C to exit, 'c' to continue, or type 'help'
% s
9 A=00 B=40 X=0000 SP=00FF H---VC 2023: F7 20 0A STB 200A EA=200A(R2) D=40
> 10 A=00 B=40 X=0000 SP=00FF H----C 2026: 79 20 09 ROL 2009
6800 Monitor: Ctrl-C to exit, 'c' to continue, or type 'help'
% s
10 A=00 B=40 X=0000 SP=00FF H----C 2026: 79 20 09 ROL 2009 EA=2009(C2)
> 11 A=00 B=40 X=0000 SP=00FF H----- 2029: 01 NOP
6800 Monitor: Ctrl-C to exit, 'c' to continue, or type 'help'
% d 2000 10
2000: 7E 20 0B 22 42 00 64 84 BC 01 40 7F 20 05 F6 20 ~ ."B.d...@. ..
%
In the first case, we didn't have a carry from the byte addition. Or, rather,
the carry was 0, and the ROL instruction recovered the 0 carry.
We see here that the ROL instruction on the 6800, 6801, and 6809 can be used to move (rotate) the carry bit into a register or a byte of memory.
If you
want, do it again on EXORsim6801, but it should do essentially the same thing. Since you're only looking at the values of registers
while stepping through the code, there is no need to bother with either
getting the terminal emulator's attention or with pausing at the end for this
code on the 6801. You won't need to add the code to do that. Same code. Same execution.
Another way to capture the carry is to use the ADd with Carry instruction, adding the carry and an immediate zero to the zero in a cleared accumulator like this:
CLRA ; 2nd carry bit
LDAB NL2 ; 2nd augend (left side addend)
ADDB NR2 ; 2nd addend (right side addend)
STAB R2 ; 2nd sum, 8 bits
* ST and LD do not alter C, carry still safe.
ADCA #0 ; 0 in A plus carry bit
STAA C2 ; 2nd carry bit
I'm going to emphasize the comments in the above code -- LoaDs and STores do
not affect the Carry flag on 680X CPUs. We can store the 8-bit result first
and capture the carry after if we want.
Just for completeness, the 6801 and the 6809 will allow you to treat the carry byte and the 8-bit sum byte as a single 16-bit integer result, as well:
...
NL1 FCB 34 ; just an arbitrary small number
NR1 FCB 66 ; another arbitrary small number
RES1 RMB 2 ; 2-byte result
C1 EQU RES1 ; To look at the carry from the sum.
R1 EQU RES1+1 ; To look at the the eight bit sum.
...
CLRA ; clear storage for the carry bit
LDAB NL1 ; Get the augend (left side addend).
ADDB NR1 ; Add the addend (right side addend).
ADCA #0 ; Save the carry bit away.
STD RES1 ; Save the 9 bit result in 16 bits.
Note the STore Double accumulator at the end, instead of storing each accumulator separately.
I intentionally put the carry byte below the sum byte in memory to allow them to be treated together as a single 16-bit integer. This is the byte order the 6800, 6801, and 6809 use, most significant byte first. (68000, too.)
Using three labels, RES1 for the 16-bit result, and C1 and R1 for the separate halves of the result, helps make it clear which half of the integer you're looking at even if you forget which order they are in.
Now, if you want, you can try the above two variations. (I recommend it.) And when you're done playing with that on the 6800, edit the LDAB and LDAA instructions to LDB and LDA, and the STAB and STAA instructions to STB and STA, and assemble the code on a 6809 instance and step through it there as well. It will execute this code exactly the same except for timing (which you won't notice in the emulator), but it will give you a chance to practice and notice more about what goes on.
(You may be wondering whether it wouldn't be possible to do the math
on the 6801 and 6809 using the 16-bit ADD Double and SUB Double accumulator instructions. It can be done, but you need more byte of memory because the ADDD and SUBD instructions want a 16-bit addend as well as the 16-bit augend.)
If you get really ambitious, you might use the (m)emory change command to change the constants that are getting added and step through again with different values, without editing the source code and re-assemlbing.
(Are the op-codes output for the source code on this also all the same on the
6809? You might want to check. 8-*)
It will run the same on all three.
So, what about subtraction?Let's review how subtraction works when we do it on paper:
66
-34
---
???
First column, difference is 2, no borrow.
0 (borrow)
66
-34
---
__2
Second column, difference is 3, no borrow.
00 (borrow)
66
-34
---
_32
And we're done. That wasn't interesting -- at least, not obviously so. Let's look at something that generates a borrow.
62
-34
---
???
First column, 2 minus 4 is minus 2. So we'll borrow a 1 from the next column over, subtracting 1 from that and adding 10 to this:
-1 (borrow)
6 12
-3 4
-- -
__ 8
Take the borrow from 6, that's 5.
0-1 (borrow)
65 12
-3 4
-- -
_2 8
5 minus 3 is 2, no borrow generated, difference is 28.
What we did was use ten's complement math in the column that needed a borrow. We borrowed from the next column over because a 1 in that column is a 10 in this column, and we remembered to take the borrowed 1 away when we moved to the next column over.
We can do the same thing in hexadecimal (sixteen's complement), but that would be a distraction.
We can also do the same thing in binary. This is called two's complement, and
is very useful.
Of the two above differences, 66 minus 34 is the more interesting in binary:
01000010 (66ten)
-00100010 (34ten)
---------
????????
Okay, the first (bit) column on the right, 0 minus 0 is 0. Not particularly ineresting:
0 (borrow)
01000010 (66ten)
-00100010 (34ten)
---------
_______0
But things don't get really interesting until the 6th bit:
00000 (borrow)
01000010
-00100010
---------
___00000
Can't take 1 from 0, so we borrow from the next column over:
-1 00000 (borrow)
01 10 00010 (10two == 2ten)
-00 1 00010
--- - -----
__ 1 00000
1 from 2 is 1. And,
-1 00000 (borrow)
0 1 10 00010 (10two == 2ten)
-0 0 1 00010
-- - - -----
_ 0 1 00000
In the next column, take the borrow from 1 and that's 0, and 0 - 0 is 0. And the next column, 0 - 0 is 0. Which gives us
-1 00000 (borrow)
0 1 10 00010 (10two == 2ten)
-0 0 1 00010
-- - - -----
0 0 1 00000
00100000two, which is 32ten. If you haven't already, you
might want to get paper and pencil out and make up some binary problems and
work them out by hand, to prove to yourself that this works, and is
essentially the same thing you're familiar with in base-ten math, but in base
two.
What happens if we take a larger number from a smaller? Let's flip 66 - 34 over and see what we can see:
34
-66
---
???
Because we've already done this and just flipped it over, we know that the answer is -32. That's the way we usually work by hand when we have a large number to take from a small number. And things have actually been done this way in some computers in the past.
But we're deliberately going to see what happens when the borrow runs off the left edge of the numbers.
You definitely want to be following along with pencil and paper on this
one. Leave some room to the left when you write it down:
First column, 4 minus 6 is ...
-1 (borrow)
3 14
-6 6
-- -
__ 8
Gotta borrow. 14 - 6 is 8.
Second column, (1-) + 3 - 6 is ...
-1 -1 (borrow)
312 14
- 6 6
-- - -
__ 6 8
Remember to scratch out the used borrow. Gotta borrow again. 12 - 6 is 6.
But now what? We've got a borrow hanging off the left, and nothing to borrow it from.
Let's invent an infinity of 0s out there. Well, not an infinity, but one or
two:
-1 -1 (borrow)
00 312 14
-00 6 6
--- - -
___ 6 8
Apply the borrows and ...
-1 -1 -1 -1 (borrow)
0 010 010 312 14
-0 0 0 6 6
-- - - - -
__ 9 9 6 8
Again, ten's complement.
Subtract 9968 from 10000, and we get 32. And, somehow, we just know that the leftmost 9 in the result really means we have to subtract from an appropriate power of ten and call the result negative.
Yeah, it's a stretch, but we do crazy things like this in computers because it
makes the mechanical adders easier to build. (Early digital computers actually worked in decimal, or in decimal coded binary, or in bi-quinary, because it was easier for many of those involved to intuit at the time.)
Two's complement for binary is especially convenient. Try it on the above problem. Fill the result out to eight bits by continually borrowing a 1 from the next left column and you should get
11100000
Or you could fill it out to sixteen bits and get
1111111111100000
And maybe you can intuit that the 1 on the left could be seen like a minus sign.
But how do we know that these numbers are not 224ten
and 65504ten?
Unfortunately, unless we remember where the numbers came from, we don't.
In other words, when we are working with integers in computers that use two's complement signed integers, we have to remember (and remind ourselves) whether the particular number we are working with is supposed to be a two's complement signed number or an unsigned number. Yes, it's a bother, but it's necessary.
(... on signed and unsigned integers. -- We're not looking at fixed-point or floating point numbers here, but you have to remember what you're looking at with those, as well.)
Okay, having seen how this works, let's look at some code.
After the subtraction, we could use the ROtate Left instruction to just
capture the carry/borrow as we did with addition, but the SuBtract with Borrow Carry
instruction can do a little more for us. So we'll use that, instead. (It's the same Carry
flag that we used in the addition routines, but it records the borrow after a
subtraction. Yes, it works.)
You'll be pleasantly surprised at how subtracting
zero and a borrow from zero plays out:
* Subtract two 8-bit numbers in memory and store them in memory:
*
ENTRY JMP SUBM8
*
NL1 FCB 66 ; just an arbitrary small number
NR1 FCB 34 ; another arbitrary small number
RH1 RMB 1 ; To hold one bit of carry from the sum.
RL1 RMB 1 ; To hold the eight bit sum.
*
NL2 FCB 132 ; Somewhat larger arbitrary number
NR2 FCB 188 ; And another
RH2 RMB 1 ; carry from 2nd sum
RL2 RMB 1 ; 2nd sum
*
NL3 FCB 34 ; just an arbitrary small number
NR3 FCB 66 ; a larger arbitrary small number
RH3 RMB 1 ; To hold one bit of carry from the sum.
RL3 RMB 1 ; To hold the eight bit sum.
*
*
SUBM8 CLRA ; clear accumulator A for the carry/sign extension
LDAB NL1 ; Get the minuend (left side).
SUBB NR1 ; Subtact the subtrahend (right side).
* Result is safely in B.
SBCA #0 ; Recover the carry bit, sign extended.
STAA RH1 ; Save high byte away.
STAB RL1 ; Save the difference low byte.
*
CLRA ; 2nd sign extension
LDAB NL2 ; 2nd minuend (left side)
SUBB NR2 ; 2nd subtrahend (right side)
SBCA #0 ; 2nd carry, sign extended
STAB RL2 ; Save 2nd difference, low byte.
STAA RH2 ; Save high byte away.
*
CLRA ; 3rd carry bit
LDAB NL3 ; 3rd minuend (left side)
SUBB NR3 ; 3rd subtrahend (right side)
STAB RL3 ; Save 3rd difference, low byte.
* ST and LD do not alter C, carry still safe.
SBCA #0 ; 3rd carry, sign extended.
STAA RH3 ; Save it away.
NOP
NOP
Assemble that and step through it on the 6800, and on the 6801 if you want. Then edit the LD and ST instructions for the 6809 and assemble it and step through it there, as well. Here's the result at the end, (d)umped out:
% d 2000 10
2000: 7E 20 0F 42 22 00 20 84 BC FF C8 22 42 FF E0 4F ~ .B". ...."B..O
Repeating that line in mark-up-able HTML so I can mark the results in red
without depending on your browser to read <span> tags buried in
pre-formatted text:
2000: 7E 20 0F 42 22
00 20
84 BC
FF C8
22 42
FF E0 4F
We now expect the result for the first subtraction:
42sixteen - 22sixteen == 20sixteen
(That's
66ten - 34ten == 32ten
right?)
The results for the second and third have a borrow from the most significant bit, and by subtracting the borrow instead of rotating it in, we end up with minus one in the stored high byte.
0 - 1 = -1
As we've seen, in signed two's complement arithmetic, a byte (or other size integer) full of 1s is -1. Subtracting 0 and the borrow from 0 does this for us quite nicely!
If you're wondering whether it's possible to use the ADD Double (ADDD) and SUBtract Double (SUBD) instructions on the 6801 and 6809, yes, sort-of. But it requires an extra couple of bytes of memory because both sides, the minuend and the subtrahend, want a 16-bit operand, so we have to expand both operands.
Keep this in mind for the 68000, though.Let's look at how that works one more time from a bit more of a high-level view:
First, let's do the math in base ten:
132ten - 188ten == -56ten
34ten - 66ten == -32ten
One more than the largest number in 8 bits is 256. If we add those results (adding negative numbers) to 256, we get
256ten + (-56ten) == 200ten => C8sixteen
256ten + (-32ten) == 224ten => E0sixteen
And the byte full of 1s is FFsixteen, which explains the results stored away, $FFC8 and $FFE0.
Okay, break out the hexadecimal calculator again. Enter those numbers and do
the math in hexadecimal and decimal. Maybe even binary.
If you're not seeing it, switch to hexadecimal base and enter -1. Then switch to binary. You should have a readout full of 1s somewhere in there.
Now switch to decimal and enter -56, then switch to hexadecimal and then binary and watch the bit patterns. Remember, using the four bits at a time conversion to hexadecimal,
1100 1000two == C8sixteen
When you've figured out what's being displayed where, and are satisfied that
the bit patterns match what I'm telling you, clear the display, switch to
decimal, and enter -32, then, again, switch to hexadecimal and binary and
remember that
1110 0000two == E0sixteen
We'll get more satisfaction about this once we have enough assembly language to build a calculator that does integer math in various bases, but I hope we've gotten enough satisfaction to move on.
Go ahead and play with it a bit more, and then let's look at this in 68000 assembler.
No comments:
Post a Comment