Help needed with overflow.

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

Help needed with overflow.

Postby yetifoot » Apr 24, 2006 19:24

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
Posts: 619
Joined: Feb 07, 2006 15:29
Location: France / Luxemburg
Contact:

Postby redcrab » Apr 24, 2006 20:58

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

Postby yetifoot » Apr 24, 2006 21:19

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: 619
Joined: Feb 07, 2006 15:29
Location: France / Luxemburg
Contact:

Postby redcrab » Apr 24, 2006 21:23

That's true it is a very good tip, that we discovered thank to you ;)
cha0s
Site Admin
Posts: 5317
Joined: May 27, 2005 6:42
Location: Illinois
Contact:

Postby cha0s » Apr 25, 2006 2:14

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: 619
Joined: Feb 07, 2006 15:29
Location: France / Luxemburg
Contact:

Postby redcrab » Apr 25, 2006 8:21

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
Site Admin
Posts: 5317
Joined: May 27, 2005 6:42
Location: Illinois
Contact:

Postby cha0s » Apr 25, 2006 9:07

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:

Postby yetifoot » Apr 25, 2006 9:44

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
Site Admin
Posts: 6211
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

Postby counting_pine » Apr 25, 2006 15:03

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:

Postby yetifoot » Apr 25, 2006 15:41

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
Site Admin
Posts: 6211
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

Postby counting_pine » Apr 25, 2006 15:49

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)

Return to “General”

Who is online

Users browsing this forum: albert, Google [Bot] and 6 guests