Movatterモバイル変換

{-# LANGUAGE BangPatterns #-}{-# LANGUAGE CApiFFI #-}{-# LANGUAGE MagicHash #-}{-# LANGUAGE UnboxedTuples #-}{-# LANGUAGE UnliftedFFITypes #-}{-# LANGUAGE DeriveDataTypeable #-}{-# LANGUAGE GHCForeignImportPrim #-}{-# LANGUAGE CPP #-}{-# LANGUAGE StandaloneDeriving #-}{-# LANGUAGE NoImplicitPrelude #-}#include "MachDeps.h"-- |-- Module      :  GHC.Integer.GMP.Internals-- Copyright   :  (c) Herbert Valerio Riedel 2014-- License     :  BSD3---- Maintainer  :  ghc-devs@haskell.org-- Stability   :  provisional-- Portability :  non-portable (GHC Extensions)---- 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-- <https://ghc.haskell.org/trac/ghc/wiki/Commentary/Libraries/Integer GHC Commentary: Libraries/Integer>.moduleGHC.Integer.GMP.Internals(-- * The 'Integer' typeInteger(..),isValidInteger#-- ** Basic 'Integer' operations,moduleGHC.Integer-- ** Additional 'Integer' operations,bitInteger,popCountInteger,gcdInteger,gcdExtInteger,lcmInteger,sqrInteger,powModInteger,powModSecInteger,recipModInteger-- ** Additional conversion operations to 'Integer',wordToNegInteger,bigNatToInteger,bigNatToNegInteger-- * The 'BigNat' type,BigNat(..),GmpLimb,GmpLimb#,GmpSize,GmpSize#-- **,isValidBigNat#,sizeofBigNat#,zeroBigNat,oneBigNat,nullBigNat-- ** Conversions to/from 'BigNat',byteArrayToBigNat#,wordToBigNat,wordToBigNat2,bigNatToInt,bigNatToWord,indexBigNat#-- ** 'BigNat' arithmetic operations,plusBigNat,plusBigNatWord,minusBigNat,minusBigNatWord,timesBigNat,timesBigNatWord,sqrBigNat,quotRemBigNat,quotRemBigNatWord,quotBigNatWord,quotBigNat,remBigNat,remBigNatWord,gcdBigNat,gcdBigNatWord,powModBigNat,powModBigNatWord,recipModBigNat-- ** 'BigNat' logic operations,shiftRBigNat,shiftLBigNat,testBitBigNat,clearBitBigNat,complementBitBigNat,setBitBigNat,andBigNat,xorBigNat,popCountBigNat,orBigNat,bitBigNat-- ** 'BigNat' comparison predicates,isZeroBigNat,isNullBigNat#,compareBigNatWord,compareBigNat,eqBigNatWord,eqBigNatWord#,eqBigNat,eqBigNat#,gtBigNatWord#-- * Miscellaneous GMP-provided operations,gcdInt,gcdWord,powModWord,recipModWord-- * Primality tests,testPrimeInteger,testPrimeBigNat,testPrimeWord#,nextPrimeInteger,nextPrimeBigNat,nextPrimeWord#-- * Import/export functions-- ** Compute size of serialisation,sizeInBaseBigNat,sizeInBaseInteger,sizeInBaseWord#-- ** Export,exportBigNatToAddr,exportIntegerToAddr,exportWordToAddr,exportBigNatToMutableByteArray,exportIntegerToMutableByteArray,exportWordToMutableByteArray-- ** Import,importBigNatFromAddr,importIntegerFromAddr,importBigNatFromByteArray,importIntegerFromByteArray)whereimportGHC.Integer.TypeimportGHC.IntegerimportGHC.PrimimportGHC.Typesdefault()-- | 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 0.5.1.0sizeInBaseInteger::Integer->Int#->Word#sizeInBaseInteger(S#i#)=sizeInBaseWord#(int2Word#(absI#i#))sizeInBaseInteger(Jp#bn)=sizeInBaseBigNatbnsizeInBaseInteger(Jn#bn)=sizeInBaseBigNatbn-- | Version of 'sizeInBaseInteger' operating on 'BigNat'---- @since 1.0.0.0sizeInBaseBigNat::BigNat->Int#->Word#sizeInBaseBigNatbn@(BN#ba#)=c_mpn_sizeinbase#ba#(sizeofBigNat#bn)foreignimportccallunsafe"integer_gmp_mpn_sizeinbase"c_mpn_sizeinbase#::ByteArray#->GmpSize#->Int#->Word#-- | Version of 'sizeInBaseInteger' operating on 'Word#'---- @since 1.0.0.0foreignimportccallunsafe"integer_gmp_mpn_sizeinbase1"sizeInBaseWord#::Word#->Int#->Word#-- | Dump 'Integer' (without sign) to @/addr/@ in base-256 representation.---- @'exportIntegerToAddr' /i/ /addr/ /e/@---- See description of 'exportIntegerToMutableByteArray' for more details.---- @since 1.0.0.0exportIntegerToAddr::Integer->Addr#->Int#->IOWordexportIntegerToAddr(S#i#)=exportWordToAddr(W#(int2Word#(absI#i#)))exportIntegerToAddr(Jp#bn)=exportBigNatToAddrbnexportIntegerToAddr(Jn#bn)=exportBigNatToAddrbn-- | Version of 'exportIntegerToAddr' operating on 'BigNat's.exportBigNatToAddr::BigNat->Addr#->Int#->IOWordexportBigNatToAddrbn@(BN#ba#)addre=c_mpn_exportToAddr#ba#(sizeofBigNat#bn)addr0#eforeignimportccallunsafe"integer_gmp_mpn_export"c_mpn_exportToAddr#::ByteArray#->GmpSize#->Addr#->Int#->Int#->IOWord-- | Version of 'exportIntegerToAddr' operating on 'Word's.exportWordToAddr::Word->Addr#->Int#->IOWordexportWordToAddr(W#w#)addr=c_mpn_export1ToAddr#w#addr0#-- TODO: we don't calling GMP for thatforeignimportccallunsafe"integer_gmp_mpn_export1"c_mpn_export1ToAddr#::GmpLimb#->Addr#->Int#->Int#->IOWord-- | 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 1.0.0.0exportIntegerToMutableByteArray::Integer->MutableByteArray#RealWorld->Word#->Int#->IOWordexportIntegerToMutableByteArray(S#i#)=exportWordToMutableByteArray(W#(int2Word#(absI#i#)))exportIntegerToMutableByteArray(Jp#bn)=exportBigNatToMutableByteArraybnexportIntegerToMutableByteArray(Jn#bn)=exportBigNatToMutableByteArraybn-- | Version of 'exportIntegerToMutableByteArray' operating on 'BigNat's.---- @since 1.0.0.0exportBigNatToMutableByteArray::BigNat->MutableByteArray#RealWorld->Word#->Int#->IOWordexportBigNatToMutableByteArraybn@(BN#ba#)=c_mpn_exportToMutableByteArray#ba#(sizeofBigNat#bn)foreignimportccallunsafe"integer_gmp_mpn_export"c_mpn_exportToMutableByteArray#::ByteArray#->GmpSize#->MutableByteArray#RealWorld->Word#->Int#->IOWord-- | Version of 'exportIntegerToMutableByteArray' operating on 'Word's.---- @since 1.0.0.0exportWordToMutableByteArray::Word->MutableByteArray#RealWorld->Word#->Int#->IOWordexportWordToMutableByteArray(W#w#)=c_mpn_export1ToMutableByteArray#w#foreignimportccallunsafe"integer_gmp_mpn_export1"c_mpn_export1ToMutableByteArray#::GmpLimb#->MutableByteArray#RealWorld->Word#->Int#->IOWord-- | 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-- <http://gmplib.org/manual/Number-Theoretic-Functions.html#index-mpz_005fprobab_005fprime_005fp-360 GMP documentation for `mpz_probab_prime_p()`>.---- @since 0.5.1.0{-# NOINLINEtestPrimeInteger#-}testPrimeInteger::Integer->Int#->Int#testPrimeInteger(S#i#)=testPrimeWord#(int2Word#(absI#i#))testPrimeInteger(Jp#n)=testPrimeBigNatntestPrimeInteger(Jn#n)=testPrimeBigNatn-- | Version of 'testPrimeInteger' operating on 'BigNat's---- @since 1.0.0.0testPrimeBigNat::BigNat->Int#->Int#testPrimeBigNatbn@(BN#ba#)=c_integer_gmp_test_prime#ba#(sizeofBigNat#bn)foreignimportccallunsafe"integer_gmp_test_prime"c_integer_gmp_test_prime#::ByteArray#->GmpSize#->Int#->Int#-- | Version of 'testPrimeInteger' operating on 'Word#'s---- @since 1.0.0.0foreignimportccallunsafe"integer_gmp_test_prime1"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.\"---- @since 0.5.1.0{-# NOINLINEnextPrimeInteger#-}nextPrimeInteger::Integer->IntegernextPrimeInteger(S#i#)|isTrue#(i#>#1#)=wordToInteger(nextPrimeWord#(int2Word#i#))|True=S#2#nextPrimeInteger(Jp#bn)=Jp#(nextPrimeBigNatbn)nextPrimeInteger(Jn#_)=S#2#-- | Version of 'nextPrimeInteger' operating on 'Word#'s---- @since 1.0.0.0foreignimportccallunsafe"integer_gmp_next_prime1"nextPrimeWord#::GmpLimb#->GmpLimb#