GHC: Ticket #4381: scaleFloat does not handle overflow correctly.
http://ghc.haskell.org/trac/ghc/ticket/4381
<p>
If you call scaleFloat with a somewhat large integer value, the result
correctly overflows and yields Infinity. However, if you call scaleFloat
with an extremely large integer value, the result is finite!
</p>
<pre class="wiki">> scaleFloat 30000 1
Infinity
> scaleFloat (maxBound :: Int) 1
0.5
</pre>en-usGHChttp://ghc.haskell.org/trac/ghc/chrome/site/ghc_logo.png
http://ghc.haskell.org/trac/ghc/ticket/4381
Trac 1.0.9simonpjFri, 08 Oct 2010 16:25:58 GMTcc set
http://ghc.haskell.org/trac/ghc/ticket/4381#comment:1
http://ghc.haskell.org/trac/ghc/ticket/4381#comment:1
<ul>
<li><strong>cc</strong>
<em>daniel.is.fischer@…</em> added
</li>
</ul>
Ticketdaniel.is.fischerFri, 08 Oct 2010 17:54:06 GMTowner set
http://ghc.haskell.org/trac/ghc/ticket/4381#comment:2
http://ghc.haskell.org/trac/ghc/ticket/4381#comment:2
<ul>
<li><strong>owner</strong>
set to <em>daniel.is.fischer</em>
</li>
</ul>
<p>
I can't reproduce precisely that, so I believe it's a 64-bit overflow, <tt>encodeFloat</tt> using 32-bit C-ints:
</p>
<pre class="wiki">Prelude> decodeFloat (1 :: Double)
(4503599627370496,-52)
Prelude Data.Int> fromIntegral ((maxBound :: Int64) - 52) :: Int
-53
</pre><p>
However,
</p>
<pre class="wiki">Prelude Data.Int> scaleFloat minBound 1
Infinity
</pre><p>
and I suspect that would evaluate to 1 on a 64-bit platform.
</p>
<p>
Easy enough to fix, though it'll cost a little speed. Just clamp the scaling factor between say -3000 and +3000.
</p>
Ticketdaniel.is.fischerFri, 08 Oct 2010 20:36:14 GMTstatus changed
http://ghc.haskell.org/trac/ghc/ticket/4381#comment:3
http://ghc.haskell.org/trac/ghc/ticket/4381#comment:3
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>patch</em>
</li>
</ul>
<p>
Sorry that the actual change is buried in so many whitespace changes ;)
</p>
<p>
Validation passed (but boy, that takes long here). Please review and merge if satisfied.
</p>
TicketsimonmarTue, 12 Oct 2010 08:50:33 GMTowner changed
http://ghc.haskell.org/trac/ghc/ticket/4381#comment:4
http://ghc.haskell.org/trac/ghc/ticket/4381#comment:4
<ul>
<li><strong>owner</strong>
changed from <em>daniel.is.fischer</em> to <em>simonmar</em>
</li>
</ul>
<p>
I don't fully understand the patch. Why the magic 2500 value? Why isn't it different for 32 vs. 64 bit, or Float vs. Double? If you could write a short explanation for us non-floating-point-experts I'll drop it into the code as a comment. Thanks!
</p>
Ticketdaniel.is.fischerTue, 12 Oct 2010 11:14:15 GMT
http://ghc.haskell.org/trac/ghc/ticket/4381#comment:5
http://ghc.haskell.org/trac/ghc/ticket/4381#comment:5
<p>
The default implementation is
</p>
<pre class="wiki">scaleFloat k x = encodeFloat m (n+k)
where (m,n) = decodeFloat x
</pre><p>
The second component of decodeFloat lies between (TYP_MIN_EXP - 2*TYP_MANT_DIG) and TYP_MAX_EXP - I don't know the exact implementation of decodeFloat, so the bounds may be inclusive or exclusive. For a nonzero mantissa, encodeFloat returns ±Infinity if the exponent is greater than (TYP_MAX_EXP - 1) and - for a mantissa resulting from decodeFloat - the result is 0 if the exponent is smaller than TYP_MIN_EXP - 2*TYP_MANT_DIG.
</p>
<p>
The exponent is apparently treated as a 32-bit int, thus passing large k to scaleFloat on 64-bit systems leads to overflow and incorrect results even when the (n+k) addition doesn't overflow on the Haskell side. In any case, if (n+k) over- or underflows on the Haskell side, the result is wrong.
</p>
<p>
The solution is to cut off the scale parameter k so that (n+k) doesn't overflow in 32-bit int and that the result of (n + clamp k) is larger than TYP_MAX_EXP if (n+k) is, and smaller than (TYP_MIN_EXP - 2*TYP_MANT_DIGS) if (n+k) is.
</p>
<p>
So the range to which the scale parameter has to be mapped must be at least TYP_MAX_EXP - TYP_MIN_EXP + 2*TYP_MANT_DIGS.
</p>
<p>
For Double, that is 1024 - (-1021) + 2*53 = 2151, for Float it's 301, assuming base-2 IEEE types.
2500 is just an arbitrary magic number large enough for Double and Float.
</p>
<p>
However, I didn't think it through properly, so a) there's the possibility of a platform with different Double and Float types (unlikely, but possible) and worse, b) it won't go through to a newtype around Double/Float with a manual RealFloat instance if the default method for scaleFloat is used.
</p>
<p>
Hence let me do it properly, fixing also the default method and using type specific clamping bounds (I trust GHC will constant-fold the values statically known at compile-time for simple Int-arithmetic).
</p>
Ticketdaniel.is.fischerTue, 12 Oct 2010 13:17:51 GMTattachment set
http://ghc.haskell.org/trac/ghc/ticket/4381
http://ghc.haskell.org/trac/ghc/ticket/4381
<ul>
<li><strong>attachment</strong>
set to <em>scaleFloat.dpatch</em>
</li>
</ul>
<p>
improved patch
</p>
Ticketdaniel.is.fischerTue, 12 Oct 2010 13:26:09 GMT
http://ghc.haskell.org/trac/ghc/ticket/4381#comment:6
http://ghc.haskell.org/trac/ghc/ticket/4381#comment:6
<p>
I've replaced the patch with the improved one.
It will not work for types whose exponent field is 30 bits or more, but those would fail badly with the current code too. long double has a 16-bit exponent, so we have plenty of space beyond that.
</p>
<p>
sh validate is running at the moment, will probably take another hour or so, validating on your boxes should finish before if you start soon ;)
</p>
TicketsimonmarWed, 13 Oct 2010 11:23:12 GMTstatus changed; milestone set
http://ghc.haskell.org/trac/ghc/ticket/4381#comment:7
http://ghc.haskell.org/trac/ghc/ticket/4381#comment:7
<ul>
<li><strong>status</strong>
changed from <em>patch</em> to <em>merge</em>
</li>
<li><strong>milestone</strong>
set to <em>7.0.1</em>
</li>
</ul>
<p>
Applied, thanks:
</p>
<pre class="wiki">Wed Oct 13 11:18:49 BST 2010 Simon Marlow <marlowsd@gmail.com>
* FIX #4381
Fix scaleFloat by clamping the scaling parameter so that
exponent + scale doesn't overflow.
Patch by: Daniel Fischer <daniel.is.fischer@web.de>
</pre>
TicketsimonpjWed, 13 Oct 2010 11:30:44 GMT
http://ghc.haskell.org/trac/ghc/ticket/4381#comment:8
http://ghc.haskell.org/trac/ghc/ticket/4381#comment:8
<p>
Regression test?
</p>
TicketsimonmarWed, 13 Oct 2010 11:43:51 GMT
http://ghc.haskell.org/trac/ghc/ticket/4381#comment:9
http://ghc.haskell.org/trac/ghc/ticket/4381#comment:9
<p>
good point, test to follow.
</p>
TicketiglooWed, 13 Oct 2010 17:17:21 GMTstatus changed; owner deleted
http://ghc.haskell.org/trac/ghc/ticket/4381#comment:10
http://ghc.haskell.org/trac/ghc/ticket/4381#comment:10
<ul>
<li><strong>owner</strong>
<em>simonmar</em> deleted
</li>
<li><strong>status</strong>
changed from <em>merge</em> to <em>new</em>
</li>
</ul>
<p>
Fix merged.
</p>
TicketsimonmarThu, 14 Oct 2010 09:18:20 GMTstatus changed; resolution set
http://ghc.haskell.org/trac/ghc/ticket/4381#comment:11
http://ghc.haskell.org/trac/ghc/ticket/4381#comment:11
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
</ul>
<p>
Test added:
</p>
<pre class="wiki">Wed Oct 13 04:43:31 PDT 2010 Simon Marlow <marlowsd@gmail.com>
* add test for #4381
</pre>
Ticket