3 ms·

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 ta

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

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.

kazinator 9y ago

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.