1

I have stumbled upon a persistent problem, that doesn't seem to have a rational explanation. The problem seems to lie inside a for loop that goes for (i = size - 1; i >= 0; i--) {etc.} where size is the size of a file stored in a memory buffer and i is an unsigned integer. Instead of stopping when i == 0, it wraps around - thus resulting in i = 4294967295 and causing a segmentation fault. Changing the conditional to i > 0 solves the problem.

However, isn't this kind of peculiar? I must be missing some crucial part of how the for loop operates in C. Doesn't it follow this scheme: initialize, check conditional, increment/decrement, check conditional and so on?

Any help is appreciated!

someone
  • 361
  • 2
  • 3
  • 13

4 Answers4

8

An unsigned integer is always >= 0.

for (i = size - 1; i >= 0; i--) {etc.}

is an infinite loop if i is an unsigned int.

ouah
  • 142,963
  • 15
  • 272
  • 331
  • Does that mean when i-- is called with i having value 0 it wraps around itself? – ckv Jul 30 '13 at 10:03
  • @ckv when `i` is `0` the value `i - 1` is equal to `UINT_MAX` which is a positive quantity. – ouah Jul 30 '13 at 10:04
  • So, that's why it doesn't stop. `i` never becomes negative... I'm so stupid some times! :D thank you very much!!! – someone Jul 30 '13 at 11:54
2

Let's see what happens when i approaches 0.

  • i == 1: loop executes normally since i >= 0. Subtract 1 from i. Now i contains 0.
  • i == 0: loop executes normally since i >= 0. Subtract 1 from i. Because i is unsigned, it will wrap around. Thus, i now contains 4294967295.
  • i == 4294967295: loop executes normally since i >= 0
  • and so on ...

The solution is to either test for something else (such as i > 0, like your example) or to increase i with every iteration and loop while it is smaller than the size of the file.

Alan
  • 929
  • 6
  • 10
  • Doesn't it first do the increment/decrement operation and then check? Because at a normal for-loop (i.e. `i++`), when the conditional is `i <= size` the last iteration is for `i == size`, and on exit `i == size + 1`. – someone Jul 30 '13 at 11:59
  • Angel: correct, but this is not relevant for my explanation as a condition-check is always followed by a decrement and a decrement is always followed by a condition-check (if we conveniently forget the loop body). – Alan Jul 30 '13 at 23:16
  • Yes, the fact is that I stupidly checked the wrong thing! You're right, it wraps around as it can't become negative and goes infinite... I fixed it, by changing it to: `for (i = size - 1; i < size; i--)`. There will never be a problem in my case, because `size` is always much less than UINT_MAX! :D – someone Jul 31 '13 at 16:47
1

According to the C99 standard:

6.2.5 Types

9) [...] A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type.

So, here's what happens in your case:

  • i == 1, therefore i-- results in i == 0.
  • i == 0, therefore i-- results in a wrap-around and i == UINT_MAX.
  • i == UINT_MAX, therefore i-- results in i == UINT_MAX - 1 and so on.

One way of fixing your loop is by using the following (https://stackoverflow.com/a/665773/676939):

for (i = size; i-- > 0;){
    /* yada yada yada */
}

Another way of doing the same is the following (https://stackoverflow.com/a/665758/676939):

unsigned fake_i;
for (fake_i = size; fake_i > 0; i--){
    unsigned i = fake_i - 1;
    /* Do something with i */
}
Community
  • 1
  • 1
Alexandros
  • 3,044
  • 1
  • 23
  • 37
1

In unsigned types the most significant bit is not treated as a sign bit. In your case unsigned int has 4bytes(32 bits).

So, when you're decrementing '0', the way it is done is 2's complement of 1 is added to 0. Which is 4294967295 and is the maximum value which is nothing but when all 32 bits are 1. Hence the result 4294967295.

While incrementing from the maximum value 4294967295( i.e. when all 32 bits are 1's) Incrementing this gives all the lower 32 bits with 0's and the 32nd bit with one. So, there is an overflow to the 32nd bit which is out of the range of 4bytes for unsigned int. Hence the value becomes 0.

In general for unsigned types there is a wrap around from 0....MaxValue. When incrementing above MaxValue you re-enter from 0. When decrementing below 0 you re-enter from MaxValue.

Uchia Itachi
  • 5,287
  • 2
  • 23
  • 26