Next: , Previous: Integer Overflow Basics, Up: Integer Overflow


12.2.2 Examples of Code Assuming Wraparound Overflow

There has long been a tension between what the C standard requires for signed integer overflow, and what C programs commonly assume. The standard allows aggressive optimizations based on assumptions that overflow never occurs, but many practical C programs rely on overflow wrapping around. These programs do not conform to the standard, but they commonly work in practice because compiler writers are understandably reluctant to implement optimizations that would break many programs, unless perhaps a user specifies aggressive optimization.

The C Standard says that if a program has signed integer overflow its behavior is undefined, and the undefined behavior can even precede the overflow. To take an extreme example:

     if (password == expected_password)
       allow_superuser_privileges ();
     else if (counter++ == INT_MAX)
       abort ();
     else
       printf ("%d password mismatches\n", counter);

If the int variable counter equals INT_MAX, counter++ must overflow and the behavior is undefined, so the C standard allows the compiler to optimize away the test against INT_MAX and the abort call. Worse, if an earlier bug in the program lets the compiler deduce that counter == INT_MAX or that counter previously overflowed, the C standard allows the compiler to optimize away the password test and generate code that allows superuser privileges unconditionally.

Despite this requirement by the standard, it has long been common for C code to assume wraparound arithmetic after signed overflow, and all known practical C implementations support some C idioms that assume wraparound signed arithmetic, even if the idioms do not conform strictly to the standard. If your code looks like the following examples it will almost surely work with real-world compilers.

Here is an example derived from the 7th Edition Unix implementation of atoi (1979-01-10):

     char *p;
     int f, n;
     ...
     while (*p >= '0' && *p <= '9')
       n = n * 10 + *p++ - '0';
     return (f ? -n : n);

Even if the input string is in range, on most modern machines this has signed overflow when computing the most negative integer (the -n overflows) or a value near an extreme integer (the first + overflows).

Here is another example, derived from the 7th Edition implementation of rand (1979-01-10). Here the programmer expects both multiplication and addition to wrap on overflow:

     static long int randx = 1;
     ...
     randx = randx * 1103515245 + 12345;
     return (randx >> 16) & 077777;

In the following example, derived from the GNU C Library 2.5 implementation of mktime (2006-09-09), the code assumes wraparound arithmetic in + to detect signed overflow:

     time_t t, t1, t2;
     int sec_requested, sec_adjustment;
     ...
     t1 = t + sec_requested;
     t2 = t1 + sec_adjustment;
     if (((t1 < t) != (sec_requested < 0))
         | ((t2 < t1) != (sec_adjustment < 0)))
       return -1;

If your code looks like these examples, it is probably safe even though it does not strictly conform to the C standard. This might lead one to believe that one can generally assume wraparound on overflow, but that is not always true, as can be seen in the next section.