Help needed with overflow.

[yetifoot]

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
  add al, 5
  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]

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

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]

That's true it is a very good tip, that we discovered thank to you ;)

[cha0s]

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]

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]

ohh, i'm sure you're right =), and i meant shr not shl.. d'oh!

[yetifoot]

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]

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]

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

[counting_pine]

That was a small error on my part. I switched, without warning, from tmp = a + b to tmp = a + b + 128. (The former should work for unsigned bytes)