autoconf: Signed Overflow Examples
1
1 13.2.2 Examples of Code Assuming Wraparound Overflow
1 ----------------------------------------------------
1
1 There has long been a tension between what the C standard requires for
1 signed integer overflow, and what C programs commonly assume. The
1 standard allows aggressive optimizations based on assumptions that
1 overflow never occurs, but many practical C programs rely on overflow
1 wrapping around. These programs do not conform to the standard, but
1 they commonly work in practice because compiler writers are
1 understandably reluctant to implement optimizations that would break
1 many programs, unless perhaps a user specifies aggressive optimization.
1
1 The C Standard says that if a program has signed integer overflow its
1 behavior is undefined, and the undefined behavior can even precede the
1 overflow. To take an extreme example:
1
1 if (password == expected_password)
1 allow_superuser_privileges ();
1 else if (counter++ == INT_MAX)
1 abort ();
1 else
1 printf ("%d password mismatches\n", counter);
1
1 If the `int' variable `counter' equals `INT_MAX', `counter++' must
1 overflow and the behavior is undefined, so the C standard allows the
1 compiler to optimize away the test against `INT_MAX' and the `abort'
1 call. Worse, if an earlier bug in the program lets the compiler deduce
1 that `counter == INT_MAX' or that `counter' previously overflowed, the
1 C standard allows the compiler to optimize away the password test and
1 generate code that allows superuser privileges unconditionally.
1
1 Despite this requirement by the standard, it has long been common
1 for C code to assume wraparound arithmetic after signed overflow, and
1 all known practical C implementations support some C idioms that assume
1 wraparound signed arithmetic, even if the idioms do not conform
1 strictly to the standard. If your code looks like the following
1 examples it will almost surely work with real-world compilers.
1
1 Here is an example derived from the 7th Edition Unix implementation
1 of `atoi' (1979-01-10):
1
1 char *p;
1 int f, n;
1 ...
1 while (*p >= '0' && *p <= '9')
1 n = n * 10 + *p++ - '0';
1 return (f ? -n : n);
1
1 Even if the input string is in range, on most modern machines this has
1 signed overflow when computing the most negative integer (the `-n'
1 overflows) or a value near an extreme integer (the first `+' overflows).
1
1 Here is another example, derived from the 7th Edition implementation
1 of `rand' (1979-01-10). Here the programmer expects both
1 multiplication and addition to wrap on overflow:
1
1 static long int randx = 1;
1 ...
1 randx = randx * 1103515245 + 12345;
1 return (randx >> 16) & 077777;
1
1 In the following example, derived from the GNU C Library 2.5
1 implementation of `mktime' (2006-09-09), the code assumes wraparound
1 arithmetic in `+' to detect signed overflow:
1
1 time_t t, t1, t2;
1 int sec_requested, sec_adjustment;
1 ...
1 t1 = t + sec_requested;
1 t2 = t1 + sec_adjustment;
1 if (((t1 < t) != (sec_requested < 0))
1 | ((t2 < t1) != (sec_adjustment < 0)))
1 return -1;
1
1 If your code looks like these examples, it is probably safe even
1 though it does not strictly conform to the C standard. This might lead
1 one to believe that one can generally assume wraparound on overflow,
1 but that is not always true, as can be seen in the next section.
1