Carry - NESdev BBS

Carry
by danimal on 2006-11-02 (#19078)

I have been having a bit of trouble fully understanding the status of the carry flag before and after subtracting.

Let me state what I know already:
The overflow status is set when the results aren't in this range:

Code:

-128 <= x <= 127

which is easy to test for if variables wider than 8 bits are used to emulate the result.

The Carry status is set when the result is greater than 127, but what happens when a subtraction result is less than -128. My guess is that it would be clear, but could someone please point me in the right direction.

Stated another way:

Code:

Carry Result:
              __SBC__ __ADC__
    in range |   0   |   1   |
out of range |   ?   |   ?   |
              ------- -------

by tokumaru on 2006-11-02 (#19079)

The carry works with unsigned math. It is set if the result goes over 255, not 127. For subtraction, the carry should be set before the operation, and if the result is less than 0, the carry will be clear.

When adding, the carry works like a 9th bit (since you are using numbers wider than 8 bits you could very well use the 9th as the carry). When subtracting, it could also be like a 9th bit, that is set before the operation, and in case the lower 8 bits go below 0, the 1 in the 9th position will be used.

Since I'm not an emulator author, I'm not sure about the most efficient way to emulate the carry flag, but considering it a 9th bit could work.

To find the value of the carry flag after an addition, just checking the 9th bit of the result will do. When subtracting, maybe you could (before the operation) put whatever is on the carry into the 9th bit, perform the subtraction, and then check the 9th bit for the new value of the carry.

Or you could just perform subtraction as it's done in hardware: just XOR/EOR the number beeing subtracted with 255 (i.e. invert all the bits) and perform a regular addition, adding the carry and everything. The result is the same!

EDIT: Just to illustrate what I said:
Say we want to subtract 10 (00001010 in binary) from 40. The correct answer would be 30. Doing it as the 6502 goes like this: 40 is already in A, the carry is set, and then comes the "SBC #10" instruction. It then inverts the bits of the operand, that becomes 245 (11110101 in binary). Now, adding 245 to 40, plus the carry (which is set) results in the number 286 (100011110 in binary). If you look at that result, the 9th (where you get the new value of the carry from) is set, as expected from this subtraction, and the lower 8 bits form the value 30 (00011110), which is the correct result.

IMO, the best way to implement SBC is by implementing ADC correctly (which is simpler), and then have SBC just invert the operand and use the ADC instruction already implemented.

by blargg on 2006-11-02 (#19080)

ADC:

temp = A + data + carry
carry = temp >> 8 & 1
A = temp & 0xFF

SBC:

data = data ^ 0xFF
temp = A + data + carry
carry = temp >> 8 & 1
A = temp & 0xFF

Yes, the only difference between ADC and SBC is that SBC flips all the bits of the value to be added. The reason this works is that you also keep carry set before SBC, therefore you have two's complement negation: invert all bits then add one (the set carry).

EDIT: note, above has A and data as unsigned bytes.

by danimal on 2006-11-03 (#19095)

tokumaru wrote:
It is set if the result goes over 255, not 127.

Fatigue does wonderful things to memory.

blargg wrote:
SBC:

data = data ^ 0xFF
temp = A + data + carry
carry = temp >> 8 & 1
A = temp & 0xFF

That's a very cool way to do it, however I am wondering how it could be implemented as subtraction, instead of complement and addition.

by tokumaru on 2006-11-03 (#19099)

danimal wrote:
That's a very cool way to do it, however I am wondering how it could be implemented as subtraction, instead of complement and addition.

Writing it as blargg did, it could be like this:

Code:
SBC:

temp = A + (carry << 8)
temp = temp - data
carry = temp >> 8 & 1
A = temp & 0xFF

by dvdmth on 2006-11-03 (#19101)

No, that isn't right. It would be more like this:
Code:
SBC:

temp = A + 0x100
temp = temp - data - 1 + carry
carry = temp >> 8 & 1
A = temp & 0xFF

If the carry bit is set, A becomes A - data. If the carry bit is clear, A becomes A - data - 1. The carry bit is set if the result is greater than or equal to zero, clear if the result is less than zero. Often the carry is referred to as "borrow" during subtraction, as it indicates that a borrow took place (when subtracting multi-byte quantities - think of how you'd do subtraction by hand).

by Disch on 2006-11-03 (#19104)

From my source:

Code:
tmp = A - val - !fC;
flgV = (A ^ tmp) & (A ^ val) & 0x80;
fC = !(tmp >> 8);
fN = fZ = A = (u8)tmp;

where 'tmp' is unsigned 16-bit or larger

by tokumaru on 2006-11-03 (#19107)

dvdmth wrote:
Often the carry is referred to as "borrow" during subtraction, as it indicates that a borrow took place (when subtracting multi-byte quantities - think of how you'd do subtraction by hand).

That's exactly why I put the carry in the position of the 9th bit, for it to be borrowed in case it was needed. If it was borrowed, (result < 0) the 9th bit will be cleared, as the carry should be.

I wrote it like that because I feel it's a more intuitive way of seeing how SBC works. Most people don't understand why it's needed to set the carry before a subtraction. Of course, when we see that SBC is just an ADC with the operand complemented, it's easy to see why, but intuitively, it may feel weird to most programmers.

So, I like to think of the carry in a subtraction as a bit that you put there, in case the subtraction needs to borrow it. If it doesn't borrow (result > 0), it will still be there after the operation. However, if the carry is clear after the operation, it means the bit was borrowed. It's a much more intuitive way of seeing it.

And I don't see why you say that my version is "incorrect". If it gives the correct results, it is correct (and, as far as I tested, it gave correct results). It's just a different implementation than yours.

by Disch on 2006-11-03 (#19109)

tokumaru wrote:
And I don't see why you say that my version is "incorrect".

You don't subtract an additional 1 when C is clear.

by tokumaru on 2006-11-03 (#19111)

Disch wrote:
You don't subtract an additional 1 when C is clear.

Oh yeah... oops! Well, I do feel stupid now! =) But I'll admit my mistake... =D

Thanks for pointing that out! But you know, trying to explain SBC as an actual subtraction is hard (look at dvdmth's code)... Seeing it as an ADC is so much simpler!

by danimal on 2006-11-05 (#19168)

Now the next question about carry.

Is there a reasonable implementation to do it with only 8-bit variables?

by Disch on 2006-11-05 (#19170)

danimal wrote:
Is there a reasonable implementation to do it with only 8-bit variables?

I don't see why that'd be necessary... but here's what I came up with:

where tmp is 8-bit unsigned:

ADC:
Code:
tmp = A + val + carry;
if(tmp < A) carry = 1;
else if(tmp > A) carry = 0;
A = tmp;

SBC:
Code:
tmp = A - val - !carry;
if(tmp < A) carry = 1;
else if(tmp > A) carry = 0;
A = tmp;

The idea here (easier to see with ADC):

If the sum (tmp) is less than A, then it must have wrapped, so you set carry. Otherwise, if the sum is greater than A, it couldn't have wrapped, so you clear carry.

Now, if A == tmp, one of two things could have happened:
- added $FF with carry
- added $00 without carry

in either case, C remains unchanged ($FF with carry would keep carry set, $00 without carry would keep carry clear)

SBC logic is the same idea.

But really -- it's probably easier to just use a 16-bit or larger variable if possible.