## Help needed with overflow.

General FreeBASIC programming questions.
yetifoot
Posts: 1710
Joined: Sep 11, 2005 7:08
Location: England
Contact:

### Help needed with overflow.

I'm working on some code at the moment, and need to test if there was an overflow in some arithmetic.

I know i could just do it in asm and test bit 11 of the flags, ie for an 8 bit add. (this is just a quick test code, i know theres better ways)

Code: Select all

``````ASM
xor eax, eax
mov al, 127
pushf
pop edx
shr edx, 11
and edx, 1
mov dword ptr [was_overflow], edx
End ASM``````
But i'd rather do it in BASIC if i can. I have a way that i borrowed from elsewhere, but i can't really understand it, and I was hoping someone could explain it for me. (again testing a 8-bit overflow)

Code: Select all

``````Dim As Byte a, b
Dim As Short tmp
a = 125
b = 3
tmp = (a + b)
Print ((a Xor (Not (b))) And (a XOR tmp) AND &H80) <> 0
Sleep
``````
I really don't get how this works...
redcrab
Posts: 623
Joined: Feb 07, 2006 15:29
Location: France / Luxemburg
Contact:
"a" and "b" are signed byte
from -128 to +127
that mean in binary format that the 8th most significant bit is the sign
1 mean negative, 0 mean positive
(not that zero is positive by this rule)

so the boolean opeartion is to test coherence result
a "positiive value" added with a "positive value" can only give a positive value
a "negative value" added with a "negative value" can only give a negative value
a "negative value" added with a "positive value" never overflow

125 is legal signed byte positive
3 is legal signed byte positive
125 + 3 = 128 (>127 mean the 8th bit is 1 now, then negative)
125 +3 = -128 by the rule

is it clear ?

EDIT : binary rule of signed type is -a = (not a) +1

Have fun
yetifoot
Posts: 1710
Joined: Sep 11, 2005 7:08
Location: England
Contact:
Thanks, i think i see it now, the XOR essentially only works on the MSB (The sign bit), because of the AND &H80. The XOR's then test for the rules you said, ie.

a "positiive value" added with a "positive value" can only give a positive value

Thats quite smart, I was thinking of silly things like

Code: Select all

``````If NOT Bit(a, 7) AND NOT Bit(b, 7) Then
' both pos
If Bit(tmp, 7) Then Print "Overflow"
End If``````
and so on for all possibles.
redcrab
Posts: 623
Joined: Feb 07, 2006 15:29
Location: France / Luxemburg
Contact:
That's true it is a very good tip, that we discovered thank to you ;)
cha0s
Posts: 5319
Joined: May 27, 2005 6:42
Location: USA
Contact:
your way is not silly. it could be faster if you do a couple things:

- seperate the AND into compund if...end if blocks
- don't use bit macros, there are mutiple operations. just shr len( op ) - 1

Code: Select all

``````If ( ( a Shl 7 ) = 0 ) Then

If ( ( b Shl 7 ) = 0 ) Then
' both pos
If ( tmp Shl 7 ) <> 0 Then
Print "Overflow"

End If

End If

End If``````
at most, 3 checks =)

the only thing is, encapsulating it into function (and the other checks) and overloading to support all types would be hard... but not impossible =)
redcrab
Posts: 623
Joined: Feb 07, 2006 15:29
Location: France / Luxemburg
Contact:
cha0s wrote:your way is not silly. it could be faster if you do a couple things:

- seperate the AND into compund if...end if blocks
- don't use bit macros, there are mutiple operations. just shr len( op ) - 1

Code: Select all

``````If ( ( a Shl 7 ) = 0 ) Then

If ( ( b Shl 7 ) = 0 ) Then
' both pos
If ( tmp Shl 7 ) <> 0 Then
Print "Overflow"

End If

End If

End If``````
at most, 3 checks =)

the only thing is, encapsulating it into function (and the other checks) and overloading to support all types would be hard... but not impossible =)
you can replace

Code: Select all

``(a shl 7) = 0``
by

Code: Select all

``(a and &h80) = 0``
it should be quicker : ASM AND is quicker than ASM SHL
cha0s
Posts: 5319
Joined: May 27, 2005 6:42
Location: USA
Contact:
ohh, i'm sure you're right =), and i meant shr not shl.. d'oh!
yetifoot
Posts: 1710
Joined: Sep 11, 2005 7:08
Location: England
Contact:
Very interesting, i'm still deciding on the best way for me to implement it. Still, i'll see if Moneo has seen the one-liners, i'm sure he'd enjoy them.
counting_pine
Posts: 6323
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs
As far as I can see, if tmp = a + b, you just need to check that
-128 < tmp <= 127
or
0 < tmp + 128 <= 255

If it's less than 0, or more than 255, then at least one of bits 8 to 31 will be set. So you know that it overflows iff tmp AND (NOT 255) <> 0.

In fact, the limited ranges of a and b means that if it overflows, bit 8 is guaranteed to be set. So you know that it overflows iff tmp AND 256 <> 0

Code: Select all

``````Dim As Byte a, b
Dim As Short tmp
a = 125
b = 3
tmp = (a + b + 128)
Print (tmp and &H100) <> 0
Sleep``````
yetifoot
Posts: 1710
Joined: Sep 11, 2005 7:08
Location: England
Contact:
counting_pine wrote: If it's less than 0, or more than 255, then at least one of bits 8 to 31 will be set. So you know that it overflows iff tmp AND (NOT 255) <> 0.
from what i understand, overflow is when it goes out of the range of a signed number.

ie 132 decimal = 10000100 binary, which still fits into the 8 bits, but has ended up causing the sign bit to change.

when it no longer fits within the 8 bits, then it is a carry. (ie 255 + 3)

This is why tmp is a short (although this also means at some points i need to AND &HFF), because i also check for carry using the method you show, ie carry = (tmp AND &H100) <> 0
Last edited by yetifoot on Apr 25, 2006 15:50, edited 1 time in total.
counting_pine