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

Jerry Leichter leichter at lrw.com
Thu May 1 12:38:42 EDT 2014


On May 1, 2014, at 11:26 AM, Bill Frantz <frantz at pwpconsult.com> wrote:
> 
> As I see it, the C language standards need to move some of the "undefined" behaviors into a different category, lets call it "target machine defined".
The C Standards, from the very first, have had two categories here:  "Implementation Defined" and "Undefined".  "Implementation Defined" means that each implementation makes its own choice, but nominally it has to document it.  The size of an int is an example of an "Implementation Defined" property.  "Undefined" properties are ... undefined.  The reason overflow handling is Undefined, rather than Implementation Defined, is that it *might* cause a trap - and there is no such concept in the C Standard.  What happens next depends on the OS, the library, the surrounding environment ... there's really no way to pin it down.

Not that *nothing says that a particular implementation can't choose to define what happens in the case of an integer overflow*.  If you're working with such an implementation, you can write your code based on that definition.  But your code is still non-portable.

> If I understand correctly, the C standard assumes that arithmetic will be performed in one of three ways, depending on the underlying hardware architecture.
No.  It allows three mappings from a set of bits to a mathematical value.  Those arithmetic operations that "don't overflow" produce sets of bits whose value, interpreted as given by the implementation, is the correct mathematical result. Otherwise, the result is undefined.

> Optimization should remove tests like if (x > x+1) only if that statement is always true in the target architecture. If the compiler doesn't know the target architecture, then it should assure the test is true in the three possible target architectures as well as standard, unlimited size, arithmetic.
The compiler always knows the target architecture.  But that result of an expression like x > x + 1 is undefined if x + 1 overflows.  Again, it might trap.

> These well defined forms of arithmetic seem to be quite different from other "undefined" operations like addressing outside the bounds of an array.
But the C Standard deliberately does *not* assume well-defined forms of arithmetic - because some hardware can't guarantee it.

A classic - now very, very dated - example of the complexities:  The CDC 6000 series had 60-bit registers.  Integer addition and subtraction operated on the the full 60 bits.  Integer multiplication only operated on the bottom 48 bits.  So now what does "overflow" mean?  You could decide that in is really 48 bits, artificially cap each addition or subtraction at 48 bits - some extra execution cost, some loss in useful functionality; or you could do a software implementation of a 60-bit multiply - *very* big execution cost.

The hardware had no integer divide instruction.  The usual approach was to convert the integer to float, divide, then convert back.  This also limited the effective size of an integer participant in a divide to the mantissa size of a double - which was also 48 bits.  (In fact, the 48 bit limit for integer multiplication came from the hardware re-using the FP multiply unit to do integer multiplies.)

(Oh, and to break two other assumptions that people often make about the C execution model:  Pointers were 18 bits, but pointed to a word, not a byte.  The hardware itself had no representation for a pointer to anything smaller than a word.)
                                                        -- Jerry

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4813 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140501/34e5f7ff/attachment.bin>


More information about the cryptography mailing list