Dont use big/small-int primops on IL32P64 (i.e. Win/x86_64) for now
[ghc.git] / libraries / integer-gmp / GHC / Integer / Type.lhs
1 \begin{code}
2 {-# LANGUAGE BangPatterns, CPP, UnboxedTuples, UnliftedFFITypes, MagicHash, NoImplicitPrelude #-}
3 {-# OPTIONS_HADDOCK hide #-}
4
5 -- Commentary of Integer library is located on the wiki:
6 -- http://ghc.haskell.org/trac/ghc/wiki/Commentary/Libraries/Integer
7 --
8 -- It gives an in-depth description of implementation details and
9 -- decisions.
10 --
11 -- TODO: Try to use optimized big/small int primops on IL32P64 archs
12 -- (mostly Windows/x86_64). Currently, we have to fall back to
13 -- unoptimized code-paths for most big/small-int primops, due to
14 -- @mpz_*()@ functions using @long@ types, which is smaller than
15 -- @mp_limb_t@ on IL32P64. The @mpn_*()@ functions are often safe to
16 -- use, as they use @mb_limb_t@ instead of @long@.
17 -- (look out for @#if SIZEOF_HSWORD == SIZEOF_LONG@ occurences)
18 --
19
20 #include "MachDeps.h"
21 #if SIZEOF_HSWORD == 4
22 #define INT_MINBOUND (-2147483648#)
23 #define NEG_INT_MINBOUND (S# 2147483647# `plusInteger` S# 1#)
24 #elif SIZEOF_HSWORD == 8
25 #define INT_MINBOUND (-9223372036854775808#)
26 #define NEG_INT_MINBOUND (S# 9223372036854775807# `plusInteger` S# 1#)
27 #else
28 #error Unknown SIZEOF_HSWORD; can't define INT_MINBOUND and NEG_INT_MINBOUND
29 #endif
30
31 module GHC.Integer.Type where
32
33 import GHC.Prim (
34     -- Other types we use, convert from, or convert to
35     Int#, Word#, Double#, Float#, ByteArray#, MutableByteArray#, Addr#, State#,
36     indexIntArray#,
37     -- Conversions between those types
38     int2Word#, int2Double#, int2Float#, word2Int#,
39     -- Operations on Int# that we use for operations on S#
40     quotInt#, remInt#, quotRemInt#, negateInt#,
41     (*#), (-#),
42     (==#), (/=#), (<=#), (>=#), (<#), (>#),
43     mulIntMayOflo#, addIntC#, subIntC#,
44     and#, or#, xor#,
45  )
46
47 import GHC.Integer.GMP.Prim (
48     -- GMP-related primitives
49     MPZ#,
50     cmpInteger#, cmpIntegerInt#,
51     plusInteger#, minusInteger#,
52     timesInteger#,
53     quotRemInteger#, quotInteger#, remInteger#,
54     divModInteger#, divInteger#, modInteger#,
55     divExactInteger#,
56     gcdInteger#, gcdExtInteger#, gcdIntegerInt#, gcdInt#,
57     decodeDouble#,
58     int2Integer#, integer2Int#, word2Integer#, integer2Word#,
59     andInteger#, orInteger#, xorInteger#, complementInteger#,
60     testBitInteger#, mul2ExpInteger#, fdivQ2ExpInteger#,
61     powInteger#, powModInteger#, powModSecInteger#, recipModInteger#,
62     nextPrimeInteger#, testPrimeInteger#,
63     sizeInBaseInteger#,
64     importIntegerFromByteArray#, importIntegerFromAddr#,
65     exportIntegerToMutableByteArray#, exportIntegerToAddr#,
66
67 #if SIZEOF_HSWORD == SIZEOF_LONG
68     plusIntegerInt#, minusIntegerInt#,
69     timesIntegerInt#,
70     divIntegerWord#, modIntegerWord#, divModIntegerWord#,
71     divExactIntegerWord#,
72     quotIntegerWord#, remIntegerWord#, quotRemIntegerWord#,
73 #endif
74
75 #if WORD_SIZE_IN_BITS < 64
76     int64ToInteger#,  integerToInt64#,
77     word64ToInteger#, integerToWord64#,
78 #endif
79  )
80
81 #if WORD_SIZE_IN_BITS < 64
82 import GHC.IntWord64 (
83             Int64#, Word64#,
84             int64ToWord64#, intToInt64#,
85             int64ToInt#, word64ToInt64#,
86             geInt64#, leInt64#, leWord64#,
87        )
88 #endif
89
90 import GHC.Classes
91 import GHC.Types
92
93 default ()
94 \end{code}
95
96 %*********************************************************
97 %*                                                      *
98 \subsection{The @Integer@ type}
99 %*                                                      *
100 %*********************************************************
101
102 Convenient boxed Integer PrimOps.
103
104 \begin{code}
105 -- | Arbitrary-precision integers.
106 data Integer
107    = S# Int#                            -- small integers
108    | J# Int# ByteArray#                 -- large integers
109
110 mkInteger :: Bool   -- non-negative?
111           -> [Int]  -- absolute value in 31 bit chunks, least significant first
112                     -- ideally these would be Words rather than Ints, but
113                     -- we don't have Word available at the moment.
114           -> Integer
115 mkInteger nonNegative is = let abs = f is
116                            in if nonNegative then abs else negateInteger abs
117     where f [] = S# 0#
118           f (I# i : is') = S# i `orInteger` shiftLInteger (f is') 31#
119
120 {-# NOINLINE smallInteger #-}
121 smallInteger :: Int# -> Integer
122 smallInteger i = S# i
123
124 {-# NOINLINE wordToInteger #-}
125 wordToInteger :: Word# -> Integer
126 wordToInteger w = if isTrue# (i >=# 0#)
127                   then S# i
128                   else case word2Integer# w of (# s, d #) -> J# s d
129     where
130       !i = word2Int# w
131
132 {-# NOINLINE integerToWord #-}
133 integerToWord :: Integer -> Word#
134 integerToWord (S# i) = int2Word# i
135 integerToWord (J# s d) = integer2Word# s d
136
137 #if WORD_SIZE_IN_BITS < 64
138 {-# NOINLINE integerToWord64 #-}
139 integerToWord64 :: Integer -> Word64#
140 integerToWord64 (S# i) = int64ToWord64# (intToInt64# i)
141 integerToWord64 (J# s d) = integerToWord64# s d
142
143 {-# NOINLINE word64ToInteger #-}
144 word64ToInteger :: Word64# -> Integer
145 word64ToInteger w = if isTrue# (w `leWord64#` int64ToWord64# (intToInt64# 0x7FFFFFFF#))
146                     then S# (int64ToInt# (word64ToInt64# w))
147                     else case word64ToInteger# w of
148                          (# s, d #) -> J# s d
149
150 {-# NOINLINE integerToInt64 #-}
151 integerToInt64 :: Integer -> Int64#
152 integerToInt64 (S# i) = intToInt64# i
153 integerToInt64 (J# s d) = integerToInt64# s d
154
155 {-# NOINLINE int64ToInteger #-}
156 int64ToInteger :: Int64# -> Integer
157 int64ToInteger i = if isTrue# (i `leInt64#` intToInt64# 0x7FFFFFFF#) &&
158                       isTrue# (i `geInt64#` intToInt64# -0x80000000#)
159                    then smallInteger (int64ToInt# i)
160                    else case int64ToInteger# i of
161                         (# s, d #) -> J# s d
162 #endif
163
164 integerToInt :: Integer -> Int#
165 {-# NOINLINE integerToInt #-}
166 integerToInt (S# i)   = i
167 integerToInt (J# s d) = integer2Int# s d
168
169 -- This manually floated out constant is needed as GHC doesn't do it on its own
170 minIntAsBig :: Integer
171 minIntAsBig = case int2Integer# INT_MINBOUND of { (# s, d #) -> J# s d }
172
173 -- | Promote 'S#' to 'J#'
174 toBig :: Integer -> Integer
175 toBig (S# i)     = case int2Integer# i of { (# s, d #) -> J# s d }
176 toBig i@(J# _ _) = i
177
178 -- | Demote 'J#' to 'S#' if possible. See also 'smartJ#'.
179 toSmall :: Integer -> Integer
180 toSmall i@(S# _)    = i
181 toSmall (J# s# mb#) = smartJ# s# mb#
182
183
184 -- | Smart 'J#' constructor which tries to construct 'S#' if possible
185 smartJ# :: Int# -> ByteArray# -> Integer
186 smartJ# 0# _ = S# 0#
187 smartJ# 1# mb#  | isTrue# (v ># 0#) = S# v
188     where
189       v = indexIntArray# mb# 0#
190 smartJ# (-1#) mb# | isTrue# (v <# 0#) = S# v
191     where
192       v = negateInt# (indexIntArray# mb# 0#)
193 smartJ# s# mb# = J# s# mb#
194
195 -- |Construct 'Integer' out of a 'MPZ#' as returned by GMP wrapper primops
196 --
197 -- IMPORTANT: The 'ByteArray#' element MUST NOT be accessed unless the
198 -- size-element indicates more than one limb!
199 --
200 -- See notes at definition site of 'MPZ#' in "GHC.Integer.GMP.Prim"
201 -- for more details.
202 mpzToInteger :: MPZ# -> Integer
203 mpzToInteger (# 0#, _, _ #) = S# 0#
204 mpzToInteger (# 1#, _, w# #) | isTrue# (v# >=# 0#) = S# v#
205                              | True = case word2Integer# w# of (# _, d #) -> J# 1# d
206     where
207       v# = word2Int# w#
208 mpzToInteger (# -1#, _, w# #) | isTrue# (v# <=# 0#) = S# v#
209                               | True = case word2Integer# w# of (# _, d #) -> J# -1# d
210     where
211       v# = negateInt# (word2Int# w#)
212 mpzToInteger (# s#, mb#, _ #) = J# s# mb#
213
214 -- | Variant of 'mpzToInteger' for pairs of 'Integer's
215 mpzToInteger2 :: (# MPZ#, MPZ# #) -> (# Integer, Integer #)
216 mpzToInteger2 (# mpz1, mpz2 #) = (# i1, i2 #)
217     where
218       !i1 = mpzToInteger mpz1 -- This use of `!` avoids creating thunks,
219       !i2 = mpzToInteger mpz2 -- see also Note [Use S# if possible].
220
221 -- |Negate MPZ#
222 mpzNeg :: MPZ# -> MPZ#
223 mpzNeg (# s#, mb#, w# #) = (# negateInt# s#, mb#, w# #)
224
225 \end{code}
226
227 Note [Use S# if possible]
228 ~~~~~~~~~~~~~~~~~~~~~~~~~
229 It's a big win to use S#, rather than J#, whenever possible.  Not only
230 does it take less space, but (probably more important) subsequent
231 operations are more efficient. See Trac #8638.
232
233 'smartJ#' is the smart constructor for J# that performs the necessary
234 tests.  When returning a nested result, we always use smartJ# strictly,
235 thus
236        let !r = smartJ# a b in (# r, somthing_else #)
237 to avoid creating a thunk that is subsequently evaluated to a J#.
238 smartJ# itself does a pretty small amount of work, so it's not worth
239 thunking it.
240
241 We call 'smartJ#' in places like quotRemInteger where a big input
242 might produce a small output.
243
244 Just using smartJ# in this way has good results:
245
246         Program           Size    Allocs   Runtime   Elapsed  TotalMem
247 --------------------------------------------------------------------------------
248          gamteb          +0.1%    -19.0%      0.03      0.03     +0.0%
249           kahan          +0.2%     -1.2%      0.17      0.17     +0.0%
250          mandel          +0.1%     -7.7%      0.05      0.05     +0.0%
251           power          +0.1%    -40.8%    -32.5%    -32.5%     +0.0%
252          symalg          +0.2%     -0.5%      0.01      0.01     +0.0%
253 --------------------------------------------------------------------------------
254             Min          +0.0%    -40.8%    -32.5%    -32.5%     -5.1%
255             Max          +0.2%     +0.1%     +2.0%     +2.0%     +0.0%
256  Geometric Mean          +0.1%     -1.0%     -2.5%     -2.5%     -0.1%
257
258 %*********************************************************
259 %*                                                      *
260 \subsection{Dividing @Integers@}
261 %*                                                      *
262 %*********************************************************
263
264 \begin{code}
265 -- XXX There's no good reason for us using unboxed tuples for the
266 -- results, but we don't have Data.Tuple available.
267
268 -- Note that we don't check for divide-by-zero here. That needs
269 -- to be done where it's used.
270 -- (we don't have error)
271
272 {-# NOINLINE quotRemInteger #-}
273 quotRemInteger :: Integer -> Integer -> (# Integer, Integer #)
274 quotRemInteger (S# INT_MINBOUND) b = quotRemInteger minIntAsBig b
275 quotRemInteger (S# i) (S# j) = case quotRemInt# i j of
276                                    (# q, r #) -> (# S# q, S# r #)
277 #if SIZEOF_HSWORD == SIZEOF_LONG
278 quotRemInteger (J# s1 d1) (S# b) | isTrue# (b <# 0#)
279   = case quotRemIntegerWord# s1 d1 (int2Word# (negateInt# b)) of
280           (# q, r #) -> let !q' = mpzToInteger(mpzNeg q)
281                             !r' = mpzToInteger(mpzNeg r)
282                         in (# q', r' #)
283 quotRemInteger (J# s1 d1) (S# b)
284   = mpzToInteger2 (quotRemIntegerWord# s1 d1 (int2Word# b))
285 #else
286 quotRemInteger i1@(J# _ _) i2@(S# _) = quotRemInteger i1 (toBig i2)
287 #endif
288 quotRemInteger i1@(S# _) i2@(J# _ _) = quotRemInteger (toBig i1) i2
289 quotRemInteger (J# s1 d1) (J# s2 d2)
290   = mpzToInteger2(quotRemInteger# s1 d1 s2 d2) -- See Note [Use S# if possible]
291
292 {-# NOINLINE divModInteger #-}
293 divModInteger :: Integer -> Integer -> (# Integer, Integer #)
294 divModInteger (S# INT_MINBOUND) b = divModInteger minIntAsBig b
295 divModInteger (S# i) (S# j) = (# S# d, S# m #)
296     where
297       -- NB. don't inline these.  (# S# (i `quotInt#` j), ... #) means
298       -- (# let q = i `quotInt#` j in S# q, ... #) which builds a
299       -- useless thunk.  Placing the bindings here means they'll be
300       -- evaluated strictly.
301       !d = i `divInt#` j
302       !m = i `modInt#` j
303 #if SIZEOF_HSWORD == SIZEOF_LONG
304 divModInteger (J# s1 d1) (S# b) | isTrue# (b <# 0#)
305   = case divModIntegerWord# (negateInt# s1) d1 (int2Word# (negateInt# b)) of
306           (# q, r #) -> let !q' = mpzToInteger (mpzNeg q)
307                             !r' = mpzToInteger r
308                         in (# q', r' #)
309 divModInteger (J# s1 d1) (S# b)
310   = mpzToInteger2(divModIntegerWord# s1 d1 (int2Word# b))
311 #else
312 divModInteger i1@(J# _ _) i2@(S# _) = divModInteger i1 (toBig i2)
313 #endif
314 divModInteger i1@(S# _) i2@(J# _ _) = divModInteger (toBig i1) i2
315 divModInteger (J# s1 d1) (J# s2 d2) = mpzToInteger2 (divModInteger# s1 d1 s2 d2)
316
317 {-# NOINLINE remInteger #-}
318 remInteger :: Integer -> Integer -> Integer
319 remInteger (S# INT_MINBOUND) b = remInteger minIntAsBig b
320 remInteger (S# a) (S# b) = S# (remInt# a b)
321 {- Special case doesn't work, because a 1-element J# has the range
322    -(2^32-1) -- 2^32-1, whereas S# has the range -2^31 -- (2^31-1)
323 remInteger ia@(S# a) (J# sb b)
324   | sb ==# 1#  = S# (remInt# a (word2Int# (integer2Word# sb b)))
325   | sb ==# -1# = S# (remInt# a (0# -# (word2Int# (integer2Word# sb b))))
326   | 0# <# sb   = ia
327   | otherwise  = S# (0# -# a)
328 -}
329 remInteger ia@(S# _) ib@(J# _ _) = remInteger (toBig ia) ib
330 #if SIZEOF_HSWORD == SIZEOF_LONG
331 remInteger (J# sa a) (S# b)
332   = mpzToInteger (remIntegerWord# sa a w)
333   where
334     w = int2Word# (if isTrue# (b <# 0#) then negateInt# b else b)
335 #else
336 remInteger i1@(J# _ _) i2@(S# _) = remInteger i1 (toBig i2)
337 #endif
338 remInteger (J# sa a) (J# sb b)
339   = mpzToInteger (remInteger# sa a sb b)
340
341 {-# NOINLINE quotInteger #-}
342 quotInteger :: Integer -> Integer -> Integer
343 quotInteger (S# INT_MINBOUND) b = quotInteger minIntAsBig b
344 quotInteger (S# a) (S# b) = S# (quotInt# a b)
345 {- Special case disabled, see remInteger above
346 quotInteger (S# a) (J# sb b)
347   | sb ==# 1#  = S# (quotInt# a (word2Int# (integer2Word# sb b)))
348   | sb ==# -1# = S# (quotInt# a (0# -# (word2Int# (integer2Word# sb b))))
349   | otherwise  = S# 0
350 -}
351 quotInteger ia@(S# _) ib@(J# _ _) = quotInteger (toBig ia) ib
352 #if SIZEOF_HSWORD == SIZEOF_LONG
353 quotInteger (J# sa a) (S# b) | isTrue# (b <# 0#)
354   = mpzToInteger (mpzNeg (quotIntegerWord# sa a (int2Word# (negateInt# b))))
355 quotInteger (J# sa a) (S# b)
356   = mpzToInteger (quotIntegerWord# sa a (int2Word# b))
357 #else
358 quotInteger i1@(J# _ _) i2@(S# _) = quotInteger i1 (toBig i2)
359 #endif
360 quotInteger (J# sa a) (J# sb b)
361   = mpzToInteger (quotInteger# sa a sb b)
362
363 {-# NOINLINE modInteger #-}
364 modInteger :: Integer -> Integer -> Integer
365 modInteger (S# INT_MINBOUND) b = modInteger minIntAsBig b
366 modInteger (S# a) (S# b) = S# (modInt# a b)
367 modInteger ia@(S# _) ib@(J# _ _) = modInteger (toBig ia) ib
368 #if SIZEOF_HSWORD == SIZEOF_LONG
369 modInteger (J# sa a) (S# b) | isTrue# (b <# 0#)
370   = mpzToInteger (mpzNeg (remIntegerWord# (negateInt# sa) a (int2Word# (negateInt# b))))
371 modInteger (J# sa a) (S# b)
372   = mpzToInteger (modIntegerWord# sa a (int2Word# b))
373 #else
374 modInteger i1@(J# _ _) i2@(S# _) = modInteger i1 (toBig i2)
375 #endif
376 modInteger (J# sa a) (J# sb b)
377   = mpzToInteger (modInteger# sa a sb b)
378
379 {-# NOINLINE divInteger #-}
380 divInteger :: Integer -> Integer -> Integer
381 divInteger (S# INT_MINBOUND) b = divInteger minIntAsBig b
382 divInteger (S# a) (S# b) = S# (divInt# a b)
383 divInteger ia@(S# _) ib@(J# _ _) = divInteger (toBig ia) ib
384 #if SIZEOF_HSWORD == SIZEOF_LONG
385 divInteger (J# sa a) (S# b) | isTrue# (b <# 0#)
386   = mpzToInteger (divIntegerWord# (negateInt# sa) a (int2Word# (negateInt# b)))
387 divInteger (J# sa a) (S# b)
388   = mpzToInteger (divIntegerWord# sa a (int2Word# b))
389 #else
390 divInteger i1@(J# _ _) i2@(S# _) = divInteger i1 (toBig i2)
391 #endif
392 divInteger (J# sa a) (J# sb b)
393   = mpzToInteger (divInteger# sa a sb b)
394 \end{code}
395
396
397
398 \begin{code}
399 -- | Compute greatest common divisor.
400 {-# NOINLINE gcdInteger #-}
401 gcdInteger :: Integer -> Integer -> Integer
402 -- SUP: Do we really need the first two cases?
403 gcdInteger (S# INT_MINBOUND) b = gcdInteger minIntAsBig b
404 gcdInteger a (S# INT_MINBOUND) = gcdInteger a minIntAsBig
405 gcdInteger (S# a) (S# b) = S# (gcdInt a b)
406 gcdInteger ia@(S# a)  ib@(J# sb b)
407  =      if isTrue# (a  ==# 0#) then absInteger ib
408    else if isTrue# (sb ==# 0#) then absInteger ia
409    else                             S# (gcdIntegerInt# absSb b absA)
410        where !absA  = if isTrue# (a  <# 0#) then negateInt# a  else a
411              !absSb = if isTrue# (sb <# 0#) then negateInt# sb else sb
412 gcdInteger ia@(J# _ _) ib@(S# _) = gcdInteger ib ia
413 gcdInteger (J# sa a) (J# sb b)   = mpzToInteger (gcdInteger# sa a sb b)
414
415 -- | Extended euclidean algorithm.
416 --
417 -- For @/a/@ and @/b/@, compute their greatest common divisor @/g/@
418 -- and the coefficient @/s/@ satisfying @/a//s/ + /b//t/ = /g/@.
419 {-# NOINLINE gcdExtInteger #-}
420 gcdExtInteger :: Integer -> Integer -> (# Integer, Integer #)
421 gcdExtInteger a@(S# _)   b@(S# _) = gcdExtInteger (toBig a) (toBig b)
422 gcdExtInteger a@(S# _) b@(J# _ _) = gcdExtInteger (toBig a) b
423 gcdExtInteger a@(J# _ _) b@(S# _) = gcdExtInteger a (toBig b)
424 gcdExtInteger (J# sa a) (J# sb b) = mpzToInteger2 (gcdExtInteger# sa a sb b)
425
426 -- | Compute least common multiple.
427 {-# NOINLINE lcmInteger #-}
428 lcmInteger :: Integer -> Integer -> Integer
429 lcmInteger a b =      if a `eqInteger` S# 0# then S# 0#
430                  else if b `eqInteger` S# 0# then S# 0#
431                  else (divExact aa (gcdInteger aa ab)) `timesInteger` ab
432   where aa = absInteger a
433         ab = absInteger b
434
435 -- | Compute greatest common divisor.
436 gcdInt :: Int# -> Int# -> Int#
437 gcdInt 0# y  = absInt y
438 gcdInt x  0# = absInt x
439 gcdInt x  y  = gcdInt# (absInt x) (absInt y)
440
441 absInt :: Int# -> Int#
442 absInt x = if isTrue# (x <# 0#) then negateInt# x else x
443
444 divExact :: Integer -> Integer -> Integer
445 divExact (S# INT_MINBOUND) b = divExact minIntAsBig b
446 divExact (S# a) (S# b) = S# (quotInt# a b)
447 divExact (S# a) (J# sb b)
448   = S# (quotInt# a (integer2Int# sb b))
449 #if SIZEOF_HSWORD == SIZEOF_LONG
450 divExact (J# sa a) (S# b) | isTrue# (b <# 0#)
451   = mpzToInteger (divExactIntegerWord# (negateInt# sa) a (int2Word# (negateInt# b)))
452 divExact (J# sa a) (S# b) = mpzToInteger (divExactIntegerWord# sa a (int2Word# b))
453 #else
454 divExact i1@(J# _ _) i2@(S# _) = divExact i1 (toBig i2)
455 #endif
456 divExact (J# sa a) (J# sb b) = mpzToInteger (divExactInteger# sa a sb b)
457 \end{code}
458
459
460 %*********************************************************
461 %*                                                      *
462 \subsection{The @Integer@ instances for @Eq@, @Ord@}
463 %*                                                      *
464 %*********************************************************
465
466 \begin{code}
467 {-# NOINLINE eqInteger# #-}
468 eqInteger# :: Integer -> Integer -> Int#
469 eqInteger# (S# i)     (S# j)     = i ==# j
470 eqInteger# (S# i)     (J# s d)   = cmpIntegerInt# s d i ==# 0#
471 eqInteger# (J# s d)   (S# i)     = cmpIntegerInt# s d i ==# 0#
472 eqInteger# (J# s1 d1) (J# s2 d2) = (cmpInteger# s1 d1 s2 d2) ==# 0#
473
474 {-# NOINLINE neqInteger# #-}
475 neqInteger# :: Integer -> Integer -> Int#
476 neqInteger# (S# i)     (S# j)     = i /=# j
477 neqInteger# (S# i)     (J# s d)   = cmpIntegerInt# s d i /=# 0#
478 neqInteger# (J# s d)   (S# i)     = cmpIntegerInt# s d i /=# 0#
479 neqInteger# (J# s1 d1) (J# s2 d2) = (cmpInteger# s1 d1 s2 d2) /=# 0#
480
481 {-# INLINE eqInteger  #-}
482 {-# INLINE neqInteger #-}
483 eqInteger, neqInteger :: Integer -> Integer -> Bool
484 eqInteger  a b = isTrue# (a `eqInteger#`  b)
485 neqInteger a b = isTrue# (a `neqInteger#` b)
486
487 instance  Eq Integer  where
488     (==) = eqInteger
489     (/=) = neqInteger
490
491 ------------------------------------------------------------------------
492
493 {-# NOINLINE leInteger# #-}
494 leInteger# :: Integer -> Integer -> Int#
495 leInteger# (S# i)     (S# j)     = i <=# j
496 leInteger# (J# s d)   (S# i)     = cmpIntegerInt# s d i <=# 0#
497 leInteger# (S# i)     (J# s d)   = cmpIntegerInt# s d i >=# 0#
498 leInteger# (J# s1 d1) (J# s2 d2) = (cmpInteger# s1 d1 s2 d2) <=# 0#
499
500 {-# NOINLINE gtInteger# #-}
501 gtInteger# :: Integer -> Integer -> Int#
502 gtInteger# (S# i)     (S# j)     = i ># j
503 gtInteger# (J# s d)   (S# i)     = cmpIntegerInt# s d i ># 0#
504 gtInteger# (S# i)     (J# s d)   = cmpIntegerInt# s d i <# 0#
505 gtInteger# (J# s1 d1) (J# s2 d2) = (cmpInteger# s1 d1 s2 d2) ># 0#
506
507 {-# NOINLINE ltInteger# #-}
508 ltInteger# :: Integer -> Integer -> Int#
509 ltInteger# (S# i)     (S# j)     = i <# j
510 ltInteger# (J# s d)   (S# i)     = cmpIntegerInt# s d i <# 0#
511 ltInteger# (S# i)     (J# s d)   = cmpIntegerInt# s d i ># 0#
512 ltInteger# (J# s1 d1) (J# s2 d2) = (cmpInteger# s1 d1 s2 d2) <# 0#
513
514 {-# NOINLINE geInteger# #-}
515 geInteger# :: Integer -> Integer -> Int#
516 geInteger# (S# i)     (S# j)     = i >=# j
517 geInteger# (J# s d)   (S# i)     = cmpIntegerInt# s d i >=# 0#
518 geInteger# (S# i)     (J# s d)   = cmpIntegerInt# s d i <=# 0#
519 geInteger# (J# s1 d1) (J# s2 d2) = (cmpInteger# s1 d1 s2 d2) >=# 0#
520
521 {-# INLINE leInteger #-}
522 {-# INLINE ltInteger #-}
523 {-# INLINE geInteger #-}
524 {-# INLINE gtInteger #-}
525 leInteger, gtInteger, ltInteger, geInteger :: Integer -> Integer -> Bool
526 leInteger a b = isTrue# (a `leInteger#` b)
527 gtInteger a b = isTrue# (a `gtInteger#` b)
528 ltInteger a b = isTrue# (a `ltInteger#` b)
529 geInteger a b = isTrue# (a `geInteger#` b)
530
531 {-# NOINLINE compareInteger #-}
532 compareInteger :: Integer -> Integer -> Ordering
533 compareInteger (S# i)  (S# j)
534    =      if isTrue# (i ==# j) then EQ
535      else if isTrue# (i <=# j) then LT
536      else                           GT
537 compareInteger (J# s d) (S# i)
538    = case cmpIntegerInt# s d i of { res# ->
539      if isTrue# (res# <# 0#) then LT else
540      if isTrue# (res# ># 0#) then GT else EQ
541      }
542 compareInteger (S# i) (J# s d)
543    = case cmpIntegerInt# s d i of { res# ->
544      if isTrue# (res# ># 0#) then LT else
545      if isTrue# (res# <# 0#) then GT else EQ
546      }
547 compareInteger (J# s1 d1) (J# s2 d2)
548    = case cmpInteger# s1 d1 s2 d2 of { res# ->
549      if isTrue# (res# <# 0#) then LT else
550      if isTrue# (res# ># 0#) then GT else EQ
551      }
552
553 instance Ord Integer where
554     (<=) = leInteger
555     (<)  = ltInteger
556     (>)  = gtInteger
557     (>=) = geInteger
558     compare = compareInteger
559 \end{code}
560
561
562 %*********************************************************
563 %*                                                      *
564 \subsection{The @Integer@ instances for @Num@}
565 %*                                                      *
566 %*********************************************************
567
568 \begin{code}
569 {-# NOINLINE absInteger #-}
570 absInteger :: Integer -> Integer
571 absInteger (S# INT_MINBOUND) = NEG_INT_MINBOUND
572 absInteger n@(S# i)   = if isTrue# (i >=# 0#) then n else S# (negateInt# i)
573 absInteger n@(J# s d) = if isTrue# (s >=# 0#) then n else J# (negateInt# s) d
574
575 {-# NOINLINE signumInteger #-}
576 signumInteger :: Integer -> Integer
577 signumInteger (S# i) = if isTrue# (i <# 0#) then S# -1#
578                        else if isTrue# (i ==# 0#) then S# 0#
579                        else S# 1#
580 signumInteger (J# s d)
581   = let
582         !cmp = cmpIntegerInt# s d 0#
583     in
584     if      isTrue# (cmp >#  0#) then S# 1#
585     else if isTrue# (cmp ==# 0#) then S# 0#
586     else                              S# (negateInt# 1#)
587
588 {-# NOINLINE plusInteger #-}
589 plusInteger :: Integer -> Integer -> Integer
590 plusInteger (S# i)      (S# j)   = case addIntC# i j of
591                                    (# r, c #) ->
592                                        if isTrue# (c ==# 0#)
593                                        then S# r
594 #if SIZEOF_HSWORD == SIZEOF_LONG
595                                        else case int2Integer# i of
596                                             (# s, d #) -> mpzToInteger (plusIntegerInt# s d j)
597 #else
598                                        else plusInteger (toBig (S# i)) (toBig (S# j))
599 #endif
600 plusInteger i1@(J# _ _) (S# 0#)   = i1
601 #if SIZEOF_HSWORD == SIZEOF_LONG
602 plusInteger (J# s1 d1)  (S# j)    = mpzToInteger (plusIntegerInt# s1 d1 j)
603 #else
604 plusInteger i1@(J# _ _) i2@(S# _) = plusInteger i1 (toBig i2)
605 #endif
606 plusInteger i1@(S# _) i2@(J# _ _) = plusInteger i2 i1
607 plusInteger (J# s1 d1) (J# s2 d2) = mpzToInteger (plusInteger# s1 d1 s2 d2)
608
609 {-# NOINLINE minusInteger #-}
610 minusInteger :: Integer -> Integer -> Integer
611 minusInteger (S# i)      (S# j)    = case subIntC# i j of
612                                      (# r, c #) ->
613                                          if isTrue# (c ==# 0#) then S# r
614 #if SIZEOF_HSWORD == SIZEOF_LONG
615                                          else case int2Integer# i of
616                                               (# s, d #) -> mpzToInteger (minusIntegerInt# s d j)
617 #else
618                                          else minusInteger (toBig (S# i)) (toBig (S# j))
619 #endif
620 minusInteger i1@(J# _ _) (S# 0#)   = i1
621 minusInteger (S# 0#)    (J# s2 d2) = J# (negateInt# s2) d2
622 #if SIZEOF_HSWORD == SIZEOF_LONG
623 minusInteger (J# s1 d1)  (S# j)    = mpzToInteger (minusIntegerInt# s1 d1 j)
624 minusInteger (S# i)     (J# s2 d2) = mpzToInteger (plusIntegerInt# (negateInt# s2) d2 i)
625 #else
626 minusInteger i1@(J# _ _) i2@(S# _) = minusInteger i1 (toBig i2)
627 minusInteger i1@(S# _) i2@(J# _ _) = minusInteger (toBig i1) i2
628 #endif
629 minusInteger (J# s1 d1) (J# s2 d2) = mpzToInteger (minusInteger# s1 d1 s2 d2)
630
631 {-# NOINLINE timesInteger #-}
632 timesInteger :: Integer -> Integer -> Integer
633 timesInteger (S# i) (S# j)         = if isTrue# (mulIntMayOflo# i j ==# 0#)
634                                      then S# (i *# j)
635 #if SIZEOF_HSWORD == SIZEOF_LONG
636                                      else case int2Integer# i of
637                                           (# s, d #) -> mpzToInteger (timesIntegerInt# s d j)
638 #else
639                                      else timesInteger (toBig (S# i)) (toBig (S# j))
640 #endif
641 timesInteger (S# 0#)     _         = S# 0#
642 timesInteger (S# -1#)    i2        = negateInteger i2
643 timesInteger (S# 1#)     i2        = i2
644 #if SIZEOF_HSWORD == SIZEOF_LONG
645 timesInteger (S# i1)    (J# s2 d2) = mpzToInteger (timesIntegerInt# s2 d2 i1)
646 #else
647 timesInteger i1@(S# _) i2@(J# _ _) = timesInteger (toBig i1) i2
648 #endif
649 timesInteger i1@(J# _ _) i2@(S# _) = timesInteger i2 i1 -- swap args & retry
650 timesInteger (J# s1 d1) (J# s2 d2) = mpzToInteger (timesInteger# s1 d1 s2 d2)
651
652 {-# NOINLINE negateInteger #-}
653 negateInteger :: Integer -> Integer
654 negateInteger (S# INT_MINBOUND) = NEG_INT_MINBOUND
655 negateInteger (S# i)            = S# (negateInt# i)
656 negateInteger (J# s d)          = J# (negateInt# s) d
657 \end{code}
658
659
660 %*********************************************************
661 %*                                                      *
662 \subsection{The @Integer@ stuff for Double@}
663 %*                                                      *
664 %*********************************************************
665
666 \begin{code}
667 {-# NOINLINE encodeFloatInteger #-}
668 encodeFloatInteger :: Integer -> Int# -> Float#
669 encodeFloatInteger (S# i) j     = int_encodeFloat# i j
670 encodeFloatInteger (J# s# d#) e = encodeFloat# s# d# e
671
672 {-# NOINLINE encodeDoubleInteger #-}
673 encodeDoubleInteger :: Integer -> Int# -> Double#
674 encodeDoubleInteger (S# i) j     = int_encodeDouble# i j
675 encodeDoubleInteger (J# s# d#) e = encodeDouble# s# d# e
676
677 {-# NOINLINE decodeDoubleInteger #-}
678 decodeDoubleInteger :: Double# -> (# Integer, Int# #)
679 decodeDoubleInteger d = case decodeDouble# d of
680                         (# exp#, man# #) -> let !man = mpzToInteger man#
681                                             in (# man, exp# #)
682
683 -- previous code: doubleFromInteger n = fromInteger n = encodeFloat n 0
684 -- doesn't work too well, because encodeFloat is defined in
685 -- terms of ccalls which can never be simplified away.  We
686 -- want simple literals like (fromInteger 3 :: Float) to turn
687 -- into (F# 3.0), hence the special case for S# here.
688
689 {-# NOINLINE doubleFromInteger #-}
690 doubleFromInteger :: Integer -> Double#
691 doubleFromInteger (S# i#) = int2Double# i#
692 doubleFromInteger (J# s# d#) = encodeDouble# s# d# 0#
693
694 {-# NOINLINE floatFromInteger #-}
695 floatFromInteger :: Integer -> Float#
696 floatFromInteger (S# i#) = int2Float# i#
697 floatFromInteger (J# s# d#) = encodeFloat# s# d# 0#
698
699 foreign import ccall unsafe "integer_cbits_encodeFloat"
700         encodeFloat# :: Int# -> ByteArray# -> Int# -> Float#
701 foreign import ccall unsafe "__int_encodeFloat"
702         int_encodeFloat# :: Int# -> Int# -> Float#
703
704 foreign import ccall unsafe "integer_cbits_encodeDouble"
705         encodeDouble# :: Int# -> ByteArray# -> Int# -> Double#
706 foreign import ccall unsafe "__int_encodeDouble"
707         int_encodeDouble# :: Int# -> Int# -> Double#
708 \end{code}
709
710 %*********************************************************
711 %*                                                      *
712 \subsection{The @Integer@ Bit definitions@}
713 %*                                                      *
714 %*********************************************************
715
716 We explicitly pattern match against J# and S# in order to produce
717 Core that doesn't have pattern matching errors, as that would
718 introduce a spurious dependency to base.
719
720 \begin{code}
721 {-# NOINLINE andInteger #-}
722 andInteger :: Integer -> Integer -> Integer
723 (S# x)     `andInteger`   (S# y)     = S# (word2Int# (int2Word# x `and#` int2Word# y))
724 x@(S# _)   `andInteger` y@(J# _ _)   = toBig x `andInteger` y
725 x@(J# _ _) `andInteger` y@(S# _)     = x `andInteger` toBig y
726 (J# s1 d1) `andInteger`   (J# s2 d2) =
727      mpzToInteger (andInteger# s1 d1 s2 d2)
728
729 {-# NOINLINE orInteger #-}
730 orInteger :: Integer -> Integer -> Integer
731 (S# x)     `orInteger`   (S# y)     = S# (word2Int# (int2Word# x `or#` int2Word# y))
732 x@(S# _)   `orInteger` y@(J# _ _)   = toBig x `orInteger` y
733 x@(J# _ _) `orInteger` y@(S# _)     = x `orInteger` toBig y
734 (J# s1 d1) `orInteger`   (J# s2 d2) =
735      mpzToInteger (orInteger# s1 d1 s2 d2)
736
737 {-# NOINLINE xorInteger #-}
738 xorInteger :: Integer -> Integer -> Integer
739 (S# x)     `xorInteger`   (S# y)     = S# (word2Int# (int2Word# x `xor#` int2Word# y))
740 x@(S# _)   `xorInteger` y@(J# _ _)   = toBig x `xorInteger` y
741 x@(J# _ _) `xorInteger` y@(S# _)     = x `xorInteger` toBig y
742 (J# s1 d1) `xorInteger`   (J# s2 d2) =
743      mpzToInteger (xorInteger# s1 d1 s2 d2)
744
745 {-# NOINLINE complementInteger #-}
746 complementInteger :: Integer -> Integer
747 complementInteger (S# x)
748     = S# (word2Int# (int2Word# x `xor#` int2Word# (0# -# 1#)))
749 complementInteger (J# s d)
750     = mpzToInteger (complementInteger# s d)
751
752 {-# NOINLINE shiftLInteger #-}
753 shiftLInteger :: Integer -> Int# -> Integer
754 shiftLInteger j@(S# _) i = shiftLInteger (toBig j) i
755 shiftLInteger (J# s d) i = mpzToInteger (mul2ExpInteger# s d i)
756
757 {-# NOINLINE shiftRInteger #-}
758 shiftRInteger :: Integer -> Int# -> Integer
759 shiftRInteger j@(S# _) i = shiftRInteger (toBig j) i
760 shiftRInteger (J# s d) i = mpzToInteger (fdivQ2ExpInteger# s d i)
761
762 {-# NOINLINE testBitInteger #-}
763 testBitInteger :: Integer -> Int# -> Bool
764 testBitInteger j@(S# _) i = testBitInteger (toBig j) i
765 testBitInteger (J# s d) i = isTrue# (testBitInteger# s d i /=# 0#)
766
767 -- | \"@'powInteger' /b/ /e/@\" computes base @/b/@ raised to exponent @/e/@.
768 {-# NOINLINE powInteger #-}
769 powInteger :: Integer -> Word# -> Integer
770 powInteger j@(S# _) e = powInteger (toBig j) e
771 powInteger (J# s d) e = mpzToInteger (powInteger# s d e)
772
773 -- | \"@'powModInteger' /b/ /e/ /m/@\" computes base @/b/@ raised to
774 -- exponent @/e/@ modulo @/m/@.
775 --
776 -- Negative exponents are supported if an inverse modulo @/m/@
777 -- exists. It's advised to avoid calling this primitive with negative
778 -- exponents unless it is guaranteed the inverse exists, as failure to
779 -- do so will likely cause program abortion due to a divide-by-zero
780 -- fault. See also 'recipModInteger'.
781 {-# NOINLINE powModInteger #-}
782 powModInteger :: Integer -> Integer -> Integer -> Integer
783 powModInteger (J# s1 d1) (J# s2 d2) (J# s3 d3) =
784     mpzToInteger (powModInteger# s1 d1 s2 d2 s3 d3)
785 powModInteger b e m = powModInteger (toBig b) (toBig e) (toBig m)
786
787 -- | \"@'powModSecInteger' /b/ /e/ /m/@\" computes base @/b/@ raised to
788 -- exponent @/e/@ modulo @/m/@. It is required that @/e/ > 0@ and
789 -- @/m/@ is odd.
790 --
791 -- This is a \"secure\" variant of 'powModInteger' using the
792 -- @mpz_powm_sec()@ function which is designed to be resilient to side
793 -- channel attacks and is therefore intended for cryptographic
794 -- applications.
795 {-# NOINLINE powModSecInteger #-}
796 powModSecInteger :: Integer -> Integer -> Integer -> Integer
797 powModSecInteger (J# s1 d1) (J# s2 d2) (J# s3 d3) =
798     mpzToInteger (powModSecInteger# s1 d1 s2 d2 s3 d3)
799 powModSecInteger b e m = powModSecInteger (toBig b) (toBig e) (toBig m)
800
801 -- | \"@'recipModInteger' /x/ /m/@\" computes the inverse of @/x/@ modulo @/m/@. If
802 -- the inverse exists, the return value @/y/@ will satisfy @0 < /y/ <
803 -- abs(/m/)@, otherwise the result is @0@.
804 --
805 -- Note: The implementation exploits the undocumented property of
806 -- @mpz_invert()@ to not mangle the result operand (which is initialized
807 -- to 0) in case of non-existence of the inverse.
808 {-# NOINLINE recipModInteger #-}
809 recipModInteger :: Integer -> Integer -> Integer
810 recipModInteger j@(S# _) m@(S# _)   = recipModInteger (toBig j) (toBig m)
811 recipModInteger j@(S# _) m@(J# _ _) = recipModInteger (toBig j) m
812 recipModInteger j@(J# _ _) m@(S# _) = recipModInteger j (toBig m)
813 recipModInteger (J# s d) (J# ms md) = mpzToInteger (recipModInteger# s d ms md)
814
815 -- | Probalistic Miller-Rabin primality test.
816 --
817 -- \"@'testPrimeInteger' /n/ /k/@\" determines whether @/n/@ is prime
818 -- and returns one of the following results:
819 --
820 -- * @2#@ is returned if @/n/@ is definitely prime,
821 --
822 -- * @1#@ if @/n/@ is a /probable prime/, or
823 --
824 -- * @0#@ if @/n/@ is definitely not a prime.
825 --
826 -- The @/k/@ argument controls how many test rounds are performed for
827 -- determining a /probable prime/. For more details, see
828 -- <http://gmplib.org/manual/Number-Theoretic-Functions.html#index-mpz_005fprobab_005fprime_005fp-360 GMP documentation for `mpz_probab_prime_p()`>.
829 {-# NOINLINE testPrimeInteger #-}
830 testPrimeInteger :: Integer -> Int# -> Int#
831 testPrimeInteger j@(S# _) reps = testPrimeInteger (toBig j) reps
832 testPrimeInteger (J# s d) reps = testPrimeInteger# s d reps
833
834 -- | Compute next prime greater than @/n/@ probalistically.
835 --
836 -- According to the GMP documentation, the underlying function
837 -- @mpz_nextprime()@ \"uses a probabilistic algorithm to identify
838 -- primes. For practical purposes it's adequate, the chance of a
839 -- composite passing will be extremely small.\"
840 {-# NOINLINE nextPrimeInteger #-}
841 nextPrimeInteger :: Integer -> Integer
842 nextPrimeInteger j@(S# _) = nextPrimeInteger (toBig j)
843 nextPrimeInteger (J# s d) = mpzToInteger (nextPrimeInteger# s d)
844
845 -- | Compute number of digits (without sign) in given @/base/@.
846 --
847 -- It's recommended to avoid calling 'sizeInBaseInteger' for small
848 -- integers as this function would currently convert those to big
849 -- integers in order to call @mpz_sizeinbase()@.
850 --
851 -- This function wraps @mpz_sizeinbase()@ which has some
852 -- implementation pecularities to take into account:
853 --
854 -- * \"@'sizeInBaseInteger' 0 /base/ = 1@\" (see also comment in 'exportIntegerToMutableByteArray').
855 --
856 -- * This function is only defined if @/base/ >= 2#@ and @/base/ <= 256#@
857 --   (Note: the documentation claims that only @/base/ <= 62#@ is
858 --   supported, however the actual implementation supports up to base 256).
859 --
860 -- * If @/base/@ is a power of 2, the result will be exact. In other
861 --   cases (e.g. for @/base/ = 10#@), the result /may/ be 1 digit too large
862 --   sometimes.
863 --
864 -- * \"@'sizeInBaseInteger' /i/ 2#@\" can be used to determine the most
865 --   significant bit of @/i/@.
866 {-# NOINLINE sizeInBaseInteger #-}
867 sizeInBaseInteger :: Integer -> Int# -> Word#
868 sizeInBaseInteger (J# s d) b = sizeInBaseInteger# s d b
869 sizeInBaseInteger j@(S# _) b = sizeInBaseInteger (toBig j) b -- TODO
870
871 -- | Dump 'Integer' (without sign) to mutable byte-array in base-256 representation.
872 --
873 -- The call
874 --
875 -- @
876 -- 'exportIntegerToMutableByteArray' /i/ /mba/ /offset/ /order/
877 -- @
878 --
879 -- writes
880 --
881 -- * the 'Integer' @/i/@
882 --
883 -- * into the 'MutableByteArray#' @/mba/@ starting at @/offset/@
884 --
885 -- * with most significant byte first if @order@ is @1#@ or least
886 --   significant byte first if @order@ is @-1#@, and
887 --
888 -- * returns number of bytes written.
889 --
890 -- Use \"@'sizeInBaseInteger' /i/ 256#@\" to compute the exact number of
891 -- bytes written in advance for @/i/ /= 0@. In case of @/i/ == 0@,
892 -- 'exportIntegerToMutableByteArray' will write and report zero bytes
893 -- written, whereas 'sizeInBaseInteger' report one byte.
894 --
895 -- It's recommended to avoid calling 'exportIntegerToMutableByteArray' for small
896 -- integers as this function would currently convert those to big
897 -- integers in order to call @mpz_export()@.
898 {-# NOINLINE exportIntegerToMutableByteArray #-}
899 exportIntegerToMutableByteArray :: Integer -> MutableByteArray# s -> Word# -> Int# -> State# s -> (# State# s, Word# #)
900 exportIntegerToMutableByteArray (J# s d) mba o e = exportIntegerToMutableByteArray# s d mba o e
901 exportIntegerToMutableByteArray j@(S# _) mba o e = exportIntegerToMutableByteArray (toBig j) mba o e -- TODO
902
903 -- | Dump 'Integer' (without sign) to @/addr/@ in base-256 representation.
904 --
905 -- @
906 -- 'exportIntegerToAddr' /addr/ /o/ /e/
907 -- @
908 --
909 -- See description of 'exportIntegerToMutableByteArray' for more details.
910 {-# NOINLINE exportIntegerToAddr #-}
911 exportIntegerToAddr :: Integer -> Addr# -> Int# -> State# s -> (# State# s, Word# #)
912 exportIntegerToAddr (J# s d) addr o e = exportIntegerToAddr# s d addr o e
913 exportIntegerToAddr j@(S# _) addr o e = exportIntegerToAddr (toBig j) addr o e -- TODO
914
915 -- | Read 'Integer' (without sign) from byte-array in base-256 representation.
916 --
917 -- The call
918 --
919 -- @
920 -- 'importIntegerFromByteArray' /ba/ /offset/ /size/ /order/
921 -- @
922 --
923 -- reads
924 --
925 -- * @/size/@ bytes from the 'ByteArray#' @/ba/@ starting at @/offset/@
926 --
927 -- * with most significant byte first if @/order/@ is @1#@ or least
928 --   significant byte first if @/order/@ is @-1#@, and
929 --
930 -- * returns a new 'Integer'
931 {-# NOINLINE importIntegerFromByteArray #-}
932 importIntegerFromByteArray :: ByteArray# -> Word# -> Word# -> Int# -> Integer
933 importIntegerFromByteArray ba o l e = mpzToInteger (importIntegerFromByteArray# ba o l e)
934
935 -- | Read 'Integer' (without sign) from memory location at @/addr/@ in
936 -- base-256 representation.
937 --
938 -- @
939 -- 'importIntegerFromAddr' /addr/ /size/ /order/
940 -- @
941 --
942 -- See description of 'importIntegerFromByteArray' for more details.
943 {-# NOINLINE importIntegerFromAddr #-}
944 importIntegerFromAddr :: Addr# -> Word# -> Int# -> State# s -> (# State# s, Integer #)
945 importIntegerFromAddr addr l e st = case importIntegerFromAddr# addr l e st of
946                                       (# st', mpz #) -> let !j = mpzToInteger mpz in (# st', j #)
947
948 \end{code}
949
950 %*********************************************************
951 %*                                                      *
952 \subsection{The @Integer@ hashing@}
953 %*                                                      *
954 %*********************************************************
955
956 \begin{code}
957 -- This is used by hashUnique
958
959 -- | hashInteger returns the same value as 'fromIntegral', although in
960 -- unboxed form.  It might be a reasonable hash function for 'Integer',
961 -- given a suitable distribution of 'Integer' values.
962
963 hashInteger :: Integer -> Int#
964 hashInteger = integerToInt
965 \end{code}
966