Arithmetics with carry

I'm designing a processor for one specific application and in my software I have need a counter. I have a problem figuring out how to make Add-with-carry work for this.

I want to do v := v + i. v and i are both 32 bit values, my ALU is 16 bits wide. Everything is 2-complement.

I would add the lower 16 bits, then add the higher 16 bits with carry. My problem: "i" may be positive or negative, so there are 3 things that can occur:

- overflow

- underflow

- none of those

If I have only one carry bit, those 3 possibilities cannot be represented. Am I right that in such an architecture it is impossible to achieve what I want? How do I have to change my ALU in order to do that? And how do I handle the sign bits in the "middle" of the 32 bit values? If possible, I would like to avoid an additional comparison and use only flags.

I have looked at PicoBlaze as an example, but I could not figure out what I am doing wrong. Please help :) Thanks, Dan

Reply to
Kevin Becker
Loading thread data ...

Reply to
Peter Alfke

Hi Kevin

"Kevin Becker" escribió en el mensaje news: snipped-for-privacy@posting.google.com...

Right for overflow/none. Can't see how could you get an underflow (a too close too zero to be represented value) as you're working with 2's complement integers. All integers in the given range are representable.

As your numbers are 32-bit wide, and overflow condition is a flag about the result of the _whole_ v := v + i operation, it can be determined by the MSB bits only (that is, from columns 31 and 30 of the addition).

Let we call cy-n to the carry out of the n-th column, and number the bits from 0 (lsb) to 31 (msb). Then, overflow = cy-31 xor cy-30.

What you have between columns 15 and 16 is a simple carry, an intermediate bit of the operation. No (directly) related with the overflow condition.

No. See comments above

Step 1.- v(lo) := v(lo) + i(lo). Store the 16-bit carry out. Call it cy-16 Setp 2.- v(hi) := v(hi) + i(hi) + cy-16. Step 3.- Check overflow using cy-32 and cy-31. These bits are cy-16 and cy-15 of step 2 addition.

Now the question are:

a) Is your ALU capable to perform result (a 16 bits plus carry out) = x (a

16-bit value) + y (a 16-bit value) + c (1-bit value, previous carry-out)? If not, many instructions will be needed to solve your problem.

b) Do you have separate access to the intermediate cy-31? (=cy-15 from step

2). If not, the overflow condition will be difficult to check.

Hope this helps

Regards Francisco ================================================================ Francisco Rodriguez Ballester ( snipped-for-privacy@disca.upv.es) Postal address: Dept. DISCA, EUI - Univ. Politecnica de Valencia c/Camino de Vera s/n, E-46022, VALENCIA (SPAIN) tlf: +(34) 96 387 70 07 ext. 75759 - fax: +(34) 96 387 75 79 ================================================================

Reply to
Francisco Rodriguez

When after you add the low halfwords, you either get a carry or you don't. That is used as carry in for the high halfword add.

After the high halfword add, you compare the carry out to the carry out of the sign bit to the carry in of the sign bit. If they are different then it is overflow or underflow. The value of such bit tells you which one.

-- glen

Reply to
Glen Herrmannsfeldt

Thank you! I think I used the wrong word "underflow". What I mean is: if "i" is negative, it might be that abs(lo(i)) is greater than lo(v). What happens then? An example:

v = 1234 0100 hex i = 0000 0101 hex

The > After the high halfword add, you compare the carry out to the carry out of

So does that mean I have to modify my architecture and set TWO flags? A carry flag and a negative flag (if sign of last operation was negative), and then the Add-With-Carry instruction would look at both?

Thanks a lot!

Reply to
Kevin Becker

determined

Yes, underflow is the right word. It isn't used very often, though.

Hmm. X'0100' + X'0101' is X'0201' with no overflow. If you want to add a small twos complement negative number, then that number will have F's in the high bits which will take care of the 1233 part. In that case, borrow means that there is no carry, otherwise there is a carry. Say v=X'12340100' and i is negative 257. Negative 257 is X'FFFFFEFF'

X'0100' + X'FEFF' is X'FFFF' with no carry. X'1234'+X'FFFF' is X'1233' with carry. The carry into the high bit is also 1, so that there is no overflow or underflow.

of

then it

No, add with carry doesn't need to know. You only need the two flags at the end if you want to detect overflow and underflow.

-- glen

Reply to
Glen Herrmannsfeldt

Hi Kevin

I would recommend you to search and study the instruction set of a microprocessor with the support you're trying to implement in your processor.

Many processors have two different add instruccions (with and without carry) to support large integer arithmetic. The simplest I know of is the 8031

8-bit microcontroller from Intel, Infineon, Dallas and many other manufacturers.

The first hit I found in google points to the page

formatting link
It contains the description and some numeric examples for arithmetic operations.

Of interest are: ADD (A =A +x, carry is not used) ADDC (A=A+x+carry) SUBB (A = A-x-carry)

"Kev> > As your numbers are 32-bit wide, and overflow condition is a flag

determined

No. I assume you're substracting the numbers, as i is positive and the result you mention is v-i. Then, take into account that substraction is performed by an adder in 2's complement arithmetic as follows:

v - i = v + 2's complement(i) = v + not(i) + 1

So v-i operation is converted to 12340100 + FFFFFEFE + 1 = 1233FFFF

The low part is 0100 + FEFF = FFFF, the carry from the low part is _not_ set, so the high part is 1234 + FFFF =

1233

Go to the mentioned page, you'll see the different descriptions for carry (or borrow) and the overflow. Carry/borrow is the cy-16 out of the add operation (remember there's no substraction circuit). It is the overflow flag if and only if you're using unsigned arithmetic Overflow for signed arithmetic is cy-16 xor cy-15. When this xor gives you 1 means you've obtained a positive result adding two negative numbers, or a negative result adding two positives.

of

then it

Never look at both. Your ALU must provide two flags, carry and overflow, and two different add instructions x+y and x+y+carry. Of course, every add must update both flags. If you also provide set-carry/clear-carry instructions, the pseudocode of the 32-bit operations would be

for 32-bit additions: add x-low, y-low addc x-high, y-high

for 32-bit substractions: set carry addc x-low, not(y-low) addc x-high, not(y-high)

When the whole operation is finished, check carry/borrow if the 32-bit numbers are unsigned, or the overflow flag if the 32-bit numbers are signed. But no both. Don't check the flags after the low part.

Best regards Francisco

Reply to
Francisco Rodriguez

Reply to
Peter Alfke

Followup to: By author: snipped-for-privacy@gmx.net (Kevin Becker) In newsgroup: comp.arch.fpga

No, you're not correct. What you're doing wrong is simply failing to recognize the fundamental reason why 2's complement is so ubiquitous:

ADDITION AND SUBTRACTION OF 2'S COMPLEMENT NUMBERS IS IDENTICAL TO THE SAME OPERATIONS ON UNSIGNED NUMBERS

Therefore, you don't care if you got overflow or underflow -- they are both represented by carry out.

In other words, build your ALU just as if "v" and "i" were unsigned numbers, and everything is good.

-hpa

--
 at work,  in private!
If you send me mail in HTML format I will assume it's spam.
 Click to see the full signature
Reply to
H. Peter Anvin

(snip)

This is true, except for generating the flags on the final add. Well, you can either generate all the flags, or only the signed or unsigned flags. For the intermediate adds only the carry, or lack of carry, from the high bit is important. To detect signed overflow or underflow (more negative than can be represented) requires comparing the carry into and out of the sign bit.

-- glen

Reply to
Glen Herrmannsfeldt

Aaaah, now I got it!

The problem was that I read somewhere that a SUB instruction generates a carry flag when subtracting a negative number and the result becomes too big. So I automatically assumed somehow that an ADD instruction also generates a carry flag when adding a negative number (which is wrong). I also forgot that when I have a negative number, also the high halfword will be FFFF. I thought it would be zero because the abs(i) is small enough to fit into the low halfword, but due to the sign it is NOT zero.

Peter: I am not using the counter macro because this operation is one of many operations in an algorithm and the value needs to be in the RAM which is only connected to the processor.

Thanks to everybody who helped me out with this.

Reply to
Kevin Becker

Followup to: By author: "Glen Herrmannsfeldt" In newsgroup: comp.arch.fpga

It depends. Some architectures define CF=0 to mean borrow-out from a subtraction. Under that definition (used by the PDP-11, for example), SUB is equivalent to NEG + ADD (a desirable property in my opinion); under the "other" definition (as used by among others Intel processors ever since the 4004), SUB ends up producing the opposite carry from NEG+ADD.

-hpa

--
 at work,  in private!
If you send me mail in HTML format I will assume it's spam.
 Click to see the full signature
Reply to
H. Peter Anvin

you

high

the

For unsigned arithmetic, or all except the most significant word of multiword signed arithmetic, yes, carry is the complement of borrow. Somewhere back in the thread I wrote that. For the most significant word or only word for signed arithmetic overflow/underflow must be computed differently.

-- glen

Reply to
Glen Herrmannsfeldt

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.