Arithmetics with carry

K

Kevin Becker

Guest
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
Click to expand...
 
Hi Kevin

"Kevin Becker" <starbugs@gmx.net> escribió 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
Click to expand...
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
Click to expand...
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
Click to expand...
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
Click to expand...
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.
Click to expand...
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).
Click to expand...
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.
Click to expand...
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).
Click to expand...
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).
Click to expand...
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?
Click to expand...
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ó 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
Click to expand...

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).
Click to expand...
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?
Click to expand...
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!
Click to expand...
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
Click to expand...
 
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.
Click to expand...
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.
Click to expand...
(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.
Click to expand...
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
 
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.
 
Followup to: <nZ%qb.101301$mZ5.680324@attbi_s54>
By author: "Glen Herrmannsfeldt" <gah@ugcs.caltech.edu>
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.
Click to expand...
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
--
<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:borkpf$p7v$1@cesium.transmeta.com...
Followup to: <nZ%qb.101301$mZ5.680324@attbi_s54
By author: "Glen Herrmannsfeldt" <gah@ugcs.caltech.edu
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.
Click to expand...
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
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top