[Cryptography] GCC bug 30475 (was Re: bounded pointers in C)

[Jerry Leichter]

On Apr 25, 2014, at 12:08 AM, Viktor Dukhovni <cryptography at dukhovni.org> wrote:
>> T max = ~(T)0;
>> if (max == 0)
>> {	// 1's complement
>> 	T sign_bit = 1;
>> 	while (sign_bit > 0)
>> 		sign_bit <<= 1;
> 
> Left shift of signed quantities, is undefined and hostile compilers
> are free to do as they please here.
You're half right.  Looking at the final draft of C11 at http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf (one of course has the problem that there are different version so "the standard" around), the actual wording is along the lines of:  If x has a signed integer type, the x << n is define if (as a mathematically correct value) x*2**n is representable in x's type, in which case that's the value; otherwise, the result is undefined.

The actual representation of types has been pinned down somewhat more tightly than in the past.  A signed integer consists of three kinds of bits:  One or more value bits; zero or one sign bits; zero or more padding bits.  The value bits must represent successive powers of two for an overall binary representation of the magnitude.  The sign bit, if present, affects the magnitude to produce one of three encodings:  Sign and magnitude; 1's complement; 2's complement.  The padding bits have no effect on the value.  For each (standard) signed integer type, there's a corresponding unsigned type which has the same size, and for positive values that are representable in the signed type, the representation of that value in the unsigned type must be the same.

C11 does distinguish "bounded undefined behavior" (things like integer overflow) from "critical undefined behaviour" (wild writes to memory), though it's up to an implementation to say whether it maintains the distinction (there's a new macro, __STDC_ANALYZABLE__).  I haven't been able to find the actual defintion of "bounded undefined behavior", though it can certainly trap, perhaps terminating the program.  (But it can't "cause bats to fly out of your nose".)

It's easy to determine the maximum value of an *unsigned* type.  It's not clear to me now that there is any portable way to determine the maximum value of a *signed* type.

One wonders just what possible machine types the C standard was trying to accommodate with that elaborate language.
                                                        -- Jerry