From: diamond@jit533.jit.dec.com (Norman Diamond)
Subject: Re: Sequence space arithmetic
Reply-To: diamond@jit.dec.com (Norman Diamond)
Organization: Digital Equipment Corporation Japan , Tokyo
Date: Thu, 7 Jan 1993 03:27:09 GMT

In article <1ifb0pINN7qq@daisy.ee.und.ac.za> barrett@daisy.ee.und.ac.za (Alan P Barrett) writes:
>#include <limits.h>
>/* how to check if (a >= b) in 32-bit sequence space arithmetic. */
>#if (UINT_MAX == 0xffffffff)            /* int is exactly 32 bits */
>#        define SEQ_GT(a,b) ((int)((unsigned int)(a)-(b)) > 0)
>#else
>#  if (ULONG_MAX == 0xffffffff)         /* long is exactly 32 bits */
>#        define SEQ_GT(a,b) ((long)((unsigned long)(a)-(b)) > 0)
>#  else
>#    if (ULONG_MAX > 0xffffffff)        /* long is wider than 32 bits */
>#      if 1 /* if you insist on evaluating a and b exactly once each */
>#        define SEQ_GT(a,b) \
>                ((((unsigned long)(a)-(b)) & 0xffffffff)-1 < 0x7fffffff)
>#      else /* this is more intuitively obvious */
>#        define SEQ_GT(a,b) \
>                (((a)!=(b)) && ((((unsigned long)(a)-(b)) & 0x80000000) == 0))
>#      endif
>#    else                               /* long is narrower than 32 bits */
>       #error "ULONG_MAX is less than 32 bits.  Get a real compiler."
>#    endif
>#  endif
>#endif

ANSI Classic section 3.2.1.2, page 35 lines 30 to 33:  "When a value with
integral type is demoted to a signed integer with smaller size, OR AN
UNSIGNED INTEGER IS CONVERTED TO ITS CORRESPONDING SIGNED INTEGER, if the
value cannot be represented the result is implementation-defined."

Even on a nice friendly two's complement machine with 32-bit ints, UINT_MAX
defined as 0xffffffff, INT_MAX as 0x7fffffff, and INT_MIN as -0x40000000<<1,
your cast of a big unsigned int (result of subtraction) to a signed int is
not guaranteed to give you what you want.

The result is equally implementation-defined for one's complement machines,
but is even less likely to give you what you want.

You're better off sticking to unsigned arithmetic entirely.

>Are both methods for handling longs wider than 32 bits guaranteed to work?

I think those work.

>Will they also work with longs of exactly 32 bits? 

No, for the same reason as ints of exactly 32 bits don't.

>Which is likely to be handled better by existing compilers?

Huh?  Obviously you're not asking a standards question here, but if you're
talking about conforming implementations, well they all have to handle the
syntax of what you've given, and you haven't given any other choices that
might be handled better or worse.  What's your question?

>I believe that casting unsigned values into signed types is implementation
>defined, and that this affects the parts that handle int or long of
>exactly 32 bits.  Is that the case?

Ah, then you knew.

>If we assume that the implementation does the obvious thing with
>casts (just interprets the bits differently), will that code work?

Are your asking about the standard or not?

>How reasonable is it to make such an assumption, given that the code is
>intended to run on a Unix system?

>Would it be reasonable to omit all the #if tests, leaving just the part
>that deals with longs wider than 32 bits, and trust the compiler to make
>the relevant optimisations if a 32-bit type is available?

I think it would be reasonable in the interests of getting correct results.
As for optimizations...  You haven't said what types the arguments (a and b)
are likely to have.  If they're longs, then unsigned long arithmetic should
be expected, and is unlikely to be optimized to unsigned int.  If they're
ints, then you want to get unsigned int arithmetic, right?  One solution is
to dictate that the expressions should be unsigned to begin with, and then
you can omit all casts in your macros.  Your integral constants will have
type int or unsigned int or long or unsigned long as necessary, and will be
promoted to unsigned int or unsigned long as necessary for the operations.
If you cannot dictate that way to your users, then you still need two versions,
one with casts to unsigned int and one with casts to unsigned long.

>Would it be reasonable to omit all the #if tests, leaving just the part
>that deals with longs of exactly 32 bits, and hope that the code never
>runs on a system that has wider longs?

You don't have to hope; you could be SURE that the code will never run on
a system that has wider longs.  Uh, I should say ALMOST sure, because the
code might start out running for a while....  Anyway, you can restrict
yourself to whatever market segment you like, but please publish your
limitations before trying to sell your product.
--
Norman Diamond                diamond@jit.dec.com
If this were the company's opinion, I wouldn't be allowed to post it.
Pardon me?  Or do I have to commit a crime first?