GHC.Integer.GMP.Internals

integer-gmp-1.0.2.0: Integer library based on GMP

Copyright | (c) Herbert Valerio Riedel 2014
License | BSD3
Maintainer | ghc-devs@haskell.org
Stability | provisional
Portability | non-portable (GHC Extensions)
Safe Haskell | None
Language | Haskell2010

GHC.Integer.GMP.Internals

Contents

- The `Integer` type
  - Basic `Integer` operations
  - Additional `Integer` operations
  - Additional conversion operations to `Integer`
- The `BigNat` type
  - Conversions to/from `BigNat`
  - `BigNat` arithmetic operations
  - `BigNat` logic operations
  - `BigNat` comparison predicates
- Miscellaneous GMP-provided operations
- Primality tests
- Import/export functions
  - Compute size of serialisation
  - Export
  - Import

Description

This modules provides access to the `Integer` constructors and exposes some highly optimized GMP-operations.

Note that since `integer-gmp` does not depend on `base`, error reporting via exceptions, `error`, or `undefined` is not available. Instead, the low-level functions will crash the runtime if called with invalid arguments.

See also GHC Commentary: Libraries/Integer.

Synopsis

- data Integer
  - = S# !Int#
  - | Jp# !BigNat
  - | Jn# !BigNat
- isValidInteger# :: Integer -> Int#
- module GHC.Integer
- bitInteger :: Int# -> Integer
- popCountInteger :: Integer -> Int#
- gcdInteger :: Integer -> Integer -> Integer
- gcdExtInteger :: Integer -> Integer -> (#Integer, Integer#)
- lcmInteger :: Integer -> Integer -> Integer
- sqrInteger :: Integer -> Integer
- powModInteger :: Integer -> Integer -> Integer -> Integer
- powModSecInteger :: Integer -> Integer -> Integer -> Integer
- recipModInteger :: Integer -> Integer -> Integer
- wordToNegInteger :: Word# -> Integer
- bigNatToInteger :: BigNat -> Integer
- bigNatToNegInteger :: BigNat -> Integer
- data BigNat = BN# ByteArray#
- type GmpLimb = Word
- type GmpLimb# = Word#
- type GmpSize = Int
- type GmpSize# = Int#
- isValidBigNat# :: BigNat -> Int#
- sizeofBigNat# :: BigNat -> GmpSize#
- zeroBigNat :: BigNat
- oneBigNat :: BigNat
- nullBigNat :: BigNat
- byteArrayToBigNat# :: ByteArray# -> GmpSize# -> BigNat
- wordToBigNat :: Word# -> BigNat
- wordToBigNat2 :: Word# -> Word# -> BigNat
- bigNatToInt :: BigNat -> Int#
- bigNatToWord :: BigNat -> Word#
- indexBigNat# :: BigNat -> GmpSize# -> GmpLimb#
- plusBigNat :: BigNat -> BigNat -> BigNat
- plusBigNatWord :: BigNat -> GmpLimb# -> BigNat
- minusBigNat :: BigNat -> BigNat -> BigNat
- minusBigNatWord :: BigNat -> GmpLimb# -> BigNat
- timesBigNat :: BigNat -> BigNat -> BigNat
- timesBigNatWord :: BigNat -> GmpLimb# -> BigNat
- sqrBigNat :: BigNat -> BigNat
- quotRemBigNat :: BigNat -> BigNat -> (#BigNat, BigNat#)
- quotRemBigNatWord :: BigNat -> GmpLimb# -> (#BigNat, GmpLimb##)
- quotBigNatWord :: BigNat -> GmpLimb# -> BigNat
- quotBigNat :: BigNat -> BigNat -> BigNat
- remBigNat :: BigNat -> BigNat -> BigNat
- remBigNatWord :: BigNat -> GmpLimb# -> Word#
- gcdBigNat :: BigNat -> BigNat -> BigNat
- gcdBigNatWord :: BigNat -> Word# -> Word#
- powModBigNat :: BigNat -> BigNat -> BigNat -> BigNat
- powModBigNatWord :: BigNat -> BigNat -> GmpLimb# -> GmpLimb#
- recipModBigNat :: BigNat -> BigNat -> BigNat
- shiftRBigNat :: BigNat -> Int# -> BigNat
- shiftLBigNat :: BigNat -> Int# -> BigNat
- testBitBigNat :: BigNat -> Int# -> Bool
- clearBitBigNat :: BigNat -> Int# -> BigNat
- complementBitBigNat :: BigNat -> Int# -> BigNat
- setBitBigNat :: BigNat -> Int# -> BigNat
- andBigNat :: BigNat -> BigNat -> BigNat
- xorBigNat :: BigNat -> BigNat -> BigNat
- popCountBigNat :: BigNat -> Int#
- orBigNat :: BigNat -> BigNat -> BigNat
- bitBigNat :: Int# -> BigNat
- isZeroBigNat :: BigNat -> Bool
- isNullBigNat# :: BigNat -> Int#
- compareBigNatWord :: BigNat -> GmpLimb# -> Ordering
- compareBigNat :: BigNat -> BigNat -> Ordering
- eqBigNatWord :: BigNat -> GmpLimb# -> Bool
- eqBigNatWord# :: BigNat -> GmpLimb# -> Int#
- eqBigNat :: BigNat -> BigNat -> Bool
- eqBigNat# :: BigNat -> BigNat -> Int#
- gtBigNatWord# :: BigNat -> GmpLimb# -> Int#
- gcdInt :: Int# -> Int# -> Int#
- gcdWord :: Word# -> Word# -> Word#
- powModWord :: GmpLimb# -> GmpLimb# -> GmpLimb# -> GmpLimb#
- recipModWord :: GmpLimb# -> GmpLimb# -> GmpLimb#
- testPrimeInteger :: Integer -> Int# -> Int#
- testPrimeBigNat :: BigNat -> Int# -> Int#
- testPrimeWord# :: GmpLimb# -> Int# -> Int#
- nextPrimeInteger :: Integer -> Integer
- nextPrimeBigNat :: BigNat -> BigNat
- nextPrimeWord# :: GmpLimb# -> GmpLimb#
- sizeInBaseBigNat :: BigNat -> Int# -> Word#
- sizeInBaseInteger :: Integer -> Int# -> Word#
- sizeInBaseWord# :: Word# -> Int# -> Word#
- exportBigNatToAddr :: BigNat -> Addr# -> Int# -> IO Word
- exportIntegerToAddr :: Integer -> Addr# -> Int# -> IO Word
- exportWordToAddr :: Word -> Addr# -> Int# -> IO Word
- exportBigNatToMutableByteArray :: BigNat -> MutableByteArray# RealWorld -> Word# -> Int# -> IO Word
- exportIntegerToMutableByteArray :: Integer -> MutableByteArray# RealWorld -> Word# -> Int# -> IO Word
- exportWordToMutableByteArray :: Word -> MutableByteArray# RealWorld -> Word# -> Int# -> IO Word
- importBigNatFromAddr :: Addr# -> Word# -> Int# -> IO BigNat
- importIntegerFromAddr :: Addr# -> Word# -> Int# -> IO Integer
- importBigNatFromByteArray :: ByteArray# -> Word# -> Word# -> Int# -> BigNat
- importIntegerFromByteArray :: ByteArray# -> Word# -> Word# -> Int# -> Integer

# The `Integer` type

data Integer #

Invariant: `Jn#` and `Jp#` are used iff value doesn't fit in `S#`

Useful properties resulting from the invariants:

-     abs (S# _) <= abs (Jp# _)

-     abs (S# _) <  abs (Jn# _)

Constructors

S# !Int# | iff value in `[minBound::`Int`, maxBound::`Int`]` range
Jp# !BigNat | iff value in `]maxBound::`Int`, +inf[` range
Jn# !BigNat | iff value in `]-inf, minBound::`Int`[` range

Instances

Eq Integer # |
Instance details Defined in GHC.Integer.Type Methods (==) :: Integer -> Integer -> Bool (/=) :: Integer -> Integer -> Bool
Ord Integer # |
Instance details Defined in GHC.Integer.Type Methods compare :: Integer -> Integer -> Ordering (<) :: Integer -> Integer -> Bool (<=) :: Integer -> Integer -> Bool (>) :: Integer -> Integer -> Bool (>=) :: Integer -> Integer -> Bool max :: Integer -> Integer -> Integer min :: Integer -> Integer -> Integer

isValidInteger# :: Integer -> Int# #

Test whether all internal invariants are satisfied by `Integer` value

Returns `1#` if valid, `0#` otherwise.

This operation is mostly useful for test-suites and/or code which constructs `Integer` values directly.

## Basic `Integer` operations

module GHC.Integer

## Additional `Integer` operations

bitInteger :: Int# -> Integer #

`Integer` for which only n-th bit is set. Undefined behaviour for negative n values.

popCountInteger :: Integer -> Int# #

Count number of set bits. For negative arguments returns negative population count of negated argument.

gcdInteger :: Integer -> Integer -> Integer #

Compute greatest common divisor.

gcdExtInteger :: Integer -> Integer -> (#Integer, Integer#) #

Extended euclidean algorithm.

For `a` and `b`, compute their greatest common divisor `g` and the coefficient `s` satisfying `as + bt = g`.

Since: integer-gmp-0.5.1.0

lcmInteger :: Integer -> Integer -> Integer #

Compute least common multiple.

sqrInteger :: Integer -> Integer #

Square `Integer`

powModInteger :: Integer -> Integer -> Integer -> Integer #

"``powModInteger` b e m`" computes base `b` raised to exponent `e` modulo `abs(m)`.

Negative exponents are supported if an inverse modulo `m` exists.

Warning: It's advised to avoid calling this primitive with negative exponents unless it is guaranteed the inverse exists, as failure to do so will likely cause program abortion due to a divide-by-zero fault. See also `recipModInteger`.

Future versions of `integer_gmp` may not support negative `e` values anymore.

Since: integer-gmp-0.5.1.0

powModSecInteger :: Integer -> Integer -> Integer -> Integer #

"``powModSecInteger` b e m`" computes base `b` raised to exponent `e` modulo `m`. It is required that `e >= 0` and `m` is odd.

This is a "secure" variant of `powModInteger` using the `mpz_powm_sec()` function which is designed to be resilient to side channel attacks and is therefore intended for cryptographic applications.

This primitive is only available when the underlying GMP library supports it (GMP >= 5). Otherwise, it internally falls back to ``powModInteger``, and a warning will be emitted when used.

Since: integer-gmp-1.0.2.0

recipModInteger :: Integer -> Integer -> Integer #

"``recipModInteger` x m`" computes the inverse of `x` modulo `m`. If the inverse exists, the return value `y` will satisfy `0 < y < abs(m)`, otherwise the result is `0`.

Since: integer-gmp-0.5.1.0

## Additional conversion operations to `Integer`

wordToNegInteger :: Word# -> Integer #

bigNatToInteger :: BigNat -> Integer #

bigNatToNegInteger :: BigNat -> Integer #

# The `BigNat` type

data BigNat #

Type representing raw arbitrary-precision 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 least-significant-limb-first order,
- the most-significant limb must be non-zero, except for
- `0` which is represented as a 1-limb.

Constructors

BN# ByteArray# |

Instances

Eq BigNat # |
Instance details Defined in GHC.Integer.Type Methods (==) :: BigNat -> BigNat -> Bool (/=) :: BigNat -> BigNat -> Bool
Ord BigNat # |
Instance details Defined in GHC.Integer.Type Methods compare :: BigNat -> BigNat -> Ordering (<) :: BigNat -> BigNat -> Bool (<=) :: BigNat -> BigNat -> Bool (>) :: BigNat -> BigNat -> Bool (>=) :: BigNat -> BigNat -> Bool max :: BigNat -> BigNat -> BigNat min :: BigNat -> BigNat -> BigNat

type GmpLimb = Word #

Type representing a GMP Limb

type GmpLimb# = Word# #

type GmpSize = Int #

Count of `GmpLimb`s, must be positive (unless specified otherwise).

type GmpSize# = Int# #

##

isValidBigNat# :: BigNat -> Int# #

Test whether all internal invariants are satisfied by `BigNat` value

Returns `1#` if valid, `0#` otherwise.

This operation is mostly useful for test-suites and/or code which constructs `Integer` values directly.

sizeofBigNat# :: BigNat -> GmpSize# #

Return number of limbs contained in `BigNat`.

zeroBigNat :: BigNat #

CAF representing the value `0 :: BigNat`

oneBigNat :: BigNat #

CAF representing the value `1 :: BigNat`

nullBigNat :: BigNat #

Special 0-sized bigNat returned in case of arithmetic underflow

This is currently only returned by the following operations:

- `minusBigNat`
- `minusBigNatWord`

Other operations such as `quotBigNat` may return `nullBigNat` as well as a dummy/place-holder value instead of `undefined` since we can't throw exceptions. But that behaviour should not be relied upon.

NB: `isValidBigNat# nullBigNat` is false

## Conversions to/from `BigNat`

byteArrayToBigNat# :: ByteArray# -> GmpSize# -> BigNat #

Construct `BigNat` from existing `ByteArray#` containing n `GmpLimb`s in least-significant-first order.

If possible `ByteArray#`, will be used directly (i.e. shared without cloning the `ByteArray#` into a newly allocated one)

Note: size parameter (times `sizeof(GmpLimb)`) must be less or equal to its `sizeofByteArray#`.

wordToBigNat :: Word# -> BigNat #

Construct 1-limb `BigNat` from `Word#`

wordToBigNat2 :: Word# -> Word# -> BigNat #

Construct BigNat from 2 limbs. The first argument is the most-significant limb.

bigNatToInt :: BigNat -> Int# #

Equivalent to ``word2Int#` . `bigNatToWord``

bigNatToWord :: BigNat -> Word# #

Same as ``indexBigNat#` bn 0#`

indexBigNat# :: BigNat -> GmpSize# -> GmpLimb# #

Extract n-th (0-based) limb in `BigNat`. n must be less than size as reported by `sizeofBigNat#`.

## `BigNat` arithmetic operations

plusBigNat :: BigNat -> BigNat -> BigNat #

plusBigNatWord :: BigNat -> GmpLimb# -> BigNat #

minusBigNat :: BigNat -> BigNat -> BigNat #

Returns `nullBigNat` (see `isNullBigNat#`) in case of underflow

minusBigNatWord :: BigNat -> GmpLimb# -> BigNat #

Returns `nullBigNat` (see `isNullBigNat#`) in case of underflow

timesBigNat :: BigNat -> BigNat -> BigNat #

timesBigNatWord :: BigNat -> GmpLimb# -> BigNat #

sqrBigNat :: BigNat -> BigNat #

Square `BigNat`

quotRemBigNat :: BigNat -> BigNat -> (#BigNat, BigNat#) #

If divisor is zero, `(# `nullBigNat`, `nullBigNat` #)` is returned

quotRemBigNatWord :: BigNat -> GmpLimb# -> (#BigNat, GmpLimb##) #

Note: Result of div/0 undefined

quotBigNatWord :: BigNat -> GmpLimb# -> BigNat #

quotBigNat :: BigNat -> BigNat -> BigNat #

remBigNat :: BigNat -> BigNat -> BigNat #

remBigNatWord :: BigNat -> GmpLimb# -> Word# #

div/0 not checked

gcdBigNat :: BigNat -> BigNat -> BigNat #

gcdBigNatWord :: BigNat -> Word# -> Word# #

powModBigNat :: BigNat -> BigNat -> BigNat -> BigNat #

Version of `powModInteger` operating on `BigNat`s

Since: integer-gmp-1.0.0.0

powModBigNatWord :: BigNat -> BigNat -> GmpLimb# -> GmpLimb# #

Version of `powModInteger` for `Word#`-sized moduli

Since: integer-gmp-1.0.0.0

recipModBigNat :: BigNat -> BigNat -> BigNat #

Version of `recipModInteger` operating on `BigNat`s

Since: integer-gmp-1.0.0.0

## `BigNat` logic operations

shiftRBigNat :: BigNat -> Int# -> BigNat #

shiftLBigNat :: BigNat -> Int# -> BigNat #

testBitBigNat :: BigNat -> Int# -> Bool #

clearBitBigNat :: BigNat -> Int# -> BigNat #

complementBitBigNat :: BigNat -> Int# -> BigNat #

setBitBigNat :: BigNat -> Int# -> BigNat #

andBigNat :: BigNat -> BigNat -> BigNat #

xorBigNat :: BigNat -> BigNat -> BigNat #

popCountBigNat :: BigNat -> Int# #

orBigNat :: BigNat -> BigNat -> BigNat #

bitBigNat :: Int# -> BigNat #

Specialised version of

    bitBigNat = shiftLBigNat (wordToBigNat 1##)

avoiding a few redundant allocations

## `BigNat` comparison predicates

isZeroBigNat :: BigNat -> Bool #

Test if `BigNat` value is equal to zero.

isNullBigNat# :: BigNat -> Int# #

Test for special 0-sized `BigNat` representing underflows.

compareBigNatWord :: BigNat -> GmpLimb# -> Ordering #

compareBigNat :: BigNat -> BigNat -> Ordering #

eqBigNatWord :: BigNat -> GmpLimb# -> Bool #

eqBigNatWord# :: BigNat -> GmpLimb# -> Int# #

eqBigNat :: BigNat -> BigNat -> Bool #

eqBigNat# :: BigNat -> BigNat -> Int# #

gtBigNatWord# :: BigNat -> GmpLimb# -> Int# #

# Miscellaneous GMP-provided operations

gcdInt :: Int# -> Int# -> Int# #

Compute greatest common divisor.

Warning: result may become negative if (at least) one argument is `minBound`

gcdWord :: Word# -> Word# -> Word# #

Compute greatest common divisor.

Since: integer-gmp-1.0.0.0

powModWord :: GmpLimb# -> GmpLimb# -> GmpLimb# -> GmpLimb# #

Version of `powModInteger` operating on `Word#`s

Since: integer-gmp-1.0.0.0

recipModWord :: GmpLimb# -> GmpLimb# -> GmpLimb# #

Version of `recipModInteger` operating on `Word#`s

Since: integer-gmp-1.0.0.0

# Primality tests

testPrimeInteger :: Integer -> Int# -> Int# #

Probalistic Miller-Rabin primality test.

"``testPrimeInteger` n k`" determines whether `n` is prime and returns one of the following results:

- `2#` is returned if `n` is definitely prime,
- `1#` if `n` is a probable prime, or
- `0#` if `n` is definitely not a prime.

The `k` argument controls how many test rounds are performed for determining a probable prime. For more details, see GMP documentation for `mpz_probab_prime_p()`.

Since: integer-gmp-0.5.1.0

testPrimeBigNat :: BigNat -> Int# -> Int# #

Version of `testPrimeInteger` operating on `BigNat`s

Since: integer-gmp-1.0.0.0

testPrimeWord# :: GmpLimb# -> Int# -> Int# #

Version of `testPrimeInteger` operating on `Word#`s

Since: integer-gmp-1.0.0.0

nextPrimeInteger :: Integer -> Integer #

Compute next prime greater than `n` probalistically.

According to the GMP documentation, the underlying function `mpz_nextprime()` "uses a probabilistic algorithm to identify primes. For practical purposes it's adequate, the chance of a composite passing will be extremely small."

Since: integer-gmp-0.5.1.0

nextPrimeBigNat :: BigNat -> BigNat #

Version of `nextPrimeInteger` operating on `BigNat`s

Since: integer-gmp-1.0.0.0

nextPrimeWord# :: GmpLimb# -> GmpLimb# #

Version of `nextPrimeInteger` operating on `Word#`s

Since: integer-gmp-1.0.0.0

# Import/export functions

## Compute size of serialisation

sizeInBaseBigNat :: BigNat -> Int# -> Word# #

Version of `sizeInBaseInteger` operating on `BigNat`

Since: integer-gmp-1.0.0.0

sizeInBaseInteger :: Integer -> Int# -> Word# #

Compute number of digits (without sign) in given `base`.

This function wraps `mpz_sizeinbase()` which has some implementation pecularities to take into account:

- "``sizeInBaseInteger` 0 base = 1`" (see also comment in `exportIntegerToMutableByteArray`).
- This function is only defined if `base >= 2#` and `base <= 256#` (Note: the documentation claims that only `base <= 62#` is supported, however the actual implementation supports up to base 256).
- If `base` is a power of 2, the result will be exact. In other cases (e.g. for `base = 10#`), the result may be 1 digit too large sometimes.
- "``sizeInBaseInteger` i 2#`" can be used to determine the most significant bit of `i`.

Since: integer-gmp-0.5.1.0

sizeInBaseWord# :: Word# -> Int# -> Word# #

Version of `sizeInBaseInteger` operating on `Word#`

Since: integer-gmp-1.0.0.0

## Export

exportBigNatToAddr :: BigNat -> Addr# -> Int# -> IO Word #

Version of `exportIntegerToAddr` operating on `BigNat`s.

exportIntegerToAddr :: Integer -> Addr# -> Int# -> IO Word #

Dump `Integer` (without sign) to `addr` in base-256 representation.

    exportIntegerToAddr i addr e

See description of `exportIntegerToMutableByteArray` for more details.

Since: integer-gmp-1.0.0.0

exportWordToAddr :: Word -> Addr# -> Int# -> IO Word #

Version of `exportIntegerToAddr` operating on `Word`s.

exportBigNatToMutableByteArray :: BigNat -> MutableByteArray# RealWorld -> Word# -> Int# -> IO Word #

Version of `exportIntegerToMutableByteArray` operating on `BigNat`s.

Since: integer-gmp-1.0.0.0

exportIntegerToMutableByteArray :: Integer -> MutableByteArray# RealWorld -> Word# -> Int# -> IO Word #

Dump `Integer` (without sign) to mutable byte-array in base-256 representation.

The call

    exportIntegerToMutableByteArray i mba offset msbf

writes

- the `Integer` `i`
- into the `MutableByteArray#` `mba` starting at `offset`
- with most significant byte first if `msbf` is `1#` or least significant byte first if `msbf` is `0#`, and
- returns number of bytes written.

Use "``sizeInBaseInteger` i 256#`" to compute the exact number of bytes written in advance for `i /= 0`. In case of `i == 0`, `exportIntegerToMutableByteArray` will write and report zero bytes written, whereas `sizeInBaseInteger` report one byte.

It's recommended to avoid calling `exportIntegerToMutableByteArray` for small integers as this function would currently convert those to big integers in msbf to call `mpz_export()`.

Since: integer-gmp-1.0.0.0

exportWordToMutableByteArray :: Word -> MutableByteArray# RealWorld -> Word# -> Int# -> IO Word #

Version of `exportIntegerToMutableByteArray` operating on `Word`s.

Since: integer-gmp-1.0.0.0

## Import

importBigNatFromAddr :: Addr# -> Word# -> Int# -> IO BigNat #

Version of `importIntegerFromAddr` constructing a `BigNat`

importIntegerFromAddr :: Addr# -> Word# -> Int# -> IO Integer #

Read `Integer` (without sign) from memory location at `addr` in base-256 representation.

    importIntegerFromAddr addr size msbf

See description of `importIntegerFromByteArray` for more details.

Since: integer-gmp-1.0.0.0

importBigNatFromByteArray :: ByteArray# -> Word# -> Word# -> Int# -> BigNat #

Version of `importIntegerFromByteArray` constructing a `BigNat`

importIntegerFromByteArray :: ByteArray# -> Word# -> Word# -> Int# -> Integer #

Read `Integer` (without sign) from byte-array in base-256 representation.

The call

    importIntegerFromByteArray ba offset size msbf

reads

- `size` bytes from the `ByteArray#` `ba` starting at `offset`
- with most significant byte first if `msbf` is `1#` or least significant byte first if `msbf` is `0#`, and
- returns a new `Integer`

Since: integer-gmp-1.0.0.0