Arithmetics with carry

Arithmetics with carry

Post by Kevin Beck » Sat, 08 Nov 2003 04:29:57



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

 
 
 

Arithmetics with carry

Post by Peter Alfk » Sat, 08 Nov 2003 05:26:06


Why do you use an ALU to implement a counter?
Just use a counter macro that is 32 bits, and you don't have to think.
Peter Alfke

> 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


 
 
 

Arithmetics with carry

Post by Francisco Rodrigue » Sat, 08 Nov 2003 05:38:38


Hi Kevin



Quote:> 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

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.

Quote:

> 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

No. See comments above

Quote:> 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

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
================================================================

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
================================================================

 
 
 

Arithmetics with carry

Post by Glen Herrmannsfeld » Sat, 08 Nov 2003 13:08:24



Quote:> 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

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.

Quote:> 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.

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

 
 
 

Arithmetics with carry

Post by Kevin Beck » Sun, 09 Nov 2003 01:13:25



> 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).

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 operation for the lo bits will result in FFFF and the carry will
be set. Then when I add the high bits, it will be 1235 when it should
actually be 1233. How do I save that the first operation was not an
overflow but a borrow? (I don't know how to call this. That's what I
mistakenly called underflow).


> 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.

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!

 
 
 

Arithmetics with carry

Post by Glen Herrmannsfeld » Sun, 09 Nov 2003 03:22:54




> > 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).

> 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).

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

Quote:> What happens then? An example:

> v = 1234 0100 hex
> i = 0000 0101 hex

> The operation for the lo bits will result in FFFF and the carry will
> be set. Then when I add the high bits, it will be 1235 when it should
> actually be 1233. How do I save that the first operation was not an
> overflow but a borrow? (I don't know how to call this. That's what I
> mistakenly called underflow).

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.


> > 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.

> 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?

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

 
 
 

Arithmetics with carry

Post by Francisco Rodrigue » Sun, 09 Nov 2003 04:36:55


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
http://www.rehn.org/YAM51/51set/instruction.shtml
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)




> > 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).

> 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 operation for the lo bits will result in FFFF and the carry will
> be set. Then when I add the high bits, it will be 1235 when it should
> actually be 1233. How do I save that the first operation was not an

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

Quote:> overflow but a borrow? (I don't know how to call this. That's what I
> mistakenly called underflow).

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.


> > 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.

> 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?

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.

Quote:

> Thanks a lot!

Best regards
    Francisco
 
 
 

Arithmetics with carry

Post by Peter Alfk » Sun, 09 Nov 2003 08:34:03


If I remember right, this is a counter application.
Forget the 16-bit ALU and use a 32-bit counter instead, and avoid all
this headache. KISS.
Peter Alfke
==========================




> > > 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).

> > 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).

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

> > What happens then? An example:

> > v = 1234 0100 hex
> > i = 0000 0101 hex

> > The operation for the lo bits will result in FFFF and the carry will
> > be set. Then when I add the high bits, it will be 1235 when it should
> > actually be 1233. How do I save that the first operation was not an
> > overflow but a borrow? (I don't know how to call this. That's what I
> > mistakenly called underflow).

> 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.


> > > 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.

> > 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?

> 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

 
 
 

Arithmetics with carry

Post by H. Peter Anvi » Sun, 09 Nov 2003 14:29:26




In newsgroup: comp.arch.fpga

Quote:

> 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.

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

--

If you send me mail in HTML format I will assume it's spam.
"Unix gives you enough rope to shoot yourself in the foot."
Architectures needed: ia64 m68k mips64 ppc ppc64 s390 s390x sh v850 x86-64

 
 
 

Arithmetics with carry

Post by Glen Herrmannsfeld » Sun, 09 Nov 2003 15:23:15






> In newsgroup: comp.arch.fpga

> > 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.

(snip)

Quote:> 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.

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

 
 
 

Arithmetics with carry

Post by Kevin Beck » Sun, 09 Nov 2003 22:35:24


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.

 
 
 

Arithmetics with carry

Post by H. Peter Anvi » Thu, 13 Nov 2003 06:36:47




In newsgroup: comp.arch.fpga

Quote:

> 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.

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
--

If you send me mail in HTML format I will assume it's spam.
"Unix gives you enough rope to shoot yourself in the foot."
Architectures needed: ia64 m68k mips64 ppc ppc64 s390 s390x sh v850 x86-64

 
 
 

Arithmetics with carry

Post by Glen Herrmannsfeld » Thu, 13 Nov 2003 15:44:49






> In newsgroup: comp.arch.fpga

> > 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.
> 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.

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