Re-implement `testPrimeInteger` 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 -- * Import/export functions
129 -- ** Compute size of serialisation
130 , sizeInBaseBigNat
131 , sizeInBaseInteger
132 , sizeInBaseWord#
133
134 -- ** Export
135 , exportBigNatToAddr
136 , exportIntegerToAddr
137 , exportWordToAddr
138
139 , exportBigNatToMutableByteArray
140 , exportIntegerToMutableByteArray
141 , exportWordToMutableByteArray
142
143 -- ** Import
144
145 , importBigNatFromAddr
146 , importIntegerFromAddr
147
148 , importBigNatFromByteArray
149 , importIntegerFromByteArray
150 ) where
151
152 import GHC.Integer.Type
153 import GHC.Integer
154 import GHC.Prim
155 import GHC.Types
156
157 default ()
158
159
160 -- | Compute number of digits (without sign) in given @/base/@.
161 --
162 -- This function wraps @mpz_sizeinbase()@ which has some
163 -- implementation pecularities to take into account:
164 --
165 -- * \"@'sizeInBaseInteger' 0 /base/ = 1@\"
166 -- (see also comment in 'exportIntegerToMutableByteArray').
167 --
168 -- * This function is only defined if @/base/ >= 2#@ and @/base/ <= 256#@
169 -- (Note: the documentation claims that only @/base/ <= 62#@ is
170 -- supported, however the actual implementation supports up to base 256).
171 --
172 -- * If @/base/@ is a power of 2, the result will be exact. In other
173 -- cases (e.g. for @/base/ = 10#@), the result /may/ be 1 digit too large
174 -- sometimes.
175 --
176 -- * \"@'sizeInBaseInteger' /i/ 2#@\" can be used to determine the most
177 -- significant bit of @/i/@.
178 --
179 -- /Since: 0.5.1.0/
180 sizeInBaseInteger :: Integer -> Int# -> Word#
181 sizeInBaseInteger (S# i#) = sizeInBaseWord# (int2Word# (absI# i#))
182 sizeInBaseInteger (Jp# bn) = sizeInBaseBigNat bn
183 sizeInBaseInteger (Jn# bn) = sizeInBaseBigNat bn
184
185 -- | Version of 'sizeInBaseInteger' operating on 'BigNat'
186 --
187 -- /Since: 1.0.0.0/
188 sizeInBaseBigNat :: BigNat -> Int# -> Word#
189 sizeInBaseBigNat bn@(BN# ba#) = c_mpn_sizeinbase# ba# (sizeofBigNat# bn)
190
191 foreign import ccall unsafe "integer_gmp_mpn_sizeinbase"
192 c_mpn_sizeinbase# :: ByteArray# -> GmpSize# -> Int# -> Word#
193
194 -- | Version of 'sizeInBaseInteger' operating on 'Word#'
195 --
196 -- /Since: 1.0.0.0/
197 foreign import ccall unsafe "integer_gmp_mpn_sizeinbase1"
198 sizeInBaseWord# :: Word# -> Int# -> Word#
199
200 -- | Dump 'Integer' (without sign) to @/addr/@ in base-256 representation.
201 --
202 -- @'exportIntegerToAddr' /i/ /addr/ /e/@
203 --
204 -- See description of 'exportIntegerToMutableByteArray' for more details.
205 --
206 -- /Since: 1.0.0.0/
207 exportIntegerToAddr :: Integer -> Addr# -> Int# -> IO Word
208 exportIntegerToAddr (S# i#) = exportWordToAddr (W# (int2Word# (absI# i#)))
209 exportIntegerToAddr (Jp# bn) = exportBigNatToAddr bn
210 exportIntegerToAddr (Jn# bn) = exportBigNatToAddr bn
211
212 -- | Version of 'exportIntegerToAddr' operating on 'BigNat's.
213 exportBigNatToAddr :: BigNat -> Addr# -> Int# -> IO Word
214 exportBigNatToAddr bn@(BN# ba#) addr e
215 = c_mpn_exportToAddr# ba# (sizeofBigNat# bn) addr 0# e
216
217 foreign import ccall unsafe "integer_gmp_mpn_export"
218 c_mpn_exportToAddr# :: ByteArray# -> GmpSize# -> Addr# -> Int# -> Int#
219 -> IO Word
220
221 -- | Version of 'exportIntegerToAddr' operating on 'Word's.
222 exportWordToAddr :: Word -> Addr# -> Int# -> IO Word
223 exportWordToAddr (W# w#) addr
224 = c_mpn_export1ToAddr# w# addr 0# -- TODO: we don't calling GMP for that
225
226 foreign import ccall unsafe "integer_gmp_mpn_export1"
227 c_mpn_export1ToAddr# :: GmpLimb# -> Addr# -> Int# -> Int#
228 -> IO Word
229
230 -- | Dump 'Integer' (without sign) to mutable byte-array in base-256
231 -- representation.
232 --
233 -- The call
234 --
235 -- @'exportIntegerToMutableByteArray' /i/ /mba/ /offset/ /msbf/@
236 --
237 -- writes
238 --
239 -- * the 'Integer' @/i/@
240 --
241 -- * into the 'MutableByteArray#' @/mba/@ starting at @/offset/@
242 --
243 -- * with most significant byte first if @msbf@ is @1#@ or least
244 -- significant byte first if @msbf@ is @0#@, and
245 --
246 -- * returns number of bytes written.
247 --
248 -- Use \"@'sizeInBaseInteger' /i/ 256#@\" to compute the exact number of
249 -- bytes written in advance for @/i/ /= 0@. In case of @/i/ == 0@,
250 -- 'exportIntegerToMutableByteArray' will write and report zero bytes
251 -- written, whereas 'sizeInBaseInteger' report one byte.
252 --
253 -- It's recommended to avoid calling 'exportIntegerToMutableByteArray' for small
254 -- integers as this function would currently convert those to big
255 -- integers in msbf to call @mpz_export()@.
256 --
257 -- /Since: 1.0.0.0/
258 exportIntegerToMutableByteArray :: Integer -> MutableByteArray# RealWorld
259 -> Word# -> Int# -> IO Word
260 exportIntegerToMutableByteArray (S# i#)
261 = exportWordToMutableByteArray (W# (int2Word# (absI# i#)))
262 exportIntegerToMutableByteArray (Jp# bn) = exportBigNatToMutableByteArray bn
263 exportIntegerToMutableByteArray (Jn# bn) = exportBigNatToMutableByteArray bn
264
265 -- | Version of 'exportIntegerToMutableByteArray' operating on 'BigNat's.
266 --
267 -- /Since: 1.0.0.0/
268 exportBigNatToMutableByteArray :: BigNat -> MutableByteArray# RealWorld -> Word#
269 -> Int# -> IO Word
270 exportBigNatToMutableByteArray bn@(BN# ba#)
271 = c_mpn_exportToMutableByteArray# ba# (sizeofBigNat# bn)
272
273 foreign import ccall unsafe "integer_gmp_mpn_export"
274 c_mpn_exportToMutableByteArray# :: ByteArray# -> GmpSize#
275 -> MutableByteArray# RealWorld -> Word#
276 -> Int# -> IO Word
277
278 -- | Version of 'exportIntegerToMutableByteArray' operating on 'Word's.
279 --
280 -- /Since: 1.0.0.0/
281 exportWordToMutableByteArray :: Word -> MutableByteArray# RealWorld -> Word#
282 -> Int# -> IO Word
283 exportWordToMutableByteArray (W# w#) = c_mpn_export1ToMutableByteArray# w#
284
285 foreign import ccall unsafe "integer_gmp_mpn_export1"
286 c_mpn_export1ToMutableByteArray# :: GmpLimb# -> MutableByteArray# RealWorld
287 -> Word# -> Int# -> IO Word
288
289
290 -- | Probalistic Miller-Rabin primality test.
291 --
292 -- \"@'testPrimeInteger' /n/ /k/@\" determines whether @/n/@ is prime
293 -- and returns one of the following results:
294 --
295 -- * @2#@ is returned if @/n/@ is definitely prime,
296 --
297 -- * @1#@ if @/n/@ is a /probable prime/, or
298 --
299 -- * @0#@ if @/n/@ is definitely not a prime.
300 --
301 -- The @/k/@ argument controls how many test rounds are performed for
302 -- determining a /probable prime/. For more details, see
303 -- <http://gmplib.org/manual/Number-Theoretic-Functions.html#index-mpz_005fprobab_005fprime_005fp-360 GMP documentation for `mpz_probab_prime_p()`>.
304 --
305 -- /Since: 0.5.1.0/
306 {-# NOINLINE testPrimeInteger #-}
307 testPrimeInteger :: Integer -> Int# -> Int#
308 testPrimeInteger (S# i#) = testPrimeWord# (int2Word# (absI# i#))
309 testPrimeInteger (Jp# n) = testPrimeBigNat n
310 testPrimeInteger (Jn# n) = testPrimeBigNat n
311
312 -- | Version of 'testPrimeInteger' operating on 'BigNat's
313 --
314 -- /Since: 1.0.0.0/
315 testPrimeBigNat :: BigNat -> Int# -> Int#
316 testPrimeBigNat bn@(BN# ba#) = c_integer_gmp_test_prime# ba# (sizeofBigNat# bn)
317
318 foreign import ccall unsafe "integer_gmp_test_prime"
319 c_integer_gmp_test_prime# :: ByteArray# -> GmpSize# -> Int# -> Int#
320
321 -- | Version of 'testPrimeInteger' operating on 'Word#'s
322 --
323 -- /Since: 1.0.0.0/
324 foreign import ccall unsafe "integer_gmp_test_prime1"
325 testPrimeWord# :: GmpLimb# -> Int# -> Int#