Careful "for" Loops
Author Message Careful "for" Loops

I'm using unsigned long (32 bits here), to limit problems of overflow,
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

Sun, 05 Sep 1993 01:41:11 GMT  Careful "for" Loops

Quote:
(Tim McDaniel) writes:
>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.
>... Zero-length ranges are a possibility.

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)

Sun, 05 Sep 1993 03:45:19 GMT  Careful "for" Loops

Quote:

>1) How do you code a "for" loop to avoid overflow gotchas?

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

Mon, 06 Sep 1993 05:25:03 GMT  Careful "for" Loops

|> >1) How do you code a "for" loop to avoid overflow gotchas?
|>
|> (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;
int *p, *q;

/* point q and at end a */

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

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

Quote:
}

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

Will

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

INTERACTIVE Systems Corp.    |          -- Will Rogers

Tue, 07 Sep 1993 02:18:07 GMT  Careful "for" Loops

Quote:
Tim McDaniel writes:
>Case a)
>   semi-open intervals, like [low,high).
>Case b)
>   closed intervals, like [low,high].

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

Quote:
>1) How do you code a "for" loop to avoid overflow gotchas?

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

Sat, 11 Sep 1993 00:24:09 GMT  Careful "for" Loops

Quote:

> 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;
>    int *p, *q;

>    /* point q and at end a */

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

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

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

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

Sat, 11 Sep 1993 01:16:47 GMT  Careful "for" Loops

(Stephen R. van den Berg) writes:
Quote:
|> Tim McDaniel 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

Sat, 11 Sep 1993 02:43:48 GMT  Careful "for" Loops

Quote:

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

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

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

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

Sun, 12 Sep 1993 04:37:35 GMT

 Page 1 of 1 [ 8 post ]

Relevant Pages