-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Integer library based on GMP -- -- This package provides the low-level implementation of the standard -- Integer type based on the GNU Multiple Precision Arithmetic -- Library (GMP). -- -- This package provides access to the internal representation of -- Integer as well as primitive operations with no proper error -- handling, and should only be used directly with the utmost care. @package integer-gmp @version 1.0.3.0 module GHC.Integer.Logarithms -- | Compute base-2 log of Word# -- -- This is internally implemented as count-leading-zeros machine -- instruction. wordLog2# :: Word# -> Int# -- | Calculate the integer base 2 logarithm of an Integer. The -- calculation is more efficient than for the general case, on platforms -- with 32- or 64-bit words much more efficient. -- -- The argument must be strictly positive, that condition is not -- checked. integerLog2# :: Integer -> Int# -- | Calculate the integer logarithm for an arbitrary base. -- -- The base must be greater than 1, the second argument, the -- number whose logarithm is sought, shall be positive, otherwise the -- result is meaningless. -- -- The following property holds -- -- 
--   base ^ integerLogBase# base m <= m < base ^(integerLogBase# base m + 1)
--
-- -- for base > 1 and m > 0. -- -- Note: Internally uses integerLog2# for base 2 integerLogBase# :: Integer -> Integer -> Int# -- | Fast Integer logarithms to base 2. integerLog2# and -- wordLog2# are of general usefulness, the others are only needed -- for a fast implementation of fromRational. Since they are -- needed in GHC.Float, we must expose this module, but it should -- not show up in the docs. -- -- See https://gitlab.haskell.org/ghc/ghc/issues/5122 for the -- origin of the code in this module module GHC.Integer.Logarithms.Internals -- | Compute base-2 log of Word# -- -- This is internally implemented as count-leading-zeros machine -- instruction. wordLog2# :: Word# -> Int# -- | Extended version of integerLog2# -- -- Assumption: Integer is strictly positive -- -- First component of result is log2 n, second is 0# -- iff n is a power of two. integerLog2IsPowerOf2# :: Integer -> (# Int#, Int# #) -- | Calculate the integer base 2 logarithm of an Integer. The -- calculation is more efficient than for the general case, on platforms -- with 32- or 64-bit words much more efficient. -- -- The argument must be strictly positive, that condition is not -- checked. integerLog2# :: Integer -> Int# roundingMode# :: Integer -> Int# -> Int# -- | The Integer type. -- -- This module exposes the portable Integer API. See -- GHC.Integer.GMP.Internals for the integer-gmp-specific -- internal representation of Integer as well as optimized -- GMP-specific operations. module GHC.Integer -- | Arbitrary precision integers. In contrast with fixed-size integral -- types such as Int, the Integer type represents the -- entire infinite range of integers. -- -- For more information about this type's representation, see the -- comments in its implementation. data Integer -- | Construct Integer value from list of Ints. -- -- This function is used by GHC for constructing Integer literals. mkInteger :: Bool -> [Int] -> Integer -- | Should rather be called intToInteger smallInteger :: Int# -> Integer wordToInteger :: Word# -> Integer integerToWord :: Integer -> Word# -- | Truncates Integer to least-significant Int# integerToInt :: Integer -> Int# encodeFloatInteger :: Integer -> Int# -> Float# floatFromInteger :: Integer -> Float# encodeDoubleInteger :: Integer -> Int# -> Double# decodeDoubleInteger :: Double# -> (# Integer, Int# #) doubleFromInteger :: Integer -> Double# -- | Add two Integers plusInteger :: Integer -> Integer -> Integer -- | Subtract one Integer from another. minusInteger :: Integer -> Integer -> Integer -- | Multiply two Integers timesInteger :: Integer -> Integer -> Integer -- | Negate Integer negateInteger :: Integer -> Integer -- | Compute absolute value of an Integer absInteger :: Integer -> Integer -- | Return -1, 0, and 1 depending on whether -- argument is negative, zero, or positive, respectively signumInteger :: Integer -> Integer -- | Simultaneous divInteger and modInteger. -- -- Divisor must be non-zero otherwise the GHC runtime will terminate with -- a division-by-zero fault. divModInteger :: Integer -> Integer -> (# Integer, Integer #) divInteger :: Integer -> Integer -> Integer modInteger :: Integer -> Integer -> Integer -- | Simultaneous quotInteger and remInteger. -- -- Divisor must be non-zero otherwise the GHC runtime will terminate with -- a division-by-zero fault. quotRemInteger :: Integer -> Integer -> (# Integer, Integer #) quotInteger :: Integer -> Integer -> Integer remInteger :: Integer -> Integer -> Integer eqInteger :: Integer -> Integer -> Bool -- | Not-equal predicate. neqInteger :: Integer -> Integer -> Bool leInteger :: Integer -> Integer -> Bool gtInteger :: Integer -> Integer -> Bool ltInteger :: Integer -> Integer -> Bool geInteger :: Integer -> Integer -> Bool compareInteger :: Integer -> Integer -> Ordering eqInteger# :: Integer -> Integer -> Int# neqInteger# :: Integer -> Integer -> Int# leInteger# :: Integer -> Integer -> Int# gtInteger# :: Integer -> Integer -> Int# ltInteger# :: Integer -> Integer -> Int# geInteger# :: Integer -> Integer -> Int# -- | Bitwise AND operation andInteger :: Integer -> Integer -> Integer -- | Bitwise OR operation orInteger :: Integer -> Integer -> Integer -- | Bitwise XOR operation xorInteger :: Integer -> Integer -> Integer -- | Bitwise NOT operation complementInteger :: Integer -> Integer -- | Shift-left operation -- -- Even though the shift-amount is expressed as Int#, the result -- is undefined for negative shift-amounts. shiftLInteger :: Integer -> Int# -> Integer -- | Arithmetic shift-right operation -- -- Even though the shift-amount is expressed as Int#, the result -- is undefined for negative shift-amounts. shiftRInteger :: Integer -> Int# -> Integer -- | Test if n-th bit is set. testBitInteger :: Integer -> Int# -> Bool -- | Count number of set bits. For negative arguments returns negative -- population count of negated argument. popCountInteger :: Integer -> Int# -- | Integer for which only n-th bit is set. Undefined -- behaviour for negative n values. bitInteger :: Int# -> Integer hashInteger :: Integer -> Int# -- | 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. module GHC.Integer.GMP.Internals -- | Arbitrary precision integers. In contrast with fixed-size integral -- types such as Int, the Integer type represents the -- entire infinite range of integers. -- -- For more information about this type's representation, see the -- comments in its implementation. data Integer -- | iff value in [minBound::Int, maxBound::Int] -- range S# :: !Int# -> Integer -- | iff value in ]maxBound::Int, +inf[ range Jp# :: {-# UNPACK #-} !BigNat -> Integer -- | iff value in ]-inf, minBound::Int[ range Jn# :: {-# UNPACK #-} !BigNat -> Integer -- | 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. isValidInteger# :: Integer -> Int# -- | Compute greatest common divisor. gcdInteger :: Integer -> Integer -> Integer -- | Extended euclidean algorithm. -- -- For a and b, compute their greatest -- common divisor g and the coefficient s -- satisfying as + bt = g. gcdExtInteger :: Integer -> Integer -> (# Integer, Integer #) -- | Compute least common multiple. lcmInteger :: Integer -> Integer -> Integer -- | Square Integer sqrInteger :: 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. powModInteger :: 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. powModSecInteger :: Integer -> 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. recipModInteger :: Integer -> Integer -> Integer wordToNegInteger :: Word# -> Integer bigNatToInteger :: BigNat -> Integer bigNatToNegInteger :: BigNat -> Integer -- | 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: -- -- data BigNat BN# :: ByteArray# -> BigNat -- | Type representing a GMP Limb type GmpLimb = Word type GmpLimb# = Word# -- | Count of GmpLimbs, must be positive (unless specified -- otherwise). type GmpSize = Int type GmpSize# = 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. isValidBigNat# :: BigNat -> Int# -- | Return number of limbs contained in BigNat. -- -- The result is always >= 1 since even zero is encoded with -- 1 limb. sizeofBigNat# :: BigNat -> GmpSize# -- | CAF representing the value 0 :: BigNat zeroBigNat :: BigNat -- | CAF representing the value 1 :: BigNat oneBigNat :: BigNat -- | Special 0-sized bigNat returned in case of arithmetic underflow -- -- This is currently only returned by the following operations: -- -- -- -- 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 nullBigNat :: BigNat -- | Construct BigNat from existing ByteArray# containing -- n GmpLimbs 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#. byteArrayToBigNat# :: ByteArray# -> GmpSize# -> BigNat -- | Construct 1-limb BigNat from Word# wordToBigNat :: Word# -> BigNat -- | Construct BigNat from 2 limbs. The first argument is the -- most-significant limb. wordToBigNat2 :: Word# -> Word# -> BigNat -- | Equivalent to word2Int# . bigNatToWord bigNatToInt :: BigNat -> Int# -- | Same as indexBigNat# bn 0# bigNatToWord :: BigNat -> Word# -- | Extract n-th (0-based) limb in BigNat. n must be -- less than size as reported by sizeofBigNat#. indexBigNat# :: BigNat -> GmpSize# -> GmpLimb# plusBigNat :: BigNat -> BigNat -> BigNat plusBigNatWord :: BigNat -> GmpLimb# -> BigNat -- | Returns nullBigNat (see isNullBigNat#) in case of -- underflow minusBigNat :: BigNat -> BigNat -> BigNat -- | Returns nullBigNat (see isNullBigNat#) in case of -- underflow minusBigNatWord :: BigNat -> GmpLimb# -> BigNat timesBigNat :: BigNat -> BigNat -> BigNat timesBigNatWord :: BigNat -> GmpLimb# -> BigNat -- | Square BigNat sqrBigNat :: BigNat -> BigNat -- | If divisor is zero, (# nullBigNat, nullBigNat -- #) is returned quotRemBigNat :: BigNat -> BigNat -> (# BigNat, BigNat #) -- | Note: Result of div/0 undefined quotRemBigNatWord :: BigNat -> GmpLimb# -> (# BigNat, GmpLimb# #) quotBigNatWord :: BigNat -> GmpLimb# -> BigNat quotBigNat :: BigNat -> BigNat -> BigNat remBigNat :: BigNat -> BigNat -> BigNat -- | div/0 not checked remBigNatWord :: BigNat -> GmpLimb# -> Word# gcdBigNat :: BigNat -> BigNat -> BigNat gcdBigNatWord :: BigNat -> Word# -> Word# -- | Version of powModInteger operating on BigNats powModBigNat :: BigNat -> BigNat -> BigNat -> BigNat -- | Version of powModInteger for Word#-sized moduli powModBigNatWord :: BigNat -> BigNat -> GmpLimb# -> GmpLimb# -- | Version of recipModInteger operating on BigNats 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 -- | Specialised version of -- -- 
--   bitBigNat = shiftLBigNat (wordToBigNat 1##)
--
-- -- avoiding a few redundant allocations bitBigNat :: Int# -> BigNat -- | Test if BigNat value is equal to zero. isZeroBigNat :: BigNat -> Bool -- | Test for special 0-sized BigNat representing underflows. 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# -- | Compute greatest common divisor. -- -- Warning: result may become negative if (at least) one argument -- is minBound gcdInt :: Int# -> Int# -> Int# -- | Compute greatest common divisor. gcdWord :: Word# -> Word# -> Word# -- | Version of powModInteger operating on Word#s powModWord :: GmpLimb# -> GmpLimb# -> GmpLimb# -> GmpLimb# -- | Version of recipModInteger operating on Word#s recipModWord :: GmpLimb# -> GmpLimb# -> GmpLimb# -- | Probalistic Miller-Rabin primality test. -- -- "testPrimeInteger n k" determines -- whether n is prime and returns one of the following -- results: -- -- -- -- 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()`. testPrimeInteger :: Integer -> Int# -> Int# -- | Version of testPrimeInteger operating on BigNats testPrimeBigNat :: BigNat -> Int# -> Int# -- | Version of testPrimeInteger operating on Word#s testPrimeWord# :: GmpLimb# -> Int# -> Int# -- | 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." nextPrimeInteger :: Integer -> Integer -- | Version of nextPrimeInteger operating on BigNats nextPrimeBigNat :: BigNat -> BigNat -- | Version of nextPrimeInteger operating on Word#s nextPrimeWord# :: GmpLimb# -> GmpLimb# -- | Version of sizeInBaseInteger operating on BigNat sizeInBaseBigNat :: BigNat -> 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 :: Integer -> Int# -> Word# -- | Version of sizeInBaseInteger operating on Word# sizeInBaseWord# :: Word# -> Int# -> Word# -- | Version of exportIntegerToAddr operating on BigNats. exportBigNatToAddr :: BigNat -> 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. exportIntegerToAddr :: Integer -> Addr# -> Int# -> IO Word -- | Version of exportIntegerToAddr operating on Words. exportWordToAddr :: Word -> Addr# -> Int# -> IO Word -- | Version of exportIntegerToMutableByteArray operating on -- BigNats. exportBigNatToMutableByteArray :: BigNat -> 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 -- -- -- -- 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(). exportIntegerToMutableByteArray :: Integer -> MutableByteArray# RealWorld -> Word# -> Int# -> IO Word -- | Version of exportIntegerToMutableByteArray operating on -- Words. exportWordToMutableByteArray :: Word -> MutableByteArray# RealWorld -> Word# -> Int# -> IO Word -- | Version of importIntegerFromAddr constructing a BigNat importBigNatFromAddr :: Addr# -> Word# -> Int# -> IO BigNat -- | Read Integer (without sign) from memory location at -- addr in base-256 representation. -- -- 
--   importIntegerFromAddr addr size msbf
--
-- -- See description of importIntegerFromByteArray for more details. importIntegerFromAddr :: Addr# -> Word# -> Int# -> IO Integer -- | Version of importIntegerFromByteArray constructing a -- BigNat importBigNatFromByteArray :: ByteArray# -> Word# -> Word# -> Int# -> BigNat -- | Read Integer (without sign) from byte-array in base-256 -- representation. -- -- The call -- -- 
--   importIntegerFromByteArray ba offset size msbf
--
-- -- reads -- -- importIntegerFromByteArray :: ByteArray# -> Word# -> Word# -> Int# -> Integer