3 ms·

The problem lies with len-1 underflowing, not the loop that uses the result. For another example, to test congruence of x and y modulo m, you check if (x-y) % m

The problem lies with len-1 underflowing, not the loop that uses the result. For another example, to test congruence of x and y modulo m, you check if (x-y) % m == 0. This also blows up for unsigned integers if y > x unless m is a power of 2. Even iteration is not always over containers or some other structure in a way where the boundaries can be inferred and do not have to be computed, and not always in an order that is implemented by an iterator (for example, some in-place sorting algorithms).

pcwalton 12y ago
Even iteration over explicit ranges of unsigned integers can be handled by a Python range()-style iterator, without the risk of this bug (since the iterator itself is responsible for avoiding this gotcha).
- rbehrends 12y ago
  Only if the language has ONLY iterators that are of the [closed, open) kind of interval. If you have, e.g., Smalltalk/Scala-like to:/to iterators (even if you have also iterators that exclude the upper end), you get the same problem in conjunction with unsigned integers (except that these languages use signed integers, so the problem doesn't show up).
deleted 12y ago
[deleted]
detrino 12y ago
It's a problem with C for loops. There is really no good way to write a counting down loop using a for loop. The fundamental problem is that a for loop is: test a condition, run a loop body, then run a step function. This is suited to counting up loops but when counting down what you want is: test a condition, run a step function, then run a loop body. If you use while loops instead of for loops, you will see the two loops are symmetrical and there is no underflow for unsigned types. See http://ideone.com/1ABiCw http://ideone.com/1ABiCw
- rbehrends 12y ago
  I don't like C for loops, either, but this can happen with other types of for loops, either. E.g. in Pascal: for i := 0 to len-1 do begin ... end This is counting up, not counting down, and len-1 is still going to be either 2^k-1 or result in an error when you're using unsigned integers. While loops also don't fix it (not to mention that they have their own problem, such as forgetting or misplacing the iteration step). The primary issue is that len-1 is underflowing. Yes, you can avoid calculating len-1, but by that token, no error is ever a problem, because they can all be avoided with enough diligence and foresight. In that universe, Heartbleed never happened and the Ariane 5 never blew up. It is, however, not the world we live in.
  - detrino 12y ago
    That's a representation problem. C/C++ use half open ranges and have no problems with unsigned integers. This is also a non-issue in C++ as you have iterators and counting loops are easy to abstract away using counting iterators or <algorithm> style functions.

pcwalton 12y ago

Even iteration over explicit ranges of unsigned integers can be handled by a Python range()-style iterator, without the risk of this bug (since the iterator itself is responsible for avoiding this gotcha).

rbehrends 12y ago
Only if the language has ONLY iterators that are of the [closed, open) kind of interval. If you have, e.g., Smalltalk/Scala-like to:/to iterators (even if you have also iterators that exclude the upper end), you get the same problem in conjunction with unsigned integers (except that these languages use signed integers, so the problem doesn't show up).

deleted 12y ago

[deleted]

detrino 12y ago

It's a problem with C for loops. There is really no good way to write a counting down loop using a for loop. The fundamental problem is that a for loop is: test a condition, run a loop body, then run a step function. This is suited to counting up loops but when counting down what you want is: test a condition, run a step function, then run a loop body. If you use while loops instead of for loops, you will see the two loops are symmetrical and there is no underflow for unsigned types. See http://ideone.com/1ABiCw http://ideone.com/1ABiCw

rbehrends 12y ago
I don't like C for loops, either, but this can happen with other types of for loops, either. E.g. in Pascal: for i := 0 to len-1 do begin ... end This is counting up, not counting down, and len-1 is still going to be either 2^k-1 or result in an error when you're using unsigned integers. While loops also don't fix it (not to mention that they have their own problem, such as forgetting or misplacing the iteration step). The primary issue is that len-1 is underflowing. Yes, you can avoid calculating len-1, but by that token, no error is ever a problem, because they can all be avoided with enough diligence and foresight. In that universe, Heartbleed never happened and the Ariane 5 never blew up. It is, however, not the world we live in.
- detrino 12y ago
  That's a representation problem. C/C++ use half open ranges and have no problems with unsigned integers. This is also a non-issue in C++ as you have iterators and counting loops are easy to abstract away using counting iterators or <algorithm> style functions.