Movatterモバイル変換

{-# LANGUAGE CPP #-}{-# LANGUAGE NoImplicitPrelude #-}{-# LANGUAGE BangPatterns #-}{-# LANGUAGE MagicHash #-}{-# LANGUAGE UnboxedTuples #-}{-# LANGUAGE NegativeLiterals #-}{-# LANGUAGE BinaryLiterals #-}{-# LANGUAGE BlockArguments #-}{-# LANGUAGE LambdaCase #-}-- |-- Module      :  GHC.Num.Integer-- Copyright   :  (c) Sylvain Henry 2019,--                (c) Herbert Valerio Riedel 2014-- License     :  BSD3---- Maintainer  :  sylvain@haskus.fr-- Stability   :  provisional-- Portability :  non-portable (GHC Extensions)---- The 'Integer' type.moduleGHC.Num.Integer(Integer(..),integerCheck,integerCheck#-- * Useful constants,integerZero,integerOne-- * Conversion with...-- ** 'Int',integerFromInt#,integerFromInt,integerToInt#,integerToInt-- ** 'BigNat',integerFromBigNat#,integerFromBigNatNeg#,integerFromBigNatSign#,integerToBigNatSign#,integerToBigNatClamp#-- ** 'Word',integerFromWord#,integerFromWord,integerFromWordNeg#,integerFromWordSign#,integerToWord#,integerToWord-- ** 'Natural',integerFromNatural,integerToNaturalClamp,integerToNatural,integerToNaturalThrow-- ** 'Int64'/'Word64',integerFromInt64#,integerFromWord64#,integerToInt64#,integerToWord64#-- ** Floating-point,integerDecodeDouble#,integerEncodeDouble#,integerEncodeDouble,integerEncodeFloat#-- ** 'Addr#',integerToAddr#,integerToAddr,integerFromAddr#,integerFromAddr-- ** Limbs,integerFromWordList,integerToMutableByteArray#,integerToMutableByteArray,integerFromByteArray#,integerFromByteArray-- * Predicates,integerIsNegative#,integerIsNegative,integerIsZero,integerIsOne-- * Comparison,integerNe,integerEq,integerLe,integerLt,integerGt,integerGe,integerEq#,integerNe#,integerGt#,integerLe#,integerLt#,integerGe#,integerCompare-- * Arithmetic,integerSub,integerAdd,integerMul,integerNegate,integerAbs,integerSignum,integerSignum#,integerQuotRem#,integerQuotRem,integerQuot,integerRem,integerDivMod#,integerDivMod,integerDiv,integerMod,integerGcd,integerLcm,integerSqr,integerLog2#,integerLog2,integerLogBaseWord#,integerLogBaseWord,integerLogBase#,integerLogBase,integerIsPowerOf2#,integerGcde#,integerGcde,integerRecipMod#,integerPowMod#-- * Bit operations,integerPopCount#,integerBit#,integerBit,integerTestBit#,integerTestBit,integerShiftR#,integerShiftR,integerShiftL#,integerShiftL,integerOr,integerXor,integerAnd,integerComplement-- * Miscellaneous,integerSizeInBase#)where#include "MachDeps.h"#include "WordSize.h"importGHC.PrimimportGHC.TypesimportGHC.ClassesimportGHC.MagicimportGHC.Num.PrimitivesimportGHC.Num.BigNatimportGHC.Num.NaturalimportqualifiedGHC.Num.BackendasBackenddefault()-- | Arbitrary precision integers. In contrast with fixed-size integral types-- such as 'Int', the 'Integer' type represents the entire infinite range of-- integers.---- Integers are stored in a kind of sign-magnitude form, hence do not expect-- two's complement form when using bit operations.---- If the value is small (i.e., fits into an 'Int'), the 'IS' constructor is-- used. Otherwise 'IP' and 'IN' constructors are used to store a 'BigNat'-- representing the positive or the negative value magnitude, respectively.---- Invariant: 'IP' and 'IN' are used iff the value does not fit in 'IS'.dataInteger=IS!Int#-- ^ iff value in @[minBound::'Int', maxBound::'Int']@ range|IP!BigNat#-- ^ iff value in @]maxBound::'Int', +inf[@ range|IN!BigNat#-- ^ iff value in @]-inf, minBound::'Int'[@ range-- | Check Integer invariantsintegerCheck#::Integer->Bool#integerCheck# :: Integer -> Bool#integerCheck#(ISBool#_)=Bool#1#integerCheck#(IPByteArray#bn)=ByteArray# -> Bool#bigNatCheck#ByteArray#bnBool# -> Bool# -> Bool#&&#(ByteArray#bnByteArray# -> Word# -> Bool#`bigNatGtWord#`INT_MAXBOUND##)integerCheck#(INByteArray#bn)=ByteArray# -> Bool#bigNatCheck#ByteArray#bnBool# -> Bool# -> Bool#&&#(ByteArray#bnByteArray# -> Word# -> Bool#`bigNatGtWord#`ABS_INT_MINBOUND##)-- | Check Integer invariantsintegerCheck::Integer->BoolintegerCheck :: Integer -> BoolintegerCheckIntegeri=Bool# -> BoolisTrue#(Integer -> Bool#integerCheck#Integeri)-- | Integer ZerointegerZero::IntegerintegerZero :: IntegerintegerZero=Bool# -> IntegerISBool#0#-- | Integer OneintegerOne::IntegerintegerOne :: IntegerintegerOne=Bool# -> IntegerISBool#1#----------------------------------------------------------------------- Conversions----------------------------------------------------------------------- | Create a positive Integer from a BigNatintegerFromBigNat#::BigNat#->IntegerintegerFromBigNat# :: ByteArray# -> IntegerintegerFromBigNat#!ByteArray#bn|ByteArray# -> BoolbigNatIsZeroByteArray#bn=IntegerintegerZero|Bool# -> BoolisTrue#(ByteArray#bnByteArray# -> Word# -> Bool#`bigNatLeWord#`INT_MAXBOUND##)=Bool# -> IntegerIS(Word# -> Bool#word2Int#(ByteArray# -> Bool# -> Word#bigNatIndex#ByteArray#bnBool#0#))|BoolTrue=ByteArray# -> IntegerIPByteArray#bn-- | Create a negative Integer from a BigNatintegerFromBigNatNeg#::BigNat#->IntegerintegerFromBigNatNeg# :: ByteArray# -> IntegerintegerFromBigNatNeg#!ByteArray#bn|ByteArray# -> BoolbigNatIsZeroByteArray#bn=IntegerintegerZero|Bool#1#<-ByteArray# -> Bool#bigNatSize#ByteArray#bn,Bool#i<-Bool# -> Bool#negateInt#(Word# -> Bool#word2Int#(ByteArray# -> Bool# -> Word#bigNatIndex#ByteArray#bnBool#0#)),Bool# -> BoolisTrue#(Bool#iBool# -> Bool# -> Bool#<=#Bool#0#)=Bool# -> IntegerISBool#i|BoolTrue=ByteArray# -> IntegerINByteArray#bn-- | Create an Integer from a sign-bit and a BigNatintegerFromBigNatSign#::Int#->BigNat#->IntegerintegerFromBigNatSign# :: Bool# -> ByteArray# -> IntegerintegerFromBigNatSign#!Bool#sign!ByteArray#bn|Bool#0#<-Bool#sign=ByteArray# -> IntegerintegerFromBigNat#ByteArray#bn|BoolTrue=ByteArray# -> IntegerintegerFromBigNatNeg#ByteArray#bn-- | Convert an Integer into a sign-bit and a BigNatintegerToBigNatSign#::Integer->(#Int#,BigNat##)integerToBigNatSign# :: Integer -> (# Bool#, ByteArray# #)integerToBigNatSign#=\caseISBool#x|Bool# -> BoolisTrue#(Bool#xBool# -> Bool# -> Bool#>=#Bool#0#)->(#Bool#0#,Word# -> ByteArray#bigNatFromWord#(Bool# -> Word#int2Word#Bool#x)#)|BoolTrue->(#Bool#1#,Word# -> ByteArray#bigNatFromWord#(Bool# -> Word#int2Word#(Bool# -> Bool#negateInt#Bool#x))#)IPByteArray#x->(#Bool#0#,ByteArray#x#)INByteArray#x->(#Bool#1#,ByteArray#x#)-- | Convert an Integer into a BigNat.---- Return 0 for negative Integers.integerToBigNatClamp#::Integer->BigNat#integerToBigNatClamp# :: Integer -> ByteArray#integerToBigNatClamp#(IPByteArray#x)=ByteArray#xintegerToBigNatClamp#(ISBool#x)|Bool# -> BoolisTrue#(Bool#xBool# -> Bool# -> Bool#>=#Bool#0#)=Word# -> ByteArray#bigNatFromWord#(Bool# -> Word#int2Word#Bool#x)integerToBigNatClamp#Integer_=(# #) -> ByteArray#bigNatZero#(##)-- | Create an Integer from an Int#integerFromInt#::Int#->IntegerintegerFromInt# :: Bool# -> IntegerintegerFromInt#Bool#i=Bool# -> IntegerISBool#i-- | Create an Integer from an IntintegerFromInt::Int->IntegerintegerFromInt :: Int -> IntegerintegerFromInt(I#Bool#i)=Bool# -> IntegerISBool#i-- | Truncates 'Integer' to least-significant 'Int#'integerToInt#::Integer->Int#{-# NOINLINEintegerToInt##-}integerToInt# :: Integer -> Bool#integerToInt#(ISBool#i)=Bool#iintegerToInt#(IPByteArray#b)=Word# -> Bool#word2Int#(ByteArray# -> Word#bigNatToWord#ByteArray#b)integerToInt#(INByteArray#b)=Bool# -> Bool#negateInt#(Word# -> Bool#word2Int#(ByteArray# -> Word#bigNatToWord#ByteArray#b))-- | Truncates 'Integer' to least-significant 'Int#'integerToInt::Integer->IntintegerToInt :: Integer -> IntintegerToIntIntegeri=Bool# -> IntI#(Integer -> Bool#integerToInt#Integeri)-- | Convert a Word# into an IntegerintegerFromWord#::Word#->Integer{-# NOINLINEintegerFromWord##-}integerFromWord# :: Word# -> IntegerintegerFromWord#Word#w|Bool#i<-Word# -> Bool#word2Int#Word#w,Bool# -> BoolisTrue#(Bool#iBool# -> Bool# -> Bool#>=#Bool#0#)=Bool# -> IntegerISBool#i|BoolTrue=ByteArray# -> IntegerIP(Word# -> ByteArray#bigNatFromWord#Word#w)-- | Convert a Word into an IntegerintegerFromWord::Word->IntegerintegerFromWord :: Word -> IntegerintegerFromWord(W#Word#w)=Word# -> IntegerintegerFromWord#Word#w-- | Create a negative Integer with the given Word magnitudeintegerFromWordNeg#::Word#->IntegerintegerFromWordNeg# :: Word# -> IntegerintegerFromWordNeg#Word#w|Bool# -> BoolisTrue#(Word#wWord# -> Word# -> Bool#`leWord#`ABS_INT_MINBOUND##)=Bool# -> IntegerIS(Bool# -> Bool#negateInt#(Word# -> Bool#word2Int#Word#w))|BoolTrue=ByteArray# -> IntegerIN(Word# -> ByteArray#bigNatFromWord#Word#w)-- | Create an Integer from a sign and a Word magnitudeintegerFromWordSign#::Int#->Word#->IntegerintegerFromWordSign# :: Bool# -> Word# -> IntegerintegerFromWordSign#Bool#0#Word#w=Word# -> IntegerintegerFromWord#Word#wintegerFromWordSign#Bool#_Word#w=Word# -> IntegerintegerFromWordNeg#Word#w-- | Truncate an Integer into a WordintegerToWord#::Integer->Word#{-# NOINLINEintegerToWord##-}integerToWord# :: Integer -> Word#integerToWord#(ISBool#i)=Bool# -> Word#int2Word#Bool#iintegerToWord#(IPByteArray#bn)=ByteArray# -> Word#bigNatToWord#ByteArray#bnintegerToWord#(INByteArray#bn)=Bool# -> Word#int2Word#(Bool# -> Bool#negateInt#(Word# -> Bool#word2Int#(ByteArray# -> Word#bigNatToWord#ByteArray#bn)))-- | Truncate an Integer into a WordintegerToWord::Integer->WordintegerToWord :: Integer -> WordintegerToWord!Integeri=Word# -> WordW#(Integer -> Word#integerToWord#Integeri)-- | Convert a Natural into an IntegerintegerFromNatural::Natural->Integer{-# NOINLINEintegerFromNatural#-}integerFromNatural :: Natural -> IntegerintegerFromNatural(NSWord#x)=Word# -> IntegerintegerFromWord#Word#xintegerFromNatural(NBByteArray#x)=ByteArray# -> IntegerIPByteArray#x-- | Convert a list of Word into an IntegerintegerFromWordList::Bool->[Word]->IntegerintegerFromWordList :: Bool -> [Word] -> IntegerintegerFromWordListBoolTrue[Word]ws=ByteArray# -> IntegerintegerFromBigNatNeg#([Word] -> ByteArray#bigNatFromWordList[Word]ws)integerFromWordListBoolFalse[Word]ws=ByteArray# -> IntegerintegerFromBigNat#([Word] -> ByteArray#bigNatFromWordList[Word]ws)-- | Convert an Integer into a Natural---- Return 0 for negative Integers.integerToNaturalClamp::Integer->Natural{-# NOINLINEintegerToNaturalClamp#-}integerToNaturalClamp :: Integer -> NaturalintegerToNaturalClamp(ISBool#x)|Bool# -> BoolisTrue#(Bool#xBool# -> Bool# -> Bool#<#Bool#0#)=NaturalnaturalZero|BoolTrue=Word# -> NaturalnaturalFromWord#(Bool# -> Word#int2Word#Bool#x)integerToNaturalClamp(IPByteArray#x)=ByteArray# -> NaturalnaturalFromBigNat#ByteArray#xintegerToNaturalClamp(INByteArray#_)=NaturalnaturalZero-- | Convert an Integer into a Natural---- Return absolute valueintegerToNatural::Integer->Natural{-# NOINLINEintegerToNatural#-}integerToNatural :: Integer -> NaturalintegerToNatural(ISBool#x)=Word# -> NaturalnaturalFromWord#(Bool# -> Word#wordFromAbsInt#Bool#x)integerToNatural(IPByteArray#x)=ByteArray# -> NaturalnaturalFromBigNat#ByteArray#xintegerToNatural(INByteArray#x)=ByteArray# -> NaturalnaturalFromBigNat#ByteArray#x-- | Convert an Integer into a Natural---- Throw an Underflow exception if input is negative.integerToNaturalThrow::Integer->Natural{-# NOINLINEintegerToNaturalThrow#-}integerToNaturalThrow :: Integer -> NaturalintegerToNaturalThrow(ISBool#x)|Bool# -> BoolisTrue#(Bool#xBool# -> Bool# -> Bool#<#Bool#0#)=Naturalforall a. araiseUnderflow|BoolTrue=Word# -> NaturalnaturalFromWord#(Bool# -> Word#int2Word#Bool#x)integerToNaturalThrow(IPByteArray#x)=ByteArray# -> NaturalnaturalFromBigNat#ByteArray#xintegerToNaturalThrow(INByteArray#_)=Naturalforall a. araiseUnderflow----------------------------------------------------------------------- Predicates---------------------------------------------------------------------{- Note [Bangs in Integer functions]~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~In this module some functions have banged arguments.  E.g.    integerNe !x !y = isTrue# (integerNe# x y)This will ensure that both argument are evaluated first, and then patternmatching takes place just a multi-way jump.In some cases (e.g. integerMul, integerSub) this actually makes the functionstrict when it would otherwise not be; but in other cases (e.g integerNe) thefunction is strict in both arguments anyway.  In the latter case it's a bit mootwhether to have the bangs or not; so this Note just documents that there is noDeep Reason why they have to be there.  See Note Note [Case-to-let forstrictly-used binders] in GHC.Core.Opt.Simplify.Iteration for discussion aboutevals on strictly-used binders.I have not pointed to this Note from every such use.  There are a lot of them!-}-- | Negative predicateintegerIsNegative#::Integer->Bool#integerIsNegative# :: Integer -> Bool#integerIsNegative#(ISBool#i#)=Bool#i#Bool# -> Bool# -> Bool#<#Bool#0#integerIsNegative#(IPByteArray#_)=Bool#0#integerIsNegative#(INByteArray#_)=Bool#1#-- | Negative predicateintegerIsNegative::Integer->BoolintegerIsNegative :: Integer -> BoolintegerIsNegative!Integeri=Bool# -> BoolisTrue#(Integer -> Bool#integerIsNegative#Integeri)-- Note [Bangs in Integer functions]-- | Zero predicateintegerIsZero::Integer->BoolintegerIsZero :: Integer -> BoolintegerIsZero(ISBool#0#)=BoolTrueintegerIsZeroInteger_=BoolFalse-- | One predicateintegerIsOne::Integer->BoolintegerIsOne :: Integer -> BoolintegerIsOne(ISBool#1#)=BoolTrueintegerIsOneInteger_=BoolFalse-- | Not-equal predicate.integerNe::Integer->Integer->BoolintegerNe :: Integer -> Integer -> BoolintegerNe!Integerx!Integery=Bool# -> BoolisTrue#(Integer -> Integer -> Bool#integerNe#IntegerxIntegery)-- Note [Bangs in Integer functions]-- | Equal predicate.integerEq::Integer->Integer->BoolintegerEq :: Integer -> Integer -> BoolintegerEq!Integerx!Integery=Bool# -> BoolisTrue#(Integer -> Integer -> Bool#integerEq#IntegerxIntegery)-- See Note [Bangs in Integer functions]-- | Lower-or-equal predicate.integerLe::Integer->Integer->BoolintegerLe :: Integer -> Integer -> BoolintegerLe!Integerx!Integery=Bool# -> BoolisTrue#(Integer -> Integer -> Bool#integerLe#IntegerxIntegery)-- See Note [Bangs in Integer functions]-- | Lower predicate.integerLt::Integer->Integer->BoolintegerLt :: Integer -> Integer -> BoolintegerLt!Integerx!Integery=Bool# -> BoolisTrue#(Integer -> Integer -> Bool#integerLt#IntegerxIntegery)-- See Note [Bangs in Integer functions]-- | Greater predicate.integerGt::Integer->Integer->BoolintegerGt :: Integer -> Integer -> BoolintegerGt!Integerx!Integery=Bool# -> BoolisTrue#(Integer -> Integer -> Bool#integerGt#IntegerxIntegery)-- See Note [Bangs in Integer functions]-- | Greater-or-equal predicate.integerGe::Integer->Integer->BoolintegerGe :: Integer -> Integer -> BoolintegerGe!Integerx!Integery=Bool# -> BoolisTrue#(Integer -> Integer -> Bool#integerGe#IntegerxIntegery)-- See Note [Bangs in Integer functions]-- | Equal predicate.integerEq#::Integer->Integer->Bool#integerEq# :: Integer -> Integer -> Bool#integerEq#(ISBool#x)(ISBool#y)=Bool#xBool# -> Bool# -> Bool#==#Bool#yintegerEq#(INByteArray#x)(INByteArray#y)=ByteArray# -> ByteArray# -> Bool#bigNatEq#ByteArray#xByteArray#yintegerEq#(IPByteArray#x)(IPByteArray#y)=ByteArray# -> ByteArray# -> Bool#bigNatEq#ByteArray#xByteArray#yintegerEq#Integer_Integer_=Bool#0#-- | Not-equal predicate.integerNe#::Integer->Integer->Bool#integerNe# :: Integer -> Integer -> Bool#integerNe#(ISBool#x)(ISBool#y)=Bool#xBool# -> Bool# -> Bool#/=#Bool#yintegerNe#(INByteArray#x)(INByteArray#y)=ByteArray# -> ByteArray# -> Bool#bigNatNe#ByteArray#xByteArray#yintegerNe#(IPByteArray#x)(IPByteArray#y)=ByteArray# -> ByteArray# -> Bool#bigNatNe#ByteArray#xByteArray#yintegerNe#Integer_Integer_=Bool#1#-- | Greater predicate.integerGt#::Integer->Integer->Bool#integerGt# :: Integer -> Integer -> Bool#integerGt#(ISBool#x)(ISBool#y)=Bool#xBool# -> Bool# -> Bool#>#Bool#yintegerGt#IntegerxIntegery|OrderingGT<-Integer -> Integer -> OrderingintegerCompareIntegerxIntegery=Bool#1#integerGt#Integer_Integer_=Bool#0#-- | Lower-or-equal predicate.integerLe#::Integer->Integer->Bool#integerLe# :: Integer -> Integer -> Bool#integerLe#(ISBool#x)(ISBool#y)=Bool#xBool# -> Bool# -> Bool#<=#Bool#yintegerLe#IntegerxIntegery|OrderingGT<-Integer -> Integer -> OrderingintegerCompareIntegerxIntegery=Bool#0#integerLe#Integer_Integer_=Bool#1#-- | Lower predicate.integerLt#::Integer->Integer->Bool#integerLt# :: Integer -> Integer -> Bool#integerLt#(ISBool#x)(ISBool#y)=Bool#xBool# -> Bool# -> Bool#<#Bool#yintegerLt#IntegerxIntegery|OrderingLT<-Integer -> Integer -> OrderingintegerCompareIntegerxIntegery=Bool#1#integerLt#Integer_Integer_=Bool#0#-- | Greater-or-equal predicate.integerGe#::Integer->Integer->Bool#integerGe# :: Integer -> Integer -> Bool#integerGe#(ISBool#x)(ISBool#y)=Bool#xBool# -> Bool# -> Bool#>=#Bool#yintegerGe#IntegerxIntegery|OrderingLT<-Integer -> Integer -> OrderingintegerCompareIntegerxIntegery=Bool#0#integerGe#Integer_Integer_=Bool#1#instanceEqIntegerwhere== :: Integer -> Integer -> Bool(==)=Integer -> Integer -> BoolintegerEq/= :: Integer -> Integer -> Bool(/=)=Integer -> Integer -> BoolintegerNe-- | Compare two IntegerintegerCompare::Integer->Integer->Ordering{-# INLINEABLEintegerCompare#-}integerCompare :: Integer -> Integer -> OrderingintegerCompare(ISBool#x)(ISBool#y)=Bool# -> Bool# -> OrderingcompareInt#Bool#xBool#yintegerCompare(IPByteArray#x)(IPByteArray#y)=ByteArray# -> ByteArray# -> OrderingbigNatCompareByteArray#xByteArray#yintegerCompare(INByteArray#x)(INByteArray#y)=ByteArray# -> ByteArray# -> OrderingbigNatCompareByteArray#yByteArray#xintegerCompare(ISBool#_)(IPByteArray#_)=OrderingLTintegerCompare(ISBool#_)(INByteArray#_)=OrderingGTintegerCompare(IPByteArray#_)(ISBool#_)=OrderingGTintegerCompare(INByteArray#_)(ISBool#_)=OrderingLTintegerCompare(IPByteArray#_)(INByteArray#_)=OrderingGTintegerCompare(INByteArray#_)(IPByteArray#_)=OrderingLTinstanceOrdIntegerwherecompare :: Integer -> Integer -> Orderingcompare=Integer -> Integer -> OrderingintegerCompare< :: Integer -> Integer -> Bool(<)=Integer -> Integer -> BoolintegerLt<= :: Integer -> Integer -> Bool(<=)=Integer -> Integer -> BoolintegerLe> :: Integer -> Integer -> Bool(>)=Integer -> Integer -> BoolintegerGt>= :: Integer -> Integer -> Bool(>=)=Integer -> Integer -> BoolintegerGe----------------------------------------------------------------------- Operations----------------------------------------------------------------------- | Subtract one 'Integer' from another.integerSub::Integer->Integer->Integer{-# NOINLINEintegerSub#-}integerSub :: Integer -> Integer -> IntegerintegerSub!Integerx(ISBool#0#)=Integerx-- Note [Bangs in Integer functions]integerSub(ISBool#x#)(ISBool#y#)=caseBool# -> Bool# -> (# Bool#, Bool# #)subIntC#Bool#x#Bool#y#of(#Bool#z#,Bool#0##)->Bool# -> IntegerISBool#z#(#Bool#0#,Bool#_#)->ByteArray# -> IntegerIN(Word# -> Word# -> ByteArray#bigNatFromWord2#Word#1##Word#0##)(#Bool#z#,Bool#_#)|Bool# -> BoolisTrue#(Bool#z#Bool# -> Bool# -> Bool#>#Bool#0#)->ByteArray# -> IntegerIN(Word# -> ByteArray#bigNatFromWord#((Bool# -> Word#int2Word#(Bool# -> Bool#negateInt#Bool#z#))))|BoolTrue->ByteArray# -> IntegerIP(Word# -> ByteArray#bigNatFromWord#((Bool# -> Word#int2Word#Bool#z#)))integerSub(ISBool#x#)(IPByteArray#y)|Bool# -> BoolisTrue#(Bool#x#Bool# -> Bool# -> Bool#>=#Bool#0#)=ByteArray# -> IntegerintegerFromBigNatNeg#(ByteArray# -> Word# -> ByteArray#bigNatSubWordUnsafe#ByteArray#y(Bool# -> Word#int2Word#Bool#x#))|BoolTrue=ByteArray# -> IntegerIN(ByteArray# -> Word# -> ByteArray#bigNatAddWord#ByteArray#y(Bool# -> Word#int2Word#(Bool# -> Bool#negateInt#Bool#x#)))integerSub(ISBool#x#)(INByteArray#y)|Bool# -> BoolisTrue#(Bool#x#Bool# -> Bool# -> Bool#>=#Bool#0#)=ByteArray# -> IntegerIP(ByteArray# -> Word# -> ByteArray#bigNatAddWord#ByteArray#y(Bool# -> Word#int2Word#Bool#x#))|BoolTrue=ByteArray# -> IntegerintegerFromBigNat#(ByteArray# -> Word# -> ByteArray#bigNatSubWordUnsafe#ByteArray#y(Bool# -> Word#int2Word#(Bool# -> Bool#negateInt#Bool#x#)))integerSub(IPByteArray#x)(IPByteArray#y)=caseByteArray# -> ByteArray# -> OrderingbigNatCompareByteArray#xByteArray#yofOrderingLT->ByteArray# -> IntegerintegerFromBigNatNeg#(ByteArray# -> ByteArray# -> ByteArray#bigNatSubUnsafeByteArray#yByteArray#x)OrderingEQ->Bool# -> IntegerISBool#0#OrderingGT->ByteArray# -> IntegerintegerFromBigNat#(ByteArray# -> ByteArray# -> ByteArray#bigNatSubUnsafeByteArray#xByteArray#y)integerSub(IPByteArray#x)(INByteArray#y)=ByteArray# -> IntegerIP(ByteArray# -> ByteArray# -> ByteArray#bigNatAddByteArray#xByteArray#y)integerSub(INByteArray#x)(IPByteArray#y)=ByteArray# -> IntegerIN(ByteArray# -> ByteArray# -> ByteArray#bigNatAddByteArray#xByteArray#y)integerSub(INByteArray#x)(INByteArray#y)=caseByteArray# -> ByteArray# -> OrderingbigNatCompareByteArray#xByteArray#yofOrderingLT->ByteArray# -> IntegerintegerFromBigNat#(ByteArray# -> ByteArray# -> ByteArray#bigNatSubUnsafeByteArray#yByteArray#x)OrderingEQ->Bool# -> IntegerISBool#0#OrderingGT->ByteArray# -> IntegerintegerFromBigNatNeg#(ByteArray# -> ByteArray# -> ByteArray#bigNatSubUnsafeByteArray#xByteArray#y)integerSub(IPByteArray#x)(ISBool#y#)|Bool# -> BoolisTrue#(Bool#y#Bool# -> Bool# -> Bool#>=#Bool#0#)=ByteArray# -> IntegerintegerFromBigNat#(ByteArray# -> Word# -> ByteArray#bigNatSubWordUnsafe#ByteArray#x(Bool# -> Word#int2Word#Bool#y#))|BoolTrue=ByteArray# -> IntegerIP(ByteArray# -> Word# -> ByteArray#bigNatAddWord#ByteArray#x(Bool# -> Word#int2Word#(Bool# -> Bool#negateInt#Bool#y#)))integerSub(INByteArray#x)(ISBool#y#)|Bool# -> BoolisTrue#(Bool#y#Bool# -> Bool# -> Bool#>=#Bool#0#)=ByteArray# -> IntegerIN(ByteArray# -> Word# -> ByteArray#bigNatAddWord#ByteArray#x(Bool# -> Word#int2Word#Bool#y#))|BoolTrue=ByteArray# -> IntegerintegerFromBigNatNeg#(ByteArray# -> Word# -> ByteArray#bigNatSubWordUnsafe#ByteArray#x(Bool# -> Word#int2Word#(Bool# -> Bool#negateInt#Bool#y#)))-- | Add two 'Integer'sintegerAdd::Integer->Integer->Integer{-# NOINLINEintegerAdd#-}integerAdd :: Integer -> Integer -> IntegerintegerAdd!Integerx(ISBool#0#)=IntegerxintegerAdd(ISBool#0#)Integery=IntegeryintegerAdd(ISBool#x#)(ISBool#y#)=caseBool# -> Bool# -> (# Bool#, Bool# #)addIntC#Bool#x#Bool#y#of(#Bool#z#,Bool#0##)->Bool# -> IntegerISBool#z#(#Bool#0#,Bool#_#)->ByteArray# -> IntegerIN(Word# -> Word# -> ByteArray#bigNatFromWord2#Word#1##Word#0##)-- 2*minBound::Int(#Bool#z#,Bool#_#)|Bool# -> BoolisTrue#(Bool#z#Bool# -> Bool# -> Bool#>#Bool#0#)->ByteArray# -> IntegerIN(Word# -> ByteArray#bigNatFromWord#((Bool# -> Word#int2Word#(Bool# -> Bool#negateInt#Bool#z#))))|BoolTrue->ByteArray# -> IntegerIP(Word# -> ByteArray#bigNatFromWord#((Bool# -> Word#int2Word#Bool#z#)))integerAddy :: Integery@(ISBool#_)Integerx=Integer -> Integer -> IntegerintegerAddIntegerxIntegeryintegerAdd(IPByteArray#x)(IPByteArray#y)=ByteArray# -> IntegerIP(ByteArray# -> ByteArray# -> ByteArray#bigNatAddByteArray#xByteArray#y)integerAdd(INByteArray#x)(INByteArray#y)=ByteArray# -> IntegerIN(ByteArray# -> ByteArray# -> ByteArray#bigNatAddByteArray#xByteArray#y)integerAdd(IPByteArray#x)(ISBool#y#)-- edge-case: @(maxBound+1) + minBound == 0@|Bool# -> BoolisTrue#(Bool#y#Bool# -> Bool# -> Bool#>=#Bool#0#)=ByteArray# -> IntegerIP(ByteArray# -> Word# -> ByteArray#bigNatAddWord#ByteArray#x(Bool# -> Word#int2Word#Bool#y#))|BoolTrue=ByteArray# -> IntegerintegerFromBigNat#(ByteArray# -> Word# -> ByteArray#bigNatSubWordUnsafe#ByteArray#x(Bool# -> Word#int2Word#(Bool# -> Bool#negateInt#Bool#y#)))integerAdd(INByteArray#x)(ISBool#y#)-- edge-case: @(minBound-1) + maxBound == -2@|Bool# -> BoolisTrue#(Bool#y#Bool# -> Bool# -> Bool#>=#Bool#0#)=ByteArray# -> IntegerintegerFromBigNatNeg#(ByteArray# -> Word# -> ByteArray#bigNatSubWordUnsafe#ByteArray#x(Bool# -> Word#int2Word#Bool#y#))|BoolTrue=ByteArray# -> IntegerIN(ByteArray# -> Word# -> ByteArray#bigNatAddWord#ByteArray#x(Bool# -> Word#int2Word#(Bool# -> Bool#negateInt#Bool#y#)))integerAddy :: Integery@(INByteArray#_)x :: Integerx@(IPByteArray#_)=Integer -> Integer -> IntegerintegerAddIntegerxIntegeryintegerAdd(IPByteArray#x)(INByteArray#y)=caseByteArray# -> ByteArray# -> OrderingbigNatCompareByteArray#xByteArray#yofOrderingLT->ByteArray# -> IntegerintegerFromBigNatNeg#(ByteArray# -> ByteArray# -> ByteArray#bigNatSubUnsafeByteArray#yByteArray#x)OrderingEQ->Bool# -> IntegerISBool#0#OrderingGT->ByteArray# -> IntegerintegerFromBigNat#(ByteArray# -> ByteArray# -> ByteArray#bigNatSubUnsafeByteArray#xByteArray#y)-- | Multiply two 'Integer'sintegerMul::Integer->Integer->Integer{-# NOINLINEintegerMul#-}integerMul :: Integer -> Integer -> IntegerintegerMul!Integer_(ISBool#0#)=Bool# -> IntegerISBool#0#-- Note [Bangs in Integer functions]integerMul(ISBool#0#)Integer_=Bool# -> IntegerISBool#0#integerMulIntegerx(ISBool#1#)=IntegerxintegerMul(ISBool#1#)Integery=IntegeryintegerMulIntegerx(ISBool#-1#)=Integer -> IntegerintegerNegateIntegerxintegerMul(ISBool#-1#)Integery=Integer -> IntegerintegerNegateIntegery#if __GLASGOW_HASKELL__ < 811integerMul(ISx)(ISy)=casemulIntMayOflo#xyof0#->IS(x*#y)_->case(#isTrue#(x>=#0#),isTrue#(y>=#0#)#)of(#False,False#)->casetimesWord2#(int2Word#(negateInt#x))(int2Word#(negateInt#y))of(#0##,l#)->integerFromWord#l(#h,l#)->IP(bigNatFromWord2#hl)(#True,False#)->casetimesWord2#(int2Word#x)(int2Word#(negateInt#y))of(#0##,l#)->integerFromWordNeg#l(#h,l#)->IN(bigNatFromWord2#hl)(#False,True#)->casetimesWord2#(int2Word#(negateInt#x))(int2Word#y)of(#0##,l#)->integerFromWordNeg#l(#h,l#)->IN(bigNatFromWord2#hl)(#True,True#)->casetimesWord2#(int2Word#x)(int2Word#y)of(#0##,l#)->integerFromWord#l(#h,l#)->IP(bigNatFromWord2#hl)#elseintegerMul(ISBool#x)(ISBool#y)=caseBool# -> Bool# -> (# Bool#, Bool#, Bool# #)timesInt2#Bool#xBool#yof(#Bool#0#,Bool#_h,Bool#l#)->Bool# -> IntegerISBool#l(#Bool#_,Bool#h,Bool#l#)|Bool# -> BoolisTrue#(Bool#hBool# -> Bool# -> Bool#>=#Bool#0#)->ByteArray# -> IntegerIP(Word# -> Word# -> ByteArray#bigNatFromWord2#(Bool# -> Word#int2Word#Bool#h)(Bool# -> Word#int2Word#Bool#l))|BoolTrue->let-- two's complement of a two-word negative Int:--   l' = complement l + 1--   h' = complement h + carry!(#Word#l',Bool#c#)=Word# -> Word# -> (# Word#, Bool# #)addWordC#(Word# -> Word#not#(Bool# -> Word#int2Word#Bool#l))Word#1##!h' :: Word#h'=Bool# -> Word#int2Word#Bool#cWord# -> Word# -> Word#`plusWord#`Word# -> Word#not#(Bool# -> Word#int2Word#Bool#h)inByteArray# -> IntegerIN(Word# -> Word# -> ByteArray#bigNatFromWord2#Word#h'Word#l')#endifintegerMulx :: Integerx@(ISBool#_)Integery=Integer -> Integer -> IntegerintegerMulIntegeryIntegerxintegerMul(IPByteArray#x)(IPByteArray#y)=ByteArray# -> IntegerIP(ByteArray# -> ByteArray# -> ByteArray#bigNatMulByteArray#xByteArray#y)integerMul(IPByteArray#x)(INByteArray#y)=ByteArray# -> IntegerIN(ByteArray# -> ByteArray# -> ByteArray#bigNatMulByteArray#xByteArray#y)integerMul(IPByteArray#x)(ISBool#y)|Bool# -> BoolisTrue#(Bool#yBool# -> Bool# -> Bool#>=#Bool#0#)=ByteArray# -> IntegerIP(ByteArray# -> Word# -> ByteArray#bigNatMulWord#ByteArray#x(Bool# -> Word#int2Word#Bool#y))|BoolTrue=ByteArray# -> IntegerIN(ByteArray# -> Word# -> ByteArray#bigNatMulWord#ByteArray#x(Bool# -> Word#int2Word#(Bool# -> Bool#negateInt#Bool#y)))integerMul(INByteArray#x)(INByteArray#y)=ByteArray# -> IntegerIP(ByteArray# -> ByteArray# -> ByteArray#bigNatMulByteArray#xByteArray#y)integerMul(INByteArray#x)(IPByteArray#y)=ByteArray# -> IntegerIN(ByteArray# -> ByteArray# -> ByteArray#bigNatMulByteArray#xByteArray#y)integerMul(INByteArray#x)(ISBool#y)|Bool# -> BoolisTrue#(Bool#yBool# -> Bool# -> Bool#>=#Bool#0#)=ByteArray# -> IntegerIN(ByteArray# -> Word# -> ByteArray#bigNatMulWord#ByteArray#x(Bool# -> Word#int2Word#Bool#y))|BoolTrue=ByteArray# -> IntegerIP(ByteArray# -> Word# -> ByteArray#bigNatMulWord#ByteArray#x(Bool# -> Word#int2Word#(Bool# -> Bool#negateInt#Bool#y)))-- | Negate 'Integer'.---- One edge-case issue to take into account is that Int's range is not-- symmetric around 0.  I.e. @minBound+maxBound = -1@---- IP is used iff n > maxBound::Int-- IN is used iff n < minBound::IntintegerNegate::Integer->Integer{-# NOINLINEintegerNegate#-}integerNegate :: Integer -> IntegerintegerNegate(INByteArray#b)=ByteArray# -> IntegerIPByteArray#bintegerNegate(ISINT_MINBOUND#)=IP(bigNatFromWord#ABS_INT_MINBOUND##)integerNegate(ISBool#i)=Bool# -> IntegerIS(Bool# -> Bool#negateInt#Bool#i)integerNegate(IPByteArray#b)|Bool# -> BoolisTrue#(ByteArray# -> Word# -> Bool#bigNatEqWord#ByteArray#bABS_INT_MINBOUND##)=ISINT_MINBOUND#|BoolTrue=ByteArray# -> IntegerINByteArray#b{-# RULES"integerNegate/integerNegate"forallx.integerNegate(integerNegatex)=x#-}-- | Compute absolute value of an 'Integer'integerAbs::Integer->Integer{-# NOINLINEintegerAbs#-}integerAbs :: Integer -> IntegerintegerAbs(INByteArray#i)=ByteArray# -> IntegerIPByteArray#iintegerAbsn :: Integern@(IPByteArray#_)=IntegernintegerAbsn :: Integern@(ISBool#i)|Bool# -> BoolisTrue#(Bool#iBool# -> Bool# -> Bool#>=#Bool#0#)=Integern|INT_MINBOUND#<-i=IPBool#(bigNatFromWord#ABS_INT_MINBOUND##)|BoolTrue=Bool# -> IntegerIS(Bool# -> Bool#negateInt#Bool#i)-- | Return @-1@, @0@, and @1@ depending on whether argument is-- negative, zero, or positive, respectivelyintegerSignum::Integer->IntegerintegerSignum :: Integer -> IntegerintegerSignum!Integerj=Bool# -> IntegerIS(Integer -> Bool#integerSignum#Integerj)-- Note [Bangs in Integer functions]-- | Return @-1#@, @0#@, and @1#@ depending on whether argument is-- negative, zero, or positive, respectivelyintegerSignum#::Integer->Int#integerSignum# :: Integer -> Bool#integerSignum#(INByteArray#_)=Bool#-1#integerSignum#(ISBool#i#)=Bool# -> Bool#sgnI#Bool#i#integerSignum#(IPByteArray#_)=Bool#1#-- | Count number of set bits. For negative arguments returns-- the negated population count of the absolute value.integerPopCount#::Integer->Int#{-# NOINLINEintegerPopCount##-}integerPopCount# :: Integer -> Bool#integerPopCount#(ISBool#i)|Bool# -> BoolisTrue#(Bool#iBool# -> Bool# -> Bool#>=#Bool#0#)=Word# -> Bool#word2Int#(Bool# -> Word#popCntI#Bool#i)|BoolTrue=Bool# -> Bool#negateInt#(Word# -> Bool#word2Int#(Bool# -> Word#popCntI#(Bool# -> Bool#negateInt#Bool#i)))integerPopCount#(IPByteArray#bn)=Word# -> Bool#word2Int#(ByteArray# -> Word#bigNatPopCount#ByteArray#bn)integerPopCount#(INByteArray#bn)=Bool# -> Bool#negateInt#(Word# -> Bool#word2Int#(ByteArray# -> Word#bigNatPopCount#ByteArray#bn))-- | Positive 'Integer' for which only /n/-th bit is setintegerBit#::Word#->Integer{-# NOINLINEintegerBit##-}integerBit# :: Word# -> IntegerintegerBit#Word#i|Bool# -> BoolisTrue#(Word#iWord# -> Word# -> Bool#`ltWord#`(WORD_SIZE_IN_BITS##`minusWord#`1##))=Bool# -> IntegerIS(Bool# -> Bool# -> Bool#uncheckedIShiftL#Bool#1#(Word# -> Bool#word2Int#Word#i))|BoolTrue=ByteArray# -> IntegerIP(Word# -> ByteArray#bigNatBit#Word#i)-- | 'Integer' for which only /n/-th bit is setintegerBit::Word->IntegerintegerBit :: Word -> IntegerintegerBit(W#Word#i)=Word# -> IntegerintegerBit#Word#i-- | Test if /n/-th bit is set.---- Fake 2's complement for negative values (might be slow)integerTestBit#::Integer->Word#->Bool#{-# NOINLINEintegerTestBit##-}integerTestBit# :: Integer -> Word# -> Bool#integerTestBit#(ISBool#x)Word#i|Bool# -> BoolisTrue#(Word#iWord# -> Word# -> Bool#`ltWord#`WORD_SIZE_IN_BITS##)=Bool# -> Word# -> Bool#testBitI#Bool#xWord#i|BoolTrue=Bool#xBool# -> Bool# -> Bool#<#Bool#0#integerTestBit#(IPByteArray#x)Word#i=ByteArray# -> Word# -> Bool#bigNatTestBit#ByteArray#xWord#iintegerTestBit#(INByteArray#x)Word#i|Bool# -> BoolisTrue#(Bool#iwBool# -> Bool# -> Bool#>=#Bool#n)=Bool#1#-- if all the limbs j with j < iw are null, then we have to consider the-- carry of the 2's complement conversion. Otherwise we just have to return-- the inverse of the bit test|Bool# -> BoolallZBool#iw=Word# -> Word# -> Bool#testBitW#(Word#xiWord# -> Word# -> Word#`minusWord#`Word#1##)Word#ibBool# -> Bool# -> Bool#==#Bool#0#|BoolTrue=Word# -> Word# -> Bool#testBitW#Word#xiWord#ibBool# -> Bool# -> Bool#==#Bool#0#where!xi :: Word#xi=ByteArray# -> Bool# -> Word#bigNatIndex#ByteArray#xBool#iw!n :: Bool#n=ByteArray# -> Bool#bigNatSize#ByteArray#x!iw :: Bool#iw=Word# -> Bool#word2Int#(Word#iWord# -> Bool# -> Word#`uncheckedShiftRL#`WORD_SIZE_BITS_SHIFT#)!ib :: Word#ib=Word#iWord# -> Word# -> Word#`and#`WORD_SIZE_BITS_MASK##allZ :: Bool# -> BoolallZBool#0#=BoolTrueallZBool#j|Bool# -> BoolisTrue#(ByteArray# -> Bool# -> Word#bigNatIndex#ByteArray#x(Bool#jBool# -> Bool# -> Bool#-#Bool#1#)Word# -> Word# -> Bool#`eqWord#`Word#0##)=Bool# -> BoolallZ(Bool#jBool# -> Bool# -> Bool#-#Bool#1#)|BoolTrue=BoolFalse-- | Test if /n/-th bit is set. For negative Integers it tests the n-th bit of-- the negated argument.---- Fake 2's complement for negative values (might be slow)integerTestBit::Integer->Word->BoolintegerTestBit :: Integer -> Word -> BoolintegerTestBit!Integeri(W#Word#n)=Bool# -> BoolisTrue#(Integer -> Word# -> Bool#integerTestBit#IntegeriWord#n)-- | Shift-right operation---- Fake 2's complement for negative values (might be slow)integerShiftR#::Integer->Word#->Integer{-# NOINLINEintegerShiftR##-}integerShiftR# :: Integer -> Word# -> IntegerintegerShiftR#!IntegerxWord#0##=Integerx-- Note [Bangs in Integer functions]integerShiftR#(ISBool#i)Word#n=Bool# -> IntegerIS(Bool# -> Bool# -> Bool#iShiftRA#Bool#i(Word# -> Bool#word2Int#Word#n))whereiShiftRA# :: Bool# -> Bool# -> Bool#iShiftRA#Bool#aBool#b|Bool# -> BoolisTrue#(Bool#bBool# -> Bool# -> Bool#>=#WORD_SIZE_IN_BITS#)=(a<#0#)*#(-1#)|BoolTrue=Bool#aBool# -> Bool# -> Bool#`uncheckedIShiftRA#`Bool#bintegerShiftR#(IPByteArray#bn)Word#n=ByteArray# -> IntegerintegerFromBigNat#(ByteArray# -> Word# -> ByteArray#bigNatShiftR#ByteArray#bnWord#n)integerShiftR#(INByteArray#bn)Word#n=caseByteArray# -> IntegerintegerFromBigNatNeg#(ByteArray# -> Word# -> ByteArray#bigNatShiftRNeg#ByteArray#bnWord#n)ofISBool#0#->Bool# -> IntegerISBool#-1#Integerr->Integerr-- | Shift-right operation---- Fake 2's complement for negative values (might be slow)integerShiftR::Integer->Word->IntegerintegerShiftR :: Integer -> Word -> IntegerintegerShiftR!Integerx(W#Word#w)=Integer -> Word# -> IntegerintegerShiftR#IntegerxWord#w-- Note [Bangs in Integer functions]-- | Shift-left operationintegerShiftL#::Integer->Word#->Integer{-# NOINLINEintegerShiftL##-}integerShiftL# :: Integer -> Word# -> IntegerintegerShiftL#!IntegerxWord#0##=Integerx-- Note [Bangs in Integer functions]integerShiftL#(ISBool#0#)Word#_=Bool# -> IntegerISBool#0#integerShiftL#(ISBool#1#)Word#n=Word# -> IntegerintegerBit#Word#nintegerShiftL#(ISBool#i)Word#n|Bool# -> BoolisTrue#(Bool#iBool# -> Bool# -> Bool#>=#Bool#0#)=ByteArray# -> IntegerintegerFromBigNat#(ByteArray# -> Word# -> ByteArray#bigNatShiftL#(Word# -> ByteArray#bigNatFromWord#(Bool# -> Word#int2Word#Bool#i))Word#n)|BoolTrue=ByteArray# -> IntegerintegerFromBigNatNeg#(ByteArray# -> Word# -> ByteArray#bigNatShiftL#(Word# -> ByteArray#bigNatFromWord#(Bool# -> Word#int2Word#(Bool# -> Bool#negateInt#Bool#i)))Word#n)integerShiftL#(IPByteArray#bn)Word#n=ByteArray# -> IntegerIP(ByteArray# -> Word# -> ByteArray#bigNatShiftL#ByteArray#bnWord#n)integerShiftL#(INByteArray#bn)Word#n=ByteArray# -> IntegerIN(ByteArray# -> Word# -> ByteArray#bigNatShiftL#ByteArray#bnWord#n)-- | Shift-left operation---- Remember that bits are stored in sign-magnitude form, hence the behavior of-- negative Integers is different from negative Int's behavior.integerShiftL::Integer->Word->IntegerintegerShiftL :: Integer -> Word -> IntegerintegerShiftL!Integerx(W#Word#w)=Integer -> Word# -> IntegerintegerShiftL#IntegerxWord#w-- Note [Bangs in Integer functions]-- | Bitwise OR operation---- Fake 2's complement for negative values (might be slow)integerOr::Integer->Integer->Integer{-# NOINLINEintegerOr#-}integerOr :: Integer -> Integer -> IntegerintegerOrIntegeraIntegerb=caseIntegeraofISBool#0#->IntegerbISBool#-1#->Bool# -> IntegerISBool#-1#ISBool#x->caseIntegerbofISBool#0#->IntegeraISBool#-1#->Bool# -> IntegerISBool#-1#ISBool#y->Bool# -> IntegerIS(Bool# -> Bool# -> Bool#orI#Bool#xBool#y)IPByteArray#y|Bool# -> BoolisTrue#(Bool#xBool# -> Bool# -> Bool#>=#Bool#0#)->ByteArray# -> IntegerIP(ByteArray# -> Word# -> ByteArray#bigNatOrWord#ByteArray#y(Bool# -> Word#int2Word#Bool#x))|BoolTrue->ByteArray# -> IntegerintegerFromBigNatNeg#(ByteArray# -> Word# -> ByteArray#bigNatAddWord#(ByteArray# -> ByteArray# -> ByteArray#bigNatAndNot-- use De Morgan's laws(Word# -> ByteArray#bigNatFromWord#(Bool# -> Word#int2Word#(Bool# -> Bool#negateInt#Bool#x)Word# -> Word# -> Word#`minusWord#`Word#1##))ByteArray#y)Word#1##)INByteArray#y|Bool# -> BoolisTrue#(Bool#xBool# -> Bool# -> Bool#>=#Bool#0#)->ByteArray# -> IntegerintegerFromBigNatNeg#(ByteArray# -> Word# -> ByteArray#bigNatAddWord#(ByteArray# -> Word# -> ByteArray#bigNatAndNotWord#-- use De Morgan's laws(ByteArray# -> Word# -> ByteArray#bigNatSubWordUnsafe#ByteArray#yWord#1##)(Bool# -> Word#int2Word#Bool#x))Word#1##)|BoolTrue->ByteArray# -> IntegerintegerFromBigNatNeg#(ByteArray# -> Word# -> ByteArray#bigNatAddWord#(ByteArray# -> Word# -> ByteArray#bigNatAndWord#-- use De Morgan's laws(ByteArray# -> Word# -> ByteArray#bigNatSubWordUnsafe#ByteArray#yWord#1##)(Bool# -> Word#int2Word#(Bool# -> Bool#negateInt#Bool#x)Word# -> Word# -> Word#`minusWord#`Word#1##))Word#1##)IPByteArray#x->caseIntegerbofISBool#_->Integer -> Integer -> IntegerintegerOrIntegerbIntegeraIPByteArray#y->ByteArray# -> IntegerIP(ByteArray# -> ByteArray# -> ByteArray#bigNatOrByteArray#xByteArray#y)INByteArray#y->ByteArray# -> IntegerintegerFromBigNatNeg#(ByteArray# -> Word# -> ByteArray#bigNatAddWord#(ByteArray# -> ByteArray# -> ByteArray#bigNatAndNot-- use De Morgan's laws(ByteArray# -> Word# -> ByteArray#bigNatSubWordUnsafe#ByteArray#yWord#1##)ByteArray#x)Word#1##)INByteArray#x->caseIntegerbofISBool#_->Integer -> Integer -> IntegerintegerOrIntegerbIntegeraINByteArray#y->ByteArray# -> IntegerintegerFromBigNatNeg#(ByteArray# -> Word# -> ByteArray#bigNatAddWord#(ByteArray# -> ByteArray# -> ByteArray#bigNatAnd-- use De Morgan's laws(ByteArray# -> Word# -> ByteArray#bigNatSubWordUnsafe#ByteArray#xWord#1##)(ByteArray# -> Word# -> ByteArray#bigNatSubWordUnsafe#ByteArray#yWord#1##))Word#1##)IPByteArray#y->ByteArray# -> IntegerintegerFromBigNatNeg#(ByteArray# -> Word# -> ByteArray#bigNatAddWord#(ByteArray# -> ByteArray# -> ByteArray#bigNatAndNot-- use De Morgan's laws(ByteArray# -> Word# -> ByteArray#bigNatSubWordUnsafe#ByteArray#xWord#1##)ByteArray#y)Word#1##)-- | Bitwise XOR operation---- Fake 2's complement for negative values (might be slow)integerXor::Integer->Integer->Integer{-# NOINLINEintegerXor#-}integerXor :: Integer -> Integer -> IntegerintegerXorIntegeraIntegerb=caseIntegeraofISBool#0#->IntegerbISBool#-1#->Integer -> IntegerintegerComplementIntegerbISBool#x->caseIntegerbofISBool#0#->IntegeraISBool#-1#->Integer -> IntegerintegerComplementIntegeraISBool#y->Bool# -> IntegerIS(Bool# -> Bool# -> Bool#xorI#Bool#xBool#y)IPByteArray#y|Bool# -> BoolisTrue#(Bool#xBool# -> Bool# -> Bool#>=#Bool#0#)->ByteArray# -> IntegerintegerFromBigNat#(ByteArray# -> Word# -> ByteArray#bigNatXorWord#ByteArray#y(Bool# -> Word#int2Word#Bool#x))|BoolTrue->ByteArray# -> IntegerintegerFromBigNatNeg#(ByteArray# -> Word# -> ByteArray#bigNatAddWord#(ByteArray# -> Word# -> ByteArray#bigNatXorWord#ByteArray#y(Bool# -> Word#int2Word#(Bool# -> Bool#negateInt#Bool#x)Word# -> Word# -> Word#`minusWord#`Word#1##))Word#1##)INByteArray#y|Bool# -> BoolisTrue#(Bool#xBool# -> Bool# -> Bool#>=#Bool#0#)->ByteArray# -> IntegerintegerFromBigNatNeg#(ByteArray# -> Word# -> ByteArray#bigNatAddWord#(ByteArray# -> Word# -> ByteArray#bigNatXorWord#(ByteArray# -> Word# -> ByteArray#bigNatSubWordUnsafe#ByteArray#yWord#1##)(Bool# -> Word#int2Word#Bool#x))Word#1##)|BoolTrue->ByteArray# -> IntegerintegerFromBigNat#(ByteArray# -> Word# -> ByteArray#bigNatXorWord#-- xor (not x) (not y) = xor x y(ByteArray# -> Word# -> ByteArray#bigNatSubWordUnsafe#ByteArray#yWord#1##)(Bool# -> Word#int2Word#(Bool# -> Bool#negateInt#Bool#x)Word# -> Word# -> Word#`minusWord#`Word#1##))IPByteArray#x->caseIntegerbofISBool#_->Integer -> Integer -> IntegerintegerXorIntegerbIntegeraIPByteArray#y->ByteArray# -> IntegerintegerFromBigNat#(ByteArray# -> ByteArray# -> ByteArray#bigNatXorByteArray#xByteArray#y)INByteArray#y->ByteArray# -> IntegerintegerFromBigNatNeg#(ByteArray# -> Word# -> ByteArray#bigNatAddWord#(ByteArray# -> ByteArray# -> ByteArray#bigNatXorByteArray#x(ByteArray# -> Word# -> ByteArray#bigNatSubWordUnsafe#ByteArray#yWord#1##))Word#1##)INByteArray#x->caseIntegerbofISBool#_->Integer -> Integer -> IntegerintegerXorIntegerbIntegeraINByteArray#y->ByteArray# -> IntegerintegerFromBigNat#(ByteArray# -> ByteArray# -> ByteArray#bigNatXor-- xor (not x) (not y) = xor x y(ByteArray# -> Word# -> ByteArray#bigNatSubWordUnsafe#ByteArray#xWord#1##)(ByteArray# -> Word# -> ByteArray#bigNatSubWordUnsafe#ByteArray#yWord#1##))IPByteArray#y->ByteArray# -> IntegerintegerFromBigNatNeg#(ByteArray# -> Word# -> ByteArray#bigNatAddWord#(ByteArray# -> ByteArray# -> ByteArray#bigNatXorByteArray#y(ByteArray# -> Word# -> ByteArray#bigNatSubWordUnsafe#ByteArray#xWord#1##))Word#1##)-- | Bitwise AND operation---- Fake 2's complement for negative values (might be slow)integerAnd::Integer->Integer->Integer{-# NOINLINEintegerAnd#-}integerAnd :: Integer -> Integer -> IntegerintegerAndIntegeraIntegerb=caseIntegeraofISBool#0#->Bool# -> IntegerISBool#0#ISBool#-1#->IntegerbISBool#x->caseIntegerbofISBool#0#->Bool# -> IntegerISBool#0#ISBool#-1#->IntegeraISBool#y->Bool# -> IntegerIS(Bool# -> Bool# -> Bool#andI#Bool#xBool#y)IPByteArray#y->ByteArray# -> IntegerintegerFromBigNat#(ByteArray# -> Bool# -> ByteArray#bigNatAndInt#ByteArray#yBool#x)INByteArray#y|Bool# -> BoolisTrue#(Bool#xBool# -> Bool# -> Bool#>=#Bool#0#)->Word# -> IntegerintegerFromWord#(Bool# -> Word#int2Word#Bool#xWord# -> Word# -> Word#`andNot#`(ByteArray# -> Bool# -> Word#indexWordArray#ByteArray#yBool#0#Word# -> Word# -> Word#`minusWord#`Word#1##))|BoolTrue->ByteArray# -> IntegerintegerFromBigNatNeg#(ByteArray# -> Word# -> ByteArray#bigNatAddWord#(ByteArray# -> Word# -> ByteArray#bigNatOrWord#-- use De Morgan's laws(ByteArray# -> Word# -> ByteArray#bigNatSubWordUnsafe#ByteArray#yWord#1##)(Bool# -> Word#wordFromAbsInt#Bool#xWord# -> Word# -> Word#`minusWord#`Word#1##))Word#1##)IPByteArray#x->caseIntegerbofISBool#_->Integer -> Integer -> IntegerintegerAndIntegerbIntegeraIPByteArray#y->ByteArray# -> IntegerintegerFromBigNat#(ByteArray# -> ByteArray# -> ByteArray#bigNatAndByteArray#xByteArray#y)INByteArray#y->ByteArray# -> IntegerintegerFromBigNat#(ByteArray# -> ByteArray# -> ByteArray#bigNatAndNotByteArray#x(ByteArray# -> Word# -> ByteArray#bigNatSubWordUnsafe#ByteArray#yWord#1##))INByteArray#x->caseIntegerbofISBool#_->Integer -> Integer -> IntegerintegerAndIntegerbIntegeraINByteArray#y->ByteArray# -> IntegerintegerFromBigNatNeg#(ByteArray# -> Word# -> ByteArray#bigNatAddWord#(ByteArray# -> ByteArray# -> ByteArray#bigNatOr-- use De Morgan's laws(ByteArray# -> Word# -> ByteArray#bigNatSubWordUnsafe#ByteArray#xWord#1##)(ByteArray# -> Word# -> ByteArray#bigNatSubWordUnsafe#ByteArray#yWord#1##))Word#1##)IPByteArray#y->ByteArray# -> IntegerintegerFromBigNat#(ByteArray# -> ByteArray# -> ByteArray#bigNatAndNotByteArray#y(ByteArray# -> Word# -> ByteArray#bigNatSubWordUnsafe#ByteArray#xWord#1##))-- | Binary complement of theintegerComplement::Integer->Integer{-# NOINLINEintegerComplement#-}integerComplement :: Integer -> IntegerintegerComplement(ISBool#x)=Bool# -> IntegerIS(Bool# -> Bool#notI#Bool#x)integerComplement(IPByteArray#x)=ByteArray# -> IntegerIN(ByteArray# -> Word# -> ByteArray#bigNatAddWord#ByteArray#xWord#1##)integerComplement(INByteArray#x)=ByteArray# -> IntegerIP(ByteArray# -> Word# -> ByteArray#bigNatSubWordUnsafe#ByteArray#xWord#1##)-- | Simultaneous 'integerQuot' and 'integerRem'.---- Divisor must be non-zero otherwise the GHC runtime will terminate-- with a division-by-zero fault.integerQuotRem#::Integer->Integer->(#Integer,Integer#){-# NOINLINEintegerQuotRem##-}integerQuotRem# :: Integer -> Integer -> (# Integer, Integer #)integerQuotRem#!Integern(ISBool#1#)=(#Integern,Bool# -> IntegerISBool#0##)-- Note [Bangs in Integer functions]integerQuotRem#!Integern(ISBool#-1#)=let!q :: Integerq=Integer -> IntegerintegerNegateIntegernin(#Integerq,(Bool# -> IntegerISBool#0#)#)integerQuotRem#!Integer_(ISBool#0#)=caseZonkAny 0forall a. araiseDivZeroof!ZonkAny 0_->(#Bool# -> IntegerISBool#0#,Bool# -> IntegerISBool#0##)-- see Note [ghc-bignum exceptions] in GHC.Num.PrimitivesintegerQuotRem#(ISBool#0#)Integer_=(#Bool# -> IntegerISBool#0#,Bool# -> IntegerISBool#0##)integerQuotRem#(ISBool#n#)(ISBool#d#)=caseBool# -> Bool# -> (# Bool#, Bool# #)quotRemInt#Bool#n#Bool#d#of(#Bool#q#,Bool#r##)->(#Bool# -> IntegerISBool#q#,Bool# -> IntegerISBool#r##)integerQuotRem#(IPByteArray#n)(IPByteArray#d)=caseByteArray# -> ByteArray# -> (# ByteArray#, ByteArray# #)bigNatQuotRem#ByteArray#nByteArray#dof(#ByteArray#q,ByteArray#r#)->(#ByteArray# -> IntegerintegerFromBigNat#ByteArray#q,ByteArray# -> IntegerintegerFromBigNat#ByteArray#r#)integerQuotRem#(IPByteArray#n)(INByteArray#d)=caseByteArray# -> ByteArray# -> (# ByteArray#, ByteArray# #)bigNatQuotRem#ByteArray#nByteArray#dof(#ByteArray#q,ByteArray#r#)->(#ByteArray# -> IntegerintegerFromBigNatNeg#ByteArray#q,ByteArray# -> IntegerintegerFromBigNat#ByteArray#r#)integerQuotRem#(INByteArray#n)(INByteArray#d)=caseByteArray# -> ByteArray# -> (# ByteArray#, ByteArray# #)bigNatQuotRem#ByteArray#nByteArray#dof(#ByteArray#q,ByteArray#r#)->(#ByteArray# -> IntegerintegerFromBigNat#ByteArray#q,ByteArray# -> IntegerintegerFromBigNatNeg#ByteArray#r#)integerQuotRem#(INByteArray#n)(IPByteArray#d)=caseByteArray# -> ByteArray# -> (# ByteArray#, ByteArray# #)bigNatQuotRem#ByteArray#nByteArray#dof(#ByteArray#q,ByteArray#r#)->(#ByteArray# -> IntegerintegerFromBigNatNeg#ByteArray#q,ByteArray# -> IntegerintegerFromBigNatNeg#ByteArray#r#)integerQuotRem#(IPByteArray#n)(ISBool#d#)|Bool# -> BoolisTrue#(Bool#d#Bool# -> Bool# -> Bool#>=#Bool#0#)=caseByteArray# -> Word# -> (# ByteArray#, Word# #)bigNatQuotRemWord#ByteArray#n(Bool# -> Word#int2Word#Bool#d#)of(#ByteArray#q,Word#r##)->(#ByteArray# -> IntegerintegerFromBigNat#ByteArray#q,Word# -> IntegerintegerFromWord#Word#r##)|BoolTrue=caseByteArray# -> Word# -> (# ByteArray#, Word# #)bigNatQuotRemWord#ByteArray#n(Bool# -> Word#int2Word#(Bool# -> Bool#negateInt#Bool#d#))of(#ByteArray#q,Word#r##)->(#ByteArray# -> IntegerintegerFromBigNatNeg#ByteArray#q,Word# -> IntegerintegerFromWord#Word#r##)integerQuotRem#(INByteArray#n)(ISBool#d#)|Bool# -> BoolisTrue#(Bool#d#Bool# -> Bool# -> Bool#>=#Bool#0#)=caseByteArray# -> Word# -> (# ByteArray#, Word# #)bigNatQuotRemWord#ByteArray#n(Bool# -> Word#int2Word#Bool#d#)of(#ByteArray#q,Word#r##)->(#ByteArray# -> IntegerintegerFromBigNatNeg#ByteArray#q,Word# -> IntegerintegerFromWordNeg#Word#r##)|BoolTrue=caseByteArray# -> Word# -> (# ByteArray#, Word# #)bigNatQuotRemWord#ByteArray#n(Bool# -> Word#int2Word#(Bool# -> Bool#negateInt#Bool#d#))of(#ByteArray#q,Word#r##)->(#ByteArray# -> IntegerintegerFromBigNat#ByteArray#q,Word# -> IntegerintegerFromWordNeg#Word#r##)integerQuotRem#n :: Integern@(ISBool#_)(INByteArray#_)=(#Bool# -> IntegerISBool#0#,Integern#)-- since @n < d@integerQuotRem#n :: Integern@(ISBool#n#)(IPByteArray#d)-- need to account for (IS minBound)|Bool# -> BoolisTrue#(Bool#n#Bool# -> Bool# -> Bool#>#Bool#0#)=(#Bool# -> IntegerISBool#0#,Integern#)|Bool# -> BoolisTrue#(ByteArray# -> Word# -> Bool#bigNatGtWord#ByteArray#d(Bool# -> Word#int2Word#(Bool# -> Bool#negateInt#Bool#n#)))=(#Bool# -> IntegerISBool#0#,Integern#)|BoolTrue{- abs(n) == d -}=(#Bool# -> IntegerISBool#-1#,Bool# -> IntegerISBool#0##)-- | Simultaneous 'integerQuot' and 'integerRem'.---- Divisor must be non-zero otherwise the GHC runtime will terminate-- with a division-by-zero fault.integerQuotRem::Integer->Integer->(Integer,Integer)integerQuotRem :: Integer -> Integer -> (Integer, Integer)integerQuotRem!Integerx!Integery=caseInteger -> Integer -> (# Integer, Integer #)integerQuotRem#IntegerxIntegeryof-- Note [Bangs in Integer functions](#Integerq,Integerr#)->(Integerq,Integerr)integerQuot::Integer->Integer->Integer{-# NOINLINEintegerQuot#-}integerQuot :: Integer -> Integer -> IntegerintegerQuot!Integern(ISBool#1#)=Integern-- Note [Bangs in Integer functions]integerQuot!Integern(ISBool#-1#)=Integer -> IntegerintegerNegateIntegernintegerQuot!Integer_(ISBool#0#)=Integerforall a. araiseDivZerointegerQuot(ISBool#0#)Integer_=Bool# -> IntegerISBool#0#integerQuot(ISBool#n#)(ISBool#d#)=Bool# -> IntegerIS(Bool# -> Bool# -> Bool#quotInt#Bool#n#Bool#d#)integerQuot(IPByteArray#n)(ISBool#d#)|Bool# -> BoolisTrue#(Bool#d#Bool# -> Bool# -> Bool#>=#Bool#0#)=ByteArray# -> IntegerintegerFromBigNat#(ByteArray# -> Word# -> ByteArray#bigNatQuotWord#ByteArray#n(Bool# -> Word#int2Word#Bool#d#))|BoolTrue=ByteArray# -> IntegerintegerFromBigNatNeg#(ByteArray# -> Word# -> ByteArray#bigNatQuotWord#ByteArray#n(Bool# -> Word#int2Word#(Bool# -> Bool#negateInt#Bool#d#)))integerQuot(INByteArray#n)(ISBool#d#)|Bool# -> BoolisTrue#(Bool#d#Bool# -> Bool# -> Bool#>=#Bool#0#)=ByteArray# -> IntegerintegerFromBigNatNeg#(ByteArray# -> Word# -> ByteArray#bigNatQuotWord#ByteArray#n(Bool# -> Word#int2Word#Bool#d#))|BoolTrue=ByteArray# -> IntegerintegerFromBigNat#(ByteArray# -> Word# -> ByteArray#bigNatQuotWord#ByteArray#n(Bool# -> Word#int2Word#(Bool# -> Bool#negateInt#Bool#d#)))integerQuot(IPByteArray#n)(IPByteArray#d)=ByteArray# -> IntegerintegerFromBigNat#(ByteArray# -> ByteArray# -> ByteArray#bigNatQuotByteArray#nByteArray#d)integerQuot(IPByteArray#n)(INByteArray#d)=ByteArray# -> IntegerintegerFromBigNatNeg#(ByteArray# -> ByteArray# -> ByteArray#bigNatQuotByteArray#nByteArray#d)integerQuot(INByteArray#n)(IPByteArray#d)=ByteArray# -> IntegerintegerFromBigNatNeg#(ByteArray# -> ByteArray# -> ByteArray#bigNatQuotByteArray#nByteArray#d)integerQuot(INByteArray#n)(INByteArray#d)=ByteArray# -> IntegerintegerFromBigNat#(ByteArray# -> ByteArray# -> ByteArray#bigNatQuotByteArray#nByteArray#d)integerQuotIntegernIntegerd=caseInteger -> Integer -> (# Integer, Integer #)integerQuotRem#IntegernIntegerdof(#Integerq,Integer_#)->IntegerqintegerRem::Integer->Integer->Integer{-# NOINLINEintegerRem#-}integerRem :: Integer -> Integer -> IntegerintegerRem!Integer_(ISBool#1#)=Bool# -> IntegerISBool#0#-- Note [Bangs in Integer functions]integerRemInteger_(ISBool#-1#)=Bool# -> IntegerISBool#0#integerRemInteger_(ISBool#0#)=Bool# -> IntegerIS(Bool# -> Bool# -> Bool#remInt#Bool#0#Bool#0#)integerRem(ISBool#0#)Integer_=Bool# -> IntegerISBool#0#integerRem(ISBool#n#)(ISBool#d#)=Bool# -> IntegerIS(Bool# -> Bool# -> Bool#remInt#Bool#n#Bool#d#)integerRem(IPByteArray#n)(ISBool#d#)=Word# -> IntegerintegerFromWord#(ByteArray# -> Word# -> Word#bigNatRemWord#ByteArray#n(Bool# -> Word#int2Word#(Bool# -> Bool#absI#Bool#d#)))integerRem(INByteArray#n)(ISBool#d#)=Word# -> IntegerintegerFromWordNeg#(ByteArray# -> Word# -> Word#bigNatRemWord#ByteArray#n(Bool# -> Word#int2Word#(Bool# -> Bool#absI#Bool#d#)))integerRem(IPByteArray#n)(IPByteArray#d)=ByteArray# -> IntegerintegerFromBigNat#(ByteArray# -> ByteArray# -> ByteArray#bigNatRemByteArray#nByteArray#d)integerRem(IPByteArray#n)(INByteArray#d)=ByteArray# -> IntegerintegerFromBigNat#(ByteArray# -> ByteArray# -> ByteArray#bigNatRemByteArray#nByteArray#d)integerRem(INByteArray#n)(IPByteArray#d)=ByteArray# -> IntegerintegerFromBigNatNeg#(ByteArray# -> ByteArray# -> ByteArray#bigNatRemByteArray#nByteArray#d)integerRem(INByteArray#n)(INByteArray#d)=ByteArray# -> IntegerintegerFromBigNatNeg#(ByteArray# -> ByteArray# -> ByteArray#bigNatRemByteArray#nByteArray#d)integerRemIntegernIntegerd=caseInteger -> Integer -> (# Integer, Integer #)integerQuotRem#IntegernIntegerdof(#Integer_,Integerr#)->Integerr-- | Simultaneous 'integerDiv' and 'integerMod'.---- Divisor must be non-zero otherwise the GHC runtime will terminate-- with a division-by-zero fault.integerDivMod#::Integer->Integer->(#Integer,Integer#){-# NOINLINEintegerDivMod##-}integerDivMod# :: Integer -> Integer -> (# Integer, Integer #)integerDivMod#!Integern!Integerd-- Note [Bangs in Integer functions]|Bool# -> BoolisTrue#(Integer -> Bool#integerSignum#IntegerrBool# -> Bool# -> Bool#==#Bool# -> Bool#negateInt#(Integer -> Bool#integerSignum#Integerd))=let!q' :: Integerq'=Integer -> Integer -> IntegerintegerSubIntegerq(Bool# -> IntegerISBool#1#)!r' :: Integerr'=Integer -> Integer -> IntegerintegerAddIntegerrIntegerdin(#Integerq',Integerr'#)|BoolTrue=(# Integer, Integer #)qrwhere!qr :: (# Integer, Integer #)qr@(#Integerq,Integerr#)=Integer -> Integer -> (# Integer, Integer #)integerQuotRem#IntegernIntegerd-- | Simultaneous 'integerDiv' and 'integerMod'.---- Divisor must be non-zero otherwise the GHC runtime will terminate-- with a division-by-zero fault.integerDivMod::Integer->Integer->(Integer,Integer)integerDivMod :: Integer -> Integer -> (Integer, Integer)integerDivMod!Integern!Integerd=caseInteger -> Integer -> (# Integer, Integer #)integerDivMod#IntegernIntegerdof-- Note [Bangs in Integer functions](#Integerq,Integerr#)->(Integerq,Integerr)integerDiv::Integer->Integer->Integer{-# NOINLINEintegerDiv#-}integerDiv :: Integer -> Integer -> IntegerintegerDiv!Integern!Integerd-- Note [Bangs in Integer functions]-- same-sign ops can be handled by more efficient 'integerQuot'|Bool# -> BoolisTrue#(Integer -> Bool#integerIsNegative#IntegernBool# -> Bool# -> Bool#==#Integer -> Bool#integerIsNegative#Integerd)=Integer -> Integer -> IntegerintegerQuotIntegernIntegerd|BoolTrue=caseInteger -> Integer -> (# Integer, Integer #)integerDivMod#IntegernIntegerdof(#Integerq,Integer_#)->IntegerqintegerMod::Integer->Integer->Integer{-# NOINLINEintegerMod#-}integerMod :: Integer -> Integer -> IntegerintegerMod!Integern!Integerd-- Note [Bangs in Integer functions]-- same-sign ops can be handled by more efficient 'integerRem'|Bool# -> BoolisTrue#(Integer -> Bool#integerIsNegative#IntegernBool# -> Bool# -> Bool#==#Integer -> Bool#integerIsNegative#Integerd)=Integer -> Integer -> IntegerintegerRemIntegernIntegerd|BoolTrue=caseInteger -> Integer -> (# Integer, Integer #)integerDivMod#IntegernIntegerdof(#Integer_,Integerr#)->Integerr-- | Compute greatest common divisor.integerGcd::Integer->Integer->Integer{-# NOINLINEintegerGcd#-}integerGcd :: Integer -> Integer -> IntegerintegerGcd(ISBool#0#)!Integerb=Integer -> IntegerintegerAbsIntegerbintegerGcdIntegera(ISBool#0#)=Integer -> IntegerintegerAbsIntegeraintegerGcd(ISBool#1#)Integer_=Bool# -> IntegerISBool#1#integerGcd(ISBool#-1#)Integer_=Bool# -> IntegerISBool#1#integerGcdInteger_(ISBool#1#)=Bool# -> IntegerISBool#1#integerGcdInteger_(ISBool#-1#)=Bool# -> IntegerISBool#1#integerGcd(ISBool#a)(ISBool#b)=Word# -> IntegerintegerFromWord#(Word# -> Word# -> Word#gcdWord#(Bool# -> Word#int2Word#(Bool# -> Bool#absI#Bool#a))(Bool# -> Word#int2Word#(Bool# -> Bool#absI#Bool#b)))integerGcda :: Integera@(ISBool#_)Integerb=Integer -> Integer -> IntegerintegerGcdIntegerbIntegeraintegerGcd(INByteArray#a)Integerb=Integer -> Integer -> IntegerintegerGcd(ByteArray# -> IntegerIPByteArray#a)IntegerbintegerGcd(IPByteArray#a)(IPByteArray#b)=ByteArray# -> IntegerintegerFromBigNat#(ByteArray# -> ByteArray# -> ByteArray#bigNatGcdByteArray#aByteArray#b)integerGcd(IPByteArray#a)(INByteArray#b)=ByteArray# -> IntegerintegerFromBigNat#(ByteArray# -> ByteArray# -> ByteArray#bigNatGcdByteArray#aByteArray#b)integerGcd(IPByteArray#a)(ISBool#b)=Word# -> IntegerintegerFromWord#(ByteArray# -> Word# -> Word#bigNatGcdWord#ByteArray#a(Bool# -> Word#int2Word#(Bool# -> Bool#absI#Bool#b)))-- | Compute least common multiple.integerLcm::Integer->Integer->Integer{-# NOINLINEintegerLcm#-}integerLcm :: Integer -> Integer -> IntegerintegerLcm(ISBool#0#)!Integer_=Bool# -> IntegerISBool#0#integerLcm(ISBool#1#)Integerb=Integer -> IntegerintegerAbsIntegerbintegerLcm(ISBool#-1#)Integerb=Integer -> IntegerintegerAbsIntegerbintegerLcmInteger_(ISBool#0#)=Bool# -> IntegerISBool#0#integerLcmIntegera(ISBool#1#)=Integer -> IntegerintegerAbsIntegeraintegerLcmIntegera(ISBool#-1#)=Integer -> IntegerintegerAbsIntegeraintegerLcmIntegeraIntegerb=(IntegeraaInteger -> Integer -> Integer`integerQuot`(IntegeraaInteger -> Integer -> Integer`integerGcd`Integerab))Integer -> Integer -> Integer`integerMul`Integerabwhere-- TODO: use extended GCD to get a's factor directlyaa :: Integeraa=Integer -> IntegerintegerAbsIntegeraab :: Integerab=Integer -> IntegerintegerAbsIntegerb-- | Square a IntegerintegerSqr::Integer->IntegerintegerSqr :: Integer -> IntegerintegerSqr!Integera=Integer -> Integer -> IntegerintegerMulIntegeraIntegera-- | Base 2 logarithm (floor)---- For numbers <= 0, return 0integerLog2#::Integer->Word#integerLog2# :: Integer -> Word#integerLog2#(ISBool#i)|Bool# -> BoolisTrue#(Bool#iBool# -> Bool# -> Bool#<=#Bool#0#)=Word#0##|BoolTrue=Word# -> Word#wordLog2#(Bool# -> Word#int2Word#Bool#i)integerLog2#(INByteArray#_)=Word#0##integerLog2#(IPByteArray#b)=ByteArray# -> Word#bigNatLog2#ByteArray#b-- | Base 2 logarithm (floor)---- For numbers <= 0, return 0integerLog2::Integer->WordintegerLog2 :: Integer -> WordintegerLog2!Integeri=Word# -> WordW#(Integer -> Word#integerLog2#Integeri)-- | Logarithm (floor) for an arbitrary base---- For numbers <= 0, return 0integerLogBaseWord#::Word#->Integer->Word#integerLogBaseWord# :: Word# -> Integer -> Word#integerLogBaseWord#Word#base!Integeri|Integer -> BoolintegerIsNegativeIntegeri=Word#0##|BoolTrue=Word# -> Natural -> Word#naturalLogBaseWord#Word#base(Integer -> NaturalintegerToNaturalIntegeri)-- | Logarithm (floor) for an arbitrary base---- For numbers <= 0, return 0integerLogBaseWord::Word->Integer->WordintegerLogBaseWord :: Word -> Integer -> WordintegerLogBaseWord(W#Word#base)!Integeri=Word# -> WordW#(Word# -> Integer -> Word#integerLogBaseWord#Word#baseIntegeri)-- | Logarithm (floor) for an arbitrary base---- For numbers <= 0, return 0integerLogBase#::Integer->Integer->Word#integerLogBase# :: Integer -> Integer -> Word#integerLogBase#!Integerbase!Integeri|Integer -> BoolintegerIsNegativeIntegeri=Word#0##|BoolTrue=Natural -> Natural -> Word#naturalLogBase#(Integer -> NaturalintegerToNaturalIntegerbase)(Integer -> NaturalintegerToNaturalIntegeri)-- | Logarithm (floor) for an arbitrary base---- For numbers <= 0, return 0integerLogBase::Integer->Integer->WordintegerLogBase :: Integer -> Integer -> WordintegerLogBase!Integerbase!Integeri=Word# -> WordW#(Integer -> Integer -> Word#integerLogBase#IntegerbaseIntegeri)-- | Indicate if the value is a power of two and which oneintegerIsPowerOf2#::Integer->(#(##)|Word##)integerIsPowerOf2# :: Integer -> (# (# #) | Word# #)integerIsPowerOf2#(ISBool#i)|Bool# -> BoolisTrue#(Bool#iBool# -> Bool# -> Bool#<=#Bool#0#)=(#(##)|#)|BoolTrue=Word# -> (# (# #) | Word# #)wordIsPowerOf2#(Bool# -> Word#int2Word#Bool#i)integerIsPowerOf2#(INByteArray#_)=(#(##)|#)integerIsPowerOf2#(IPByteArray#w)=ByteArray# -> (# (# #) | Word# #)bigNatIsPowerOf2#ByteArray#w-- | Convert an Int64# into an IntegerintegerFromInt64#::Int64#->Integer{-# NOINLINEintegerFromInt64##-}integerFromInt64# :: Int64# -> IntegerintegerFromInt64#Int64#i|Bool# -> BoolisTrue#((Int64#iInt64# -> Int64# -> Bool#`leInt64#`Bool# -> Int64#intToInt64#INT_MAXBOUND#)Bool# -> Bool# -> Bool#&&#(Int64#iInt64# -> Int64# -> Bool#`geInt64#`Bool# -> Int64#intToInt64#INT_MINBOUND#))=Bool# -> IntegerIS(Int64# -> Bool#int64ToInt#Int64#i)|Bool# -> BoolisTrue#(Int64#iInt64# -> Int64# -> Bool#`geInt64#`Bool# -> Int64#intToInt64#Bool#0#)=ByteArray# -> IntegerIP(Word64# -> ByteArray#bigNatFromWord64#(Int64# -> Word64#int64ToWord64#Int64#i))|BoolTrue=ByteArray# -> IntegerIN(Word64# -> ByteArray#bigNatFromWord64#(Int64# -> Word64#int64ToWord64#(Int64# -> Int64#negateInt64#Int64#i)))-- | Convert a Word64# into an IntegerintegerFromWord64#::Word64#->Integer{-# NOINLINEintegerFromWord64##-}integerFromWord64# :: Word64# -> IntegerintegerFromWord64#!Word64#w|Bool# -> BoolisTrue#(Word64#wWord64# -> Word64# -> Bool#`leWord64#`Word# -> Word64#wordToWord64#INT_MAXBOUND##)=Bool# -> IntegerIS(Int64# -> Bool#int64ToInt#(Word64# -> Int64#word64ToInt64#Word64#w))|BoolTrue=ByteArray# -> IntegerIP(Word64# -> ByteArray#bigNatFromWord64#Word64#w)-- | Convert an Integer into an Int64#integerToInt64#::Integer->Int64#{-# NOINLINEintegerToInt64##-}integerToInt64# :: Integer -> Int64#integerToInt64#(ISBool#i)=Bool# -> Int64#intToInt64#Bool#iintegerToInt64#(IPByteArray#b)=Word64# -> Int64#word64ToInt64#(ByteArray# -> Word64#bigNatToWord64#ByteArray#b)integerToInt64#(INByteArray#b)=Int64# -> Int64#negateInt64#(Word64# -> Int64#word64ToInt64#(ByteArray# -> Word64#bigNatToWord64#ByteArray#b))-- | Convert an Integer into a Word64#integerToWord64#::Integer->Word64#{-# NOINLINEintegerToWord64##-}integerToWord64# :: Integer -> Word64#integerToWord64#(ISBool#i)=Int64# -> Word64#int64ToWord64#(Bool# -> Int64#intToInt64#Bool#i)integerToWord64#(IPByteArray#b)=ByteArray# -> Word64#bigNatToWord64#ByteArray#bintegerToWord64#(INByteArray#b)=Int64# -> Word64#int64ToWord64#(Int64# -> Int64#negateInt64#(Word64# -> Int64#word64ToInt64#(ByteArray# -> Word64#bigNatToWord64#ByteArray#b)))------------------------------------------------------------------------------ Conversions to/from floating point------------------------------------------------------------------------------ | Decode a Double# into (# Integer mantissa, Int# exponent #)integerDecodeDouble#::Double#->(#Integer,Int##){-# INLINEintegerDecodeDouble##-}-- decodeDouble_Int64# is constant-folded-- in GHC.Core.Opt.ConstantFoldintegerDecodeDouble# :: Double# -> (# Integer, Bool# #)integerDecodeDouble#!Double#x=caseDouble# -> (# Int64#, Bool# #)decodeDouble_Int64#Double#xof(#Int64#m,Bool#e#)->(#Int64# -> IntegerintegerFromInt64#Int64#m,Bool#e#)-- | Encode (# Integer mantissa, Int# exponent #) into a Double#integerEncodeDouble#::Integer->Int#->Double#{-# NOINLINEintegerEncodeDouble##-}integerEncodeDouble# :: Integer -> Bool# -> Double#integerEncodeDouble#(ISBool#i)Bool#0#=Bool# -> Double#int2Double#Bool#iintegerEncodeDouble#(ISBool#i)Bool#e=Bool# -> Bool# -> Double#intEncodeDouble#Bool#iBool#eintegerEncodeDouble#(IPByteArray#b)Bool#e=ByteArray# -> Bool# -> Double#bigNatEncodeDouble#ByteArray#bBool#eintegerEncodeDouble#(INByteArray#b)Bool#e=Double# -> Double#negateDouble#(ByteArray# -> Bool# -> Double#bigNatEncodeDouble#ByteArray#bBool#e)-- | Encode (Integer mantissa, Int exponent) into a DoubleintegerEncodeDouble::Integer->Int->DoubleintegerEncodeDouble :: Integer -> Int -> DoubleintegerEncodeDouble!Integerm(I#Bool#e)=Double# -> DoubleD#(Integer -> Bool# -> Double#integerEncodeDouble#IntegermBool#e)-- | Encode (# Integer mantissa, Int# exponent #) into a Float#---- TODO: Not sure if it's worth to write 'Float' optimized versions hereintegerEncodeFloat#::Integer->Int#->Float#{-# NOINLINEintegerEncodeFloat##-}integerEncodeFloat# :: Integer -> Bool# -> Float#integerEncodeFloat#!IntegermBool#e=Double# -> Float#double2Float#(Integer -> Bool# -> Double#integerEncodeDouble#IntegermBool#e)-- | Compute the number of digits of the Integer (without the sign) in the given base.---- `base` must be > 1integerSizeInBase#::Word#->Integer->Word#integerSizeInBase# :: Word# -> Integer -> Word#integerSizeInBase#Word#base(ISBool#i)=Word# -> Word# -> Word#wordSizeInBase#Word#base(Bool# -> Word#int2Word#(Bool# -> Bool#absI#Bool#i))integerSizeInBase#Word#base(IPByteArray#n)=Word# -> ByteArray# -> Word#bigNatSizeInBase#Word#baseByteArray#nintegerSizeInBase#Word#base(INByteArray#n)=Word# -> ByteArray# -> Word#bigNatSizeInBase#Word#baseByteArray#n-- | Write an 'Integer' (without sign) to @/addr/@ in base-256 representation-- and return the number of bytes written.---- The endianness is selected with the Bool# parameter: write most significant-- byte first (big-endian) if @1#@ or least significant byte first-- (little-endian) if @0#@.integerToAddr#::Integer->Addr#->Bool#->State#s->(#State#s,Word##)integerToAddr# :: forall s.Integer -> Addr# -> Bool# -> State# s -> (# State# s, Word# #)integerToAddr#(ISBool#i)=Word# -> Addr# -> Bool# -> State# s -> (# State# s, Word# #)forall s.Word# -> Addr# -> Bool# -> State# s -> (# State# s, Word# #)wordToAddr#(Bool# -> Word#int2Word#(Bool# -> Bool#absI#Bool#i))integerToAddr#(IPByteArray#n)=ByteArray# -> Addr# -> Bool# -> State# s -> (# State# s, Word# #)forall s.ByteArray# -> Addr# -> Bool# -> State# s -> (# State# s, Word# #)bigNatToAddr#ByteArray#nintegerToAddr#(INByteArray#n)=ByteArray# -> Addr# -> Bool# -> State# s -> (# State# s, Word# #)forall s.ByteArray# -> Addr# -> Bool# -> State# s -> (# State# s, Word# #)bigNatToAddr#ByteArray#n-- | Write an 'Integer' (without sign) to @/addr/@ in base-256 representation-- and return the number of bytes written.---- The endianness is selected with the Bool# parameter: write most significant-- byte first (big-endian) if @1#@ or least significant byte first-- (little-endian) if @0#@.integerToAddr::Integer->Addr#->Bool#->IOWordintegerToAddr :: Integer -> Addr# -> Bool# -> IO WordintegerToAddrIntegeraAddr#addrBool#e=(State# RealWorld -> (# State# RealWorld, Word #)) -> IO Wordforall a. (State# RealWorld -> (# State# RealWorld, a #)) -> IO aIO\State# RealWorlds->caseInteger-> Addr#-> Bool#-> State# RealWorld-> (# State# RealWorld, Word# #)forall s.Integer -> Addr# -> Bool# -> State# s -> (# State# s, Word# #)integerToAddr#IntegeraAddr#addrBool#eState# RealWorldsof(#State# RealWorlds',Word#w#)->(#State# RealWorlds',Word# -> WordW#Word#w#)-- | Read an 'Integer' (without sign) in base-256 representation from an Addr#.---- The size is given in bytes.---- The endianness is selected with the Bool# parameter: most significant-- byte first (big-endian) if @1#@ or least significant byte first-- (little-endian) if @0#@.---- Null higher limbs are automatically trimed.integerFromAddr#::Word#->Addr#->Bool#->State#s->(#State#s,Integer#)integerFromAddr# :: forall s.Word# -> Addr# -> Bool# -> State# s -> (# State# s, Integer #)integerFromAddr#Word#szAddr#addrBool#eState# ss=caseWord# -> Addr# -> Bool# -> State# s -> (# State# s, ByteArray# #)forall s.Word# -> Addr# -> Bool# -> State# s -> (# State# s, ByteArray# #)bigNatFromAddr#Word#szAddr#addrBool#eState# ssof(#State# ss',ByteArray#n#)->(#State# ss',ByteArray# -> IntegerintegerFromBigNat#ByteArray#n#)-- | Read an 'Integer' (without sign) in base-256 representation from an Addr#.---- The size is given in bytes.---- The endianness is selected with the Bool# parameter: most significant-- byte first (big-endian) if @1#@ or least significant byte first-- (little-endian) if @0#@.---- Null higher limbs are automatically trimed.integerFromAddr::Word#->Addr#->Bool#->IOIntegerintegerFromAddr :: Word# -> Addr# -> Bool# -> IO IntegerintegerFromAddrWord#szAddr#addrBool#e=(State# RealWorld -> (# State# RealWorld, Integer #)) -> IO Integerforall a. (State# RealWorld -> (# State# RealWorld, a #)) -> IO aIO(Word#-> Addr#-> Bool#-> State# RealWorld-> (# State# RealWorld, Integer #)forall s.Word# -> Addr# -> Bool# -> State# s -> (# State# s, Integer #)integerFromAddr#Word#szAddr#addrBool#e)-- | Write an 'Integer' (without sign) in base-256 representation and return the-- number of bytes written.---- The endianness is selected with the Bool# parameter: most significant-- byte first (big-endian) if @1#@ or least significant byte first-- (little-endian) if @0#@.integerToMutableByteArray#::Integer->MutableByteArray#s->Word#->Bool#->State#s->(#State#s,Word##)integerToMutableByteArray# :: forall s.Integer-> MutableByteArray# s-> Word#-> Bool#-> State# s-> (# State# s, Word# #)integerToMutableByteArray#(ISBool#i)=Word#-> MutableByteArray# s-> Word#-> Bool#-> State# s-> (# State# s, Word# #)forall s.Word#-> MutableByteArray# s-> Word#-> Bool#-> State# s-> (# State# s, Word# #)wordToMutableByteArray#(Bool# -> Word#int2Word#(Bool# -> Bool#absI#Bool#i))integerToMutableByteArray#(IPByteArray#a)=ByteArray#-> MutableByteArray# s-> Word#-> Bool#-> State# s-> (# State# s, Word# #)forall s.ByteArray#-> MutableByteArray# s-> Word#-> Bool#-> State# s-> (# State# s, Word# #)bigNatToMutableByteArray#ByteArray#aintegerToMutableByteArray#(INByteArray#a)=ByteArray#-> MutableByteArray# s-> Word#-> Bool#-> State# s-> (# State# s, Word# #)forall s.ByteArray#-> MutableByteArray# s-> Word#-> Bool#-> State# s-> (# State# s, Word# #)bigNatToMutableByteArray#ByteArray#a-- | Write an 'Integer' (without sign) in base-256 representation and return the-- number of bytes written.---- The endianness is selected with the Bool# parameter: most significant-- byte first (big-endian) if @1#@ or least significant byte first-- (little-endian) if @0#@.integerToMutableByteArray::Integer->MutableByteArray#RealWorld->Word#->Bool#->IOWordintegerToMutableByteArray :: Integer -> MutableByteArray# RealWorld -> Word# -> Bool# -> IO WordintegerToMutableByteArrayIntegeriMutableByteArray# RealWorldmbaWord#wBool#e=(State# RealWorld -> (# State# RealWorld, Word #)) -> IO Wordforall a. (State# RealWorld -> (# State# RealWorld, a #)) -> IO aIO\State# RealWorlds->caseInteger-> MutableByteArray# RealWorld-> Word#-> Bool#-> State# RealWorld-> (# State# RealWorld, Word# #)forall s.Integer-> MutableByteArray# s-> Word#-> Bool#-> State# s-> (# State# s, Word# #)integerToMutableByteArray#IntegeriMutableByteArray# RealWorldmbaWord#wBool#eState# RealWorldsof(#State# RealWorlds',Word#r#)->(#State# RealWorlds',Word# -> WordW#Word#r#)-- | Read an 'Integer' (without sign) in base-256 representation from a ByteArray#.---- The size is given in bytes.---- The endianness is selected with the Bool# parameter: most significant-- byte first (big-endian) if @1#@ or least significant byte first-- (little-endian) if @0#@.---- Null higher limbs are automatically trimed.integerFromByteArray#::Word#->ByteArray#->Word#->Bool#->State#s->(#State#s,Integer#)integerFromByteArray# :: forall s.Word#-> ByteArray#-> Word#-> Bool#-> State# s-> (# State# s, Integer #)integerFromByteArray#Word#szByteArray#baWord#offBool#eState# ss=caseWord#-> ByteArray#-> Word#-> Bool#-> State# s-> (# State# s, ByteArray# #)forall s.Word#-> ByteArray#-> Word#-> Bool#-> State# s-> (# State# s, ByteArray# #)bigNatFromByteArray#Word#szByteArray#baWord#offBool#eState# ssof(#State# ss',ByteArray#a#)->(#State# ss',ByteArray# -> IntegerintegerFromBigNat#ByteArray#a#)-- | Read an 'Integer' (without sign) in base-256 representation from a ByteArray#.---- The size is given in bytes.---- The endianness is selected with the Bool# parameter: most significant-- byte first (big-endian) if @1#@ or least significant byte first-- (little-endian) if @0#@.---- Null higher limbs are automatically trimed.integerFromByteArray::Word#->ByteArray#->Word#->Bool#->IntegerintegerFromByteArray :: Word# -> ByteArray# -> Word# -> Bool# -> IntegerintegerFromByteArrayWord#szByteArray#baWord#offBool#e=case(State# RealWorld -> (# State# RealWorld, Integer #))-> (# State# RealWorld, Integer #)forall o. (State# RealWorld -> o) -> orunRW#(Word#-> ByteArray#-> Word#-> Bool#-> State# RealWorld-> (# State# RealWorld, Integer #)forall s.Word#-> ByteArray#-> Word#-> Bool#-> State# s-> (# State# s, Integer #)integerFromByteArray#Word#szByteArray#baWord#offBool#e)of(#State# RealWorld_,Integeri#)->Integeri-- | Get the extended GCD of two integers.---- `integerGcde# a b` returns (# g,x,y #) where--    * ax + by = g = |gcd a b|integerGcde#::Integer->Integer->(#Integer,Integer,Integer#)integerGcde# :: Integer -> Integer -> (# Integer, Integer, Integer #)integerGcde#IntegeraIntegerb|Integer -> BoolintegerIsZeroIntegeraBool -> Bool -> Bool&&Integer -> BoolintegerIsZeroIntegerb=(#IntegerintegerZero,IntegerintegerZero,IntegerintegerZero#)|Integer -> BoolintegerIsZeroIntegera=(# Integer, Integer, Integer #) -> (# Integer, Integer, Integer #)fix(#Integerb,IntegerintegerZero,IntegerintegerOne#)|Integer -> BoolintegerIsZeroIntegerb=(# Integer, Integer, Integer #) -> (# Integer, Integer, Integer #)fix(#Integera,IntegerintegerOne,IntegerintegerZero#)|Integer -> IntegerintegerAbsIntegeraInteger -> Integer -> Bool`integerEq`Integer -> IntegerintegerAbsIntegerb=(# Integer, Integer, Integer #) -> (# Integer, Integer, Integer #)fix(#Integerb,IntegerintegerZero,IntegerintegerOne#)|BoolTrue=Integer -> Integer -> (# Integer, Integer, Integer #)Backend.integer_gcdeIntegeraIntegerbwhere-- returned "g" must be positivefix :: (# Integer, Integer, Integer #) -> (# Integer, Integer, Integer #)fix(#Integerg,Integerx,Integery#)|Integer -> BoolintegerIsNegativeIntegerg=(#Integer -> IntegerintegerNegateIntegerg,Integer -> IntegerintegerNegateIntegerx,Integer -> IntegerintegerNegateIntegery#)|BoolTrue=(#Integerg,Integerx,Integery#)-- | Get the extended GCD of two integers.---- `integerGcde a b` returns (g,x,y) where--    * ax + by = g = |gcd a b|integerGcde::Integer->Integer->(Integer,Integer,Integer)integerGcde :: Integer -> Integer -> (Integer, Integer, Integer)integerGcdeIntegeraIntegerb=caseInteger -> Integer -> (# Integer, Integer, Integer #)integerGcde#IntegeraIntegerbof(#Integerg,Integerx,Integery#)->(Integerg,Integerx,Integery)-- | Computes the modular inverse.---- I.e. y = integerRecipMod# x m--        = x^(-1) `mod` m---- with 0 < y < |m|--integerRecipMod#::Integer->Natural->(#Natural|()#)integerRecipMod# :: Integer -> Natural -> (# Natural | () #)integerRecipMod#IntegerxNaturalm|Integer -> BoolintegerIsZeroIntegerx=(#|()#)|Natural -> BoolnaturalIsZeroNaturalm=(#|()#)|Natural -> BoolnaturalIsOneNaturalm=(#|()#)|BoolTrue=Integer -> Natural -> (# Natural | () #)Backend.integer_recip_modIntegerxNaturalm-- | Computes the modular exponentiation.---- I.e. y = integer_powmod b e m--        = b^e `mod` m---- with 0 <= y < abs m---- If e is negative, we use `integerRecipMod#` to try to find a modular-- multiplicative inverse (which may not exist).integerPowMod#::Integer->Integer->Natural->(#Natural|()#)integerPowMod# :: Integer -> Integer -> Natural -> (# Natural | () #)integerPowMod#!Integerb!Integere!Naturalm|Natural -> BoolnaturalIsZeroNaturalm=(#|()#)|Natural -> BoolnaturalIsOneNaturalm=(#NaturalnaturalZero|#)|Integer -> BoolintegerIsZeroIntegere=(#NaturalnaturalOne|#)|Integer -> BoolintegerIsZeroIntegerb=(#NaturalnaturalZero|#)|Integer -> BoolintegerIsOneIntegerb=(#NaturalnaturalOne|#)-- when the exponent is negative, try to find the modular multiplicative-- inverse and use it instead|Integer -> BoolintegerIsNegativeIntegere=caseInteger -> Natural -> (# Natural | () #)integerRecipMod#IntegerbNaturalmof(#|()#)->(#|()#)(#Naturalb'|#)->Integer -> Integer -> Natural -> (# Natural | () #)integerPowMod#(Natural -> IntegerintegerFromNaturalNaturalb')(Integer -> IntegerintegerNegateIntegere)Naturalm-- e > 0 by cases above|BoolTrue=(#Integer -> Natural -> Natural -> NaturalBackend.integer_powmodIntegerb(Integer -> NaturalintegerToNaturalIntegere)Naturalm|#){-Note [Optimising conversions between numeric types]~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Converting between numeric types is very common in Haskell codes.  Suppose thatwe have N inter-convertible numeric types (Word, Word8, Word32, Int, etc.).- We don't want to have to use one conversion function per pair of types as thatwould require N^2 functions: wordToWord8, wordToInt, word8ToWord32...- The following kind of class would allow us to have a single conversionfunction but at the price of N^2 instances and of the use ofMultiParamTypeClasses extension.    class Convert a b where      convert :: a -> bSo what we do instead is that we use the Integer type (signed, unbounded) as apassthrough type to perform every conversion. Hence we only need to define twofunctions per numeric type:  class Integral a where    toInteger :: a -> Integer  class Num a where    fromInteger :: Integer -> aThese classes have a single parameter and can be derived automatically (e.g. fornewtypes). So we don't even have to define 2*N instances. For example, all theinstances for the types in Foreign.C.Types (CChar, CShort, CInt, CUInt, etc.)are automatically derived from the instances for Word, Int, Word8, Word16, etc.Finally we can define a generic conversion function:  -- in the Prelude  fromIntegral :: (Integral a, Num b) => a -> b  fromIntegral = fromInteger . toIntegerEfficient conversions~~~~~~~~~~~~~~~~~~~~~An issue with this approach is that performance might be terrible. E.g.converting an Int into a Word, which is a no-op at the machine level, becomescostly when performed via `fromIntegral` or any similar function because anintermediate Integer has to be allocated in the heap to perform the conversion.A solution is to bless one particular `fromIntegral`-like function and to userewrite rules to replace it with a more efficient function when both types areknown. This is what was done in the past, see next section. We use anotherapproach nowadays:Notice that the set of primitive operations to convert from and to Integer andNatural is pretty small:  - Natural <-> Word#/BigNat#  - Integer <-> Int#/Word#/Natural/BigNat# (+ Int64#/Word64# on 32-bit arch)For example, we have the following primitives:  - integerToWord#   :: Integer -> Word#  - integerFromWord# :: Word# -> Integer  - integerToInt#    :: Integer -> Int#  - ...Compared to optimising `fromIntegral :: (Integral a, Num b) => a -> b` where `a`and `b` are arbitrary, we only have to write rewrite rules for the concretetypes that can be converted from and to Natural/Integer. All the other onesnecessarily pass through these concrete types!For example we have the following rules:    integerToWord# (integerFromWord# x) ===> x    integerToInt# (integerFromWord# x)  ===> word2Int# xBut we don't need rules to handle conversion from/to e.g. Word32# because thereis no Word32#-to-Integer primitive: Word32# must be converted into somethingelse first (e.g. Word#) for which we have rules.We rely on inlining of fromInteger/toInteger and on other transformations (e.g.float-in) to make these rules likely to fire. It seems to work well in practice.Example 1: converting an Int into a Word  fromIntegral @Int @Word x  ===> {inline fromIntegral}  fromInteger @Word (toInteger @Int x)  ===> {inline fromInteger and toInteger}  W# (integerToWord# (case x of { I# x# -> IS x# }))  ===> {float-in}  case x of { I# x# -> W# (integerToWord# (IS x#)) }  ===> {rewrite rule for "integerToWord# . IS"}  case x of { I# x# -> W# (int2Word# x#) }Example 2: converting an Int8 into a Word32  fromIntegral @Int8 @Word32 x  ===> {inline fromIntegral}  fromInteger @Word32 (toInteger @Int8 x)  ===> {inline fromInteger and toInteger}  W32# (wordToWord32# (integerToWord# (case x of { I8# x# -> IS (int8ToInt# x#) })))  ===> {float-in}  case x of { I8# x# -> W32# (wordToWord32# (integerToWord# (IS (int8ToInt# x#)))) }  ===> {rewrite rule for "integerToWord# . IS"}  case x of { I8# x# -> W32# (wordToWord32# (int2Word# (int8ToInt# x#))) }  Notice that in the resulting expression the value passes through types Int#  and Word# with native machine word size: it is first sign-extended from Int8#  to Int#, then cast into Word#, and finally truncated into Word32#. These are  all very cheap operations that are performed in registers without allocating  anything in the heap.Historical fromIntegral optimisations~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~In the past, `fromIntegral` function in the Prelude was special because manyrewrite rules were mentioning it explicitly. For example to replace a call to`fromIntegral :: Int -> Word`, which allocates an intermediate Integer, with acall to `intToWord`, which is a no-op when compiled into machine code. Nowadays`fromIntegral` isn't a special function anymore and we just INLINE it (see above).- first `fromIntegral` was specialized (SPECIALIZE pragma). However it wouldneed N^2 pragmas to cover every case and it wouldn't cover user defined numerictypes which don't belong to base.- `-fwarn-identities` enables a warning to detect useless conversions viafromIntegral (since 0656c72a8f):  > fromIntegral (1 :: Int) :: Int  <interactive>:3:21: warning: [-Widentities]      Call of fromIntegral :: Int -> Int        can probably be omitted- many rules were added (e.g. in e0c787c10f) to perform float-in transformationsexplicitly (to allow more fromIntegral rules to fire) and to replace somefromIntegral calls with faster operations:    "fromIntegral/Int8->Int8" fromIntegral = id :: Int8 -> Int8    "fromIntegral/a->Int8"    fromIntegral = \x -> case fromIntegral x of I# x# -> I8# (intToInt8# x#)    "fromIntegral/Int8->a"    fromIntegral = \(I8# x#) -> fromIntegral (I# x#)It worked but there were still some issues with this approach:1. These rules only work for `fromIntegral`. If we wanted to define our own   similar function (e.g. using other type-classes), we would also have to redefine   all the rules to get similar performance.2. `fromIntegral` had to be marked `NOINLINE [1]`:    - NOINLINE to allow rules to match    - [1] to allow inlining in later phases to avoid incurring a function call      overhead for such a trivial operation   Users of the function had to be careful because a simple helper without an   INLINE pragma like:      toInt :: Integral a => a -> Int      toInt = fromIntegral   had the following unfolding:      toInt = integerToInt . toInteger   which doesn't mention `fromIntegral` anymore. Hence `fromIntegral` rules   wouldn't fire for codes using `toInt` while they would if they had used   `fromIntegral` directly!   For this reason, a bunch of rules for bignum primitives as we have now were   already present to handle these cases.3. These rewrite rules were tedious to write and error-prone (cf #19345).For these reasons, it is simpler to not consider fromIntegral special at all andto only rely on rewrite rules for bignum functions.-}-- See Note [Optimising conversions between numeric types]{-# RULES"Word# -> Natural -> Integer"forallx.integerFromNatural(NSx)=integerFromWord#x"BigNat# -> Natural -> Integer"forallx.integerFromNatural(NBx)=IPx"Int# -> Integer -> Int#"forallx.integerToInt#(ISx)=x"Word# -> Integer -> Word#"forallx.integerToWord#(integerFromWord#x)=x"Natural -> Integer -> Natural (wrap)"forallx.integerToNatural(integerFromNaturalx)=x"Natural -> Integer -> Natural (throw)"forallx.integerToNaturalThrow(integerFromNaturalx)=x"Natural -> Integer -> Natural (clamp)"forallx.integerToNaturalClamp(integerFromNaturalx)=x"Natural -> Integer -> Word#"forallx.integerToWord#(integerFromNaturalx)=naturalToWord#x"Int# -> Integer -> Word#"forallx.integerToWord#(ISx)=int2Word#x"Word# -> Integer -> Int#"forallx.integerToInt#(integerFromWord#x)=word2Int#x"Word# -> Integer -> Natural (wrap)"forallx.integerToNatural(integerFromWord#x)=NSx"Word# -> Integer -> Natural (throw)"forallx.integerToNaturalThrow(integerFromWord#x)=NSx"Word# -> Integer -> Natural (clamp)"forallx.integerToNaturalClamp(integerFromWord#x)=NSx#-}{-# RULES"Int64# -> Integer -> Int64#"forallx.integerToInt64#(integerFromInt64#x)=x"Word64# -> Integer -> Word64#"forallx.integerToWord64#(integerFromWord64#x)=x"Int64# -> Integer -> Word64#"forallx.integerToWord64#(integerFromInt64#x)=int64ToWord64#x"Word64# -> Integer -> Int64#"forallx.integerToInt64#(integerFromWord64#x)=word64ToInt64#x"Word# -> Integer -> Word64#"forallx.integerToWord64#(integerFromWord#x)=wordToWord64#x"Word64# -> Integer -> Word#"forallx.integerToWord#(integerFromWord64#x)=word64ToWord#x"Int# -> Integer -> Int64#"forallx.integerToInt64#(ISx)=intToInt64#x"Int64# -> Integer -> Int#"forallx.integerToInt#(integerFromInt64#x)=int64ToInt#x"Int# -> Integer -> Word64#"forallx.integerToWord64#(ISx)=int64ToWord64#(intToInt64#x)"Int64# -> Integer -> Word#"forallx.integerToWord#(integerFromInt64#x)=int2Word#(int64ToInt#x)"Word# -> Integer -> Int64#"forallx.integerToInt64#(integerFromWord#x)=word64ToInt64#(wordToWord64#x)"Word64# -> Integer -> Int#"forallx.integerToInt#(integerFromWord64#x)=word2Int#(word64ToWord#x)#-}