It is currently Mon Jun 17, 2019 7:58 pm

All times are UTC - 7 hours





Post new topic Reply to topic  [ 12 posts ] 
Author Message
 Post subject: Carry
PostPosted: Thu Nov 02, 2006 4:00 pm 
Offline

Joined: Wed Nov 16, 2005 6:38 pm
Posts: 47
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 |   ?   |   ?   |
              ------- -------


Top
 Profile  
 
 Post subject:
PostPosted: Thu Nov 02, 2006 5:02 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 11369
Location: Rio de Janeiro - Brazil
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.


Top
 Profile  
 
 Post subject:
PostPosted: Thu Nov 02, 2006 5:56 pm 
Offline
User avatar

Joined: Mon Sep 27, 2004 8:33 am
Posts: 3715
Location: Central Texas, USA
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.


Last edited by blargg on Sat Oct 19, 2013 4:27 pm, edited 1 time in total.

Top
 Profile  
 
 Post subject:
PostPosted: Fri Nov 03, 2006 1:16 pm 
Offline

Joined: Wed Nov 16, 2005 6:38 pm
Posts: 47
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.


Top
 Profile  
 
 Post subject:
PostPosted: Fri Nov 03, 2006 1:38 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 11369
Location: Rio de Janeiro - Brazil
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


Top
 Profile  
 
 Post subject:
PostPosted: Fri Nov 03, 2006 3:09 pm 
Offline

Joined: Wed Mar 22, 2006 8:00 am
Posts: 354
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).


Top
 Profile  
 
 Post subject:
PostPosted: Fri Nov 03, 2006 4:04 pm 
Offline
User avatar

Joined: Wed Nov 10, 2004 6:47 pm
Posts: 1849
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


Top
 Profile  
 
 Post subject:
PostPosted: Fri Nov 03, 2006 4:31 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 11369
Location: Rio de Janeiro - Brazil
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.


Top
 Profile  
 
 Post subject:
PostPosted: Fri Nov 03, 2006 5:16 pm 
Offline
User avatar

Joined: Wed Nov 10, 2004 6:47 pm
Posts: 1849
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.


Top
 Profile  
 
 Post subject:
PostPosted: Fri Nov 03, 2006 6:23 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 11369
Location: Rio de Janeiro - Brazil
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!


Top
 Profile  
 
 Post subject:
PostPosted: Sun Nov 05, 2006 5:36 pm 
Offline

Joined: Wed Nov 16, 2005 6:38 pm
Posts: 47
Now the next question about carry.

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


Top
 Profile  
 
 Post subject:
PostPosted: Sun Nov 05, 2006 6:15 pm 
Offline
User avatar

Joined: Wed Nov 10, 2004 6:47 pm
Posts: 1849
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.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 12 posts ] 

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group