Re-implement `nextPrimeInteger` predicate (#9281)
[ghc.git] / libraries / integer-gmp2 / src / GHC / Integer / GMP / Internals.hs
1 {-# LANGUAGE BangPatterns #-}
2 {-# LANGUAGE CApiFFI #-}
3 {-# LANGUAGE MagicHash #-}
4 {-# LANGUAGE UnboxedTuples #-}
5 {-# LANGUAGE UnliftedFFITypes #-}
6 {-# LANGUAGE DeriveDataTypeable #-}
7 {-# LANGUAGE GHCForeignImportPrim #-}
8 {-# LANGUAGE CPP #-}
9 {-# LANGUAGE StandaloneDeriving #-}
10 {-# LANGUAGE NoImplicitPrelude #-}
11
12 #include "MachDeps.h"
13
14 -- |
15 -- Module : GHC.Integer.GMP.Internals
16 -- Copyright : (c) Herbert Valerio Riedel 2014
17 -- License : BSD3
18 --
19 -- Maintainer : ghc-devs@haskell.org
20 -- Stability : provisional
21 -- Portability : non-portable (GHC Extensions)
22 --
23 -- This modules provides access to the 'Integer' constructors and
24 -- exposes some highly optimized GMP-operations.
25 --
26 -- Note that since @integer-gmp@ does not depend on `base`, error
27 -- reporting via exceptions, 'error', or 'undefined' is not
28 -- available. Instead, the low-level functions will crash the runtime
29 -- if called with invalid arguments.
30 --
31 -- See also
32 -- <https://ghc.haskell.org/trac/ghc/wiki/Commentary/Libraries/Integer GHC Commentary: Libraries/Integer>.
33
34 module GHC.Integer.GMP.Internals
35 ( -- * The 'Integer' type
36 Integer(..)
37 , isValidInteger#
38
39 -- ** Basic 'Integer' operations
40
41 , module GHC.Integer
42
43 -- ** Additional 'Integer' operations
44 , bitInteger
45 , popCountInteger
46 , gcdInteger
47 , lcmInteger
48 , sqrInteger
49
50 -- ** Additional conversion operations to 'Integer'
51 , wordToNegInteger
52 , bigNatToInteger
53 , bigNatToNegInteger
54
55 -- * The 'BigNat' type
56 , BigNat(..)
57
58 , GmpLimb, GmpLimb#
59 , GmpSize, GmpSize#
60
61 -- **
62
63 , isValidBigNat#
64 , sizeofBigNat#
65 , zeroBigNat
66 , oneBigNat
67 , nullBigNat
68
69 -- ** Conversions to/from 'BigNat'
70
71 , byteArrayToBigNat#
72 , wordToBigNat
73 , wordToBigNat2
74 , bigNatToInt
75 , bigNatToWord
76 , indexBigNat#
77
78 -- ** 'BigNat' arithmetic operations
79 , plusBigNat
80 , plusBigNatWord
81 , minusBigNat
82 , minusBigNatWord
83 , timesBigNat
84 , timesBigNatWord
85 , sqrBigNat
86
87 , quotRemBigNat
88 , quotRemBigNatWord
89 , quotBigNatWord
90 , quotBigNat
91 , remBigNat
92 , remBigNatWord
93
94 , gcdBigNat
95 , gcdBigNatWord
96
97 -- ** 'BigNat' logic operations
98 , shiftRBigNat
99 , shiftLBigNat
100 , testBitBigNat
101 , andBigNat
102 , xorBigNat
103 , popCountBigNat
104 , orBigNat
105 , bitBigNat
106
107 -- ** 'BigNat' comparision predicates
108 , isZeroBigNat
109 , isNullBigNat#
110
111 , compareBigNatWord
112 , compareBigNat
113 , eqBigNatWord
114 , eqBigNatWord#
115 , eqBigNat
116 , eqBigNat#
117 , gtBigNatWord#
118
119 -- * Miscellaneous GMP-provided operations
120 , gcdInt
121 , gcdWord
122
123 -- * Primality tests
124 , testPrimeInteger
125 , testPrimeBigNat
126 , testPrimeWord#
127
128 , nextPrimeInteger
129 , nextPrimeBigNat
130 , nextPrimeWord#
131
132 -- * Import/export functions
133 -- ** Compute size of serialisation
134 , sizeInBaseBigNat
135 , sizeInBaseInteger
136 , sizeInBaseWord#
137
138 -- ** Export
139 , exportBigNatToAddr
140 , exportIntegerToAddr
141 , exportWordToAddr
142
143 , exportBigNatToMutableByteArray
144 , exportIntegerToMutableByteArray
145 , exportWordToMutableByteArray
146
147 -- ** Import
148
149 , importBigNatFromAddr
150 , importIntegerFromAddr
151
152 , importBigNatFromByteArray
153 , importIntegerFromByteArray
154 ) where
155
156 import GHC.Integer.Type
157 import GHC.Integer
158 import GHC.Prim
159 import GHC.Types
160
161 default ()
162
163
164 -- | Compute number of digits (without sign) in given @/base/@.
165 --
166 -- This function wraps @mpz_sizeinbase()@ which has some
167 -- implementation pecularities to take into account:
168 --
169 -- * \"@'sizeInBaseInteger' 0 /base/ = 1@\"
170 -- (see also comment in 'exportIntegerToMutableByteArray').
171 --
172 -- * This function is only defined if @/base/ >= 2#@ and @/base/ <= 256#@
173 -- (Note: the documentation claims that only @/base/ <= 62#@ is
174 -- supported, however the actual implementation supports up to base 256).
175 --
176 -- * If @/base/@ is a power of 2, the result will be exact. In other
177 -- cases (e.g. for @/base/ = 10#@), the result /may/ be 1 digit too large
178 -- sometimes.
179 --
180 -- * \"@'sizeInBaseInteger' /i/ 2#@\" can be used to determine the most
181 -- significant bit of @/i/@.
182 --
183 -- /Since: 0.5.1.0/
184 sizeInBaseInteger :: Integer -> Int# -> Word#
185 sizeInBaseInteger (S# i#) = sizeInBaseWord# (int2Word# (absI# i#))
186 sizeInBaseInteger (Jp# bn) = sizeInBaseBigNat bn
187 sizeInBaseInteger (Jn# bn) = sizeInBaseBigNat bn
188
189 -- | Version of 'sizeInBaseInteger' operating on 'BigNat'
190 --
191 -- /Since: 1.0.0.0/
192 sizeInBaseBigNat :: BigNat -> Int# -> Word#
193 sizeInBaseBigNat bn@(BN# ba#) = c_mpn_sizeinbase# ba# (sizeofBigNat# bn)
194
195 foreign import ccall unsafe "integer_gmp_mpn_sizeinbase"
196 c_mpn_sizeinbase# :: ByteArray# -> GmpSize# -> Int# -> Word#
197
198 -- | Version of 'sizeInBaseInteger' operating on 'Word#'
199 --
200 -- /Since: 1.0.0.0/
201 foreign import ccall unsafe "integer_gmp_mpn_sizeinbase1"
202 sizeInBaseWord# :: Word# -> Int# -> Word#
203
204 -- | Dump 'Integer' (without sign) to @/addr/@ in base-256 representation.
205 --
206 -- @'exportIntegerToAddr' /i/ /addr/ /e/@
207 --
208 -- See description of 'exportIntegerToMutableByteArray' for more details.
209 --
210 -- /Since: 1.0.0.0/
211 exportIntegerToAddr :: Integer -> Addr# -> Int# -> IO Word
212 exportIntegerToAddr (S# i#) = exportWordToAddr (W# (int2Word# (absI# i#)))
213 exportIntegerToAddr (Jp# bn) = exportBigNatToAddr bn
214 exportIntegerToAddr (Jn# bn) = exportBigNatToAddr bn
215
216 -- | Version of 'exportIntegerToAddr' operating on 'BigNat's.
217 exportBigNatToAddr :: BigNat -> Addr# -> Int# -> IO Word
218 exportBigNatToAddr bn@(BN# ba#) addr e
219 = c_mpn_exportToAddr# ba# (sizeofBigNat# bn) addr 0# e
220
221 foreign import ccall unsafe "integer_gmp_mpn_export"
222 c_mpn_exportToAddr# :: ByteArray# -> GmpSize# -> Addr# -> Int# -> Int#
223 -> IO Word
224
225 -- | Version of 'exportIntegerToAddr' operating on 'Word's.
226 exportWordToAddr :: Word -> Addr# -> Int# -> IO Word
227 exportWordToAddr (W# w#) addr
228 = c_mpn_export1ToAddr# w# addr 0# -- TODO: we don't calling GMP for that
229
230 foreign import ccall unsafe "integer_gmp_mpn_export1"
231 c_mpn_export1ToAddr# :: GmpLimb# -> Addr# -> Int# -> Int#
232 -> IO Word
233
234 -- | Dump 'Integer' (without sign) to mutable byte-array in base-256
235 -- representation.
236 --
237 -- The call
238 --
239 -- @'exportIntegerToMutableByteArray' /i/ /mba/ /offset/ /msbf/@
240 --
241 -- writes
242 --
243 -- * the 'Integer' @/i/@
244 --
245 -- * into the 'MutableByteArray#' @/mba/@ starting at @/offset/@
246 --
247 -- * with most significant byte first if @msbf@ is @1#@ or least
248 -- significant byte first if @msbf@ is @0#@, and
249 --
250 -- * returns number of bytes written.
251 --
252 -- Use \"@'sizeInBaseInteger' /i/ 256#@\" to compute the exact number of
253 -- bytes written in advance for @/i/ /= 0@. In case of @/i/ == 0@,
254 -- 'exportIntegerToMutableByteArray' will write and report zero bytes
255 -- written, whereas 'sizeInBaseInteger' report one byte.
256 --
257 -- It's recommended to avoid calling 'exportIntegerToMutableByteArray' for small
258 -- integers as this function would currently convert those to big
259 -- integers in msbf to call @mpz_export()@.
260 --
261 -- /Since: 1.0.0.0/
262 exportIntegerToMutableByteArray :: Integer -> MutableByteArray# RealWorld
263 -> Word# -> Int# -> IO Word
264 exportIntegerToMutableByteArray (S# i#)
265 = exportWordToMutableByteArray (W# (int2Word# (absI# i#)))
266 exportIntegerToMutableByteArray (Jp# bn) = exportBigNatToMutableByteArray bn
267 exportIntegerToMutableByteArray (Jn# bn) = exportBigNatToMutableByteArray bn
268
269 -- | Version of 'exportIntegerToMutableByteArray' operating on 'BigNat's.
270 --
271 -- /Since: 1.0.0.0/
272 exportBigNatToMutableByteArray :: BigNat -> MutableByteArray# RealWorld -> Word#
273 -> Int# -> IO Word
274 exportBigNatToMutableByteArray bn@(BN# ba#)
275 = c_mpn_exportToMutableByteArray# ba# (sizeofBigNat# bn)
276
277 foreign import ccall unsafe "integer_gmp_mpn_export"
278 c_mpn_exportToMutableByteArray# :: ByteArray# -> GmpSize#
279 -> MutableByteArray# RealWorld -> Word#
280 -> Int# -> IO Word
281
282 -- | Version of 'exportIntegerToMutableByteArray' operating on 'Word's.
283 --
284 -- /Since: 1.0.0.0/
285 exportWordToMutableByteArray :: Word -> MutableByteArray# RealWorld -> Word#
286 -> Int# -> IO Word
287 exportWordToMutableByteArray (W# w#) = c_mpn_export1ToMutableByteArray# w#
288
289 foreign import ccall unsafe "integer_gmp_mpn_export1"
290 c_mpn_export1ToMutableByteArray# :: GmpLimb# -> MutableByteArray# RealWorld
291 -> Word# -> Int# -> IO Word
292
293
294 -- | Probalistic Miller-Rabin primality test.
295 --
296 -- \"@'testPrimeInteger' /n/ /k/@\" determines whether @/n/@ is prime
297 -- and returns one of the following results:
298 --
299 -- * @2#@ is returned if @/n/@ is definitely prime,
300 --
301 -- * @1#@ if @/n/@ is a /probable prime/, or
302 --
303 -- * @0#@ if @/n/@ is definitely not a prime.
304 --
305 -- The @/k/@ argument controls how many test rounds are performed for
306 -- determining a /probable prime/. For more details, see
307 -- <http://gmplib.org/manual/Number-Theoretic-Functions.html#index-mpz_005fprobab_005fprime_005fp-360 GMP documentation for `mpz_probab_prime_p()`>.
308 --
309 -- /Since: 0.5.1.0/
310 {-# NOINLINE testPrimeInteger #-}
311 testPrimeInteger :: Integer -> Int# -> Int#
312 testPrimeInteger (S# i#) = testPrimeWord# (int2Word# (absI# i#))
313 testPrimeInteger (Jp# n) = testPrimeBigNat n
314 testPrimeInteger (Jn# n) = testPrimeBigNat n
315
316 -- | Version of 'testPrimeInteger' operating on 'BigNat's
317 --
318 -- /Since: 1.0.0.0/
319 testPrimeBigNat :: BigNat -> Int# -> Int#
320 testPrimeBigNat bn@(BN# ba#) = c_integer_gmp_test_prime# ba# (sizeofBigNat# bn)
321
322 foreign import ccall unsafe "integer_gmp_test_prime"
323 c_integer_gmp_test_prime# :: ByteArray# -> GmpSize# -> Int# -> Int#
324
325 -- | Version of 'testPrimeInteger' operating on 'Word#'s
326 --
327 -- /Since: 1.0.0.0/
328 foreign import ccall unsafe "integer_gmp_test_prime1"
329 testPrimeWord# :: GmpLimb# -> Int# -> Int#
330
331
332 -- | Compute next prime greater than @/n/@ probalistically.
333 --
334 -- According to the GMP documentation, the underlying function
335 -- @mpz_nextprime()@ \"uses a probabilistic algorithm to identify
336 -- primes. For practical purposes it's adequate, the chance of a
337 -- composite passing will be extremely small.\"
338 --
339 -- /Since: 0.5.1.0/
340 {-# NOINLINE nextPrimeInteger #-}
341 nextPrimeInteger :: Integer -> Integer
342 nextPrimeInteger (S# i#)
343 | isTrue# (i# ># 1#) = wordToInteger (nextPrimeWord# (int2Word# i#))
344 | True = S# 2#
345 nextPrimeInteger (Jp# bn) = Jp# (nextPrimeBigNat bn)
346 nextPrimeInteger (Jn# _) = S# 2#
347
348 -- | Version of 'nextPrimeInteger' operating on 'Word#'s
349 --
350 -- /Since: 1.0.0.0/
351 foreign import ccall unsafe "integer_gmp_next_prime1"
352 nextPrimeWord# :: GmpLimb# -> GmpLimb#