fnf@mcdsun.UUCP (Fred Fish) (09/08/87)
I am posting this for a coworker, please respond directly to him with
comments or questions. Thanks. His email address is
hao!noao!mcdsun!nud!dragon!jon
-Fred
======cut before next line======cut after this line=====cut before next line==
Message-ID: <472@dragon.UUCP>
Date: 18 Aug 87 22:47:34 GMT
Reply-To: jon@dragon.UUCP (Jon Kettenhofen, x5656)
Organization: Motorola Microcomputer Division, Tempe, Az.
Lines: 159
Does (a-b) < 0 imply a < b ? Pick a and b for controversy.
Here's a program, the output of which may cause some uproar.
The answers I like most are the ones which ignore overflow. Do you
believe that the ANSI standard should define this can of worms or
cop out with the usual "implementation defined"?
jon kettenhofen, Motorola MCD, Tempe AZ
======cut before next line======cut after this line=====cut before next line==
/*
Inconsistent comparison operator when overflow is forced.
The problem in these cases has to do with the special case of
comparison to zero. The resultant status flags from the calculation of
the (left-hand) expression are said (in reader.c) to be the same as the
comparison of that result with zero. However, if the zero is instead
in a variable, we shouldn't get the same result because the overflow
status will be reset (0) when the result of the expression is compared
with the variable. The VAX compiler code never looks at overflow. jon
870727
Error status at present is arbitrary. jon 870728
*/
#define VAL1 0x81818181
#define VAL2 0x7f7f7f7f
main()
{
int error = 0;
char z;
z ^= z;
{
#define TYPA char /* char, short, int, long */
#define sTYPA "(char)" /* char, short, int, long */
unsigned TYPA a, b;
TYPA c = 0;
a = VAL1;
b = VAL2;
if( (TYPA) a > (TYPA) b )
{
++error;
}
printf("%sa<%sb is %x\n", sTYPA, sTYPA,
( (TYPA) a < (TYPA) b ) );
if( (TYPA) ( a - b ) > (TYPA) 0 )
{
++error;
}
printf("%s(a-b)<%s0 is %x\n", sTYPA, sTYPA,
( (TYPA)(a-b) < (TYPA) 0 ) );
if( (TYPA) ( a - b ) > (TYPA) z )
{
++error;
}
printf( "%s(a-b)<%sz = %x\n", sTYPA, sTYPA,
( (TYPA)(a-b) < (TYPA)z ) );
if( (TYPA) ( a -= b ) > (TYPA) 0 )
{
++error;
}
a = VAL1;
printf( "%s(a-=b)<%s0 = %x\n", sTYPA, sTYPA,
( (TYPA)(a-=b) < (TYPA)0 ) );
if( (TYPA) ( a -= b ) > (TYPA) z )
{
++error;
}
a = VAL1;
printf( "%s(a-=b)<%sz = %x\n", sTYPA, sTYPA,
( (TYPA)(a-=b) < (TYPA)z ) );
if( (TYPA) ( c = a - b ) > (TYPA) 0 )
{
++error;
}
printf("%s(c=a-b)<%s0 is %x\n", sTYPA, sTYPA,
( (TYPA)(c=a-b) < (TYPA) 0 ) );
if( (TYPA) ( c = a - b ) > (TYPA) z )
{
++error;
}
printf("%s(c=a-b)<%sz is %x\n", sTYPA, sTYPA,
( (TYPA)(c=a-b) < (TYPA) z ) );
}
{
struct usl
{
int sum : 3;
int dummy : 23;
int unbits : 3;
unsigned tib932 : 3;
unsigned tiba32 : 3;
} pgm;
#define a pgm.tib932
#define b pgm.tiba32
#define c pgm.sum
#define z pgm.unbits
#define TYPE int /* char, short, int, long */
#define sTYPE "(3bits)" /* char, short, int, long */
a = 0x5;
b = 0x3;
z ^= z;
if( (TYPE) a > (TYPE) b )
{
++error;
}
printf("%stib932<%stiba32 is %x\n", sTYPE, sTYPE,
( (TYPE) a < (TYPE) b ) );
if( (TYPE) ( a - b ) > (TYPE) 0 )
{
++error;
}
printf("%s(tib932-tiba32)<%s0 is %x\n", sTYPE, sTYPE,
( (TYPE)(a-b) < (TYPE) 0 ) );
if( (TYPE) ( a - b ) > (TYPE) z )
{
++error;
}
printf( "%s(tib932-tiba32)<%spgm.unbits = %x\n", sTYPE, sTYPE,
( (TYPE)(a-b) < (TYPE)z ) );
if( (TYPE) ( a -= b ) > (TYPE) 0 )
{
++error;
}
a = 0x5;
printf( "%s(tib932-=tiba32)<%s0 = %x\n", sTYPE, sTYPE,
( (TYPE)(a-=b) < (TYPE)0 ) );
if( (TYPE) ( a -= b ) > (TYPE) z )
{
++error;
}
a = 0x5;
printf( "%s(tib932-=tiba32)<%spgm.unbits = %x\n", sTYPE, sTYPE,
( (TYPE)(a-=b) < (TYPE)z ) );
if( (TYPE) ( c = a - b ) > (TYPE) 0 )
{
++error;
}
printf("%s(pgm.sum=tib932-tiba32)<%s0 is %x\n", sTYPE, sTYPE,
( (TYPE)(c=a-b) < (TYPE) 0 ) );
if( (TYPE) ( c = a - b ) > (TYPE) z )
{
++error;
}
printf("%s(pgm.sum=tib932-tiba32)<%spgm.unbits is %x\n", sTYPE, sTYPE,
( (TYPD)(c=a-b) < (TYPD) z ) );
}
exit( error );
}
--
= Drug tests; just say *NO*!
= Fred Fish Motorola Computer Division, 3013 S 52nd St, Tempe, Az 85282 USA
= seismo!noao!mcdsun!fnf (602) 438-3614ron@topaz.rutgers.edu (Ron Natalie) (09/09/87)
> Does (a-b) < 0 imply a < b ? Pick a and b for controversy.
NO. Not if you overflow the value, the calculations are invalid.
For example. Define MAXINT to be the largest positive number representable
by type int. The expression MAXINT+1 will on most machines be the largest
negative number. Do you insist that it compare ">" 0 ? Even if the compiler
had the hope of knowing that ( a - b ) caused an overflow that is checkable
by the adjacent > operator, you've destroyed that with the cast in your
example program. A cast has exactly the same effect as assigning a value
to a variable of the type of the cast and then referencing that variable
That is
TYPEA x;
TYPEB y;
((TYPEB) x)
is equivelent to
(y = x)
only without the need for the intermediate "y" value.
Hence (CAST) (a-b) becomes a positive number by virtue of being stored,
(CAST) (MAXINT+1) becomes negative by virtue of being stored. C doesn't
keep overflow bits in the stored variables.
Overflowing variables (unless you know what will happen) is an error.
This is an EXCEPTION. You either have to check this carefully or hope
you have hardware that is going to notify you of the error.peter@sugar.UUCP (Peter da Silva) (09/12/87)
> Does (a-b) < 0 imply a < b ? Pick a and b for controversy. The Great FORTH comparison question makes it to 'C'... > believe that the ANSI standard should define this can of worms or > cop out with the usual "implementation defined"? > jon kettenhofen, Motorola MCD, Tempe AZ The latter. It's just too much work to figure out an implementation independent way of handling this. -- -- Peter da Silva `-_-' ...!seismo!soma!uhnix1!sugar!peter -- 'U` <-- Public domain wolf.
gordan@maccs.UUCP (Gordan Palameta) (09/14/87)
In article <374@mcdsun.UUCP> fnf@mcdsun.UUCP (Fred Fish) writes: > >Does (a-b) < 0 imply a < b ? Pick a and b for controversy. As has already been pointed out, these two expressions are not equivalent when overflow takes place. However, this can occasionally be useful. In TCP/IP networking code, it is necessary to compare sequence numbers. These are 32 bit unsigned quantities, and the comparison must be done modulo 2**32, i.e. 1 > 0 2**31 > 2**31 - 1 0 > 2**32 - 1 etc. It is easy to see that the comparison a > b will fail under some circumstances, whether a,b are signed long or unsigned long. However, if the comparison is done as a - b > 0, everything magically works thanks to the properties of two's complement arithmetic under overflows. In fact it works regardless of whether a,b are signed long or unsigned long (however the result a - b _must_ be considered as a signed long value, necessitating a cast if a,b are unsigned). In fact if you picture a clock dial with 0 at noon, and numbers increasing clockwise (i.e. 2**30 at 3 o'clock, 2 * 2**30 at 6 o'clock, 3 * 2**30 at 9 o'clock, etc.), then if you pick an arbitrary A on the clock dial, it turns out that A - B > 0 will be true for all B in the half circle counterclockwise from A A - B < 0 will be true for all B in the half circle clockwise from A (where A-B is a signed 32-bit value) thus satisfying the requirements for modulo 32 comparisons. This is the basis of the macros SEQ_LT, SEQ_LEQ, SEQ_GT, SEQ_GEQ in the include file tcp_seq.h of the BSD TCP/IP code: #define SEQ_LT(a,b) ((long)((a)-(b)) < 0) etc. This same property is useful, for instance, in dealing with timers. If a longword value is incremented every clock tick, and its values are read as T1 and T2 at two different times, the comparison T2 - T1 > 0 will always work in distinguishing the later event (and in fact the value of T2 - T1 will always be the correct number of ticks between the two events, regardless of overflows). >I am posting this for a coworker, please respond directly to him with >comments or questions. Thanks. His email address is > > hao!noao!mcdsun!nud!dragon!jon Oops, well, I figured it was of general interest...
dhesi@bsu-cs.UUCP (Rahul Dhesi) (09/15/87)
In article <766@maccs.UUCP> gordan@maccs.UUCP (Gordan Palameta) writes: >However, if the comparison is done as a - b > 0, everything magically >works thanks to the properties of two's complement arithmetic under >overflows. ...Except if the hardware causes a trap when a signed quantity overflows. -- Rahul Dhesi UUCP: <backbones>!{iuvax,pur-ee,uunet}!bsu-cs!dhesi
henry@utzoo.UUCP (Henry Spencer) (09/15/87)
> However, if the comparison is done as a - b > 0, everything magically > works thanks to the properties of two's complement arithmetic under > overflows. In fact it works regardless of whether a,b are signed long or > unsigned long (however the result a - b _must_ be considered as a signed long > value, necessitating a cast if a,b are unsigned)... Thou hast missed a fine point: this subtraction should always be done with unsigned longs, because the result of overflow in signed subtraction is *undefined*. That is, it could give you a trap or the wrong answer. The latter possibility is real; many C compilers can AND WILL give wrong results in certain situations involving signed overflow. The two statements "the compiler ignores the possibility of overflow" and "the generated code ignores overflows" are ***NOT*** synonymous. If the compiler is ignoring the issue of overflows, it ignores the possibility that overflow may put the hardware into an unexpected state. For unsigned arithmetic, it is (theoretically... sigh) required to cope properly. Those who think I am kidding might try compiling and running the following. (If your machine is 16 bits, change "2000000000" to "32000" everywhere.) ---------- main() { int foo; foo = 2000000000; if ((foo += 2000000000) < 0) printf("%d is negative\n", foo); else printf("%d is non-negative (!)\n", foo); } ---------- Now, for extra marks, change the declaration of foo to unsigned and the condition to "((int)(foo += 2000000000) < 0)" and see whether the people who wrote your compiler were aware of the issue! (It may console them to know that Dennis Ritchie overlooked this one too... although he had the excuse that he wrote his compiler before X3J11 made it explicit that unsigned arithmetic never overflows.) For those whose machines give the right answer, and who can't understand what the fuss is about, on many pdp11-derived machines (VAX, 68k, etc etc) the compiler will cleverly realize that for a comparison against 0, it only needs to test the condition codes set by the addition. Unfortunately, the condition codes from the addition are the same as those of a comparison of the result to 0 *only if* the addition did not overflow. Change the "0" to "1" and the problem goes away. -- "There's a lot more to do in space | Henry Spencer @ U of Toronto Zoology than sending people to Mars." --Bova | {allegra,ihnp4,decvax,utai}!utzoo!henry
karl@haddock.ISC.COM (Karl Heuer) (09/15/87)
In article <766@maccs.UUCP> gordan@maccs.UUCP (Gordan Palameta) writes: >However, if the comparison is done as a - b > 0, everything magically >works thanks to the properties of two's complement arithmetic under >overflows. In fact it works regardless of whether a,b are signed long or >unsigned long (however the result a - b _must_ be considered as a signed long >value, necessitating a cast if a,b are unsigned). A slight quibble here: a and b should be cast into an unsigned type before doing the subtraction. Unsigned arithmetic is *guaranteed* to be modulo 2**N, but signed arithmetic may cause a surprise when overflow occurs. Karl W. Z. Heuer (ima!haddock!karl or karl@haddock.isc.com), The Walking Lint