## C Integer Quiz Rationale

This post is a quick explanation of what my integer quiz was intended to do.

The background is that our Integer Overflow Checker paper is being presented at ICSE this week. One of the things that bothered us when we wrote that paper was that we couldn’t find any concise explanation of C’s integer rules that we could reference. The C99 standard is less than readable. So I started writing up an explanation of C’s promotion rules and that sort of material. But it was boring — so I made a quiz instead.

At first I wanted to make the quiz about pure C, but very quickly it became clear that for practical purposes, no such thing exists. In other words, truly portable C code is so far from C as it actually exists that there’s no point pretending. So I added in (but didn’t word very clearly) the set of implementation-defined behaviors that most of us are used to: those that pertain to common compilers such as Intel CC, GCC, Clang, and many others on x86 and x86-64. I’m not totally sure why so many people missed this part of the instructions, but it seems that some people followed links into the quiz, bypassing this critical bit of information, and others (shockingly) just started answering questions without reading the instructions.

The quiz has two points:

• C programmers need to understand the integer promotion rules and related parts of the C standard. This isn’t because anyone should write the kind of code shown in the quiz, but rather so that we can avoiding writing that kind of code and also so we can understand how other people’s code goes wrong. The IOC paper shows that without tool support, some significant fraction of C programmers do not understand and/or are not capable of following the rules for integer operations. (I’m one of these programmers.)
• C programmers must understand and respect the sharp distinction between implementation-defined behavior and undefined behavior. Implementation-defined behavior can be relied on (for a single compiler, or a collection of compatible compilers) but undefined behavior should never be executed. This material is confusing and people commonly get it wrong. The nastiness of undefined behavior is something that I’ve written about before and also Chris Lattner’s article is a must-read.

I agree with the sentiment expressed in several comments that this quiz serves as something of an indictment of the C language. Integers should not be so difficult. But since we have no realistic story for getting rid of the mountains of C/C++ code that run so many real-world systems, we might as well figure out what to do about it. It’s 2012 and I cannot even think of a language that would be a better choice for implementing a JVM, an OS kernel, or a hypervisor. This is depressing.

There are definitely things the quiz could have done better but overall I’m happy with it. The wide exposure aided by HN and Reddit (more than 50,000 hits as of June 5) hopefully means that some number of programmers who did not previously appreciate these issues now do.

The last issue I wanted to address is especially tricky: the rules for left-shifts of signed numbers in C99. As the quiz tried to make clear, basically any code that left-shifts a signed value will encounter undefined behavior. Now, it so happens that compilers don’t take advantage of this (or at least, I don’t know of any that do). Does that mean that it’s OK to write code that does these undefined operations? Probably not. Signed overflows were reliably compiled to 2’s complement semantics until one day (some years ago) when they no longer were. This broke a lot of code and pissed people off but the compiler writers just pointed to the C standard and effectively said: “Not our problem.” To this day a lot of C programmers (perhaps even a majority of them, if we consider the large number of C programmers who don’t know the language very well) are unaware of the fact that signed overflow is not 2’s complement. Will the compiler developers start to exploit the undefinedness of many left shifts? My guess is that if doing so can increase the performance of at least one important program, they will.

1. Jessie | June 4, 2012 at 7:24 pm | Permalink

“I’m not totally sure why so many people missed this part of the instructions”

Because these instructions disappeared when you clicked “Start”.

When we’re reading the intro, we’re thinking “yeah, yeah, get me to the questions”. It’s not until several questions in that any of that matters, and by then, if you scroll up to the top to see if there’s any other information you need, it’s gone.

2. | June 4, 2012 at 8:08 pm | Permalink

Hi Jessie, it’s true. But as a long-time instructor I’ve come to expect my students to retain instructions between pages of an exam (“please write in complete sentences” etc.) and I feel that it is reasonable to expect the same thing from my readers here.

Maybe this works better in class because the students have time to adjust to my style (“this asshole expects us to read? damn…”) but here all of a sudden 40,000 people show up for the first time.

3. Lee | June 5, 2012 at 12:28 am | Permalink

In the paper:

> A second kind of non-standardization occurs with
> constructs such as INT_MIN%-1 which is…

> However, we are not aware of a C or C++ compiler that
> reliably returns the correct result, zero, for this expression.

Why is it that you don’t consider the gcc / x86 result correct?
I ran three tests, and it yielded 0 as the result for all three.
Do you have either a test program that gcc compiles wrong, or a set of compiler flags for which it gives a non-zero
result to INT_MIN%-1 ?

4. | June 5, 2012 at 9:28 am | Permalink

Hi Lee, I get a floating point exception from both GCC and Clang on multiple platforms at multiple optimization levels. YMMV.

5. | June 5, 2012 at 9:31 am | Permalink

Program here:

http://www.cs.utah.edu/~regehr/int_min.c

How you write the program matters. If you expose the constants to the optimizer (for example by ensuring that foo() gets inlined) then you’ll get 0 (EDIT: from GCC). If the compiler actually generates an idiv, you’ll get the FPE.

You’ll notice, I hope, that this all supports my argument that undefined behavior is hard to deal with. Any time the generated code behaves differently depending on which optimizations fire, we’re in trouble. The situation is exactly the same for signed overflow and certain kinds of null-pointer problems.

6. cokernel_hacker | June 5, 2012 at 11:53 am | Permalink

Hi John,

If you look closely, you will see that clang at -O0 turns the mod with constant operands into undef and does not even give you back zero. It does not fill in eax at all…

7. | June 5, 2012 at 1:57 pm | Permalink

Hi cokernel, sounds right.

Using my test program above, I get FPE from Clang at -O0 and -O1 and integer garbage at -O2 and -O3.

8. Lee | June 5, 2012 at 3:10 pm | Permalink

Hi regehr,
I had written the program ever so slightly differently, and
not gotten the FPE … but I got the FPE with your source code.

My File #1: sneaky_mod_op.c
#include

void set_x_to_min( int *x_p )
{
*x_p = INT_MIN;
}

void sneaky_mod_op( int *x_p, int y )
{
int tmp = *x_p;

*x_p = tmp % y;
}

——————————————————
My file #2: u_vs_i_test.c:
#include

void set_x_to_min( int *x_p );

void sneaky_mod_op( int *x_p, int y );

int main(void)
{
int x;

x = 1U > -1;

printf( “%d\n”, x );

set_x_to_min( &x );

/* below gets optimized away by the compiler… */
x = x % -1;
printf( “x=%d\n”, x );

/* Putting the mod operating in another file to avoid having it
* be optimized out.
*/
sneaky_mod_op( &x, -1 );
printf( “x=%d\n”, x );

return 0;
}

I agree this is a really tricky case. I ran into it while
working the r2k target for sdcc (small device c compiler).
But I had not seen an FP for any of the code I wrote.

9. | June 5, 2012 at 3:19 pm | Permalink

Lee, thanks for the background on this.

I think this same kind of problem is why a lot of people have trouble believing signed overflow isn’t 2’s complement. A lot of compilers, for a lot of overflowing expressions, actually do return the 2’s complement result.

10. Ben L. Titzer | June 5, 2012 at 10:28 pm | Permalink

Hi John, would it be possible to compile a suite of say, a few hundred of these edge cases and at least get compilers to agree on which (surprising) results they should produce? Even though the standard might leave such things unspecified, there is no reason that the big 3 (icc, llvm, and gcc) couldn’t collaborate to define a de-facto standard.

11. reno | June 6, 2012 at 6:21 am | Permalink

1) when the instructor makes a communication “error”, as you did, it is the students who pay the price (having lower grades) so this is not necessarily obvious to the instructor.
2) an instructor who is a “good” communicator doesn’t help his student, because the real tests may not be so clear

12. | June 6, 2012 at 8:10 am | Permalink

Hi Ben, I like that agenda a lot, but don’t believe that it’s possible to get buyin from compiler developers. It’s too much work. C/C++ will die before this gets fixed…

13. | June 6, 2012 at 9:09 am | Permalink

Hi reno, indeed I think about this kind of thing a lot. You have made one excellent point but missed another one. I was going to respond here but it got long, if I can find time I’ll make this into its own post.

14. Lee | June 6, 2012 at 11:46 am | Permalink

Hi Ben,
I think the various C standards have been steadily trying to
spell out these edge cases. For example, in regards to
INT_MIN%-1 mentioned earlier, the C99 standard states
the definition in terms of a/b when a/b is representable.
Since INT_MIN/-1 is not representable (as an int) for two-s
complement, the gcc developers probably consider it undefined.

Generating an FPE for an x86 program running on an OS is considered acceptable for gcc. However, an exception
mechanism is not even present on many embedded systems.
When writing the library function to handle divison
and modulus for a Z80 like processor, I choose to make
even division by zero simply result in zero. That isn’t a
“correct” result in any sense, but I don’t have many options.

15. David Majnemer | June 6, 2012 at 1:55 pm | Permalink

I believe C11 lays question 20 to rest:

N1570
6.5.5p6
“If the quotient a/b is representable, the expression
(a/b)*b + a%b shall equal a; otherwise, the behavior of both a/b and a%b is
undeﬁned.”

http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf

16. | June 6, 2012 at 4:59 pm | Permalink

Speaking as a compiler developer: Your last paragraph is 100% correct. We compiler devs take standards *very* seriously, and are constantly surprised at the fact that nobody else seems to.

@15: David, you’re correct; C11 makes (INT_MIN%-1) undefined behavior.

@14: Lee, you’re incorrect: C99 clause 6.5.5#5 specifically defines (INT_MIN%-1) to yield a result equal to “the remainder … from the division of the first operand by the second”; that is, zero. The language you saw in 6.5.5#6 is simply to work around the fact that the entire expression “(a/b)*b + a%b” is nonsensical if “a/b” itself is unrepresentable!

17. Jessie | June 6, 2012 at 10:40 pm | Permalink

“But as a long-time instructor I’ve come to expect my students to retain instructions between pages of an exam (“please write in complete sentences” etc.)”

There are some pretty significant differences here!

“Please write in complete sentences” is basically common sense. Your students might not be reading those instructions, either, and you’d never know it. You may note that I’m writing in complete sentences here (as are most others) even though your comment form doesn’t have any such instructions!

“Assume C99, LP64, …” is both extremely specific, and doesn’t match what most programmers are using today. Anyone who misses these instructions and tries applying common sense will get “wrong” answers.

Also, I suspect that if all instructions on your paper exams simply disappeared from the test once the student looked at the first question, the compliance rate would likely be a bit lower.