Hacker News Reader

Comment by maxton | Hacker News Reader

That line from the C/C++ "fix" is an atrocity; `low`, `mid`, and `high` should never have been declared as signed integers in the first place, since array indices are never negative. It's unfortunate that in Java there is no other option than to use signed ints.

View on HN

Even with unsigned int (or even size_t), the C/C++ code still doesn't sit well with me. The addition can still overflow, and while unsigned overflow is well-defined, the result here is still nonsense. (i.e., while the result of (low + high) >> 1 during overflow will be well defined, it won't be the midpoint…)

You might argue that you're never going to overflow a size_t on a 64-bit, maybe, but given that the correct code is right there above in the article, it seems easy enough to just do the right thing (add half the delta to the lower bound, which avoids overflow all together for unsigned integer inputs).

With size_t, it would never overflow, even on 32 bits.

The input is an array of int, ints are 4 bytes, 32 bit systems can only address 2^32 bytes, so the array is no more than 2^30 elements long, so in the worst case, low+high equals 2^31-3, less than even a signed it.

It could overflow if we pass it a char* instead but if you have a >2GB array of sorted single bytes, you probably have a problem somewhere else...

For C99, the correct type for an array index is size_t. unsigned int isn't guaranteed to be big enough, while size_t is guaranteed to be large enough for the target architecture.

> size_t is guaranteed to be large enough for the target architecture

I'm not sure if you've misunderstood this (some of the other comments mentioning type certainly have) but size_t being large enough for the purpose of indexing an array is absolutely not the issue. The issue, illustrated by the glibc code pishpash shared, is that a size_t (or any other integer type) is not necessarily large enough to hold the sum of two other variables of the same type without overflowing.

Right, my comment wasn't intended to imply that simply changing the type was a fix for the bug. Just that the best practice is to use size_t for the index types, you still have to perform the calculation in a way that won't overflow.

Here's some code you can compile, it shows the problem:

  #include <stdio.h>
  #include <stdint.h>
  
  int main() {
    printf("size_t bytes: %u\n", sizeof(size_t));
    
    size_t high = SIZE_MAX;
    size_t low = high-1;
    size_t mid_correct = low+(high-low)/2;
    size_t mid_incorrect = (low+high)/2;
    
    printf("low: %.ju\n", low);
    printf("high: %.ju\n", high);
    printf("low+high: %.ju\n", low+high);
    printf("(low+high)/2 -- incorrect: %.ju\n", mid_incorrect);
    printf("low+(high-low)/2 -- correct: %.ju\n", mid_correct);
  }

On my 64-bit machine, I get:

  size_t bytes: 8
  low: 18446744073709551614
  high: 18446744073709551615
  low+high: 18446744073709551613
  (low+high)/2 -- incorrect: 9223372036854775806
  low+(high-low)/2 -- correct: 18446744073709551614

This is a great illustration of the actual bug.

The range of size_t only comes into play if the array can potentially be huge. If the array is small, there may be other considerations. Suppose you have a displaced array with negative indices: p[-2], p[-1], p[0], p[1], ... size_t is good for nothing here.

The unsigned types are generally awful; they have a big discontinuity right at zero, so you have to be careful with arithmetic even if it involves small values.

If I'm working with int and I know that all quantities fit into two decimal digits, then there isn't possibly any problem. Not so with unsigned int or size_t or what have you.

If a, b, c are small integers in a signed type then I know I can rewrite a < b + c as a - c < b, following straight algebraic rules of derivation. Not so if these are unsigned; moving c from the right side to the left may break the inequality because a may be smaller than c.

Agreed completely; the right fix is that anything indexing an array should be an unsigned size_t (or equivalent for your language of choice).

Simply changing to size_t doesn't really fix this bug. You still have to use the low + (high - low) / 2 fix.

If "this bug" is the ability to sort >2^30 elements on a 64-bit machine, this bug IS addressed by changing the index type.

Of course sorting 2^63 elements would require the different calculation.

Pointers are 64-bit on 64-bit machines, and so are the largest unsigned ints, hence the problem. On the other hand, you're probably searching at least 4-byte objects, so your actual list length isn't 64 bits but at most 62 bits even if you filled the memory space.

It doesn't, by itself, fix the bug identified in the article (though it does avoid a memory safety issue). But it's still important. Indexes should never be signed, any more than pointers should.

Why not? Indices are not pointers, so that's a poor argument by itself. Indices are offsets to pointers. If you can see any use for a negative offset off a pointer, that's your negative index use case. A nice example use is implementing IIR filters in a way that looks like the common mathematical form:

    y = a[0]*y[-1] + a[1]*y[-2] + b[0]*x[-1] + b[1]*x[-2]

Reply on news.ycombinator.com