Overflow confusion

[dclxvi]

barrym95838 wrote:

However, the correct result will always still fit properly in nine bits, and this 9-bit twos complement result can be utilized by simply appending the C flag to the high end of the accumulator as the "ninth bit".

Not quite; the ninth bit of the result is N xor V.

[barrym95838]

Thanks, dclxvi. If V is clear then C is clearly not the ninth bit in the signed sense. But if V is set, is there a (signed) test case you can provide to us where C != N xor V ??

P.S. In other words, can you tell me if the following statements are true in the general case:

On the 65xx, the 8-bit twos complement result of the ADC and SBC instructions is contained in the accumulator, unless the V flag is set, in which case the 9-bit twos complement result is contained in the C flag appended to the most-significant edge of the accumulator. In the former case, the N flag contains the sign of the result, and in the latter case the C flag contains the sign. Also, the Z flag is invalid in the special 9-bit case of 1 00000000 (-256), but valid otherwise.

[MichaelM]

A few months ago I presented a 16 x 16 Signed Multiplication routine for my M65C02A core and Bitwise provided one for th 65816. Initial testing provided good results, but Bitwise indicated that he wasn't getting the expected result for a product of -32768 x -32768.

Bitwise wrote:

I had a go for the 65C816. This works for normal values but not -32768 - Not sure where the extra bit P can be held.

Some time ago I had decided to implement an arithmetic right shift instruction for my M65C02A core. The intention was to use it improve the time required for multiplications using the Booth algorithm. A previous attempt at a 8 x 8 signed multiplication routine for the 65C02 using a Booth algorithm required keeping a "guard" bit for the sign bit.

In my M65C02A core, I also implemented an instruction to reverse the bits of a register which allows the C flag / bit to function as the Booth "recoding" memory bit and the N flag to sense the state of the next bit in the multiplier. The multiplier is shifted left after reversing it which allows the C flag / bit to hold the previously shifted value and the N flag to test the state of the next multiplier bit. A simple SEC instruction at the beginning of the routine correctly initializes the Booth "recoding" memory bit.

Regardless, a guard bit is required for the sign bit of the product register. In an hardware implementation, an additional bit duplicating the sign bit is very easily included. Because of the number of additional instructions and memory cycles / locations required to implement a guard bit, I decided to use the overflow flag V to indicate those cases where the addition / subtraction of the multiplicand to the double length product register overflowed the representation. I restore the sign of the product during the arithmetic right shift as described below. In short, I think that the sign is determined from the N and V flags rather than the C and V flags:

MichaelM wrote:

BitWise:

Something you said regarding the -32768 * -32768 case made me go back and check my implementation. I found that my result was 0xC000_0000 instead of the correct 0x4000_0000.

In getting the bugs out of the M65C02A Python model and the _imul() source, I had removed a feature of the M65C02A-specific asr.w a instruction that enables the restoration of the correct sign bit when the preceding add/sub operation of the Booth multiplication operation generates an arithmetic overflow. When -32768 is added to -32768 in the upper product register, the result is 0x8000_0000. The V flag correctly indicates an overflow.

I had modified the asr.w a to restore the sign by using the V flag and the N flag. If V is set, then the correct sign bit is the complement of the N flag. (If the V flag is not set, then the sign is the same as the N flag.) With this feature restored to the asr.w a instruction, the _imul() does correctly compute the product of -32768 * -32768.

[barrym95838]

MichaelM wrote:

... A previous attempt at a 8 x 8 signed multiplication routine for the 65C02 using a Booth algorithm required keeping a "guard" bit for the sign bit ...

Holy moly, Batman! That thing is ginormous!

[MichaelM]

Thing of beauty isn't it?

[andreamazzai]

ttlworks wrote:

Also, see here.

Just wanted to say thank you because I was having a hard time trying to understand the Overflow thing while having some fun with a customization of the Ben Eater 8 bit computer based on TTL chips (https://tomnisbet.github.io/nqsap/docs/flags/ linking to your 74181 with V_Flag and related pages, that I found very difficult to comprehend at the beginning, but now I'm so happy I managed to understand let's say 95%)

[andreamazzai]

Hello gurus,

I have built a TTL 6502 and I'm writing some documentation (in Italian) that could be useful to someone interested in the matter, or maybe some students keen to learn more from someone that moved from theory to practice. What I'm experiencing is that explaining things to other people is the best learning method!

It seems that I do not understand something about V Flag explanation by Dieter found in http://6502.org/users/dieter/v_flag/v_4.htm.

AIUI for A + B additions V is set on (A7 = B7 = 1 AND Q7 = 0) OR (A7 = B7 = 0 AND Q7 = 1).

Also for A - B subtractions V is set on (A7 = 1 AND B7 = Q7 = 0) OR (A7 = 0 AND B7 = Q7 = 1).

I don't care about B - A (not implemented in my TTL 6502).

This puzzles me:

Quote:

Well, we would need six 4_Input_ANDs, one 6_Input_OR, and three inverters.
Could be done with 3*7420, 1*7430, and 0.5*7404.

If we don't account for B-A, then we could draw the attached schematic, but to me there is something I cannot explain / an error.

As far as I understand, I believe that some additional logic should be added after the A + B and A - B overflow detectors to detect a sum or a subtraction, otherwise V could be set even if there is no actual overflow.

In example, let's try to make a subtraction A - B where A = 4 and B = 6 (result should be = -2). Let's use a four bit word for simplicity.

Code: Select all

A 0100-                0100+
B 0110=  ==> 2C  ==>   1010=
  ----                 ----
Q 1110                 1110

MSB of A = 0, B = 0 and Q = 1 is not an Overflow case for a subtraction, but it for a sum, hence the attached schematic would show that there is an Overflow, even if that's not true.

What I think is that I should add additional logic to detect if we are executing a sum or a subtraction.

Am I wrong? Am I missing something?

I hope I made myself understood.

BTW, the actual Overflow detection logic in my CPU is implemented via 74151 and it is great!

Ciao, Andrea

Edit: wording, better explanation.

[John West]

andreamazzai wrote:

AIUI for A + B additions V is set on (A7 = B7 = 1 AND Q7 = 0) OR (A7 = B7 = 0 AND Q7 = 1).

Also for A - B subtractions V is set on (A7 = 1 AND B7 = Q7 = 0) OR (A7 = 0 AND B7 = Q7 = 1).

Yes, but there's a subtlety. Subtraction is implemented by inverting B then adding. We can rewrite the expression for subtraction's overflow as
(A7 = !B7 = 1 AND Q7 = 0) OR (A7 = !B7 = 0 AND Q7 = 1). !B7 is the inverse of B7, which is what the adder is being given for subtraction. So as far is it is concerned, overflow is set on the same condition for both addition and subtraction - it's just the inputs that have changed.

All you have to do is move the B input to your overflow circuit from the ALU's B input (which is always B) to the adder's input (which is B or !B depending on whether it's adding or subtracting), and the overflow circuit doesn't need to know what the operation is.

[andreamazzai]

Hi John, thank you for taking time to help me out!

All is fine, but I think I was not 100% understandable in my wording, forgive me, I'm not a native speaker.

I am at the step http://6502.org/users/dieter/v_flag/v_4.htm where Dieter says "Problem is, that with ALU chips like the 74181, we don't have access to B'. So we have to build our own B'."

I am actually using 2x '181s, hence I must build my B7'.

For additions, B7' = B7.
For subtractions, B7' = !B7

The point here is that, from Dieter explanation, one could understand that you can simply connect the inputs of the A+B, B-A and A-B overflow detectors to the ALU A7, B7 and Q7 pins, and you will get a functioning overflow alert.

Quote:

"Well, we would need six 4_Input_ANDs, one 6_Input_OR, and three inverters."

Actually, if you built an A+B and A-B overflow detector like this:

there will be cases where an overflow is detected, but actually there is no overflow, as I described in my previous post:

... in A - B, the case where

Quote:

MSB of A = 0, B = 0 and Q = 1 is not an Overflow case for a subtraction, but it is for a sum, hence the attached schematic would show that there is an Overflow, even if that's not true.

Please note only 4 ANDs because I am not using B-A.

The misleading (to me, at least, but I understand that American English has some tricks that I don't get the first time I read them) part of the sentence is in bold and underlined, one 6_Input_OR. This could lead to think that one can simply OR all the outputs of the A+B and A-B overflow detectors, whereas I believe that some additional gates should be added at the level of each detector to understand if current operation is addiction or subtraction:

Did I totally miss the point, or am I on the right path?

Andrea

[ttlworks]

Hi Andrea,

Sorry for the delay, dissecting that floppy controller chip is a lot of work.
So I'm not reading the forum often, and I had not noticed your confusion.

IIRC what I had in my backhead when writing my article 19 years ago was something like this:

Three inverters (0.5* 7404), plus six 4 input AND gates (3*7421), plus "something like a 6 input OR gate".
Hope, this helps.

[andreamazzai]

Ahhhhh!

Dear Dieter, the devil is in the details

Quote:

Well, we would need six 4_Input_ANDs, one 6_Input_OR, and three inverters.

In the sentence above, you clearly stated that you need 4-input AND gates, and now I see your schematic—the fourth input is used to determine which operation is being processed (A+B, A-B, or B-A).

In the past, I read that sentence hundreds of times, but I didn’t catch the '4,' and my eyes always read '3' because I was thinking of A, B, and Q.

Now, seeing the "4" and looking at your schematic, it all makes sense.

As a small form of self-encouragement, I have to say that when I was writing the "All About Overflow Detection" documentation for my computer, I actually noticed that something was missing in the AND/OR story to correctly detect overflow for the different operations. But thinking in terms of "3_Input_ANDs" didn’t help me solve the puzzle.

With the 4_Input_ANDs, everything falls into place - and I also get a clean understanding of how you demonstrated that the 74LS151 was great for the job!

Thank you so much for your answer, it cleared up all my doubts, and now I can move forward with completing the documentation.

Andrea

[White Flame]

Testing equality can be done with A XOR B = 0, and inequality with A XOR B = 1, so you don't have to capture the e.g. 0,0 and 1,1 cases individually.

The best implementation description, IMO, is from DerTrueForce

DerTrueForce wrote:

Signed overflow occurs when the sign bits of the addend and augend are the same, but the sign bit of the result is different. This is what the V status bit indicates.

This can be implemented in one of two ways:

1. Test that the 2 input signs are equal, and that one is not equal to the sum sign
2. Test that both input signs are each not equal to the sum sign. Since it's binary, that implies the 2 input signs are equal.

I've implemented the 2nd in emulation as

Code: Select all

V = (A7 ^ Q7) & (B7 ^ Q7)

, which might be simpler in TTL if you've got XORs involved.

For subtraction, mine flipped the bits of the one number and then fed into the same adder, so its B7 reflected the changed sign implicitly. You'd might need to handle that externally, which might just be another XOR per input to flip the subtrahend sign. This might handle addition & both subtraction directions (untested):

Code: Select all

V = ((OP_SUB_A ^ A7) ^ Q7) & ((OP_SUB_B ^ B7) ^ Q7)

The inner nested XORs are "invert if this operation is active" operations, and the outer XORs are inequality tests.

4x 2-input XORs (3 if you don't have B-A), and 1x 2-input AND, plus no inverted inputs are required. If you were going to go the raw route.