Fwd: doesn't Primitive 33 primitiveQuoLargeIntegers relies on C Undefined Behaviour ? uncover a BUG in Primitive 32 primitiveDivLargeIntegers and maybe some others
Locked
Fwd: doesn't Primitive 33 primitiveQuoLargeIntegers relies on C Undefined Behaviour ? uncover a BUG in Primitive 32 primitiveDivLargeIntegers and maybe some others
 
|
Sorry to post here, this bounced at vm-dev
But I think it's important Nicolas ---------- Forwarded message ---------- From: Nicolas Cellier <[hidden email]> 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: [hidden email] (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? ((1 << 63) negated quo: 2) = (1 << 62) negated I guess it must be some compiler optimization, like: 0 - (0-a)/b -> 0 - (0/b-a/b) -> a/b But then, why doing the sign checks at all? Isn't it just result = integerRcvr / integerArg; whatever the signs? Maybe the compiler is able to just do that, but it sounds like obfuscation... Anyway, that won't work in primitiveDivLargeIntegers, i would expect: ((1 << 63) negated // -2) = (1 << 62) But I get ((1 << 63) negated // -2) = (1 << 62) negated Ah Ah, it looks like a bug this time, no Compiler optimization did save us We have several solutions... - let signed64BitValueOf: (1 << 63) negated fail - protect each and every negation of those - perform most arithmetic with unsigned, handle sign separately Nicolas |
Re: doesn't Primitive 33 primitiveQuoLargeIntegers relies on C Undefined Behaviour ? uncover a BUG in Primitive 32 primitiveDivLargeIntegers and maybe some others
|
|
Do you want an other one ?
Try (1 << 63) negated / -1 for fun Nicolas 2012/8/28 Nicolas Cellier <[hidden email]>: > Sorry to post here, this bounced at vm-dev > But I think it's important > > Nicolas > > > ---------- Forwarded message ---------- > From: Nicolas Cellier <[hidden email]> > 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: [hidden email] > > > (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? > > ((1 << 63) negated quo: 2) = (1 << 62) negated > > I guess it must be some compiler optimization, like: > > 0 - (0-a)/b -> 0 - (0/b-a/b) -> a/b > > But then, why doing the sign checks at all? > Isn't it just result = integerRcvr / integerArg; whatever the signs? > > Maybe the compiler is able to just do that, but it sounds like obfuscation... > > Anyway, that won't work in primitiveDivLargeIntegers, i would expect: > ((1 << 63) negated // -2) = (1 << 62) > But I get > ((1 << 63) negated // -2) = (1 << 62) negated > > Ah Ah, it looks like a bug this time, no Compiler optimization did save us > > We have several solutions... > - let signed64BitValueOf: (1 << 63) negated fail > - protect each and every negation of those > - perform most arithmetic with unsigned, handle sign separately > > Nicolas |
Re: doesn't Primitive 33 primitiveQuoLargeIntegers relies on C Undefined Behaviour ? uncover a BUG in Primitive 32 primitiveDivLargeIntegers and maybe some others
|
|
And of course a cousin
((1 << 63) negated * -1) 2012/8/29 Nicolas Cellier <[hidden email]>: > Do you want an other one ? > > Try > (1 << 63) negated / -1 > for fun > > Nicolas > > 2012/8/28 Nicolas Cellier <[hidden email]>: >> Sorry to post here, this bounced at vm-dev >> But I think it's important >> >> Nicolas >> >> >> ---------- Forwarded message ---------- >> From: Nicolas Cellier <[hidden email]> >> 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: [hidden email] >> >> >> (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? >> >> ((1 << 63) negated quo: 2) = (1 << 62) negated >> >> I guess it must be some compiler optimization, like: >> >> 0 - (0-a)/b -> 0 - (0/b-a/b) -> a/b >> >> But then, why doing the sign checks at all? >> Isn't it just result = integerRcvr / integerArg; whatever the signs? >> >> Maybe the compiler is able to just do that, but it sounds like obfuscation... >> >> Anyway, that won't work in primitiveDivLargeIntegers, i would expect: >> ((1 << 63) negated // -2) = (1 << 62) >> But I get >> ((1 << 63) negated // -2) = (1 << 62) negated >> >> Ah Ah, it looks like a bug this time, no Compiler optimization did save us >> >> We have several solutions... >> - let signed64BitValueOf: (1 << 63) negated fail >> - protect each and every negation of those >> - perform most arithmetic with unsigned, handle sign separately >> >> Nicolas |
Re: Fwd: doesn't Primitive 33 primitiveQuoLargeIntegers relies on C Undefined Behaviour ? uncover a BUG in Primitive 32 primitiveDivLargeIntegers and maybe some others
|
|
In reply to this post by Nicolas Cellier
On 28 August 2012 23:36, Nicolas Cellier
<[hidden email]> wrote: > Sorry to post here, this bounced at vm-dev > But I think it's important > > Nicolas > > > ---------- Forwarded message ---------- > From: Nicolas Cellier <[hidden email]> > 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: [hidden email] > > > (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. -- Best regards, Igor Stasenko. |
Re: Fwd: doesn't Primitive 33 primitiveQuoLargeIntegers relies on C Undefined Behaviour ? uncover a BUG in Primitive 32 primitiveDivLargeIntegers and maybe some others
|
|
In reply to this post by Nicolas Cellier
When I try your examples using a VM compiled in 64-bit mode, the VM crashes.
(1 << 63) negated / -1 ==> crash So there is a problem in the primitive. Dave On Tue, Aug 28, 2012 at 11:36:43PM +0200, Nicolas Cellier wrote: > Sorry to post here, this bounced at vm-dev > But I think it's important > > Nicolas > > > ---------- Forwarded message ---------- > From: Nicolas Cellier <[hidden email]> > 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: [hidden email] > > > (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? > > ((1 << 63) negated quo: 2) = (1 << 62) negated > > I guess it must be some compiler optimization, like: > > 0 - (0-a)/b -> 0 - (0/b-a/b) -> a/b > > But then, why doing the sign checks at all? > Isn't it just result = integerRcvr / integerArg; whatever the signs? > > Maybe the compiler is able to just do that, but it sounds like obfuscation... > > Anyway, that won't work in primitiveDivLargeIntegers, i would expect: > ((1 << 63) negated // -2) = (1 << 62) > But I get > ((1 << 63) negated // -2) = (1 << 62) negated > > Ah Ah, it looks like a bug this time, no Compiler optimization did save us > > We have several solutions... > - let signed64BitValueOf: (1 << 63) negated fail > - protect each and every negation of those > - perform most arithmetic with unsigned, handle sign separately > > Nicolas |
Re: Fwd: doesn't Primitive 33 primitiveQuoLargeIntegers relies on C Undefined Behaviour ? uncover a BUG in Primitive 32 primitiveDivLargeIntegers and maybe some others
|
|
In reply to this post by Igor Stasenko
2012/8/29 Igor Stasenko <[hidden email]>:
> On 28 August 2012 23:36, Nicolas Cellier > <[hidden email]> wrote: >> Sorry to post here, this bounced at vm-dev >> But I think it's important >> >> Nicolas >> >> >> ---------- Forwarded message ---------- >> From: Nicolas Cellier <[hidden email]> >> 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: [hidden email] >> >> >> (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. > |
«
Return to Squeak - Dev
|
1 view|%1 views
| Free forum by Nabble | Edit this page |