summaryrefslogtreecommitdiff
path: root/libraries/integer-gmp/cbits
Commit message (Collapse)AuthorAgeFilesLines
* Update integer_gmp_gcdext documentation.David Eichmann2018-10-151-7/+7
| | | | | | | | | | | | Reviewers: hvr, bgamari, monoidal Reviewed By: monoidal Subscribers: rwbarton, carter GHC Trac Issues: #15350 Differential Revision: https://phabricator.haskell.org/D5091
* Correct limb length and assertion for gcdExtIntegerDavidEichamnn2018-08-211-3/+13
| | | | | | | | | | | | Reviewers: hvr, bgamari, monoidal Reviewed By: monoidal Subscribers: monoidal, rwbarton, thomie, carter GHC Trac Issues: #15350 Differential Revision: https://phabricator.haskell.org/D5042
* Restore function powModSecIntegerOlivier Chéron2017-09-191-1/+60
| | | | | | | | | | | | | | | The function existed in integer-gmp-0.5.1.0 but was removed as part of integer-gmp2 rewrite in #9281. This is to bring it back. Test Plan: Case integerGmpInternals, with GMP 4.3.2 and GMP 6.1.2 Reviewers: austin, hvr, goldfire, bgamari Reviewed By: bgamari Subscribers: rwbarton, thomie Differential Revision: https://phabricator.haskell.org/D3947
* Make function intToSBigNat# preserve sign (fixes #14085)Olivier Chéron2017-08-171-1/+1
| | | | | | | | | | | | | | | | | | | Impacts only functions gcdExtInteger, powModInteger and recipModInteger which gave invalid results on negative S# inputs. Also fixes gcdExtInteger assertion when first argument is negative. Test Plan: Updated test case integerGmpInternals Reviewers: austin, hvr, goldfire, bgamari Reviewed By: bgamari Subscribers: rwbarton, thomie GHC Trac Issues: #14085 Differential Revision: https://phabricator.haskell.org/D3826
* Fix the right-shift operation for negative big integers (fixes #12136)Daishi Nakajima2017-01-261-3/+11
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | In `x shiftR y`, any of the following conditions cause an abort: - `x` is a negative big integer - The size of `x` and `y` is a multiple of `GMP_NUMB_BITS` - The bit of the absolute value of `x` is filled with `1` For example: Assuming `GMP_NUMB_BITS = 2`, the processing of `-15 shiftR 2` is as follows: 1. -15 = -1111 (twos complement: 10001) 2. right shift 2 (as a positive number) -> 0011 3. Due to the shift larger than GMP_NUMB_BITS, the size of the destination is decreasing (2bit) -> 11 4. Add 1, and get carry: (1) 00 5. abort I fixed it that the destination size does not decrease in such a case. Test Plan: I tested the specific case being reported. Reviewers: goldfire, austin, hvr, bgamari, rwbarton Reviewed By: bgamari, rwbarton Subscribers: mpickering, rwbarton, thomie Differential Revision: https://phabricator.haskell.org/D2998 GHC Trac Issues: #12136
* Drop old integer-gmp-0.5 from GHC source treeHerbert Valerio Riedel2015-03-316-1249/+832
| | | | | | | | | | | | | | | | | | 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
* Revert "Rename _closure to _static_closure, apply naming consistently."Edward Z. Yang2014-10-201-2/+2
| | | | | | | This reverts commit 35672072b4091d6f0031417bc160c568f22d0469. Conflicts: compiler/main/DriverPipeline.hs
* Rename _closure to _static_closure, apply naming consistently.Edward Z. Yang2014-10-011-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: In preparation for indirecting all references to closures, we rename _closure to _static_closure to ensure any old code will get an undefined symbol error. In order to reference a closure foobar_closure (which is now undefined), you should instead use STATIC_CLOSURE(foobar). For convenience, a number of these old identifiers are macro'd. Across C-- and C (Windows and otherwise), there were differing conventions on whether or not foobar_closure or &foobar_closure was the address of the closure. Now, all foobar_closure references are addresses, and no & is necessary. CHARLIKE/INTLIKE were not changed, simply alpha-renamed. Part of remove HEAP_ALLOCED patch set (#8199) Depends on D265 Signed-off-by: Edward Z. Yang <ezyang@mit.edu> Test Plan: validate Reviewers: simonmar, austin Subscribers: simonmar, ezyang, carter, thomie Differential Revision: https://phabricator.haskell.org/D267 GHC Trac Issues: #8199
* Fix GMP v4 compatibility.Austin Seipp2014-02-261-0/+8
| | | | | | | | | | | | | | | | | | 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>
* Introduce new SIZEOF_MP_LIMB_T derived constantHerbert Valerio Riedel2014-01-162-9/+6
| | | | | | | | This allows to simplify code in `float.c` and to encode the "sizeof(mp_limb_t) != sizeof(W_)" assumption as a compile-time assertion. Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Use correct package id for `stg_INTLIKE_closure` importHerbert Valerio Riedel2014-01-141-1/+1
| | | | | | | | I'm a bit surprised though this didn't cause linkage errors (the incorrect import statement was introduced in 7bdcadda7e) Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Wrap `gmpz_fdiv_{q,r,qr}_ui` to optimize `div`/`mod`Herbert Valerio Riedel2014-01-131-0/+8
| | | | | | | | | | | | | | 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-131-68/+156
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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-1/+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>
* Wrap `gmpz_tdiv_{q,r,qr}_ui` to optimize `quot`/`rem`Herbert Valerio Riedel2014-01-081-0/+33
| | | | | | | | | | | | | | | | | 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-041-0/+34
| | | | | | | | | | | | | | | | | | | | | | | | | 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-041-0/+2
| | | | | | | | | | | 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>
* Refactor C-- wrappers to use macros for mpz_t accessHerbert Valerio Riedel2014-01-041-90/+43
| | | | | | | This factors out the recurring task of converting mpz_t structures to/from Int#/ByteArrays# pairs and makes the code more readable. Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Refactor `stgReallocForGMP` to use `memcpy`Herbert Valerio Riedel2014-01-031-13/+5
| | | | | | | | | | GCC is able to generate better code when using `memcpy` instead of manually copying bytes in a loop. Otoh, `stgAllocForGMP` is typically called for enlarging initial single-limb structures (see also #8647 for more information) and so this minor optimization won't be very visible in measurements. Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Add `Addr#` based `{import,export}Integer` variantsHerbert Valerio Riedel2013-11-071-0/+42
| | | | | | | 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-071-2/+2
| | | | | | | | | | | | | 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>
* Clean-up Cmm of import/export primitivesHerbert Valerio Riedel2013-11-051-16/+17
| | | | | | | This is a follow-up to e94799c9 fixing the Cmm implementation of the primops based on suggestions by Duncan Coutts. Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Add primitives to write/read Integers to/from bytearraysHerbert Valerio Riedel2013-11-051-0/+50
| | | | | | | | | | | | | | | | | | | | 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-281-1/+30
| | | | | | | | 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-271-0/+2
| | | | | | | This is a follow-up to 97c101b7363f84d925a600acb56a9fa3a997ea0d which introduced the "ordinary" `powModInteger` operation. Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
* Expose GMP's `mpz_gcdext()` as internal primitiveHerbert Valerio Riedel2013-09-291-0/+3
| | | | | | | 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-291-0/+48
| | | | | | | | 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>
* Build system refactoringIan Lynagh2013-04-201-74/+0
|
* integer-gmp: mpn_gcd_1 allocate one Word on stack instead of 'sizeof ↵Sergei Trofimovich2013-03-171-2/+2
| | | | | | | | | (__mpz_struct)' gmp.h defines 'mpn_gcd_1' as following: mp_limb_t mpn_gcd_1 (mp_srcptr /* aka 'mp_limb_t *' */, mp_size_t, mp_limb_t); Signed-off-by: Sergei Trofimovich <slyfox@gentoo.org>
* Revert "integer-gmp: improve cross-compiling support GmpDerivedConstants.h"Simon Marlow2013-01-262-10/+74
| | | | | | | This reverts commit 860f2fa9a1f1ca4f8d94388723687f90d122ae81. People reported problems with it on the mailing list, so reverting until we can figure out the cause.
* integer-gmp: improve cross-compiling support GmpDerivedConstants.hSergei Trofimovich2013-01-242-74/+10
| | | | | | | | | | Before the patch GmpDerivedConstants.h was generated by running mkGmpDerivedConstants on target. Now it's generated only with help of autoconf macros. Tested on --target=ia64-unknown-linux-gnu. Signed-off-by: Sergei Trofimovich <slyfox@gentoo.org>
* zap obsolete FIXME, fix typosGabor Greif2012-12-141-5/+3
|
* fix type mismatch in result of integer_cmm_testBitIntegerzhSimon Marlow2012-10-221-1/+1
|
* Adapt to new Cmm syntaxSimon Marlow2012-10-041-244/+182
|
* Fix building on WindowsIan Lynagh2012-08-071-0/+1
|
* Define testBitInteger; part of #3489Ian Lynagh2012-08-051-0/+31
| | | | Based on a patch from pumpkingod@gmail.com
* Whitespace only: Line some things up betterIan Lynagh2012-08-051-18/+18
|
* Add missing imports.Paolo Capriotti2012-06-271-0/+2
|
* Use CLong, not CInt, for mp_bitcnt_t value; fixes #5965Ian Lynagh2012-06-201-2/+2
| | | | | | | | The GMP docs say: Counts of bits of a multi-precision number are represented in the C type mp_bitcnt_t. Currently this is always an unsigned long, but on some systems it will be an unsigned long long in the future.
* Add divInteger and modInteger functionsIan Lynagh2012-06-191-0/+2
| | | | | Now that divModInteger isn't inlined, we were getting allocations for both results even if we're just going to throw one away.
* Fix compilation under LLVM backend. (#5965)David Terei2012-03-281-1/+1
| | | | Recent change means ul is truncate to an int, not a long anymore.
* Win64 fixIan Lynagh2012-03-151-1/+1
|
* Track changes to the way we reference CCCS in GHC (was: W_[CCCS], now: CCCS)Simon Marlow2011-12-011-5/+5
|
* update to track changes to CCCS in the RTSSimon Marlow2011-11-291-2/+4
|
* Eliminate intermediate overflow for encodeFloat, fixes #5524Daniel Fischer2011-10-011-4/+90
|
* Untabify cbits/float.cDaniel Fischer2011-10-011-35/+35
|
* implement integer2Int# and integer2Word# in Haskell, not foreign primSimon Marlow2010-08-131-38/+0
|
* Follow SET_ARR_HDR changeIan Lynagh2010-06-191-1/+1
|
* Replace an (incorrect) bytes-to-words calculation with ROUNDUP_BYTES_TO_WDSIan Lynagh2010-06-191-1/+1
|
* FIX #38000 Store StgArrWords payload size in bytesAntoine Latter2010-01-011-11/+11
|
View Lorry Controller Status