Re: BUG #14722: Segfault in tuplesort_heap_siftup, 32 bit overflow

Heikki Linnakangas <hlinnaka(at)iki(dot)fi> writes:
> On 07/12/2017 07:14 PM, Tom Lane wrote:
>> Uh ... what assumption? That's certainly true on any twos-complement
>> machine. Besides, if you're worried about hypothetical portability
>> issues, ...

> Right, it's a hypothetical portability issue. The assumption we're
> making is that UINT_MAX >= INT_MAX * 2 + 1. I'm not aware of any system
> where it's not true, but I don't know what the C standards say about that.

Actually, at the top of the loop we have i < n <= INT_MAX, so the
assumption only needs to be UINT_MAX >= INT_MAX * 2 - 1.

My copy of the C99 draft says, among other things

6.2.5 Types

[#6] For each of the signed integer types, there is a
corresponding (but different) unsigned integer type
(designated with the keyword unsigned) that uses the same
amount of storage (including sign information) and has the
same alignment requirements.

[#9] The range of nonnegative values of a signed integer
type is a subrange of the corresponding unsigned integer
type, and the representation of the same value in each type
is the same.

6.2.6.2 Integer types

[#1] For unsigned integer types other than unsigned char,
the bits of the object representation shall be divided into
two groups: value bits and padding bits (there need not be
any of the latter). If there are N value bits, each bit
shall represent a different power of 2 between 1 and 2N-1,
so that objects of that type shall be capable of
representing values from 0 to 2N-1 using a pure binary
representation; this shall be known as the value
representation. The values of any padding bits are
unspecified.37)

[#2] For signed integer types, the bits of the object
representation shall be divided into three groups: value
bits, padding bits, and the sign bit. There need not be any
padding bits; there shall be exactly one sign bit. Each bit
that is a value bit shall have the same value as the same
bit in the object representation of the corresponding
unsigned type (if there are M value bits in the signed type
and N in the unsigned type, then M<=N). If the sign bit is
zero, it shall not affect the resulting value. If the sign
bit is one, then the value shall be modified in one of the
following ways:

-- the corresponding value with sign bit 0 is negated;

-- the sign bit has the value -2N;

-- the sign bit has the value 1-2N.

[#3] The values of any padding bits are unspecified.

Both 6.2.5.9 and 6.2.6.2.2 constrain INT_MAX to be <= UINT_MAX.
In principle, you could have a conforming implementation in which
they were the same, and the sign bit of a signed integer was treated
as a useless padding bit in an unsigned integer. I can't imagine
anyone actually building it that way though; what would be the point?
But as long as there aren't wasted bits in an unsigned int, these
rules require INT_MAX to be <= UINT_MAX/2, AFAICS.

regards, tom lane