-ftrapv reports signed integer overflows on left shift

[nmathewson]

Apparently, C thinks that a left shift of a negative number is undefined behavior. But the donna code does this.

A volunteer contributor to Tor, named "teor", has sent us a patch to fix this issue. We'd like it to go upstream before we merge it, though. You can see the ticket at https://trac.torproject.org/projects/tor/ticket/13538 . This code will need a bit of hacking to go into donna. I'm making this issue as a placeholder.

[agl]

From looking at teor2345/tor@ced74e0, it seems very ugly -- I don't want to merge that I'm afraid.

[nmathewson]

Okay. Would you be amenable in principle to some other approach to avoid left-shifting negative numbers? It is technically undefined, if I'm researching this properly.

[agl]

Yes, it's technically undefined behaviour:

2 The value of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are zero-filled. If E1 has an unsigned type, the value of the result is E1 × 2^E2, reduced modulo one more than the maximum value representable in the result type. Otherwise, if E1 has a signed type and non-negative value, and E1 × 2^E2 is representable in the corresponding unsigned type of the result type, then that value, converted to the result type, is the resulting value; otherwise, the behavior is undefined.

However, it's the result of trying to support non-two's complement machines. That may have made sense in the 1970's but I'm very dubious that we should be paying the cost to support them now. (I'm not sure if they still even exist.)

Rather I'm seeing whether there's support in the standards group for defining this behaviour.

[nmathewson]

Any updates here?

[zackw]

Even if the C committee makes this defined -- and I strongly suspect they won't -- it will be decades before C compilers are all updated to acknowledge the change.

The patch should be merged.

[thestinger]

@agl: You should at least add -fwrapv to CFLAGS as the Linux kernel does to get well-defined two's complement wrapping. Clang and GCC really do break code with signed overflow unless -fwrapv is passed.

[richfelker]

The right way to "left shift a possibly negative number" is to simply write x*(1<<n). It has the exact semantics you want but without the undefined behavior (assuming no overflow). If you also want well-defined behavior on overflow without depending on non-portable compiler extensions you need to convert to an unsigned type and back.