Friday, 9 April 2021

Lunchtime Coder #6 - Space Invaders / INTEL 8080 Emulator with DAA and Auxiliary Carry Bit

If you are writing a Space Invaders Emulator or other INTEL 8080 based emulator, sooner or later you will come up against the DAA opcode (0x27) and the Auxiliary Carry bit / flag.

The Space Invaders game itself doesn't use Opcode DAA or the Aux. Carry bit to function correctly, however if you want your emulator to increment and decrement the credits correctly, you will need to implement both of these.

There is some information about implementation floating around on line, and a reasonable decription in the INTEL 8080 handbook however there are a few finer points of emulating this that seem to trip people up continously.

Its usually a lot easier to emulate something if you completely understand how it works and what is actually going on, and so I will attempt to explain exactly what is happening when the DAA Opcode is used, and how the Aux. bit setting affects it.


So What Does the DAA Opcode Actually Do?

The Intel 8080 DAA or "Decimal Adjust Accumulator" opcode converts a two digit hexadecimal value into a two digit decimal value aka a Binary Coded Decimal value. Its still a hexadecimal value really, but the Hex values that don't appear in decimal number range (a, b, c, d, e and f) are skipped over so that the value increments like a decimal value.

In the case of Space Invaders, as you insert a coin, the number of Credits you have available increments by 1.
If you start a One Player Game, the number of credits remaining decrements by 1. If you start a Two Player Game, the number of Credits decrements by 2.

But...the number of credits remaining displayed on the screen is a decimal value that ranges from 0 to 99, not a hexadecimal value from 0 to FF. How does that work? The DAA Opcode!

In short, if the lower digit of the hexidecimal value of the byte (lower 4 bits of the byte) is a value greater than 9 (not in the decimal range) OR the Aux. carry bit / flag is set to 1, it adds 6 to skip over the a,b,c,d,e,f range of hexidecimal, making the value appear to be decimal.

If by adding 6 to the lower 4 bits of the byte, the value of the lower 4 bits is now greater than 15D (the maximum that can be stored in 4 bits), the value has 16D minused from it and a carry of 1 is added to the higher 4 bits of the byte and the Aux. Carry bit / flag is set to 1, otherwise it is reset to 0.

Now the same process is carried out to the higher 4 bits of the byte. This time if the resulting value of the higher 4 bits is greater than 15D, the higher byte has 16D minused from it and the Carry bit / flag is set to 1, otherwise it is reset to 0.

Example 1.
Accumulator: 1001 0011
Split that into two 4 bit words:
Higher 4 bit word: 1001=9H
Lower 4 bit word: 0011=3H
As a whole byte in Hexadecimal: 93H
But the numbers 9 and 3 are also in the decimal range (0 to 9) and when read would be read as "93" so the DAA Opcode leaves the value untouched.

Example 2.
Accumulator: 0110 1000
Split that into two 4 bit words:
Higher 4 bit word: 0110=6H
Lower 4 bit word: 1000=8H
As a whole byte in Hexadecimal: 68H
But the numbers 6 and 8 are also in the decimal range (0 to 9) and when read would be read as "68" so the DAA Opcode leaves the value untouched.

Example 3.
Accumulator: 00111101
Split that into two 4 bit words:
Higher 4 bit word: 0011=3H
Lower 4 bit word: 1101=dH
As a whole byte in Hexadecimal: 3dH
The number 3 is in the decimal range (0 to 9) but D isn't. Decimal is base 10 (0 to 9) but Hexadecimal is Base 16 (0 to f).
In this case, DAA will add 6 to the value d so that the a, b, c, d, e and f part of hexadecimal is "Skipped".
If we add 6 to D, we get 13 in hexidecimal. As we can only have a maximum of fH in a 4 bit word, we then minus 16 and that gives us 3 (and a carry to the higher 4 bit word). Is 3 correct?


In Decimal, 3 and a carry would be 13. We can see from the numbers arranged above that d in HEX is 13, or 3 and a carry in DEC, so adding 6 has worked and adjusted the lower HEX value into a Binary Coded Decimal value, in this case and including the carry to the higher 4 bit word, 43.

Example 4.
Accumulator: 10111010
Split that into two 4 bit words:
Higher 4 bit word: 0011=b in HEX
Lower 4 bit word: 1101=a in HEX
As a whole byte in Hexadecimal: ba
Both b and a are not in the decimal range (0 to 9).
In this case, DAA will add 6 to the lower value so that the a, b, c, d, e and f part of hexadecimal is "Skipped".
If we add 6 to a, we get 10H. As we can only have a maximum of fH in a 4 bit word, we then minus 16 from the lower word and that gives us 0 and a carry to the higher 4 bit word.

As the higher 4 bit word is also not in the decimal range, 6 is also added to this value. The higher 4 bit word started off as b. Then when the lower 4 bit word was adjusted, there was a carry so the higher 4 bit word is now c. Adding 6 to c gives you 12H. As a maximum value of 15D can be stored in a 4 bit word, we minus 16D from the higher word to give us 2 (And set the Carry bit).
This means that ba in binary coded decimal is 20. (What?!)

The maximum binary coded decimal value you can store in 8 bits is 99. that is a 9 for each 4 bit word. As our binary coded decimal has reached and breached this, the clock has reset so to speak, the carry bit is set, and 100 BCD has been taken off of our final value. If we had a 12 bit word, the value would be 120.



How Do We Code That?

Well, lets try something simple to start with? After all, its an emulator so we can get away with cutting a few corners?

It doesn't get simpler than that.
If we paste this routine into a loop that keeps incrementing the Accumulator by 1 and running it through DAA, lets see what values we get out. The values are displayed as HEX values, but hopefully the HEX values should come out as BCD numbers.
Perfect! And that's that..... Well unfortunately not.

The routine we have above looks perfect for incrementing the Space Invaders Credit value every time a coin is inserted, but what about decrementing the value? (And here is where things get tricky... )

But surely we can just do the reverse of what we did incrementing it?

You would think so right? But DAA just doesn't work that way. If we run the same program again, but this time start the accumulator at 153 DEC (99 in HEX and BCD), and then decrement the Accumulator by 1 each loop and run it through our DAA routine, we get this.

All goes ok until we step from 90 down to 8f, then the routine boosts us up 6 from 8f to 95 because f isn't in the decimal range, which is exactly what DAA is meant to do by the way.

The Space Invaders code has a completely different way of decrementing the Credits. It adds 99H or 153D to the value. In BCD, 99+99=98 and a carry bit.
We can check if this works by modifying our original program that increments the Accumulator by 1, and then DAA's it to then add 153D to the resultant value, and DAA that as well. It should come out 1 less than the first value.

This should sort us right?
WRONG! You can see that 10 to 16, 20 to 26, 30 to 36 etc does work, but 0 to 10, 16 to 20, 26 to 30 etc doesn't work at all, and beyond 66 it has gone seriously wrong.
We may have oversimplified our DAA routine...

To be fair, I did mention that it was simplistic (too simplistic as it turns out), so lets try and write it more in the spirit of what the Intel 8080 manual asks for. This time we will consider the Carry bit for the High 4 bit word.

This new routine has low word to high word carry check, and sets the carry bit if the carry from the low word to the high word requires it. It also passes the carry from low word to high word, before the high word is checked. Lets see how this works:
So this has cleaned up the bottom end values, but we still have the issue for values of 65 and higher, and we still have issues if the lower digit is 7, 8 or 9.
Its time to discuss the Auxiliary Carry bit.

The auxiliary carry bit or Aux. flag is similar to the Carry bit / flag but it looks for a carry from bit 3 to bit 4 rather than an overflow from bit 7.
The way that this is checked is dependant on whether its called by an addition \ increment, or by a subtraction \ decrement.
As an example, if the Opcode was ADD B (0x80) then before register B is added to the Accumulator, the lower 4 bit words of Register A and B should be removed and added together to see if the resultant value is greater than 15, which would indicate a carry from bit 3 to bit 4. If the resultant is greater than 15, the Aux. Carry bit is set, if not it's reset.
Then B is added to A, and if the resultant is greater than 255, the Carry bit should be set, and if not reset.

In terms of Space Invaders, when the credits are decremented by 1, Register B is set to 99H (153D) and then Opcode ADD B (0x80) is performed adding the value in Register B to the value in the Accumulator, so that the Aux. Carry bit and Carry bit are set correctly ready for the resultant value to be put through the DAA Opcode.
This means that for our DAA Opcode test program to operate correctly, we should pass the simulated Accumulator value through an ADD B Opcode with Aux Carry and Carry bits correctly set at the end, before then passing the accumulator value through DAA.

Ok, now we are on the down hill part.
In my test program, I first run Accumulator through a DAA routine, then I make a new Value, A2, which is A+153, and then run that through the DAA routine, and that should come out as A2 decremented by 1 from A, simulating a Space Invaders credit decrement.

As was seen in the result of the last test program, we can get close to a correct value using just DAA (without an Aux. Flag) but the values beyond 65 BCD don't decrement. They stay at 66 BCD.

To resolve this, we need to add the Opcode that is used before the DAA Opcode (ADD B), and set both the Carry bit and the Auxiliary Carry bit correctly for the DAA Opcode to use.

The code that I have used to simulate an ADD B with the Auxiliary Carry and Carry bit checks is as follows:

In this way, the Carry Bit and the Aux. Carry Bit are set correctly for DAA to calculate the BCD value of A+153 correctly.
The code of DAA also needs to be modified so that the set Carry Bit and set Aux. Carry Bit can trigger the parts of DAA required.
Executing this code on the back of the simulated ADD B Opcode gives the following output:
Success! The BCD value now correctly increments by 1 from 0 to 99, and decrements by one.

So what have we learned?

  • Space Invaders Emulator does required the Auxiliary Carry bit emulated to work correctly.
  • The DAA opcode requires the Auxiliary Carry bit emulated to work correctly.
  • The DAA opcode will only function correctly if the correct preceding Opcode is executed, to set the Carry and Aux. Carry bits as required.

And some final notes.
If you are writing just a Space Invaders emulator, Aux. Carry need only be used with the ADD B opcode, as that's the only place in the code that it is called for.
If you are writing a complete Intel 8080 emulator, then the Aux. Carry is applicable to all ADD SUB INC DEC and CMP opcodes.
I have it fully implemented in my emulator as a function where I pass the two values into the function and get a 1 or a 0 returned.

No comments:

Post a comment