summaryrefslogtreecommitdiff
path: root/libraries/integer-gmp/GHC
Commit message (Collapse)AuthorAgeFilesLines
* Drop old integer-gmp-0.5 from GHC source treeHerbert Valerio Riedel2015-03-316-1802/+0
| | | | | | | | | | | | | | | | | | This completes what c774b28f76ee4c220f7c1c9fd81585e0e3af0e8a (#9281) started. `integer-gmp-1.0` was added as an additional `libraries/integer-gmp2` folder while retaining the ability to configure GHC w/ the old `integer-gmp-0.5` to have a way back, and or the ability to easily switch between old/new `integer-gmp` for benchmark/debugging purposes. This commit removes the old `libraries/integer-gmp` folder and moves `libraries/integer-gmp2` into its place, while removing any mentions of "gmp2" as well as the to support two different `integer-gmp` packages in GHC's source-tree. Reviewed By: austin Differential Revision: https://phabricator.haskell.org/D769
* Fix GMP v4 compatibility.Austin Seipp2014-02-261-0/+10
| | | | | | | | | | | | | | | | | | We had started relying on GMP 5.x (for usage of mpz_powm_sec), but this is pretty painful on RHEL-esque targets, which still use GMP 4.x. In the mean time while we're still supporting this, it's easier to just fallback to mpz_powm when _sec is unavailable, and emit a WARNING for using the primitive. This also installs a header, HsIntegerGmp.h, which clients could use for a fallback. As a side note, this will probably also help Debian oldstable users who might have outdated GMP versions (which I believe is the cause for #8666.) Reviewed-by: Herbert Valerio Riedel <hvr@gnu.org> Signed-off-by: Austin Seipp <austin@well-typed.com>
* Fix negation of `divMod`/`quotRem` results (fixes #8726)Herbert Valerio Riedel2014-02-021-7/+7
| | | | | | | | | | | | | | | | | | | | | | | High-level pseudo code of what the code was supposed to implement: quotRem' :: Integer -> Integer -> (Integer,Integer) quotRem' a b@(S# _) | b < 0 = negFst . uncurry quotRem' . negSnd $ (a,b) | otherwise = quotRemUI a (fromIntegral (abs b)) divMod' :: Integer -> Integer -> (Integer,Integer) divMod' a b@(S# _) | b < 0 = negSnd . uncurry divMod' . negBoth $ (a,b) | otherwise = divModUI a (fromIntegral b) negFst (q,r) = (-q,r) negSnd (q,r) = ( q,-r) negBoth (q,r) = (-q,-r) -- quotRemUI and divModUI represent GMP's `mpz_{f,t}div_qr_ui()` quotRemUI, divModUI :: Integer -> Word -> (Integer,Integer) Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Improve documentation of `integer-gmp`Herbert Valerio Riedel2014-01-313-31/+105
| | | | | | | | Among other things, this unhides `GHC.Integer` and re-groups the export list. Moreover, the internal representation of `Integer` is explained a bit more, and `/Since: 0.5.1.0/` annotations have been added. Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Dont use big/small-int primops on IL32P64 (i.e. Win/x86_64) for nowHerbert Valerio Riedel2014-01-171-9/+78
| | | | | | | | | | | | | | This is due to `mpz_*()` functions having @long@ arguments which are 32bit on IL32P64, whereas `Int#` and `Word#` are 64bit wide, causing all sorts of malfunction due to truncation. This affects mostly the new big/small-int primops introduced in the course of #8647, so when `SIZEOF_W != SIZEOF_LONG` we simply fall back to using the big/big-int primops. big/small primops implemented via the low-level `mpn_*()` GMP operations are not affected, as those use `mp_limb_t` arguments. Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Wrap `gmpz_fdiv_{q,r,qr}_ui` to optimize `div`/`mod`Herbert Valerio Riedel2014-01-132-10/+33
| | | | | | | | | | | | | | This is similiar to what has been done in [af2ba9c8/integer-gmp] for `gmpz_tdiv_{q,r,qr}_ui` (re #8647); However, the gain is more modest here, as performance-conscious code tends to use `quot`/`rem` rather than `div`/`mod`: Program Size Allocs Runtime Elapsed TotalMem ------------------------------------------------------------- primetest +0.3% -2.4% 0.06 0.06 +0.0% rsa +0.2% -3.3% 0.02 0.02 +0.0% Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Allocate initial 1-limb mpz_t on the Stack and introduce MPZ# typeHerbert Valerio Riedel2014-01-132-119/+150
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | We now allocate a 1-limb mpz_t on the stack instead of doing a more expensive heap-allocation (especially if the heap-allocated copy becomes garbage right away); this addresses #8647. In order to delay heap allocations of 1-limb `ByteArray#`s instead of the previous `(# Int#, ByteArray# #)` pair, a 3-tuple `(# Int#, ByteArray#, Word# #)` is returned now. This tuple is given the type-synonym `MPZ#`. This 3-tuple representation uses either the 1st and the 2nd element, or the 1st and the 3rd element to represent the limb(s) (NB: undefined `ByteArray#` elements must not be accessed as they don't point to a proper `ByteArray#`, see also `DUMMY_BYTE_ARR`); more specifically, the following encoding is used (where `⊥` means undefined/unused): - (# 0#, ⊥, 0## #) -> value = 0 - (# 1#, ⊥, w #) -> value = w - (# -1#, ⊥, w #) -> value = -w - (# s#, d, 0## #) -> value = J# s d The `mpzToInteger` helper takes care of converting `MPZ#` into an `Integer`, and allocating a 1-limb `ByteArray#` in case the value (`w`/`-w`) doesn't fit the `S# Int#` representation). The following nofib benchmarks benefit from this optimization: Program Size Allocs Runtime Elapsed TotalMem ------------------------------------------------------------------ bernouilli +0.2% -5.2% 0.12 0.12 +0.0% gamteb +0.2% -1.7% 0.03 0.03 +0.0% kahan +0.3% -13.2% 0.17 0.17 +0.0% mandel +0.2% -24.6% 0.04 0.04 +0.0% power +0.2% -2.6% -2.0% -2.0% -8.3% primetest +0.1% -17.3% 0.06 0.06 +0.0% rsa +0.2% -18.5% 0.02 0.02 +0.0% scs +0.1% -2.9% -0.1% -0.1% +0.0% sphere +0.3% -0.8% 0.03 0.03 +0.0% symalg +0.2% -3.1% 0.01 0.01 +0.0% ------------------------------------------------------------------ Min +0.1% -24.6% -4.6% -4.6% -8.3% Max +0.3% +0.0% +5.9% +5.9% +4.5% Geometric Mean +0.2% -1.0% +0.2% +0.2% -0.0% Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Drop redundant formal parameter from TAKE1_UL1_RET2Herbert Valerio Riedel2014-01-111-9/+1
| | | | | | | | | | | This fixes the actual cause for #8661, i.e. a mismatch between the actual arity of the Cmm implementation and the arity declared in the foreign import statement. This also reverts [a3878d17/integer-gmp] as the workaround isn't needed anymore. Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Follow-up to a3878d17Herbert Valerio Riedel2014-01-101-1/+4
| | | | | | Forgot to add this chunk to the commit [a3878d17/integer-gmp] Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Temporary disable `mpz_gmpz_tdiv_qr_ui` to workaround #8661Herbert Valerio Riedel2014-01-101-1/+6
| | | | | | | | | | | I still need to investigated, but for some reason not yet obvious to me, commit [af2ba9c8/integer-gmp] (re #8647) seems to have triggered #8661 on linux/32 This commit disables the use of the `quotRemIntegerWord#` primop on 32bit (which seems to trigger the issue). Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Manually float out `int2Integer# INT_MINBOUND`Herbert Valerio Riedel2014-01-081-9/+13
| | | | | | | This avoids allocating this special value over and over again every time it's needed, and therefore this addresses #8647. Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Wrap `gmpz_tdiv_{q,r,qr}_ui` to optimize `quot`/`rem`Herbert Valerio Riedel2014-01-082-7/+38
| | | | | | | | | | | | | | | | | This is useful as `quot`/`rem` are often used with small-int divisors, like when computing the digits of an `Integer`. This optimization reduces allocations in the following `nofib` benchmarks: Program Size Allocs Runtime Elapsed TotalMem ----------------------------------------------------------------- power +0.3% -0.8% -1.2% -1.2% +0.0% primetest +0.3% -3.9% 0.07 0.07 +0.0% rsa +0.3% -4.0% 0.02 0.02 +0.0% symalg +0.2% -1.4% 0.01 0.01 +0.0% This addresses #8647 Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Add new `mpz_{sub,add}_ui`-based primop (re #8647)Herbert Valerio Riedel2014-01-042-10/+32
| | | | | | | | | | | | | | | | | | | | | | | | | This adds `{plus,minus}IntegerInt#` which help to reduce temporary allocations in `plusInteger` and `minusInteger`. This and the previous commit introducing `timesIntegerInt#` (i.e. baeeef7af6e) result in reduced allocations for the following nofib benchmarks on Linux/amd64: Program Size Allocs Runtime Elapsed TotalMem ------------------------------------------------------------------ bernouilli +0.0% -4.2% 0.12 0.12 +0.0% kahan +0.1% -12.6% 0.17 0.17 +0.0% pidigits +0.0% -0.5% -4.7% -4.5% +0.0% power +0.0% -2.7% +3.1% +3.1% +9.1% primetest +0.0% -4.2% 0.07 0.07 +0.0% rsa +0.0% -4.1% 0.02 0.02 +0.0% scs +0.0% -2.6% -0.8% -0.7% +0.0% ------------------------------------------------------------------ Min +0.0% -12.6% -4.7% -4.5% -5.0% Max +0.1% +0.2% +3.1% +3.1% +9.1% Geometric Mean +0.1% -0.3% -0.0% +0.0% +0.1% ------------------------------------------------------------------ Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Add new `mpz_mul_si`-based primop (re #8647)Herbert Valerio Riedel2014-01-042-4/+13
| | | | | | | | | | | This primop helps reducing allocation by being able to pass one `S#` argument directly to the GMP multiplication primitive without needing to promote (and thus allocate a `ByteArray#` as well) the `J#` first. This benefits a few nofib benchmarks wrt to allocations (having most impact on `kahan` resulting in about 10% less allocations) Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Make use of `quotRemInt#` primop in `quotRemInteger`Herbert Valerio Riedel2014-01-031-10/+7
| | | | | | | | Otoh, `divModInt#` is not a proper primop (it's implemented as wrapper around `quotRemInt#` in `GHC.Base`), so we can't do the same for `divModInteger` yet. Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Refactor and comment the smartJ# changes (re Trac #8638)Simon Peyton Jones2014-01-031-9/+41
|
* Try harder to demote results from `J#` to `S#` (re #8638)Herbert Valerio Riedel2014-01-021-33/+59
| | | | Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Improve Haddock documentationHerbert Valerio Riedel2013-11-082-47/+95
| | | | Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Optimize order of pattern matches for export operationsHerbert Valerio Riedel2013-11-071-2/+2
| | | | | | | These are supposed to be called with `J#`-kind `Integer`s, so check that constructor first. Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Add `Addr#` based `{import,export}Integer` variantsHerbert Valerio Riedel2013-11-073-6/+37
| | | | | | | These follow closely the existing implementations for `importIntegerFromByteArray` and `exportIntegerToMutableByteArray`. Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Rename `{import,export}Integer`Herbert Valerio Riedel2013-11-073-19/+19
| | | | | | | | | | | | | This renames to more verbose names which include the type these operations import/export from/to: - `importIntegerFromByteArray`, and - `exportIntegerToMutableByteArray`. This follows the naming convention used for other primitive operations, such as the recently added `copyMutableByteArrayToAddr` operation. Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Add primitives to write/read Integers to/from bytearraysHerbert Valerio Riedel2013-11-053-2/+92
| | | | | | | | | | | | | | | | | | | | This adds the following new (internal) primitives {{{#!hs sizeInBaseInteger :: Integer -> Int# -> Word# exportInteger :: Integer -> MutableByteArray# s -> Word# -> Int# -> State# s -> (# State# s, Word# #) importInteger :: ByteArray# -> Word# -> Word# -> Int# -> Integer }}} The import/export primitives support selecting most/least significant byte first order as well as using an offset into the byte-arrays. See Haddock comments for more details. Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Expose two GMP primality operationsHerbert Valerio Riedel2013-10-283-2/+46
| | | | | | | | This exposes `mpz_probab_prime_p()` and `mpz_nextprime()` as `testPrimeInteger` and `nextPrimeInteger` respectively and is especially useful for cryptographic algorithms such as RSA. Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Add side-channel attack resilient `powModSecInteger`Herbert Valerio Riedel2013-10-273-2/+22
| | | | | | | This is a follow-up to 97c101b7363f84d925a600acb56a9fa3a997ea0d which introduced the "ordinary" `powModInteger` operation. Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Refactor & modernize `.cabal` to `cabal-version>=1.10`Herbert Valerio Riedel2013-10-242-4/+3
| | | | | | | | | This sets a sensible cabal category (i.e. `Numerical`), extends `extra-tmp-{files,files}` to make this package self-contained, updates the bug-report URL, and cleans up the `{-# LANGUAGE #-}` pragma usage in the source code. Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Expose GMP's `mpz_gcdext()` as internal primitiveHerbert Valerio Riedel2013-09-293-2/+19
| | | | | | | The extended GCD computation is useful to have for implementing algorithms such as the chinese reminder theorem. Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Expose new internal exponentiation primitivesHerbert Valerio Riedel2013-09-293-1/+59
| | | | | | | | This exposes the GMP functions `mpz_pow_ui()`, `mpz_powm()`, and `mpz_invert()` as `powInteger`, `powModInteger`, and `recipModInteger` respectively in the module `GHC.Integer.GMP.Internals`. Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Follow changes in comparison primops (see #6135)Jan Stolarek2013-09-163-96/+91
|
* Comments onlyJan Stolarek2013-08-191-0/+6
| | | | Link to documentation of library on the wiki
* Comparison primops return Int# (Fixes #6135)Jan Stolarek2013-07-194-44/+70
| | | | | For a deatiled discussion of this changes please visit the wiki page: http://hackage.haskell.org/trac/ghc/wiki/PrimBool
* Define testBitInteger; part of #3489Ian Lynagh2012-08-053-2/+13
| | | | Based on a patch from pumpkingod@gmail.com
* Simplify how gcd @ Int is implementedIan Lynagh2012-07-182-11/+2
|
* Move some rules into PrelRulesIan Lynagh2012-07-181-10/+0
|
* Add another gcdInteger ruleIan Lynagh2012-07-131-3/+8
| | | | This one is better when the result is converted to an Int
* Tweak RULEs; fixes #7041Ian Lynagh2012-07-131-6/+3
| | | | | | | In particular, the gcd rule now uses smallInteger rather than S#, which means that it actually fires. Also fixed a bug when the result is minBound :: Int.
* Add divInteger and modInteger functionsIan Lynagh2012-06-193-2/+33
| | | | | Now that divModInteger isn't inlined, we were getting allocations for both results even if we're just going to throw one away.
* Use divInt#/modInt# from ghc-primIan Lynagh2012-06-191-16/+1
|
* Add some rules; fixes #5767Ian Lynagh2012-01-261-0/+10
| | | | | | | | We now have rules for integerToInt (smallInteger x) = x integerToWord (wordToInteger x) = x integerToInt64 (int64ToInteger x) = x integerToWord64 (word64ToInteger x) = x
* Define mkIntegerIan Lynagh2011-09-172-1/+11
| | | | Now used by GHC to generate Integer literals.
* Export GMP-only functions from the Internals moduleIan Lynagh2011-09-131-1/+1
|
* NOINLINE a couple more functionsIan Lynagh2011-09-131-2/+2
| | | | | We don't need them to be inlined at all, following changes in how GHC handles Integers.
* Don't export gcdInteger, lcmInteger from GHC.IntegerIan Lynagh2011-09-131-1/+1
| | | | integer-simple doesn't export them
* Follow ghc-prim changesIan Lynagh2011-08-261-1/+0
|
* Export Integer(..) from GHC.Integer.GMP.Internals again; fixes #5419Ian Lynagh2011-08-253-194/+200
| | | | The GMP primitives are now in GHC.Integer.GMP.Prim instead.
* Eliminate orphan instancesIan Lynagh2011-07-303-569/+567
| | | | | The type and implementation are now in the same module, so the orphan instances are no longer orphaned.
* No need to export Integer from GHC.Integer.GMP.InternalsIan Lynagh2011-07-302-5/+2
| | | | This caused an odd dependency in the module hierarchy.
* Don't inline most integer operationsIan Lynagh2011-07-231-6/+37
| | | | | | We get lots of code, and the simplifier generally can't do much with it. We'll instead use builtin rules to do constant folding where possible.
* Rename toInt# -> integerToInt for consistencyIan Lynagh2011-07-231-8/+8
|
* Fix build following modules moving aroundIan Lynagh2011-07-221-11/+3
|
* Eq and Ord instances are now in the integer package, not baseIan Lynagh2011-07-221-0/+12
|
View Lorry Controller Status