toofishes.net

C, unsigned integers, and the infinite for loop

Posted July 19, 2011 at 5:17 a.m.

Take a close look at the two snippets below. If you can see what is wrong in the first one, you either 1) paid attention to the blog article title or 2) have likely been burned by this before.

Incorrect

size_t i;
alpm_filelist_t *filelist = alpm_pkg_get_files(pkg);
/* iterate through the list backwards, unlinking files */
for(i = filelist->count - 1; i >= 0; i--) {
    alpm_file_t *file = filelist->files + i;
    unlink_file(file);
}

Correct

size_t i;
alpm_filelist_t *filelist = alpm_pkg_get_files(pkg);
/* iterate through the list backwards, unlinking files */
for(i = filelist->count; i > 0; i--) {
    alpm_file_t *file = filelist->files + i - 1;
    unlink_file(file);
}

What we see here is a classic case of a unsigned variable combined with an optimizing C compiler. Unfortunately in this case warnings are not emitted and a few vocal WTFs and inline printf calls ensued before I realized exactly what was happening.

In the incorrect code, the i >= 0 loop test might as well not even be there, as size_t is defined as an unsigned integer. That results in 0--, yielding some very large integer value, which is of course greater than zero.

The correct code ensures our iteration loop variable never takes a value "below" zero by virtue of moving the minus one offset around. Keep this in mind anytime you are iterating an array backwards (the easiest place to fall into this trap)- if your loop variable is unsigned, letting it go past zero is a definite no-no.

C pacman

Comments (6)

Augusute Pop on July 19, 2011 at 8:36 a.m.:

what about this one?
for (i = filelist->count - 1; i < filelist->count; i--)

Tamas on July 19, 2011 at 9:48 a.m.:

Actually, gcc with the option -Wextra do emit a warning for this code.

Dan McGee on July 19, 2011 at 10:12 a.m.:

@Augusute: That is clever, but totally hard to comprehend what is going on at quick glance. Depending on wraparound is usually just as bad as forgetting it happens.

cactus on July 19, 2011 at 11:36 a.m.:

> Depending on wraparound is usually just as bad as forgetting it happens.

That is _so_ quotable. :P

Auguste Pop on July 21, 2011 at 9:11 p.m.:

@Tamas, I compiled my code with -Wall -Wextra -Wfloat-equal -Wmissing-declarations -Wmissing-prototypes -Wstrict-prototypes -Wdouble-promotion -Winit-self -Wpointer-arith -Wformat-security -march=native -mtune=native -pipe -O3 -Wstrict-prototypes, and no warning emitted. Which version of gcc are you using?

Anyway, i think the trick is not important. What's important is we should never forget the pitfall of unsigned integers. Every decent programmer can come up with a solution as long as he/she remembers to do so.

In really life, I often assume that a size_t variable larger than INT_MAX should not be looped, and thus blindly define the loop variable i as int. That's very very wrong. I know. ;P

Lukas Fleischer on July 24, 2011 at 9:09 a.m.:

Some other suggestions:

* "for(i = filelist->count; i-- > 0;)"

* Use a do-while loop instead.

C, unsigned integers, and the infinite for loop

Posted July 19, 2011 at 5:17 a.m.

Similar Posts

Comments (6)