Opened 15 months ago

Last modified 11 months ago

#15350 new bug

gcdExtInteger violates assertion

Reported by: Bodigrim Owned by:
Priority: high Milestone: 8.6.1
Component: Core Libraries Version: 8.6.1
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime crash Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s): Phab:D5042
Wiki Page:

Description (last modified by Bodigrim)

{-# LANGUAGE UnboxedTuples #-}
import GHC.Integer.GMP.Internals

main = let (# _, s #) = gcdExtInteger 2 (2^65 + 1) in print s

fails with

Assertion failed: (sn <= mp_size_abs(xn)), function integer_gmp_gcdext, file libraries/integer-gmp/cbits/wrappers.c, line 316.
Abort trap: 6

It happens because s = -2^64 and does not fit one-limbed BigNat. The implementation of gcdExtInteger x y (https://github.com/ghc/ghc/blob/master/libraries/integer-gmp/src/GHC/Integer/Type.hs#L1392) allocates for s a buffer, equal to size of x (one limb in our case), but according to GMP manual (https://gmplib.org/manual/Number-Theoretic-Functions.html#index-mpz_005fgcdext) it should be equal to size of y (two limbs in our case).

Hopefully, the diff is simple enough for a PR on GitHub (https://github.com/ghc/ghc/pull/163). Otherwise I'll be happy to prepare a patch for Phabricator.

-        s@(MBN# s#) <- newBigNat# (absI# xn#)
+        s@(MBN# s#) <- newBigNat# (absI# yn#)

---

Reopening, because

{-# LANGUAGE UnboxedTuples #-}
import GHC.Integer.GMP.Internals

main = let (# _, s #) = gcdExtInteger (- (2^63 - 1) * 2^63) 0 in print s

fails in GHC 8.6.1 with

Assertion failed: (0 <= gn && gn <= gn0), function integer_gmp_gcdext, file libraries/integer-gmp/cbits/wrappers.c, line 309.
Abort trap: 6

I have not yet understood what is going on.

Change History (11)

comment:1 Changed 15 months ago by Bodigrim

Description: modified (diff)

comment:2 Changed 14 months ago by Ben Gamari <ben@…>

In 7c207c86/ghc:

Fix gcdExtInteger (trac#15350)

comment:3 Changed 14 months ago by Bodigrim

Owner: set to Bodigrim

comment:4 Changed 14 months ago by monoidal

What's the status here? I see that the change was merged, but I don't see a test. I've tried adding a test, but it's still failing with the same error on my machine. Maybe I'm doing something wrong? Is the plan to release a new version of integer-gmp?

diff --git a/testsuite/tests/lib/integer/integerGmpInternals.hs b/testsuite/tests/lib/integer/integerGmpInternals.hs
index c90df5c90d..e1faf900c7 100644
--- a/testsuite/tests/lib/integer/integerGmpInternals.hs
+++ b/testsuite/tests/lib/integer/integerGmpInternals.hs
@@ -86,6 +86,7 @@ main = do
     print $ gcdExtInteger x (-y)
     print $ gcdExtInteger (-x) y
     print $ gcdExtInteger (-x) (-y)
+    print $ gcdExtInteger 2 (2^65 + 1)  -- see Trac #15350
     print $ powInteger 12345 0
     print $ powInteger 12345 1
     print $ powInteger 12345 30

comment:5 Changed 14 months ago by bgamari

Priority: normalhigh

comment:6 Changed 14 months ago by bgamari

Differential Rev(s): Phab:D5042
Status: newpatch

comment:7 Changed 13 months ago by Ben Gamari <ben@…>

In c331592/ghc:

Correct limb length and assertion for gcdExtInteger

Reviewers: hvr, bgamari, monoidal

Reviewed By: monoidal

Subscribers: monoidal, rwbarton, thomie, carter

GHC Trac Issues: #15350

Differential Revision: https://phabricator.haskell.org/D5042

comment:8 Changed 13 months ago by bgamari

Status: patchmerge

comment:9 Changed 13 months ago by bgamari

Resolution: fixed
Status: mergeclosed

comment:10 Changed 11 months ago by Ben Gamari <ben@…>

In 45d5eff/ghc:

Update integer_gmp_gcdext documentation.

Reviewers: hvr, bgamari, monoidal

Reviewed By: monoidal

Subscribers: rwbarton, carter

GHC Trac Issues: #15350

Differential Revision: https://phabricator.haskell.org/D5091

comment:11 in reply to:  description Changed 11 months ago by Bodigrim

Description: modified (diff)
Owner: Bodigrim deleted
Resolution: fixed
Status: closednew
Version: 8.4.38.6.1
Note: See TracTickets for help on using tickets.