Song of The Day: People of the Sun - Artist: Rage Against The Machine

Recently, I received an inquiry concerning my algorithm tested within the Integer Overflow blog series. Here’s the algorithm:


#ifdef __GNUC__
#define INLINE inline
#else
#define INLINE __forceinline
#endif

INLINE static long ericoSafeAdd (long a, long b)
{
    long c=a+b;
     if (((((unsigned long)a) & 0×80000000) != (((unsigned long)c) & 0×80000000))
      && (((unsigned long)a) & 0×80000000) == (((unsigned long)b) & 0×80000000)) {
        SafeIntOnOverflow();
     }
    return c;
}

So why does this work? Perhaps, a better question is why does this appear to work with limited testing… :)

Interestingly, the code assumes the presence of a sign bit and of two’s complement arithmetic. Most importantly, the sign bit needs to be in the most significant bit of the most significant byte. A sign bit of 1 means negative; a 0 means positive. Furthermore, the code assumes addition only.

First, the code excerpt checks to determine if the first operand’s sign, negative or positive, is different from the result’s sign. If it is, then there is an additional check to see if both of the original operands are of the same sign. If the sign has changed AND the original operands are of the same sign (i.e., positive or negative), then an integer overflow has occurred.

Do the results change with endianness? Again, interestingly, the results do not vary between architectures (i.e., with Intel/PowerPC Macs and a Wintel laptop).

For example, I wrote the following GDB macro to view the variables and byte orders within the ericoSafeAdd function:


#
# .gdbinit file
#
# GDB macros by erico
#

file safeadd
b ericoSafeAdd

#
# print a variable and its byte contents
#

define pe
set var $ch = (unsigned char *)&$arg0
set var $i = 0
printf “variable: 0x%x\n”, $arg0
printf “bytes: ”
while $i < $arg1
printf "0x%02x ", $ch[$i]
set $i = $i + 1
end
printf "\n"
end

document pe
pe variable size
Prints the variable and bytes in machine order.
end

After placing the macro in one’s .gdbinit file, then gdb can be invoked. When this is run on an Intel MacBook, one receives output like the following (commands emphasized):

[initialization text deleted]

This GDB was configured as “i386-apple-darwin”.Reading symbols for shared libraries …. done
Breakpoint 1 at 0×2bbc: file safeint.cpp, line 260.

(gdb) r
Starting program: /Users/eolaughlen/Desktop/safeint/safeadd
Reading symbols for shared libraries . done
——————– Testing Addition
——————– Math requiring no overflow detection
——————– This is for speed (overhead)
Test Simple… total: 149994981 Time = 756.970 ms
Test MS Safe… total: 149994981 Time = 5550.954 ms
Test sree C Safe… total: 149994981 Time = 1713.621 ms

Breakpoint 1, ericoSafeAdd (a=1, b=0) at safeint.cpp:260
260 long c=a+b;
(gdb) n 2
(gdb) pe mask 4
variable: 0×80000000
bytes: 0×00 0×00 0×00 0×80
(gdb) quit

On my PowerPC MacBook Pro G4 notice the following difference:


(gdb) pe mask 4
variable: 0×80000000
bytes: 0×80 0×00 0×00 0×00
(gdb) quit

Although the byte orders are different between the two CPUs (i.e., Intel: little-endian versus PowerPC: big-endian), the sign bit and mask are consistent (i.e., MSB compares) using gcc/C++ (or Visual C++) and a recompile. Now, something like this could be an issue if storing or transmitting data between computers, but in our circumstance the details are hidden.

Thus, we have a semi-portable safe addition routine as long as the sign bit doesn’t deviate within two’s complement form.

Note: I did add the following line to the function above to make it easier to pass the mask variable to the GDB macro:


unsigned long mask = 0×80000000;

600) )4j

Tags: , ,