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

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

Kevin Becker wrote:
> 
> 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

Hi Kevin

"Kevin Becker" <starbugs@gmx.net> escribi&#4294967295; en el mensaje
news:bbc55e92.0311061129.28af9d44@posting.google.com...
> 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.

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

> 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
================================================================
Francisco Rodriguez Ballester (prodrig@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
================================================================

"Kevin Becker" <starbugs@gmx.net> wrote in message
news:bbc55e92.0311061129.28af9d44@posting.google.com...
> 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.

> 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

Francisco Rodriguez wrote:
> 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).

Glen Herrmannsfeld wrote:
> 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!

"Kevin Becker" <starbugs@gmx.net> wrote in message
news:bbc55e92.0311070813.507ea083@posting.google.com...
> Francisco Rodriguez wrote:
> > 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.

> Glen Herrmannsfeld wrote:
> > 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

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)


"Kevin Becker" <starbugs@gmx.net> escribi&#4294967295; en el mensaje
news:bbc55e92.0311070813.507ea083@posting.google.com...
> Francisco Rodriguez wrote:
> > 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

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

>
> Glen Herrmannsfeld wrote:
> > 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.

>
> Thanks a lot!

Best regards
    Francisco

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
==========================
Glen Herrmannsfeldt wrote:
> 
> "Kevin Becker" <starbugs@gmx.net> wrote in message
> news:bbc55e92.0311070813.507ea083@posting.google.com...
> > Francisco Rodriguez wrote:
> > > 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.
> 
> > Glen Herrmannsfeld wrote:
> > > 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

Followup to:  <bbc55e92.0311061129.28af9d44@posting.google.com>
By author:    starbugs@gmx.net (Kevin Becker)
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.
> 
> 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

	
-- 
<hpa@transmeta.com> at work, <hpa@zytor.com> in private!
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

"H. Peter Anvin" <hpa@zytor.com> wrote in message
news:bohuvm$4v4$1@cesium.transmeta.com...
> Followup to:  <bbc55e92.0311061129.28af9d44@posting.google.com>
> By author:    starbugs@gmx.net (Kevin Becker)
> 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)

> 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