6 ms·

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 indic

by maxton 9y ago

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.

JoshTriplett 9y ago
Agreed completely; the right fix is that anything indexing an array should be an unsigned size_t (or equivalent for your language of choice).
- albinofrenchy 9y ago
  Simply changing to size_t doesn't really fix this bug. You still have to use the low + (high - low) / 2 fix.
  - throwaway91111 9y ago
    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.
    - deleted 9y ago
      [deleted]
    - pishpash 9y ago
      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.
  - JoshTriplett 9y ago
    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.
    - boomlinde 9y ago
      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]
SAI_Peregrinus 9y ago
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.
- justin66 9y ago
  > 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.
  - SAI_Peregrinus 9y ago
    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.
- pishpash 9y ago
  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
  - SAI_Peregrinus 9y ago
    This is a great illustration of the actual bug.
deathanatos 9y ago
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).
- GuB-42 9y ago
  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...

by maxton 9y ago

JoshTriplett 9y ago

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

albinofrenchy 9y ago
Simply changing to size_t doesn't really fix this bug. You still have to use the low + (high - low) / 2 fix.
- throwaway91111 9y ago
  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.
  - deleted 9y ago
    [deleted]
  - pishpash 9y ago
    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.
- JoshTriplett 9y ago
  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.
  - boomlinde 9y ago
    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]

SAI_Peregrinus 9y ago

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.

justin66 9y ago
> 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.
- SAI_Peregrinus 9y ago
  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.
pishpash 9y ago
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
- SAI_Peregrinus 9y ago
  This is a great illustration of the actual bug.

deathanatos 9y ago

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

GuB-42 9y ago
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...