Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!genat!maccs!gordan
From: gordan@maccs.UUCP (Gordan Palameta)
Newsgroups: comp.lang.c
Subject: Re: Expressions compared to zero in *c*
Message-ID: <766@maccs.UUCP>
Date: Mon, 14-Sep-87 12:57:37 EDT
Article-I.D.: maccs.766
Posted: Mon Sep 14 12:57:37 1987
Date-Received: Tue, 15-Sep-87 00:44:39 EDT
References: <374@mcdsun.UUCP>
Reply-To: gordan@maccs.UUCP (Gordan Palameta)
Organization: DCSS, McMaster University, Hamilton, Ontario, Canada
Lines: 58

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...