I'm using unsigned long (32 bits here), to limit problems of overflow,
and because I'm working with machine addresses (on a byte-addressed
machine).  I need to describe address spaces.  I have two choices:

Case a)
   semi-open intervals, like [low,high).  low is in the range, but
   high is not.  If high==0, the range extends from low through all
   higher memory.  The problem is that high==0 is likely to prove a
   special case in iteration.
Case b)
   closed intervals, like [low,high].  The range is inclusive: high is
   in the range. The problem is that upper bounds look ugly, like
   0x01ffffff.

We don't have to worry about an address range that wraps around high
memory, with the quasi-exception of [low,0).  I don't think that all
memory will have to be in a range, like [0,0xffffffff].  Zero-length
ranges are a possibility, so [0,0) would be considered the null
range.  Increments for for-loops will be relatively small, certainly
less than LONG_MAX.

The problem is if the upper end is very near high memory.

   for (i = low; i != high; i += incr)
fails if, say, high is odd and incr is 4.

Case a) If high == 0,
   for (i = low; i < high; i += incr)
fails because the loop is never entered.  If high==0xfffffffe and
incr==4, it fails because it's an infinite loop.

Case b) If high=0xffffffff,
   for (i = low; i <= high; i += incr)
is an infinite loop.

So I have two questions.
1) How do you code a "for" loop to avoid overflow gotchas?
2) Depending on the best answer to 1), should I use semi-open or
   closed intervals?

I don't have easy access to the University of Michigan library; I
think I have access to JACM, SIGPLAN, and a few similar journals.

Bonus questions:  8-)
3) If shorts are 16 bits and ints are 32 bits, and low, high, and incr
   are shorts, does it get easier?  Addresses will have to be
   high-bit-extended before access: 0xff00 would map to 0xffffff00.
4) What do you do for arbitrary low, high, and incr?  (I.e. if incr >=
   LONG_MAX, run the loop backwards.)

--
   "Of course he has a knife.  We all have knives.  It's 1183, and we're
   all barbarians."
Tim McDaniel                 Applied Dynamics Int'l.; Ann Arbor, Michigan, USA

Languages that do this sort of thing usually take closed intervals,
although there are ways to handle both.

For instance, the loop

        for i := 1 to 300 do foo

(in Pascal) is usually generated as

        if (1 <= 300) {
                for (i = 1;; i++) {
                        foo;
                        if (i == 300)
                                break;
                }
        }

(equivalent C code).  (Yes, it is OK to leave `i' unset; Pascal index
variables may not be examined after the loop ends, until they are set
to some other values.)

If there is a step, the loop must compute the terminator value (or
the number of iterations):

        for i := 1 to 4 by 2

should compare for 3 (for ending) or compute a count of ((4-1)+1)/2
iterations.  In some cases this can be done at compile time.

To do the same for half-open intervals, simply subtract one from the
end value (using unsigned arithemtic, if necessary, to avoid underflow)
and do the same.  The loop

        for i in [m..n) do foo;

can be `compiled' to

        if (m < n) {
                stop = n - 1;
                for (i = 0;; i++) {
                        foo;
                        if (i == stop)
                                break;
                }
        }

Iteration count computations are identical except that instead of

        ((end - start) + 1) / incr

you simply use

        (end - start) / incr
--
In-Real-Life: Chris Torek, Lawrence Berkeley Lab CSE/EE (+1 415 486 5427)

(a) Use pointers instead.
(b) Don't push against the very limit of the representable range.
(c) Use unsigned types and compare for equality with zero.
(d) Consider each case on its own merits.

|> >1) How do you code a "for" loop to avoid overflow gotchas?
|>
|> (a) Use pointers instead.
|> (b) Don't push against the very limit of the representable range.
|> (c) Use unsigned types and compare for equality with zero.
|> (d) Consider each case on its own merits.

On a somewhat related note, the ANSI C standard guarantees that the address of
the element one past the end of an array is representable and won't overflow.
This makes loops like

{
        int a[10];
        int *p, *q;

        /* point q and at end a */

        q = &a[sizeof a / sizeof a[0]];

        for (p = a; p != q; p++)
                useful_work_goes_here();

work properly.  [The (sizeof a / sizeof a[0]) expression keeps the explicit
knowledge of the size of the array in its declaration.]  The implementation
must place the array a such that &a[10] is representable and will not
overflow.

Will

--------------------------------------------------------------------------------
Will Crowder, MTS            | "I belong to no organized politcal party.  

INTERACTIVE Systems Corp.    |          -- Will Rogers

Use case a) like intervals, seems to be more intuitive (more "round" numbers).

 unsigned long i,low,high,incr;
        for(i=low;(long)(high-i)>0;i+=incr)

The only restrictions here are: high-low<=LONG_MAX && incr<=LONG_MAX && incr>0

The first restriction can be avoided if you code it as follows:

 unsigned long i,low,high,incr;
        for(i=low;i-high>=incr;i+=incr)

Restriction is now: high-low<=UNSIGNED_LONG_MAX-incr
--

           Stephen R. van den Berg.
"I code it in 5 min, optimize it in 90 min, because it's so well optimized:
it runs in only 5 min.  Actually, most of the time I optimize programs."

I use
        for (p=a; p<a; p++)
Then if my loop also increments p, the loop still terminates.

(Yes, I know my loop _shouldn't_ increment p, but sometimes I
make coding errors.)

My opinions are mine:  I don't speak for any other person or company.

Stan Brown, Oak Road Systems, Cleveland, Ohio, USA    +1 216 371 0043

(Stephen R. van den Berg) writes:
|> >Case a)
|> >   semi-open intervals, like [low,high).
|> >Case b)
|> >   closed intervals, like [low,high].
|> [...]
|>  unsigned long i,low,high,incr;
|>         for(i=low;i-high>=incr;i+=incr)
|>
|> Restriction is now: high-low<=UNSIGNED_LONG_MAX-incr

Since this is a Case a) loop, the restriction can be further
narrowed (by just the value of incr):

  unsigned long i, j, low, high, incr, trip_count;
            ...
            trip_count = (high-low)/incr;
            for (i=low, j=0; j<trip_count; i+=incr, j++) ...

The restrictions are now: high-low <= UNSIGNED_LONG_MAX, incr != 0,
and high >= low.  (These last two conditions are obvious, but should
be bourne in mind anyway.)

Similarly, Case b) can be handled with the same restrictions:

  unsigned long i, j, low, high, incr, trip_count;
            ...
            trip_count = (high-low)/incr;
            i=low; j=0;
            while (1){                  /* loop forever (sort of) */
               ...
               if (j==trip_count) exit; /* exit condition in middle */
               i+=incr; j++;
            }

Note that in Case a) the trip_count variable is actually the number
of times the loop body is executed.  In case b), trip_count is one
less than the number of passes through the loop.

J. Giles

I would guess it would terminate before it ever went into the loop,
so it doesn't matter what the loop does.  8^)

Oh.  Then you meant for (p=0; p<a; p++) ??
--
======= !{sun,psuvax1,bcm,rice,decwrl,cs.utexas.edu}!shell!rjohnson =======
Feel free to correct me, but don't preface your correction with "BZZT!"
Roy Johnson, Shell Development Company