The other day a student and I were trying to understand a subtle part of the C standard. Often, the easiest way to clarify this kind of issue is to recognize that compiler writers have already grappled with it — so just write some code and see what various compilers do with it. I wrote this function:
int foo (char x) {
char y = x;
return ++x > y;
}
Since the expression ++x evaluates to the incremented value of x, it is clear that this function should return “1” for most values of x. The question is: What does it compute for CHAR_MAX? One possibility is that the function reliably returns “0” for that input, the other possibility is that ++x is undefined on platforms where char is a signed type. For completeness here’s the test harness that prints foo()’s output for all possible inputs:
int main (void) {
int i;
for (i=CHAR_MIN; i<=CHAR_MAX; i++) {
printf ("%d ", foo(i));
if ((i&31)==31) printf ("\n");
}
return 0;
}
This code only works if char is narrower than int, but I’ve never seen a platform where that is not the case.
The first sign that something odd was going on appeared when I compiled the code using Clang:
regehr@home:~$ clang -O foo.c -o foo
regehr@home:~$ ./foo
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Not cool — the function is supposed to mostly return true. But then I realized that my default Clang was out of date (2.7) so I tried a very recent Clang snapshot (rev 126534):
regehr@home:~$ clang -O0 overflow.c -o overflow
regehr@home:~$ ./overflow
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
regehr@home:~$ clang -O1 overflow.c -o overflow
regehr@home:~$ ./overflow
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
The result (look at the last character) changed when we changed the optimization level — this is OK if incrementing CHAR_MAX is undefined, and is a compiler bug otherwise.
The Intel C compiler (12.0.2 for x86-64) has similar behavior:
[regehr@bethe ~]$ icc -O0 foo.c -o foo
[regehr@bethe ~]$ ./foo
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
[regehr@bethe ~]$ icc -O foo.c -o foo
[regehr@bethe ~]$ ./foo
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
A very recent GCC (rev 170512 for x86) gives a consistent output:
regehr@home:~$ current-gcc -O0 foo.c -o foo
regehr@home:~$ ./foo
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
regehr@home:~$ current-gcc -O2 foo.c -o foo
regehr@home:~$ ./foo
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
However, the story changes if we ask it not to perform function inlining:
regehr@home:~$ current-gcc -O2 -fno-inline foo.c -o foo
regehr@home:~$ ./foo
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
So far, Clang 2.7 appears to be wrong, but all other observed behavior is consistent with ++x being undefined when x is CHAR_MAX. Then I tried CompCert and things took a turn for the worse:
regehr@home:~$ ccomp foo.c -o foo
regehr@home:~$ ./foo
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
This is very odd because CompCert contains a verified version of C’s tricky implicit casts — the exact thing that foo() was designed to test in the first place.
To make a long story short: when the “char” type is narrower than the “int” type and when x has type “signed char” and value CHAR_MAX, ++x is well-defined by both ANSI C and C99. We know that it is well-defined because:
- The standard says: “The expression ++E is equivalent to (E+=1).”
- The standard says: “A compound assignment of the form E1 op= E2 differs from the simple assignment
expression E1 = E1 op (E2) only in that the lvalue E1 is evaluated only once.” - The RHS of the simple assignment expression “E1 op E2” is subject to C’s “usual arithmetic conversions.”
- The usual arithmetic conversions ensure that two operands to a “+” operator of type signed char are both promoted to signed int before the addition is performed.
- When int is wider than char, there is no possibility of the resulting addition overflowing. Thus, the behavior is well-defined and every correct compiler must emit this output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
In other words, to evaluate ++x > y when both variables have type signed char and value CHAR_MAX:
- Signed char 127 is promoted to signed int 127.
- Signed int 127 is incremented to signed int 128.
- Signed int 128 is cast to signed char -128, which is the new value for x and also the value of the subexpression ++x. (Update: As Mans points out in comment #5, the result of this type cast is implementation defined. All common C implementations define the behavior to be truncation of a 2’s complement integer.)
- Signed char -128 is promoted to signed int -128.
- Signed int -128 > signed int 127 is evaluated to 0.
But what about the fact that none of the four compilers I commonly use reliably returns the correct result?
- In GCC the bug is known and has existed for some time.
- In LLVM/Clang the bug was not known but was fixed in less than 24 hours.
- The Intel compiler is wrong too.
- In CompCert there is no bug. However, there is an unfortunate interaction between its definition of “char” to be unsigned and the signed values for CHAR_MIN and CHAR_MAX found in my Linux machine’s limits.h file. Verifying a compiler is an extremely difficult problem and verifying its entire environment (header files, libraries, assemblers, I/O routines, etc.) is pretty much an open problem. This is why we test.
That’s a lot of trouble being caused by a two-line function. C may be a small language, but it’s not a simple one.
[Thanks to Chucky Ellison from UIUC and to Xavier Leroy for helping me puzzle though all this.]
18 responses to “The Little C Function From Hell”
Does the standard say whether or not “char” is “unsigned char” or “signed char”? (I guess not from what you wrote above.)
Assuming not, that means that there are two legal behaviors for this function (when CHAR_MIN and CHAR_MAX are defined in a consistent manner with the choice of unsigned vs signed char)?
Also: what happened that made that zero show up in the middle for compcert?
Hi Robby, Yes, a C implementation may choose whether “char” is signed or unsigned by default. The x86-64 ABI requires it to be signed, but I know of no analogous document for x86.
The function’s output is independent of the signedness of char, so long as char is narrower than int.
The “0” in the middle of CompCert’s output comes from an overflow happening at the wrong place due to the inconsistent header file. It’s easy to reproduce that behavior without the header file problem like so:
#include <stdio.h>
#include <limits.h>
int foo (unsigned char x) {
unsigned char y = x;
return ++x > y;
}
int main (void) {
int i;
for (i=SCHAR_MIN; i<=SCHAR_MAX; i++) {
printf (“%d “, foo(i));
if ((i&31)==31) printf (“\n”);
}
return 0;
}
Oh, I think I see why there’s only one legitimate behavior now.
So CHAR_MAX is really the bit pattern 11111111 and if you use that in a signed context, you just get -1, which is why the 0 appears in the middle for compcert (its just doing the same loop, but offset)? There’s no type information (or maybe the type information is irrelevant because it is being assigned into a signed variable)?
Hi Robby, on common platforms UCHAR_MAX is 0xff and SCHAR_MAX is 0x7f. CHAR_MAX is always defined to be one of these. Type information isn’t quite irrelevant; the rules are actually sort of complicated, see for example here:
http://blog.regehr.org/archives/268
You are missing one detail. In your step 3, signed int 128 is cast to signed char -128, is not defined by the C99 standard.
See section 6.3.1.3: “When a value with integer type is converted to another integer type, […] the new type is signed and the value cannot be represented in it; either the result is implementation-deï¬ned or an implementation-deï¬ned signal is raised.”
The compiler is thus free implement this conversion anyway it pleases, but it must specify what it does. In your example, the end result is the same, the incremented value is not greater than the original. However, if the test is changed to >= an implementation with saturating conversion (as opposed to wrapping) would give a different result.
Thanks Mans, you’re right. I’ll add an update to that part of the post.
Do you know of any modern C implementations where the implementation-defined behavior is anything other than truncating high order bits of a 2’s complement integer? I don’t, but the compilers I use don’t target any really weird architectures.
The “char need not be 8 bits” is another head-scratcher for many. It is a requirement that sizeof(char) = 1, meaning that sizes are multiples of chars, meaning the logical choice for chars is 8 bits, but the standard doesn’t mandate this. Note that sizes being multiples of chars does not mean every object takes up a number of bits that’s a clean multiple of the number of bits in a char…
On platforms where it is not the case that sizeof(int) > sizeof(char), you’d expect that sizeof(char) = sizeof(int) = sizeof(long) = 1, i.e. you cannot address anything smaller than a machine word. I’ve been told such architectures do exist, though I’ve never seen one. It’s nevertheless possible within the standard.
And it’s very true that C is anything but simple. It’s not even simple for compilers, as this post demonstrates. In theory, the places where the standard allows undefined behavior make life simple for the compiler as it can just do “whatever’s most convenient” (and hopefully fastest) and still comply with the standard. In practice, when you throw in optimizations and the more esoteric consequences of the rules, it becomes much harder to verify the compiler is only acting out when it’s allowed to.
So, it seems the issue is the compilers not doing an integer promotion of E in the expression ++E . Another way to express the issue is:
$ cat > bla.c
#include
int main (void)
{
char c = 0;
printf(“%zu %zu\n”, sizeof +c, sizeof ++c);
return 0;
}
$ gcc -Wall bla.c && ./a.out
4 1
$
Without the bug the second value printed should be 4 as well because of the integer promotion. (Note I tested with gcc, icc, clang, and solarisstudio cc and all gave me the same result).
That’s a great example program Olivier (but the formatting got messed up a bit).
Err, my last example was a bad one: ++c is equivalent to c+=1 equivalent to c=c+1 but the result of the assignment is the same type as its left operand.
Argh, you’re right Olivier. I think you’re stuck with my function as the litmus test :).
C is not a small language. It’s not even a language. There are thousands of C languages, mostly alike, but every one slightly different.
I don’t know of a C compiler implementing integer conversions in any other way than simple truncation. Likely deviants would be those on systems not using two’s complement integer representation.
The behaviour of floating-point to integer conversions does vary considerably, even between compilers on the same architecture.
Since the behavior of the signed int to signed char conversion is undefined, it seems legitimate from an optimization standpoint to rewrite “(++x > y)” into “(x + 1 > x)” into “1”.
This is because “x + 1” should always be larger than “x” unless there is an overflow (which leads to undefined behavior).
Hi Joe, the conversion is implementation-defined, not undefined, as described in Section 6.3.1.3 of the C99 standard.
Some processors (mostly signal processing or graphics oriented) saturate on overflow. See fig 687.1 in http://www.knosof.co.uk/cbook/cbook1_2.pdf for an example of why this can be a good idea. Of course implementation-defined allows implementation behavior to depend on the setting of optimization switches.
Hi Derek- I know these processors provide saturating modes, but is this the default overflow behavior for actual C implementations? If so, could you name a couple of implementation that provide this behavior? Thanks!
Hi John,
The StarCore ABI, http://cache.freescale.com/files/soft_dev_tools/doc/ref_manual/STARCORE_ABI_RM.pdf, specifies the behavior of a compiler ‘satuation mode’ option and the FreeScale C compiler (Code Warrior) provides an ‘overflow saturates’ option, http://cache.freescale.com/files/soft_dev_tools/doc/user_guide/SC_COMPILER_USERS_GUIDE.pdf, and saturate=1 is the default option.
I thought the nVidia CUDA C compiler might also support such an option but I cannot find any manual containing the level of detail needed to find out.