[squeak-dev] Fwd: doesn't Primitive 33 primitiveQuoLargeIntegers relies on C Undefined Behaviour ? uncover a BUG in Primitive 32 primitiveDivLargeIntegers and maybe some others

Nicolas Cellier nicolas.cellier.aka.nice at gmail.com
Wed Aug 29 08:15:47 UTC 2012


2012/8/29 Igor Stasenko <siguctua at gmail.com>:
> On 28 August 2012 23:36, Nicolas Cellier
> <nicolas.cellier.aka.nice at gmail.com> wrote:
>> Sorry to post here, this bounced at vm-dev
>> But I think it's important
>>
>> Nicolas
>>
>>
>> ---------- Forwarded message ----------
>> From: Nicolas Cellier <nicolas.cellier.aka.nice at gmail.com>
>> Date: 2012/8/28
>> Subject: doesn't Primitive 33 primitiveQuoLargeIntegers relies on C
>> Undefined Behaviour ? uncover a BUG in Primitive 32
>> primitiveDivLargeIntegers and maybe some others
>> To: vm-dev-request at lists.squeakfoundation.org
>>
>>
>> (1 << 63) negated is converted to signed long long
>> 0x8000000000000000LL by signed64BitValueOf:
>>
>> So far so good...
>> Then in primitiveQuoLargeIntegers, we will try to take absolute value
>> of this beast...
>>
>> integerRcvr > 0 ifTrue: [
>>                 integerArg > 0
>>                         ifTrue: [result := integerRcvr // integerArg]
>>                         ifFalse: [result := 0 - (integerRcvr // (0 -
>> integerArg))].
>>         ] ifFalse: [
>>                 integerArg > 0
>>                         ifTrue: [result := 0 - ((0 - integerRcvr) //
>> integerArg)]
>>                         ifFalse: [result := (0 - integerRcvr) // (0 -
>> integerArg)].
>>         ].
>>
>> That is translated straightfully in C...
>>
>>     sqLong integerArg;
>>     sqLong integerRcvr;
>>     sqLong result;
>>
>> snip...
>>
>>         if (integerRcvr > 0) {
>>                 if (integerArg > 0) {
>>                         result = integerRcvr / integerArg;
>>                 }
>>                 else {
>>                         result = 0 - (integerRcvr / (0 - integerArg));
>>                 }
>>         }
>>         else {
>>                 if (integerArg > 0) {
>>                         result = 0 - ((0 - integerRcvr) / integerArg);
>>                 }
>>                 else {
>>                         result = (0 - integerRcvr) / (0 - integerArg);
>>                 }
>>         }
>>
>> Isn't this relying on UB? like
>> http://stackoverflow.com/questions/2539178/why-is-abs0x80000000-0x80000000
>> At worse, I would expect 0 -  0x8000000000000000LL to be converted to
>> itself  0x8000000000000000LL...
>> So can someone explain why this works?
>>
>
> i think i know , what is wrong here.
>
> the 'bug' is an arithmetic overflow, because of asymmetry in negative
> and positive value ranges.
>
> to simplify, what happens lets consider we dealing with 8-bit integer values.
> So, a positive range for 8-bit integer is
> 1..127
> but a negative is
> -128 .. -1
>
> mathematically speaking..
>   if value E belongs to [-128 .. 127 ],  we want that for any E a
> following should also hold:
>   (0 - E) belongs to [-128..127]
>
> but apparently it doesn't holds for E = -128.
>
> That means , an expression
>
> x := 0 - y ,
>
> where y is our machine integer may not result in a correct negation,
> but can lead to arithmetic overflow.
>

Yes Igor, exactly, (0 - INT_MIN) is not a thing we should rely on, and
I'm not surprised that it strikes...
What surprised me was why some examples do still work !

When I saw this code, my first idea was to track reliance on Undefined
Behaviour (like the result of integer overflow will be negative and
the like), but then I saw some more serious flaws like (0 - INT_MIN)
and was certain to find a bug, but my first attempts at exhibiting one
miserably and unexpectedly failed...

The fact that we are in presence of UB, with an optimizing compiler
in-between source and machine code is a good recipe for surprise.

Nicolas

>
> --
> Best regards,
> Igor Stasenko.
>


More information about the Squeak-dev mailing list