

# Design of `IntegerGmp2` ([\#9281](https://gitlab.haskell.org//ghc/ghc/issues/9281))









This wiki page is meant as a scratchpad to describe the plans/ideas behind the `integergmp2` rewrite






## Motivations






 allow to avoid the custom GMP allocator hack, and thus



 avoid issues when linking against other C libraries using GMP,



 simplify code, as we would perform all heap allocations in Haskell code (and never inside Cmm/C code as its done now),



 maybe even remove a few more superfluous temporary heap allocations.



 linktime selectable integerlibrary backend (think `ghc make O fintegerlibrary=bsdnt` Hello.hs)






 simplifies handling on platforms where GMP is not a systemlibrary (mostly OSX and Windows)



 user code can still link with GMP, even though the primitive operation use `bsdnt`



 Allow to implement (big) Natural number type w/o redundant sign handling






## Rough Design






### Haskellside API Types






```



  Type representing /raw/ arbitraryprecision Naturals This is common type used by 'Natural' and 'Integer'. As this type consists of a single constructor wrapping a 'ByteArray#' it can be unpacked. Essential invariants:  'ByteArray#' size is an exact multiple of 'Word#' size  limbs are stored in leastsignificantlimbfirst order,  the mostsignificant limb must be nonzero, except for  @0@ which is represented as a 1limb.dataBigNat=BN#ByteArray#  Invariant: 'Jn#' and 'Jp#' are used iff value doesn't fit in 'SI#' Useful properties resulting from the invariants:  @abs ('SI#' _) <= abs ('Jp#' _)@  @abs ('SI#' _) < abs ('Jn#' _)@dataInteger=SI#!Int# ^ iff value in @[minBound::'Int', maxBound::'Int']@ rangeJp#{# UNPACK #}!BigNat ^ iff value in @]maxBound::'Int', +inf[@ rangeJn#{# UNPACK #}!BigNat ^ iff value in @]inf, minBound::'Int'[@ range  Type representing arbitraryprecision Naturals Invariant: 'NatJ#' is used iff when value doesn't fit in 'NatS#'dataNatural=NatS#!Word# ^ @[0, maxBound::Word]@NatJ#{# UNPACK #}!BigNat ^ @]maxBound::GmpLimb, +inf[@deriving(Eq,Ord)



```






 `BigNat` is a internal common type to `Integer` and `Natural` and not exposed through `base`



 `Natural` finally fills the gap of the missing unsigned `Integer` counterpart in `base`






 requires fallback implementation (on top of `Integer`) in `base` if `integer{simple,gmp}` are still to be supported






 Most operations can avoid calling into the FFI backend integerlibrary, if the values don't exceed the `SI#`/`NatS#` capacity. This also means that the performance difference between using e.g. `bsdnt` or `gmp` is only noticeable for large operands.






### Linktime integerlibrary selection






 The basic requirements to be able to write an adapter for a FFI integerlibrary for `integergmp2`:






 no memory allocation of result BigNums (but rather writes into callerallocated buffers)



 BigNums are represented as machinewordsized arrays + length information






 `integergmp2` needs only about a dozen of rather generic lowlevel primitive arithmetic BigNum operations, such as e.g.






```



 mp_limb_t mpn_add_1 (mp_limb_t *rp, const mp_limb_t *s1p, mp_size_t n, mp_limb_t s2limb)foreignimportccall unsafe "gmp.h __gmpn_add_1"



c_mpn_add_1 ::MutableByteArray# s >ByteArray#>GmpSize#>GmpLimb#>IOGmpLimb mp_limb_t mpn_add (mp_limb_t *rp, const mp_limb_t *s1p, mp_size_t s1n, const mp_limb_t *s2p, mp_size_t s2n)foreignimportccall unsafe "gmp.h __gmpn_add"



c_mpn_add ::MutableByteArray# s >ByteArray#>GmpSize#>ByteArray#>GmpSize#>IOGmpLimb



```






 The plan is to write a small shimlike C library that implements a uniform adapter for `integergmp2` to call into, that wraps libraries such as GMP or `bsdnt`. This small adapter is then selected at linktime by `ghc make` similiar to how `ghc` selects one of its various runtimes (threaded, debugging, nonthreaded, ...) 