Invalid cases for decimal mode addition

[bonimy]

Background

Addition operations in SNES's 65816 processor can work in a base-10 binary coded decimal (BCD) mode, where addition operations give results like

0x01 + 0x01 = 0x02
0x05 + 0x05 = 0x10 // Not 0x0A
0x98 + 0x23 = 0x123 // Not 0xBB

Question

What is the expected outcome if we were to add invalid numbers in decimal mode (i.e. numbers with digits not between 0 and 9)? A good example is 0xFFFF + 0xFFFF.

Steps to reproduce

The 0xFFFF + 0xFFFF operation can be triggered in snes9x with

REP #38
SEC
LDA #$FFFF
ADC #$FFFF

whose machine code equivalent is C2 38 38 A9 FF FF 69 FF FF and the A register will have the result.

Current implementation

The current snes9x code for BCD addition is located at cpumacro.h:318:

uint16  A1 = Registers.A.W & 0x000F;
uint16  A2 = Registers.A.W & 0x00F0;
uint16  A3 = Registers.A.W & 0x0F00;
uint32  A4 = Registers.A.W & 0xF000;
uint16  W1 = Work16 & 0x000F;
uint16  W2 = Work16 & 0x00F0;
uint16  W3 = Work16 & 0x0F00;
uint16  W4 = Work16 & 0xF000;
A1 += W1 + CheckCarry();
if (A1 > 0x0009)
{
    A1 -= 0x000A;
    A1 &= 0x000F;
    A2 += 0x0010;
}
A2 += W2;
if (A2 > 0x0090)
{
    A2 -= 0x00A0;
    A2 &= 0x00F0;
    A3 += 0x0100;
}
A3 += W3;
if (A3 > 0x0900)
{
    A3 -= 0x0A00;
    A3 &= 0x0F00;
    A4 += 0x1000;
}
A4 += W4;
if (A4 > 0x9000)
{
    A4 -= 0xA000;
    A4 &= 0xF000;
    SetCarry();
}
else
    ClearCarry();
uint16  Ans16 = A4 | A3 | A2 | A1;
...

This code is a little messy and can be improved.

Proposed change

I wanted to propose the following change:

int sum = bcd_add(Registers.A., Work16);
sum = bcd_add(sum, CheckCarry());
ICPU._Carry = bcdSum >= 0x10000;
uint16 Ans16 = bcdSum;
...

where the function bcd_add(int, int) does the actual BCD addition. Note that we have to do a second separate addition for the carry bit in the event that Registers.A ends with a 9.

The BCD add function I wanted to use (stolen from this article) is

int bcd_add(int left, int right)
{
    // If we assume that left is a valid BCD value, then this
    // addition should produce no carries.
    int t1 = left + 0x06666666;

    // Digits in this sum are correct for any sums that
    // produced a carry. Digits that didn't produce a carry
    // will have an excess value of 6.
    int t2 = t1 + right;

    // t2 and t3 will differ wherever there was a carry.
    int t3 = t1 ^ right;

    // Records where all carries took place in the sum.
    int t4 = t2 ^ t3;

    // Holds all positions where a carry didn't take place.
    int t5 = ~t4 & 0x11111110;

    // Each digit that didn't have a carry will be 6. Each
    // digit that did have a carry will be 0.
    int t6 = (t5 >> 2) | (t5 >> 3);

    // Remove the excess of 6 from each digit that didn't have
    // a carry in its addition.
    int result = t2 - t6;
    return result;
}

This has the benefit of using less operations and having no cyclomatic complexity.

Issue

While this produces the expected output for valid BCD integers, the two implementations diverge for invalid values. For example, assuming the carry bit is set, then 0xFFFF + 0xFFFF will be 0x5555 using the snes9x code and 0x6665 using the implementation I found.

So the question then becomes which one would the SNES actually do in this scenario?

[bearoso]

I know the decimal mode operations are wrong, but nothing uses them, so I didn’t feel much obligation to fix them. See the tests at https://snescentral.com/article.php?id=1118 If you want, try to get those tests passing. The expected behavior is documented therein as well. The example you posted is 32 bit, which disregarding undocumented behavior wouldn’t work anyway. I assume you adapted it to 16 before trying it?

[bonimy]

I didn't know there were tests. Awesome!

[bonimy]

Hey @bearoso do you know the validity of those BCD tests? It seems he just tests against this addition function:

const int n80 = 0x80;
const int v40 = 0x40;
const int d08 = 0x08;
const int z02 = 0x02;
const int c01 = 0x01;

int adc16( int a, ref int p, int operand )
{
    int carry = p & c01;

    p &= ~(n80 | v40 | z02 | c01);

    int result;

    if ((p & d08) == 0)
    {
        result = a + operand + carry;
    }
    else
    {
        result = (a & 0x000F) + (operand & 0x000F) + carry;
        if (result > 0x0009)
            result += 0x0006;

        carry = (result > 0x000F) ? 1 : 0;

        result = (a & 0x00F0) + (operand & 0x00F0) + (result & 0x000F) + carry * 0x10;
        if (result > 0x009F)
            result += 0x0060;

        carry = (result > 0x00FF) ? 1 : 0;

        result = (a & 0x0F00) + (operand & 0x0F00) + (result & 0x00FF) + carry * 0x100;
        if (result > 0x09FF)
            result += 0x0600;

        carry = (result > 0x0FFF) ? 1 : 0;

        result = (a & 0xF000) + (operand & 0xF000) + (result & 0x0FFF) + carry * 0x1000;
    }

    // signs of a and operand match, and sign of result doesn't
    if ((a & 0x8000) == (operand & 0x8000) && (a & 0x8000) != (result & 0x8000))
        p |= v40;

    if ((p & d08) != 0 && result > 0x9FFF)
        result += 0x6000;

    if (result > 0xFFFF)
        p |= c01;

    if ((result & 0x8000) != 0)
        p |= n80;

    if ((result & 0xFFFF) == 0)
        p |= z02;

    return result & 0xFFFF;
}

However, this comes back to the original question of how do we know this is accurate? I wasn't able to find any technical references that say why they are right.

Either way, if you did want snes9x to pass the ADC and SBC tests, this would be the implementation to do it.

[bearoso]

That’s the reference implementation. The expected results come from hardware, so the behavior is correct.

[bonimy]

Ah alright. I'll make a PR when I have some time.

[bearoso]

I changed the Snes9x version to the reference version to pass the tests. Your optimized version wouldn't work because we can't assume the inputs are proper BCD values.

[bonimy]

Yeah I think we'll have to use the C code the tests use. They're pretty ugly-looking but they're accurate.

[bearoso]

Since we're passing the tests now, despite the convoluted code to accurately reflect the hardware, I'm going to close this.