Re: [BUGS] BUG #14722: Segfault in tuplesort_heap_siftup, 32 bit overflow - Mailing list pgsql-bugs

From Tom Lane
Subject Re: [BUGS] BUG #14722: Segfault in tuplesort_heap_siftup, 32 bit overflow
Date
Msg-id 15154.1499878016@sss.pgh.pa.us
Whole thread Raw
In response to Re: [BUGS] BUG #14722: Segfault in tuplesort_heap_siftup, 32 bitoverflow  (Heikki Linnakangas <hlinnaka@iki.fi>)
List pgsql-bugs
Heikki Linnakangas <hlinnaka@iki.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
unsignedinteger      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
exactlyone 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
andN in the unsigned type, then M<=N).  If the sign bit  is      zero,  it shall not affect the resulting value.  If
thesign      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


-- 
Sent via pgsql-bugs mailing list (pgsql-bugs@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-bugs

pgsql-bugs by date:

Previous
From: Heikki Linnakangas
Date:
Subject: Re: [BUGS] BUG #14722: Segfault in tuplesort_heap_siftup, 32 bitoverflow
Next
From: Peter Geoghegan
Date:
Subject: Re: [BUGS] BUG #14722: Segfault in tuplesort_heap_siftup, 32 bit overflow