{-# LANGUAGE CPP #-}
{-# LANGUAGE NoImplicitPrelude #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE UnboxedTuples #-}
{-# LANGUAGE NegativeLiterals #-}
{-# LANGUAGE BinaryLiterals #-}
{-# LANGUAGE BlockArguments #-}
{-# LANGUAGE LambdaCase #-}

-- |
-- Module      :  GHC.Internal.Bignum.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.

module GHC.Internal.Bignum.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"

import GHC.Internal.Prim
import GHC.Internal.Types
import GHC.Internal.Classes
import GHC.Internal.Magic
import GHC.Internal.Bignum.Primitives
import GHC.Internal.Bignum.BigNat
import GHC.Internal.Bignum.Natural
import qualified GHC.Internal.Bignum.Backend as Backend

default ()

-- | 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'.
data Integer
   = 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 invariants
integerCheck# :: Integer -> Bool#
integerCheck# :: Integer -> Bool#
integerCheck# (IS  Bool#
_) = Bool#
1#
integerCheck# (IP ByteArray#
bn) = ByteArray# -> Bool#
bigNatCheck# ByteArray#
bn Bool# -> Bool# -> Bool#
&&# (ByteArray#
bn ByteArray# -> Word# -> Bool#
`bigNatGtWord#` INT_MAXBOUND##)
integerCheck# (IN ByteArray#
bn) = ByteArray# -> Bool#
bigNatCheck# ByteArray#
bn Bool# -> Bool# -> Bool#
&&# (ByteArray#
bn ByteArray# -> Word# -> Bool#
`bigNatGtWord#` ABS_INT_MINBOUND##)

-- | Check Integer invariants
integerCheck :: Integer -> Bool
integerCheck :: Integer -> Bool
integerCheck Integer
i = Bool# -> Bool
isTrue# (Integer -> Bool#
integerCheck# Integer
i)

-- | Integer Zero
integerZero :: Integer
integerZero :: Integer
integerZero = Bool# -> Integer
IS Bool#
0#

-- | Integer One
integerOne :: Integer
integerOne :: Integer
integerOne = Bool# -> Integer
IS Bool#
1#

---------------------------------------------------------------------
-- Conversions
---------------------------------------------------------------------

-- | Create a positive Integer from a BigNat
integerFromBigNat# :: BigNat# -> Integer
integerFromBigNat# :: ByteArray# -> Integer
integerFromBigNat# !ByteArray#
bn
   | ByteArray# -> Bool
bigNatIsZero ByteArray#
bn
   = Integer
integerZero

   | Bool# -> Bool
isTrue# (ByteArray#
bn ByteArray# -> Word# -> Bool#
`bigNatLeWord#` INT_MAXBOUND##)
   = Bool# -> Integer
IS (Word# -> Bool#
word2Int# (ByteArray# -> Bool# -> Word#
bigNatIndex# ByteArray#
bn Bool#
0#))

   | Bool
True
   = ByteArray# -> Integer
IP ByteArray#
bn

-- | Create a negative Integer from a BigNat
integerFromBigNatNeg# :: BigNat# -> Integer
integerFromBigNatNeg# :: ByteArray# -> Integer
integerFromBigNatNeg# !ByteArray#
bn
   | ByteArray# -> Bool
bigNatIsZero ByteArray#
bn
   = Integer
integerZero

   | Bool#
1# <- ByteArray# -> Bool#
bigNatSize# ByteArray#
bn
   , Bool#
i <- Bool# -> Bool#
negateInt# (Word# -> Bool#
word2Int# (ByteArray# -> Bool# -> Word#
bigNatIndex# ByteArray#
bn Bool#
0#))
   , Bool# -> Bool
isTrue# (Bool#
i Bool# -> Bool# -> Bool#
<=# Bool#
0#)
   = Bool# -> Integer
IS Bool#
i

   | Bool
True
   = ByteArray# -> Integer
IN ByteArray#
bn

-- | Create an Integer from a sign-bit and a BigNat
integerFromBigNatSign# :: Int# -> BigNat# -> Integer
integerFromBigNatSign# :: Bool# -> ByteArray# -> Integer
integerFromBigNatSign# !Bool#
sign !ByteArray#
bn
   | Bool#
0# <- Bool#
sign
   = ByteArray# -> Integer
integerFromBigNat# ByteArray#
bn

   | Bool
True
   = ByteArray# -> Integer
integerFromBigNatNeg# ByteArray#
bn

-- | Convert an Integer into a sign-bit and a BigNat
integerToBigNatSign# :: Integer -> (# Int#, BigNat# #)
integerToBigNatSign# :: Integer -> (# Bool#, ByteArray# #)
integerToBigNatSign# = \case
   IS Bool#
x
      | Bool# -> Bool
isTrue# (Bool#
x Bool# -> Bool# -> Bool#
>=# Bool#
0#)
      -> (# Bool#
0#, Word# -> ByteArray#
bigNatFromWord# (Bool# -> Word#
int2Word# Bool#
x) #)
      | Bool
True
      -> (# Bool#
1#, Word# -> ByteArray#
bigNatFromWord# (Bool# -> Word#
int2Word# (Bool# -> Bool#
negateInt# Bool#
x)) #)
   IP ByteArray#
x -> (# Bool#
0#, ByteArray#
x #)
   IN ByteArray#
x -> (# Bool#
1#, ByteArray#
x #)

-- | Convert an Integer into a BigNat.
--
-- Return 0 for negative Integers.
integerToBigNatClamp# :: Integer -> BigNat#
integerToBigNatClamp# :: Integer -> ByteArray#
integerToBigNatClamp# (IP ByteArray#
x) = ByteArray#
x
integerToBigNatClamp# (IS Bool#
x)
   | Bool# -> Bool
isTrue# (Bool#
x Bool# -> Bool# -> Bool#
>=# Bool#
0#)     = Word# -> ByteArray#
bigNatFromWord# (Bool# -> Word#
int2Word# Bool#
x)
integerToBigNatClamp# Integer
_     = (# #) -> ByteArray#
bigNatZero# (# #)

-- | Create an Integer from an Int#
integerFromInt# :: Int# -> Integer
integerFromInt# :: Bool# -> Integer
integerFromInt# Bool#
i = Bool# -> Integer
IS Bool#
i

-- | Create an Integer from an Int
integerFromInt :: Int -> Integer
integerFromInt :: Int -> Integer
integerFromInt (I# Bool#
i) = Bool# -> Integer
IS Bool#
i

-- | Truncates 'Integer' to least-significant 'Int#'
integerToInt# :: Integer -> Int#
{-# NOINLINE integerToInt# #-}
integerToInt# :: Integer -> Bool#
integerToInt# (IS Bool#
i) = Bool#
i
integerToInt# (IP ByteArray#
b) = Word# -> Bool#
word2Int# (ByteArray# -> Word#
bigNatToWord# ByteArray#
b)
integerToInt# (IN ByteArray#
b) = Bool# -> Bool#
negateInt# (Word# -> Bool#
word2Int# (ByteArray# -> Word#
bigNatToWord# ByteArray#
b))

-- | Truncates 'Integer' to least-significant 'Int#'
integerToInt :: Integer -> Int
integerToInt :: Integer -> Int
integerToInt Integer
i = Bool# -> Int
I# (Integer -> Bool#
integerToInt# Integer
i)

-- | Convert a Word# into an Integer
integerFromWord# :: Word# -> Integer
{-# NOINLINE integerFromWord# #-}
integerFromWord# :: Word# -> Integer
integerFromWord# Word#
w
   | Bool#
i <- Word# -> Bool#
word2Int# Word#
w
   , Bool# -> Bool
isTrue# (Bool#
i Bool# -> Bool# -> Bool#
>=# Bool#
0#)
   = Bool# -> Integer
IS Bool#
i

   | Bool
True
   = ByteArray# -> Integer
IP (Word# -> ByteArray#
bigNatFromWord# Word#
w)

-- | Convert a Word into an Integer
integerFromWord :: Word -> Integer
integerFromWord :: Word -> Integer
integerFromWord (W# Word#
w) = Word# -> Integer
integerFromWord# Word#
w

-- | Create a negative Integer with the given Word magnitude
integerFromWordNeg# :: Word# -> Integer
integerFromWordNeg# :: Word# -> Integer
integerFromWordNeg# Word#
w
  | Bool# -> Bool
isTrue# (Word#
w Word# -> Word# -> Bool#
`leWord#` ABS_INT_MINBOUND##)
  = Bool# -> Integer
IS (Bool# -> Bool#
negateInt# (Word# -> Bool#
word2Int# Word#
w))

  | Bool
True
  = ByteArray# -> Integer
IN (Word# -> ByteArray#
bigNatFromWord# Word#
w)

-- | Create an Integer from a sign and a Word magnitude
integerFromWordSign# :: Int# -> Word# -> Integer
integerFromWordSign# :: Bool# -> Word# -> Integer
integerFromWordSign# Bool#
0# Word#
w = Word# -> Integer
integerFromWord# Word#
w
integerFromWordSign# Bool#
_  Word#
w = Word# -> Integer
integerFromWordNeg# Word#
w

-- | Truncate an Integer into a Word
integerToWord# :: Integer -> Word#
{-# NOINLINE integerToWord# #-}
integerToWord# :: Integer -> Word#
integerToWord# (IS Bool#
i)  = Bool# -> Word#
int2Word# Bool#
i
integerToWord# (IP ByteArray#
bn) = ByteArray# -> Word#
bigNatToWord# ByteArray#
bn
integerToWord# (IN ByteArray#
bn) = Bool# -> Word#
int2Word# (Bool# -> Bool#
negateInt# (Word# -> Bool#
word2Int# (ByteArray# -> Word#
bigNatToWord# ByteArray#
bn)))

-- | Truncate an Integer into a Word
integerToWord :: Integer -> Word
integerToWord :: Integer -> Word
integerToWord !Integer
i = Word# -> Word
W# (Integer -> Word#
integerToWord# Integer
i)

-- | Convert a Natural into an Integer
integerFromNatural :: Natural -> Integer
{-# NOINLINE integerFromNatural #-}
integerFromNatural :: Natural -> Integer
integerFromNatural (NS Word#
x) = Word# -> Integer
integerFromWord# Word#
x
integerFromNatural (NB ByteArray#
x) = ByteArray# -> Integer
IP ByteArray#
x

-- | Convert a list of Word into an Integer
integerFromWordList :: Bool -> [Word] -> Integer
integerFromWordList :: Bool -> [Word] -> Integer
integerFromWordList Bool
True  [Word]
ws = ByteArray# -> Integer
integerFromBigNatNeg# ([Word] -> ByteArray#
bigNatFromWordList [Word]
ws)
integerFromWordList Bool
False [Word]
ws = ByteArray# -> Integer
integerFromBigNat#    ([Word] -> ByteArray#
bigNatFromWordList [Word]
ws)

-- | Convert an Integer into a Natural
--
-- Return 0 for negative Integers.
integerToNaturalClamp :: Integer -> Natural
{-# NOINLINE integerToNaturalClamp #-}
integerToNaturalClamp :: Integer -> Natural
integerToNaturalClamp (IS Bool#
x)
   | Bool# -> Bool
isTrue# (Bool#
x Bool# -> Bool# -> Bool#
<# Bool#
0#) = Natural
naturalZero
   | Bool
True              = Word# -> Natural
naturalFromWord# (Bool# -> Word#
int2Word# Bool#
x)
integerToNaturalClamp (IP ByteArray#
x) = ByteArray# -> Natural
naturalFromBigNat# ByteArray#
x
integerToNaturalClamp (IN ByteArray#
_) = Natural
naturalZero

-- | Convert an Integer into a Natural
--
-- Return absolute value
integerToNatural :: Integer -> Natural
{-# NOINLINE integerToNatural #-}
integerToNatural :: Integer -> Natural
integerToNatural (IS Bool#
x) = Word# -> Natural
naturalFromWord# (Bool# -> Word#
wordFromAbsInt# Bool#
x)
integerToNatural (IP ByteArray#
x) = ByteArray# -> Natural
naturalFromBigNat# ByteArray#
x
integerToNatural (IN ByteArray#
x) = ByteArray# -> Natural
naturalFromBigNat# ByteArray#
x

-- | Convert an Integer into a Natural
--
-- Throw an Underflow exception if input is negative.
integerToNaturalThrow :: Integer -> Natural
{-# NOINLINE integerToNaturalThrow #-}
integerToNaturalThrow :: Integer -> Natural
integerToNaturalThrow (IS Bool#
x)
  | Bool# -> Bool
isTrue# (Bool#
x Bool# -> Bool# -> Bool#
<# Bool#
0#) = Natural
forall a. a
raiseUnderflow
  | Bool
True              = Word# -> Natural
naturalFromWord# (Bool# -> Word#
int2Word# Bool#
x)
integerToNaturalThrow (IP ByteArray#
x) = ByteArray# -> Natural
naturalFromBigNat# ByteArray#
x
integerToNaturalThrow (IN ByteArray#
_) = Natural
forall a. a
raiseUnderflow

---------------------------------------------------------------------
-- 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 pattern
matching takes place just a multi-way jump.

In some cases (e.g. integerMul, integerSub) this actually makes the function
strict when it would otherwise not be; but in other cases (e.g integerNe) the
function is strict in both arguments anyway.  In the latter case it's a bit moot
whether to have the bangs or not; so this Note just documents that there is no
Deep Reason why they have to be there.  See Note Note [Case-to-let for
strictly-used binders] in GHC.Core.Opt.Simplify.Iteration for discussion about
evals on strictly-used binders.

I have not pointed to this Note from every such use.  There are a lot of them!
-}

-- | Negative predicate
integerIsNegative# :: Integer -> Bool#
integerIsNegative# :: Integer -> Bool#
integerIsNegative# (IS Bool#
i#) = Bool#
i# Bool# -> Bool# -> Bool#
<# Bool#
0#
integerIsNegative# (IP ByteArray#
_)  = Bool#
0#
integerIsNegative# (IN ByteArray#
_)  = Bool#
1#

-- | Negative predicate
integerIsNegative :: Integer -> Bool
integerIsNegative :: Integer -> Bool
integerIsNegative !Integer
i = Bool# -> Bool
isTrue# (Integer -> Bool#
integerIsNegative# Integer
i)
   -- Note [Bangs in Integer functions]

-- | Zero predicate
integerIsZero :: Integer -> Bool
integerIsZero :: Integer -> Bool
integerIsZero (IS Bool#
0#) = Bool
True
integerIsZero Integer
_       = Bool
False

-- | One predicate
integerIsOne :: Integer -> Bool
integerIsOne :: Integer -> Bool
integerIsOne (IS Bool#
1#) = Bool
True
integerIsOne Integer
_       = Bool
False

-- | Not-equal predicate.
integerNe :: Integer -> Integer -> Bool
integerNe :: Integer -> Integer -> Bool
integerNe !Integer
x !Integer
y = Bool# -> Bool
isTrue# (Integer -> Integer -> Bool#
integerNe# Integer
x Integer
y)
   -- Note [Bangs in Integer functions]

-- | Equal predicate.
integerEq :: Integer -> Integer -> Bool
integerEq :: Integer -> Integer -> Bool
integerEq !Integer
x !Integer
y = Bool# -> Bool
isTrue# (Integer -> Integer -> Bool#
integerEq# Integer
x Integer
y)
   -- See Note [Bangs in Integer functions]

-- | Lower-or-equal predicate.
integerLe :: Integer -> Integer -> Bool
integerLe :: Integer -> Integer -> Bool
integerLe !Integer
x !Integer
y = Bool# -> Bool
isTrue# (Integer -> Integer -> Bool#
integerLe# Integer
x Integer
y)
   -- See Note [Bangs in Integer functions]

-- | Lower predicate.
integerLt :: Integer -> Integer -> Bool
integerLt :: Integer -> Integer -> Bool
integerLt !Integer
x !Integer
y = Bool# -> Bool
isTrue# (Integer -> Integer -> Bool#
integerLt# Integer
x Integer
y)
   -- See Note [Bangs in Integer functions]

-- | Greater predicate.
integerGt :: Integer -> Integer -> Bool
integerGt :: Integer -> Integer -> Bool
integerGt !Integer
x !Integer
y = Bool# -> Bool
isTrue# (Integer -> Integer -> Bool#
integerGt# Integer
x Integer
y)
   -- See Note [Bangs in Integer functions]

-- | Greater-or-equal predicate.
integerGe :: Integer -> Integer -> Bool
integerGe :: Integer -> Integer -> Bool
integerGe !Integer
x !Integer
y = Bool# -> Bool
isTrue# (Integer -> Integer -> Bool#
integerGe# Integer
x Integer
y)
   -- See Note [Bangs in Integer functions]

-- | Equal predicate.
integerEq# :: Integer -> Integer -> Bool#
integerEq# :: Integer -> Integer -> Bool#
integerEq# (IS Bool#
x) (IS Bool#
y) = Bool#
x Bool# -> Bool# -> Bool#
==# Bool#
y
integerEq# (IN ByteArray#
x) (IN ByteArray#
y) = ByteArray# -> ByteArray# -> Bool#
bigNatEq# ByteArray#
x ByteArray#
y
integerEq# (IP ByteArray#
x) (IP ByteArray#
y) = ByteArray# -> ByteArray# -> Bool#
bigNatEq# ByteArray#
x ByteArray#
y
integerEq# Integer
_       Integer
_     = Bool#
0#

-- | Not-equal predicate.
integerNe# :: Integer -> Integer -> Bool#
integerNe# :: Integer -> Integer -> Bool#
integerNe# (IS Bool#
x) (IS Bool#
y) = Bool#
x Bool# -> Bool# -> Bool#
/=# Bool#
y
integerNe# (IN ByteArray#
x) (IN ByteArray#
y) = ByteArray# -> ByteArray# -> Bool#
bigNatNe# ByteArray#
x ByteArray#
y
integerNe# (IP ByteArray#
x) (IP ByteArray#
y) = ByteArray# -> ByteArray# -> Bool#
bigNatNe# ByteArray#
x ByteArray#
y
integerNe# Integer
_       Integer
_     = Bool#
1#

-- | Greater predicate.
integerGt# :: Integer -> Integer -> Bool#
integerGt# :: Integer -> Integer -> Bool#
integerGt# (IS Bool#
x) (IS Bool#
y)                  = Bool#
x Bool# -> Bool# -> Bool#
># Bool#
y
integerGt# Integer
x Integer
y | Ordering
GT <- Integer -> Integer -> Ordering
integerCompare Integer
x Integer
y = Bool#
1#
integerGt# Integer
_ Integer
_                            = Bool#
0#

-- | Lower-or-equal predicate.
integerLe# :: Integer -> Integer -> Bool#
integerLe# :: Integer -> Integer -> Bool#
integerLe# (IS Bool#
x) (IS Bool#
y)                  = Bool#
x Bool# -> Bool# -> Bool#
<=# Bool#
y
integerLe# Integer
x Integer
y | Ordering
GT <- Integer -> Integer -> Ordering
integerCompare Integer
x Integer
y = Bool#
0#
integerLe# Integer
_ Integer
_                            = Bool#
1#

-- | Lower predicate.
integerLt# :: Integer -> Integer -> Bool#
integerLt# :: Integer -> Integer -> Bool#
integerLt# (IS Bool#
x) (IS Bool#
y)                  = Bool#
x Bool# -> Bool# -> Bool#
<# Bool#
y
integerLt# Integer
x Integer
y | Ordering
LT <- Integer -> Integer -> Ordering
integerCompare Integer
x Integer
y = Bool#
1#
integerLt# Integer
_ Integer
_                            = Bool#
0#

-- | Greater-or-equal predicate.
integerGe# :: Integer -> Integer -> Bool#
integerGe# :: Integer -> Integer -> Bool#
integerGe# (IS Bool#
x) (IS Bool#
y)                  = Bool#
x Bool# -> Bool# -> Bool#
>=# Bool#
y
integerGe# Integer
x Integer
y | Ordering
LT <- Integer -> Integer -> Ordering
integerCompare Integer
x Integer
y = Bool#
0#
integerGe# Integer
_ Integer
_                            = Bool#
1#

instance Eq Integer where
   == :: Integer -> Integer -> Bool
(==) = Integer -> Integer -> Bool
integerEq
   /= :: Integer -> Integer -> Bool
(/=) = Integer -> Integer -> Bool
integerNe

-- | Compare two Integer
integerCompare :: Integer -> Integer -> Ordering
{-# INLINEABLE integerCompare #-}
integerCompare :: Integer -> Integer -> Ordering
integerCompare (IS Bool#
x) (IS Bool#
y) = Bool# -> Bool# -> Ordering
compareInt# Bool#
x Bool#
y
integerCompare (IP ByteArray#
x) (IP ByteArray#
y) = ByteArray# -> ByteArray# -> Ordering
bigNatCompare ByteArray#
x ByteArray#
y
integerCompare (IN ByteArray#
x) (IN ByteArray#
y) = ByteArray# -> ByteArray# -> Ordering
bigNatCompare ByteArray#
y ByteArray#
x
integerCompare (IS Bool#
_) (IP ByteArray#
_) = Ordering
LT
integerCompare (IS Bool#
_) (IN ByteArray#
_) = Ordering
GT
integerCompare (IP ByteArray#
_) (IS Bool#
_) = Ordering
GT
integerCompare (IN ByteArray#
_) (IS Bool#
_) = Ordering
LT
integerCompare (IP ByteArray#
_) (IN ByteArray#
_) = Ordering
GT
integerCompare (IN ByteArray#
_) (IP ByteArray#
_) = Ordering
LT

instance Ord Integer where
   compare :: Integer -> Integer -> Ordering
compare = Integer -> Integer -> Ordering
integerCompare
   < :: Integer -> Integer -> Bool
(<)     = Integer -> Integer -> Bool
integerLt
   <= :: Integer -> Integer -> Bool
(<=)    = Integer -> Integer -> Bool
integerLe
   > :: Integer -> Integer -> Bool
(>)     = Integer -> Integer -> Bool
integerGt
   >= :: Integer -> Integer -> Bool
(>=)    = Integer -> Integer -> Bool
integerGe

---------------------------------------------------------------------
-- Operations
---------------------------------------------------------------------

-- | Subtract one 'Integer' from another.
integerSub :: Integer -> Integer -> Integer
{-# NOINLINE integerSub #-}
integerSub :: Integer -> Integer -> Integer
integerSub !Integer
x      (IS Bool#
0#) = Integer
x     -- Note [Bangs in Integer functions]
integerSub (IS Bool#
x#) (IS Bool#
y#)
  = case Bool# -> Bool# -> (# Bool#, Bool# #)
subIntC# Bool#
x# Bool#
y# of
    (# Bool#
z#, Bool#
0# #) -> Bool# -> Integer
IS Bool#
z#
    (# Bool#
0#, Bool#
_  #) -> ByteArray# -> Integer
IN (Word# -> Word# -> ByteArray#
bigNatFromWord2# Word#
1## Word#
0##)
    (# Bool#
z#, Bool#
_  #)
      | Bool# -> Bool
isTrue# (Bool#
z# Bool# -> Bool# -> Bool#
># Bool#
0#)
      -> ByteArray# -> Integer
IN (Word# -> ByteArray#
bigNatFromWord# ( (Bool# -> Word#
int2Word# (Bool# -> Bool#
negateInt# Bool#
z#))))
      | Bool
True
      -> ByteArray# -> Integer
IP (Word# -> ByteArray#
bigNatFromWord# ( (Bool# -> Word#
int2Word# Bool#
z#)))
integerSub (IS Bool#
x#) (IP ByteArray#
y)
  | Bool# -> Bool
isTrue# (Bool#
x# Bool# -> Bool# -> Bool#
>=# Bool#
0#)
  = ByteArray# -> Integer
integerFromBigNatNeg# (ByteArray# -> Word# -> ByteArray#
bigNatSubWordUnsafe# ByteArray#
y (Bool# -> Word#
int2Word# Bool#
x#))
  | Bool
True
  = ByteArray# -> Integer
IN (ByteArray# -> Word# -> ByteArray#
bigNatAddWord# ByteArray#
y (Bool# -> Word#
int2Word# (Bool# -> Bool#
negateInt# Bool#
x#)))
integerSub (IS Bool#
x#) (IN ByteArray#
y)
  | Bool# -> Bool
isTrue# (Bool#
x# Bool# -> Bool# -> Bool#
>=# Bool#
0#)
  = ByteArray# -> Integer
IP (ByteArray# -> Word# -> ByteArray#
bigNatAddWord# ByteArray#
y (Bool# -> Word#
int2Word# Bool#
x#))
  | Bool
True
  = ByteArray# -> Integer
integerFromBigNat# (ByteArray# -> Word# -> ByteArray#
bigNatSubWordUnsafe# ByteArray#
y (Bool# -> Word#
int2Word# (Bool# -> Bool#
negateInt# Bool#
x#)))
integerSub (IP ByteArray#
x) (IP ByteArray#
y)
  = case ByteArray# -> ByteArray# -> Ordering
bigNatCompare ByteArray#
x ByteArray#
y of
    Ordering
LT -> ByteArray# -> Integer
integerFromBigNatNeg# (ByteArray# -> ByteArray# -> ByteArray#
bigNatSubUnsafe ByteArray#
y ByteArray#
x)
    Ordering
EQ -> Bool# -> Integer
IS Bool#
0#
    Ordering
GT -> ByteArray# -> Integer
integerFromBigNat# (ByteArray# -> ByteArray# -> ByteArray#
bigNatSubUnsafe ByteArray#
x ByteArray#
y)
integerSub (IP ByteArray#
x) (IN ByteArray#
y) = ByteArray# -> Integer
IP (ByteArray# -> ByteArray# -> ByteArray#
bigNatAdd ByteArray#
x ByteArray#
y)
integerSub (IN ByteArray#
x) (IP ByteArray#
y) = ByteArray# -> Integer
IN (ByteArray# -> ByteArray# -> ByteArray#
bigNatAdd ByteArray#
x ByteArray#
y)
integerSub (IN ByteArray#
x) (IN ByteArray#
y)
  = case ByteArray# -> ByteArray# -> Ordering
bigNatCompare ByteArray#
x ByteArray#
y of
    Ordering
LT -> ByteArray# -> Integer
integerFromBigNat# (ByteArray# -> ByteArray# -> ByteArray#
bigNatSubUnsafe ByteArray#
y ByteArray#
x)
    Ordering
EQ -> Bool# -> Integer
IS Bool#
0#
    Ordering
GT -> ByteArray# -> Integer
integerFromBigNatNeg# (ByteArray# -> ByteArray# -> ByteArray#
bigNatSubUnsafe ByteArray#
x ByteArray#
y)
integerSub (IP ByteArray#
x) (IS Bool#
y#)
  | Bool# -> Bool
isTrue# (Bool#
y# Bool# -> Bool# -> Bool#
>=# Bool#
0#)
  = ByteArray# -> Integer
integerFromBigNat# (ByteArray# -> Word# -> ByteArray#
bigNatSubWordUnsafe# ByteArray#
x (Bool# -> Word#
int2Word# Bool#
y#))
  | Bool
True
  = ByteArray# -> Integer
IP (ByteArray# -> Word# -> ByteArray#
bigNatAddWord# ByteArray#
x (Bool# -> Word#
int2Word# (Bool# -> Bool#
negateInt# Bool#
y#)))
integerSub (IN ByteArray#
x) (IS Bool#
y#)
  | Bool# -> Bool
isTrue# (Bool#
y# Bool# -> Bool# -> Bool#
>=# Bool#
0#)
  = ByteArray# -> Integer
IN (ByteArray# -> Word# -> ByteArray#
bigNatAddWord# ByteArray#
x (Bool# -> Word#
int2Word# Bool#
y#))
  | Bool
True
  = ByteArray# -> Integer
integerFromBigNatNeg# (ByteArray# -> Word# -> ByteArray#
bigNatSubWordUnsafe# ByteArray#
x (Bool# -> Word#
int2Word# (Bool# -> Bool#
negateInt# Bool#
y#)))

-- | Add two 'Integer's
integerAdd :: Integer -> Integer -> Integer
{-# NOINLINE integerAdd #-}
integerAdd :: Integer -> Integer -> Integer
integerAdd !Integer
x      (IS Bool#
0#) = Integer
x
integerAdd (IS Bool#
0#) Integer
y       = Integer
y
integerAdd (IS Bool#
x#) (IS Bool#
y#)
  = case Bool# -> Bool# -> (# Bool#, Bool# #)
addIntC# Bool#
x# Bool#
y# of
    (# Bool#
z#, Bool#
0# #) -> Bool# -> Integer
IS Bool#
z#
    (# Bool#
0#, Bool#
_  #) -> ByteArray# -> Integer
IN (Word# -> Word# -> ByteArray#
bigNatFromWord2# Word#
1## Word#
0##) -- 2*minBound::Int
    (# Bool#
z#, Bool#
_  #)
      | Bool# -> Bool
isTrue# (Bool#
z# Bool# -> Bool# -> Bool#
># Bool#
0#) -> ByteArray# -> Integer
IN (Word# -> ByteArray#
bigNatFromWord# ( (Bool# -> Word#
int2Word# (Bool# -> Bool#
negateInt# Bool#
z#))))
      | Bool
True               -> ByteArray# -> Integer
IP (Word# -> ByteArray#
bigNatFromWord# ( (Bool# -> Word#
int2Word# Bool#
z#)))
integerAdd y :: Integer
y@(IS Bool#
_) Integer
x = Integer -> Integer -> Integer
integerAdd Integer
x Integer
y
integerAdd (IP ByteArray#
x) (IP ByteArray#
y) = ByteArray# -> Integer
IP (ByteArray# -> ByteArray# -> ByteArray#
bigNatAdd ByteArray#
x ByteArray#
y)
integerAdd (IN ByteArray#
x) (IN ByteArray#
y) = ByteArray# -> Integer
IN (ByteArray# -> ByteArray# -> ByteArray#
bigNatAdd ByteArray#
x ByteArray#
y)
integerAdd (IP ByteArray#
x) (IS Bool#
y#) -- edge-case: @(maxBound+1) + minBound == 0@
  | Bool# -> Bool
isTrue# (Bool#
y# Bool# -> Bool# -> Bool#
>=# Bool#
0#) = ByteArray# -> Integer
IP (ByteArray# -> Word# -> ByteArray#
bigNatAddWord# ByteArray#
x (Bool# -> Word#
int2Word# Bool#
y#))
  | Bool
True                = ByteArray# -> Integer
integerFromBigNat# (ByteArray# -> Word# -> ByteArray#
bigNatSubWordUnsafe# ByteArray#
x (Bool# -> Word#
int2Word#
                                                              (Bool# -> Bool#
negateInt# Bool#
y#)))
integerAdd (IN ByteArray#
x) (IS Bool#
y#) -- edge-case: @(minBound-1) + maxBound == -2@
  | Bool# -> Bool
isTrue# (Bool#
y# Bool# -> Bool# -> Bool#
>=# Bool#
0#) = ByteArray# -> Integer
integerFromBigNatNeg# (ByteArray# -> Word# -> ByteArray#
bigNatSubWordUnsafe# ByteArray#
x (Bool# -> Word#
int2Word# Bool#
y#))
  | Bool
True                = ByteArray# -> Integer
IN (ByteArray# -> Word# -> ByteArray#
bigNatAddWord# ByteArray#
x (Bool# -> Word#
int2Word# (Bool# -> Bool#
negateInt# Bool#
y#)))
integerAdd y :: Integer
y@(IN ByteArray#
_) x :: Integer
x@(IP ByteArray#
_) = Integer -> Integer -> Integer
integerAdd Integer
x Integer
y
integerAdd (IP ByteArray#
x) (IN ByteArray#
y)
    = case ByteArray# -> ByteArray# -> Ordering
bigNatCompare ByteArray#
x ByteArray#
y of
      Ordering
LT -> ByteArray# -> Integer
integerFromBigNatNeg# (ByteArray# -> ByteArray# -> ByteArray#
bigNatSubUnsafe ByteArray#
y ByteArray#
x)
      Ordering
EQ -> Bool# -> Integer
IS Bool#
0#
      Ordering
GT -> ByteArray# -> Integer
integerFromBigNat# (ByteArray# -> ByteArray# -> ByteArray#
bigNatSubUnsafe ByteArray#
x ByteArray#
y)

-- | Multiply two 'Integer's
integerMul :: Integer -> Integer -> Integer
{-# NOINLINE integerMul #-}
integerMul :: Integer -> Integer -> Integer
integerMul !Integer
_       (IS Bool#
0#)  = Bool# -> Integer
IS Bool#
0#  -- Note [Bangs in Integer functions]
integerMul (IS Bool#
0#)  Integer
_        = Bool# -> Integer
IS Bool#
0#
integerMul Integer
x        (IS Bool#
1#)  = Integer
x
integerMul (IS Bool#
1#)  Integer
y        = Integer
y
integerMul Integer
x        (IS Bool#
-1#) = Integer -> Integer
integerNegate Integer
x
integerMul (IS Bool#
-1#) Integer
y        = Integer -> Integer
integerNegate Integer
y
integerMul (IS Bool#
x)   (IS Bool#
y)   = case Bool# -> Bool# -> (# Bool#, Bool#, Bool# #)
timesInt2# Bool#
x Bool#
y of
   (# Bool#
0#, Bool#
_h, Bool#
l #) -> Bool# -> Integer
IS Bool#
l
   (# Bool#
_ ,  Bool#
h, Bool#
l #)
      | Bool# -> Bool
isTrue# (Bool#
h Bool# -> Bool# -> Bool#
>=# Bool#
0#)
      -> ByteArray# -> Integer
IP (Word# -> Word# -> ByteArray#
bigNatFromWord2# (Bool# -> Word#
int2Word# Bool#
h) (Bool# -> Word#
int2Word# Bool#
l))
      | Bool
True
      -> 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#
c Word# -> Word# -> Word#
`plusWord#` Word# -> Word#
not# (Bool# -> Word#
int2Word# Bool#
h)
         in ByteArray# -> Integer
IN (Word# -> Word# -> ByteArray#
bigNatFromWord2# Word#
h' Word#
l')
integerMul x :: Integer
x@(IS Bool#
_) Integer
y    = Integer -> Integer -> Integer
integerMul Integer
y Integer
x
integerMul (IP ByteArray#
x) (IP ByteArray#
y) = ByteArray# -> Integer
IP (ByteArray# -> ByteArray# -> ByteArray#
bigNatMul ByteArray#
x ByteArray#
y)
integerMul (IP ByteArray#
x) (IN ByteArray#
y) = ByteArray# -> Integer
IN (ByteArray# -> ByteArray# -> ByteArray#
bigNatMul ByteArray#
x ByteArray#
y)
integerMul (IP ByteArray#
x) (IS Bool#
y)
  | Bool# -> Bool
isTrue# (Bool#
y Bool# -> Bool# -> Bool#
>=# Bool#
0#)   = ByteArray# -> Integer
IP (ByteArray# -> Word# -> ByteArray#
bigNatMulWord# ByteArray#
x (Bool# -> Word#
int2Word# Bool#
y))
  | Bool
True                 = ByteArray# -> Integer
IN (ByteArray# -> Word# -> ByteArray#
bigNatMulWord# ByteArray#
x (Bool# -> Word#
int2Word# (Bool# -> Bool#
negateInt# Bool#
y)))
integerMul (IN ByteArray#
x) (IN ByteArray#
y) = ByteArray# -> Integer
IP (ByteArray# -> ByteArray# -> ByteArray#
bigNatMul ByteArray#
x ByteArray#
y)
integerMul (IN ByteArray#
x) (IP ByteArray#
y) = ByteArray# -> Integer
IN (ByteArray# -> ByteArray# -> ByteArray#
bigNatMul ByteArray#
x ByteArray#
y)
integerMul (IN ByteArray#
x) (IS Bool#
y)
  | Bool# -> Bool
isTrue# (Bool#
y Bool# -> Bool# -> Bool#
>=# Bool#
0#)   = ByteArray# -> Integer
IN (ByteArray# -> Word# -> ByteArray#
bigNatMulWord# ByteArray#
x (Bool# -> Word#
int2Word# Bool#
y))
  | Bool
True                 = ByteArray# -> Integer
IP (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::Int
integerNegate :: Integer -> Integer
{-# NOINLINE integerNegate #-}
integerNegate :: Integer -> Integer
integerNegate (IN ByteArray#
b)             = ByteArray# -> Integer
IP ByteArray#
b
integerNegate (IS INT_MINBOUND#) = IP (bigNatFromWord# ABS_INT_MINBOUND##)
integerNegate (IS Bool#
i)             = Bool# -> Integer
IS (Bool# -> Bool#
negateInt# Bool#
i)
integerNegate (IP ByteArray#
b)
  | Bool# -> Bool
isTrue# (ByteArray# -> Word# -> Bool#
bigNatEqWord# ByteArray#
b ABS_INT_MINBOUND##) = IS INT_MINBOUND#
  | Bool
True                                         = ByteArray# -> Integer
IN ByteArray#
b

{-# RULES
"integerNegate/integerNegate" forall x. integerNegate (integerNegate x) = x
#-}

-- | Compute absolute value of an 'Integer'
integerAbs :: Integer -> Integer
{-# NOINLINE integerAbs #-}
integerAbs :: Integer -> Integer
integerAbs   (IN ByteArray#
i)     = ByteArray# -> Integer
IP ByteArray#
i
integerAbs n :: Integer
n@(IP ByteArray#
_)     = Integer
n
integerAbs n :: Integer
n@(IS Bool#
i)
   | Bool# -> Bool
isTrue# (Bool#
i Bool# -> Bool# -> Bool#
>=# Bool#
0#) = Integer
n
   | INT_MINBOUND# <- i = IP Bool#
(bigNatFromWord# ABS_INT_MINBOUND##)
   | Bool
True               = Bool# -> Integer
IS (Bool# -> Bool#
negateInt# Bool#
i)


-- | Return @-1@, @0@, and @1@ depending on whether argument is
-- negative, zero, or positive, respectively
integerSignum :: Integer -> Integer
integerSignum :: Integer -> Integer
integerSignum !Integer
j = Bool# -> Integer
IS (Integer -> Bool#
integerSignum# Integer
j)
     -- Note [Bangs in Integer functions]

-- | Return @-1#@, @0#@, and @1#@ depending on whether argument is
-- negative, zero, or positive, respectively
integerSignum# :: Integer -> Int#
integerSignum# :: Integer -> Bool#
integerSignum# (IN ByteArray#
_)  = Bool#
-1#
integerSignum# (IS Bool#
i#) = Bool# -> Bool#
sgnI# Bool#
i#
integerSignum# (IP ByteArray#
_ ) =  Bool#
1#

-- | Count number of set bits. For negative arguments returns
-- the negated population count of the absolute value.
integerPopCount# :: Integer -> Int#
{-# NOINLINE integerPopCount# #-}
integerPopCount# :: Integer -> Bool#
integerPopCount# (IS Bool#
i)
   | Bool# -> Bool
isTrue# (Bool#
i Bool# -> Bool# -> Bool#
>=# Bool#
0#)  = Word# -> Bool#
word2Int# (Bool# -> Word#
popCntI# Bool#
i)
   | Bool
True                = Bool# -> Bool#
negateInt# (Word# -> Bool#
word2Int# (Bool# -> Word#
popCntI# (Bool# -> Bool#
negateInt# Bool#
i)))
integerPopCount# (IP ByteArray#
bn) = Word# -> Bool#
word2Int# (ByteArray# -> Word#
bigNatPopCount# ByteArray#
bn)
integerPopCount# (IN ByteArray#
bn) = Bool# -> Bool#
negateInt# (Word# -> Bool#
word2Int# (ByteArray# -> Word#
bigNatPopCount# ByteArray#
bn))

-- | Positive 'Integer' for which only /n/-th bit is set
integerBit# :: Word# -> Integer
{-# NOINLINE integerBit# #-}
integerBit# :: Word# -> Integer
integerBit# Word#
i
  | Bool# -> Bool
isTrue# (Word#
i Word# -> Word# -> Bool#
`ltWord#` (WORD_SIZE_IN_BITS## `minusWord#` 1##))
  = Bool# -> Integer
IS (Bool# -> Bool# -> Bool#
uncheckedIShiftL# Bool#
1# (Word# -> Bool#
word2Int# Word#
i))

  | Bool
True = ByteArray# -> Integer
IP (Word# -> ByteArray#
bigNatBit# Word#
i)

-- | 'Integer' for which only /n/-th bit is set
integerBit :: Word -> Integer
integerBit :: Word -> Integer
integerBit (W# Word#
i) = Word# -> Integer
integerBit# Word#
i

-- | Test if /n/-th bit is set.
--
-- Fake 2's complement for negative values (might be slow)
integerTestBit# :: Integer -> Word# -> Bool#
{-# NOINLINE integerTestBit# #-}
integerTestBit# :: Integer -> Word# -> Bool#
integerTestBit# (IS Bool#
x) Word#
i
   | Bool# -> Bool
isTrue# (Word#
i Word# -> Word# -> Bool#
`ltWord#` WORD_SIZE_IN_BITS##)
   = Bool# -> Word# -> Bool#
testBitI# Bool#
x Word#
i
   | Bool
True
   = Bool#
x Bool# -> Bool# -> Bool#
<# Bool#
0#
integerTestBit# (IP ByteArray#
x) Word#
i = ByteArray# -> Word# -> Bool#
bigNatTestBit# ByteArray#
x Word#
i
integerTestBit# (IN ByteArray#
x) Word#
i
   | Bool# -> Bool
isTrue# (Bool#
iw Bool# -> 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# -> Bool
allZ Bool#
iw = Word# -> Word# -> Bool#
testBitW# (Word#
xi Word# -> Word# -> Word#
`minusWord#` Word#
1##) Word#
ib Bool# -> Bool# -> Bool#
==# Bool#
0#
   | Bool
True    = Word# -> Word# -> Bool#
testBitW# Word#
xi Word#
ib Bool# -> Bool# -> Bool#
==# Bool#
0#
   where
      !xi :: Word#
xi  = ByteArray# -> Bool# -> Word#
bigNatIndex# ByteArray#
x Bool#
iw
      !n :: Bool#
n   = ByteArray# -> Bool#
bigNatSize# ByteArray#
x
      !iw :: Bool#
iw  = Word# -> Bool#
word2Int# (Word#
i Word# -> Bool# -> Word#
`uncheckedShiftRL#` WORD_SIZE_BITS_SHIFT#)
      !ib :: Word#
ib  = Word#
i Word# -> Word# -> Word#
`and#` WORD_SIZE_BITS_MASK##

      allZ :: Bool# -> Bool
allZ Bool#
0# = Bool
True
      allZ Bool#
j | Bool# -> Bool
isTrue# (ByteArray# -> Bool# -> Word#
bigNatIndex# ByteArray#
x (Bool#
j Bool# -> Bool# -> Bool#
-# Bool#
1#) Word# -> Word# -> Bool#
`eqWord#` Word#
0##) = Bool# -> Bool
allZ (Bool#
j Bool# -> Bool# -> Bool#
-# Bool#
1#)
             | Bool
True                 = Bool
False

-- | 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 -> Bool
integerTestBit :: Integer -> Word -> Bool
integerTestBit !Integer
i (W# Word#
n) = Bool# -> Bool
isTrue# (Integer -> Word# -> Bool#
integerTestBit# Integer
i Word#
n)

-- | Shift-right operation
--
-- Fake 2's complement for negative values (might be slow)
integerShiftR# :: Integer -> Word# -> Integer
{-# NOINLINE integerShiftR# #-}
integerShiftR# :: Integer -> Word# -> Integer
integerShiftR# !Integer
x      Word#
0## = Integer
x   -- Note [Bangs in Integer functions]
integerShiftR# (IS Bool#
i)  Word#
n   = Bool# -> Integer
IS (Bool# -> Bool# -> Bool#
iShiftRA# Bool#
i (Word# -> Bool#
word2Int# Word#
n))
  where
    iShiftRA# :: Bool# -> Bool# -> Bool#
iShiftRA# Bool#
a Bool#
b
      | Bool# -> Bool
isTrue# (Bool#
b Bool# -> Bool# -> Bool#
>=# WORD_SIZE_IN_BITS#) = (a <# 0#) *# (-1#)
      | Bool
True                               = Bool#
a Bool# -> Bool# -> Bool#
`uncheckedIShiftRA#` Bool#
b
integerShiftR# (IP ByteArray#
bn) Word#
n   = ByteArray# -> Integer
integerFromBigNat# (ByteArray# -> Word# -> ByteArray#
bigNatShiftR# ByteArray#
bn Word#
n)
integerShiftR# (IN ByteArray#
bn) Word#
n   =
   case ByteArray# -> Integer
integerFromBigNatNeg# (ByteArray# -> Word# -> ByteArray#
bigNatShiftRNeg# ByteArray#
bn Word#
n) of
      IS Bool#
0# -> Bool# -> Integer
IS Bool#
-1#
      Integer
r     -> Integer
r

-- | Shift-right operation
--
-- Fake 2's complement for negative values (might be slow)
integerShiftR :: Integer -> Word -> Integer
integerShiftR :: Integer -> Word -> Integer
integerShiftR !Integer
x (W# Word#
w) = Integer -> Word# -> Integer
integerShiftR# Integer
x Word#
w
   -- Note [Bangs in Integer functions]

-- | Shift-left operation
integerShiftL# :: Integer -> Word# -> Integer
{-# NOINLINE integerShiftL# #-}
integerShiftL# :: Integer -> Word# -> Integer
integerShiftL# !Integer
x      Word#
0## = Integer
x  -- Note [Bangs in Integer functions]
integerShiftL# (IS Bool#
0#) Word#
_   = Bool# -> Integer
IS Bool#
0#
integerShiftL# (IS Bool#
1#) Word#
n   = Word# -> Integer
integerBit# Word#
n
integerShiftL# (IS Bool#
i)  Word#
n
  | Bool# -> Bool
isTrue# (Bool#
i Bool# -> Bool# -> Bool#
>=# Bool#
0#) = ByteArray# -> Integer
integerFromBigNat#    (ByteArray# -> Word# -> ByteArray#
bigNatShiftL# (Word# -> ByteArray#
bigNatFromWord# (Bool# -> Word#
int2Word# Bool#
i)) Word#
n)
  | Bool
True               = ByteArray# -> Integer
integerFromBigNatNeg# (ByteArray# -> Word# -> ByteArray#
bigNatShiftL# (Word# -> ByteArray#
bigNatFromWord# (Bool# -> Word#
int2Word# (Bool# -> Bool#
negateInt# Bool#
i))) Word#
n)
integerShiftL# (IP ByteArray#
bn) Word#
n   = ByteArray# -> Integer
IP (ByteArray# -> Word# -> ByteArray#
bigNatShiftL# ByteArray#
bn Word#
n)
integerShiftL# (IN ByteArray#
bn) Word#
n   = ByteArray# -> Integer
IN (ByteArray# -> Word# -> ByteArray#
bigNatShiftL# ByteArray#
bn Word#
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 -> Integer
integerShiftL :: Integer -> Word -> Integer
integerShiftL !Integer
x (W# Word#
w) = Integer -> Word# -> Integer
integerShiftL# Integer
x Word#
w
    -- Note [Bangs in Integer functions]

-- | Bitwise OR operation
--
-- Fake 2's complement for negative values (might be slow)
integerOr :: Integer -> Integer -> Integer
{-# NOINLINE integerOr #-}
integerOr :: Integer -> Integer -> Integer
integerOr Integer
a Integer
b = case Integer
a of
   IS  Bool#
0# -> Integer
b
   IS Bool#
-1# -> Bool# -> Integer
IS Bool#
-1#
   IS  Bool#
x  -> case Integer
b of
               IS  Bool#
0# -> Integer
a
               IS Bool#
-1# -> Bool# -> Integer
IS Bool#
-1#
               IS  Bool#
y  -> Bool# -> Integer
IS (Bool# -> Bool# -> Bool#
orI# Bool#
x Bool#
y)
               IP  ByteArray#
y
                  | Bool# -> Bool
isTrue# (Bool#
x Bool# -> Bool# -> Bool#
>=# Bool#
0#) -> ByteArray# -> Integer
IP (ByteArray# -> Word# -> ByteArray#
bigNatOrWord# ByteArray#
y (Bool# -> Word#
int2Word# Bool#
x))
                  | Bool
True               -> ByteArray# -> Integer
integerFromBigNatNeg#
                                             (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##)
               IN ByteArray#
y
                  | Bool# -> Bool
isTrue# (Bool#
x Bool# -> Bool# -> Bool#
>=# Bool#
0#) -> ByteArray# -> Integer
integerFromBigNatNeg#
                                             (ByteArray# -> Word# -> ByteArray#
bigNatAddWord#
                                                (ByteArray# -> Word# -> ByteArray#
bigNatAndNotWord# -- use De Morgan's laws
                                                   (ByteArray# -> Word# -> ByteArray#
bigNatSubWordUnsafe# ByteArray#
y Word#
1##)
                                                   (Bool# -> Word#
int2Word# Bool#
x))
                                                Word#
1##)
                  | Bool
True               -> ByteArray# -> Integer
integerFromBigNatNeg#
                                             (ByteArray# -> Word# -> ByteArray#
bigNatAddWord#
                                                (ByteArray# -> Word# -> ByteArray#
bigNatAndWord#  -- use De Morgan's laws
                                                   (ByteArray# -> Word# -> ByteArray#
bigNatSubWordUnsafe# ByteArray#
y Word#
1##)
                                                   (Bool# -> Word#
int2Word# (Bool# -> Bool#
negateInt# Bool#
x) Word# -> Word# -> Word#
`minusWord#` Word#
1##))
                                                Word#
1##)
   IP  ByteArray#
x  -> case Integer
b of
               IS Bool#
_ -> Integer -> Integer -> Integer
integerOr Integer
b Integer
a
               IP ByteArray#
y -> ByteArray# -> Integer
IP (ByteArray# -> ByteArray# -> ByteArray#
bigNatOr ByteArray#
x ByteArray#
y)
               IN ByteArray#
y -> ByteArray# -> Integer
integerFromBigNatNeg#
                        (ByteArray# -> Word# -> ByteArray#
bigNatAddWord#
                           (ByteArray# -> ByteArray# -> ByteArray#
bigNatAndNot -- use De Morgan's laws
                              (ByteArray# -> Word# -> ByteArray#
bigNatSubWordUnsafe# ByteArray#
y Word#
1##)
                              ByteArray#
x)
                           Word#
1##)
   IN  ByteArray#
x  -> case Integer
b of
               IS Bool#
_ -> Integer -> Integer -> Integer
integerOr Integer
b Integer
a
               IN ByteArray#
y -> ByteArray# -> Integer
integerFromBigNatNeg#
                        (ByteArray# -> Word# -> ByteArray#
bigNatAddWord#
                           (ByteArray# -> ByteArray# -> ByteArray#
bigNatAnd  -- use De Morgan's laws
                              (ByteArray# -> Word# -> ByteArray#
bigNatSubWordUnsafe# ByteArray#
x Word#
1##)
                              (ByteArray# -> Word# -> ByteArray#
bigNatSubWordUnsafe# ByteArray#
y Word#
1##))
                           Word#
1##)
               IP ByteArray#
y -> ByteArray# -> Integer
integerFromBigNatNeg#
                        (ByteArray# -> Word# -> ByteArray#
bigNatAddWord#
                           (ByteArray# -> ByteArray# -> ByteArray#
bigNatAndNot -- use De Morgan's laws
                              (ByteArray# -> Word# -> ByteArray#
bigNatSubWordUnsafe# ByteArray#
x Word#
1##)
                              ByteArray#
y)
                           Word#
1##)


-- | Bitwise XOR operation
--
-- Fake 2's complement for negative values (might be slow)
integerXor :: Integer -> Integer -> Integer
{-# NOINLINE integerXor #-}
integerXor :: Integer -> Integer -> Integer
integerXor Integer
a Integer
b = case Integer
a of
   IS  Bool#
0# -> Integer
b
   IS Bool#
-1# -> Integer -> Integer
integerComplement Integer
b
   IS Bool#
x   -> case Integer
b of
               IS  Bool#
0# -> Integer
a
               IS Bool#
-1# -> Integer -> Integer
integerComplement Integer
a
               IS Bool#
y   -> Bool# -> Integer
IS (Bool# -> Bool# -> Bool#
xorI# Bool#
x Bool#
y)
               IP ByteArray#
y
                  | Bool# -> Bool
isTrue# (Bool#
x Bool# -> Bool# -> Bool#
>=# Bool#
0#) -> ByteArray# -> Integer
integerFromBigNat# (ByteArray# -> Word# -> ByteArray#
bigNatXorWord# ByteArray#
y (Bool# -> Word#
int2Word# Bool#
x))
                  | Bool
True               -> ByteArray# -> Integer
integerFromBigNatNeg#
                                             (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##)
               IN ByteArray#
y
                  | Bool# -> Bool
isTrue# (Bool#
x Bool# -> Bool# -> Bool#
>=# Bool#
0#) -> ByteArray# -> Integer
integerFromBigNatNeg#
                                             (ByteArray# -> Word# -> ByteArray#
bigNatAddWord#
                                                (ByteArray# -> Word# -> ByteArray#
bigNatXorWord#
                                                   (ByteArray# -> Word# -> ByteArray#
bigNatSubWordUnsafe# ByteArray#
y Word#
1##)
                                                   (Bool# -> Word#
int2Word# Bool#
x))
                                                Word#
1##)
                  | Bool
True               -> ByteArray# -> Integer
integerFromBigNat#
                                             (ByteArray# -> Word# -> ByteArray#
bigNatXorWord# -- xor (not x) (not y) = xor x y
                                                (ByteArray# -> Word# -> ByteArray#
bigNatSubWordUnsafe# ByteArray#
y Word#
1##)
                                                (Bool# -> Word#
int2Word# (Bool# -> Bool#
negateInt# Bool#
x) Word# -> Word# -> Word#
`minusWord#` Word#
1##))
   IP ByteArray#
x   -> case Integer
b of
               IS Bool#
_ -> Integer -> Integer -> Integer
integerXor Integer
b Integer
a
               IP ByteArray#
y -> ByteArray# -> Integer
integerFromBigNat# (ByteArray# -> ByteArray# -> ByteArray#
bigNatXor ByteArray#
x ByteArray#
y)
               IN ByteArray#
y -> ByteArray# -> Integer
integerFromBigNatNeg#
                        (ByteArray# -> Word# -> ByteArray#
bigNatAddWord#
                           (ByteArray# -> ByteArray# -> ByteArray#
bigNatXor
                              ByteArray#
x
                              (ByteArray# -> Word# -> ByteArray#
bigNatSubWordUnsafe# ByteArray#
y Word#
1##))
                           Word#
1##)
   IN ByteArray#
x   -> case Integer
b of
               IS Bool#
_ -> Integer -> Integer -> Integer
integerXor Integer
b Integer
a
               IN ByteArray#
y -> ByteArray# -> Integer
integerFromBigNat#
                        (ByteArray# -> ByteArray# -> ByteArray#
bigNatXor -- xor (not x) (not y) = xor x y
                           (ByteArray# -> Word# -> ByteArray#
bigNatSubWordUnsafe# ByteArray#
x Word#
1##)
                           (ByteArray# -> Word# -> ByteArray#
bigNatSubWordUnsafe# ByteArray#
y Word#
1##))
               IP ByteArray#
y -> ByteArray# -> Integer
integerFromBigNatNeg#
                        (ByteArray# -> Word# -> ByteArray#
bigNatAddWord#
                           (ByteArray# -> ByteArray# -> ByteArray#
bigNatXor
                              ByteArray#
y
                              (ByteArray# -> Word# -> ByteArray#
bigNatSubWordUnsafe# ByteArray#
x Word#
1##))
                           Word#
1##)



-- | Bitwise AND operation
--
-- Fake 2's complement for negative values (might be slow)
integerAnd :: Integer -> Integer -> Integer
{-# NOINLINE integerAnd #-}
integerAnd :: Integer -> Integer -> Integer
integerAnd Integer
a Integer
b = case Integer
a of
   IS Bool#
0#  -> Bool# -> Integer
IS Bool#
0#
   IS Bool#
-1# -> Integer
b
   IS Bool#
x   -> case Integer
b of
               IS  Bool#
0# -> Bool# -> Integer
IS Bool#
0#
               IS Bool#
-1# -> Integer
a
               IS Bool#
y   -> Bool# -> Integer
IS (Bool# -> Bool# -> Bool#
andI# Bool#
x Bool#
y)
               IP ByteArray#
y   -> ByteArray# -> Integer
integerFromBigNat# (ByteArray# -> Bool# -> ByteArray#
bigNatAndInt# ByteArray#
y Bool#
x)
               IN ByteArray#
y
                  | Bool# -> Bool
isTrue# (Bool#
x Bool# -> Bool# -> Bool#
>=# Bool#
0#) -> Word# -> Integer
integerFromWord# (Bool# -> Word#
int2Word# Bool#
x Word# -> Word# -> Word#
`andNot#` (ByteArray# -> Bool# -> Word#
indexWordArray# ByteArray#
y Bool#
0# Word# -> Word# -> Word#
`minusWord#` Word#
1##))
                  | Bool
True               -> ByteArray# -> Integer
integerFromBigNatNeg#
                                             (ByteArray# -> Word# -> ByteArray#
bigNatAddWord#
                                                (ByteArray# -> Word# -> ByteArray#
bigNatOrWord#  -- use De Morgan's laws
                                                   (ByteArray# -> Word# -> ByteArray#
bigNatSubWordUnsafe# ByteArray#
y Word#
1##)
                                                   (Bool# -> Word#
wordFromAbsInt# Bool#
x Word# -> Word# -> Word#
`minusWord#` Word#
1##))
                                                Word#
1##)
   IP ByteArray#
x   -> case Integer
b of
               IS Bool#
_ -> Integer -> Integer -> Integer
integerAnd Integer
b Integer
a
               IP ByteArray#
y -> ByteArray# -> Integer
integerFromBigNat# (ByteArray# -> ByteArray# -> ByteArray#
bigNatAnd ByteArray#
x ByteArray#
y)
               IN ByteArray#
y -> ByteArray# -> Integer
integerFromBigNat# (ByteArray# -> ByteArray# -> ByteArray#
bigNatAndNot ByteArray#
x (ByteArray# -> Word# -> ByteArray#
bigNatSubWordUnsafe# ByteArray#
y Word#
1##))
   IN ByteArray#
x   -> case Integer
b of
               IS Bool#
_ -> Integer -> Integer -> Integer
integerAnd Integer
b Integer
a
               IN ByteArray#
y -> ByteArray# -> Integer
integerFromBigNatNeg#
                        (ByteArray# -> Word# -> ByteArray#
bigNatAddWord#
                           (ByteArray# -> ByteArray# -> ByteArray#
bigNatOr  -- use De Morgan's laws
                              (ByteArray# -> Word# -> ByteArray#
bigNatSubWordUnsafe# ByteArray#
x Word#
1##)
                              (ByteArray# -> Word# -> ByteArray#
bigNatSubWordUnsafe# ByteArray#
y Word#
1##))
                           Word#
1##)
               IP ByteArray#
y -> ByteArray# -> Integer
integerFromBigNat# (ByteArray# -> ByteArray# -> ByteArray#
bigNatAndNot ByteArray#
y (ByteArray# -> Word# -> ByteArray#
bigNatSubWordUnsafe# ByteArray#
x Word#
1##))



-- | Binary complement of the
integerComplement :: Integer -> Integer
{-# NOINLINE integerComplement #-}
integerComplement :: Integer -> Integer
integerComplement (IS Bool#
x) = Bool# -> Integer
IS (Bool# -> Bool#
notI# Bool#
x)
integerComplement (IP ByteArray#
x) = ByteArray# -> Integer
IN (ByteArray# -> Word# -> ByteArray#
bigNatAddWord# ByteArray#
x Word#
1##)
integerComplement (IN ByteArray#
x) = ByteArray# -> Integer
IP (ByteArray# -> Word# -> ByteArray#
bigNatSubWordUnsafe# ByteArray#
x Word#
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 #)
{-# NOINLINE integerQuotRem# #-}
integerQuotRem# :: Integer -> Integer -> (# Integer, Integer #)
integerQuotRem# !Integer
n      (IS Bool#
1#) = (# Integer
n, Bool# -> Integer
IS Bool#
0# #) -- Note [Bangs in Integer functions]
integerQuotRem# !Integer
n     (IS Bool#
-1#) = let !q :: Integer
q = Integer -> Integer
integerNegate Integer
n in (# Integer
q, (Bool# -> Integer
IS Bool#
0#) #)
integerQuotRem# !Integer
_      (IS Bool#
0#) = case ZonkAny 0
forall a. a
raiseDivZero of
                                    !ZonkAny 0
_ -> (# Bool# -> Integer
IS Bool#
0#, Bool# -> Integer
IS Bool#
0# #)
                                    -- see Note [ghc-bignum exceptions] in GHC.Internal.Bignum.Primitives
integerQuotRem# (IS Bool#
0#) Integer
_       = (# Bool# -> Integer
IS Bool#
0#, Bool# -> Integer
IS Bool#
0# #)
integerQuotRem# (IS Bool#
n#) (IS Bool#
d#) = case Bool# -> Bool# -> (# Bool#, Bool# #)
quotRemInt# Bool#
n# Bool#
d# of
    (# Bool#
q#, Bool#
r# #) -> (# Bool# -> Integer
IS Bool#
q#, Bool# -> Integer
IS Bool#
r# #)
integerQuotRem# (IP ByteArray#
n)  (IP ByteArray#
d)  = case ByteArray# -> ByteArray# -> (# ByteArray#, ByteArray# #)
bigNatQuotRem# ByteArray#
n ByteArray#
d of
    (# ByteArray#
q, ByteArray#
r #) -> (# ByteArray# -> Integer
integerFromBigNat# ByteArray#
q, ByteArray# -> Integer
integerFromBigNat# ByteArray#
r #)
integerQuotRem# (IP ByteArray#
n)  (IN ByteArray#
d)  = case ByteArray# -> ByteArray# -> (# ByteArray#, ByteArray# #)
bigNatQuotRem# ByteArray#
n ByteArray#
d of
    (# ByteArray#
q, ByteArray#
r #) -> (# ByteArray# -> Integer
integerFromBigNatNeg# ByteArray#
q, ByteArray# -> Integer
integerFromBigNat# ByteArray#
r #)
integerQuotRem# (IN ByteArray#
n)  (IN ByteArray#
d)  = case ByteArray# -> ByteArray# -> (# ByteArray#, ByteArray# #)
bigNatQuotRem# ByteArray#
n ByteArray#
d of
    (# ByteArray#
q, ByteArray#
r #) -> (# ByteArray# -> Integer
integerFromBigNat# ByteArray#
q, ByteArray# -> Integer
integerFromBigNatNeg# ByteArray#
r #)
integerQuotRem# (IN ByteArray#
n)  (IP ByteArray#
d)  = case ByteArray# -> ByteArray# -> (# ByteArray#, ByteArray# #)
bigNatQuotRem# ByteArray#
n ByteArray#
d of
    (# ByteArray#
q, ByteArray#
r #) -> (# ByteArray# -> Integer
integerFromBigNatNeg# ByteArray#
q, ByteArray# -> Integer
integerFromBigNatNeg# ByteArray#
r #)
integerQuotRem# (IP ByteArray#
n)  (IS Bool#
d#)
  | Bool# -> Bool
isTrue# (Bool#
d# Bool# -> Bool# -> Bool#
>=# Bool#
0#) = case ByteArray# -> Word# -> (# ByteArray#, Word# #)
bigNatQuotRemWord# ByteArray#
n (Bool# -> Word#
int2Word# Bool#
d#) of
      (# ByteArray#
q, Word#
r# #) -> (# ByteArray# -> Integer
integerFromBigNat# ByteArray#
q, Word# -> Integer
integerFromWord# Word#
r# #)
  | Bool
True                = case ByteArray# -> Word# -> (# ByteArray#, Word# #)
bigNatQuotRemWord# ByteArray#
n (Bool# -> Word#
int2Word# (Bool# -> Bool#
negateInt# Bool#
d#)) of
      (# ByteArray#
q, Word#
r# #) -> (# ByteArray# -> Integer
integerFromBigNatNeg# ByteArray#
q, Word# -> Integer
integerFromWord# Word#
r# #)
integerQuotRem# (IN ByteArray#
n)  (IS Bool#
d#)
  | Bool# -> Bool
isTrue# (Bool#
d# Bool# -> Bool# -> Bool#
>=# Bool#
0#) = case ByteArray# -> Word# -> (# ByteArray#, Word# #)
bigNatQuotRemWord# ByteArray#
n (Bool# -> Word#
int2Word# Bool#
d#) of
      (# ByteArray#
q, Word#
r# #) -> (# ByteArray# -> Integer
integerFromBigNatNeg# ByteArray#
q, Word# -> Integer
integerFromWordNeg# Word#
r# #)
  | Bool
True                = case ByteArray# -> Word# -> (# ByteArray#, Word# #)
bigNatQuotRemWord# ByteArray#
n (Bool# -> Word#
int2Word# (Bool# -> Bool#
negateInt# Bool#
d#)) of
      (# ByteArray#
q, Word#
r# #) -> (# ByteArray# -> Integer
integerFromBigNat# ByteArray#
q, Word# -> Integer
integerFromWordNeg# Word#
r# #)
integerQuotRem# n :: Integer
n@(IS Bool#
_) (IN ByteArray#
_) = (# Bool# -> Integer
IS Bool#
0#, Integer
n #) -- since @n < d@
integerQuotRem# n :: Integer
n@(IS Bool#
n#) (IP ByteArray#
d) -- need to account for (IS minBound)
    | Bool# -> Bool
isTrue# (Bool#
n# Bool# -> Bool# -> Bool#
># Bool#
0#)                                    = (# Bool# -> Integer
IS Bool#
0#, Integer
n #)
    | Bool# -> Bool
isTrue# (ByteArray# -> Word# -> Bool#
bigNatGtWord# ByteArray#
d (Bool# -> Word#
int2Word# (Bool# -> Bool#
negateInt# Bool#
n#))) = (# Bool# -> Integer
IS Bool#
0#, Integer
n #)
    | Bool
True {- abs(n) == d -}                                = (# Bool# -> Integer
IS Bool#
-1#, Bool# -> Integer
IS Bool#
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 !Integer
x !Integer
y = case Integer -> Integer -> (# Integer, Integer #)
integerQuotRem# Integer
x Integer
y of
  -- Note [Bangs in Integer functions]
  (# Integer
q, Integer
r #) -> (Integer
q, Integer
r)


integerQuot :: Integer -> Integer -> Integer
{-# NOINLINE integerQuot #-}
integerQuot :: Integer -> Integer -> Integer
integerQuot !Integer
n      (IS Bool#
1#)  = Integer
n  -- Note [Bangs in Integer functions]
integerQuot !Integer
n      (IS Bool#
-1#) = Integer -> Integer
integerNegate Integer
n
integerQuot !Integer
_      (IS Bool#
0#)  = Integer
forall a. a
raiseDivZero
integerQuot (IS Bool#
0#) Integer
_        = Bool# -> Integer
IS Bool#
0#
integerQuot (IS Bool#
n#) (IS Bool#
d#)  = Bool# -> Integer
IS (Bool# -> Bool# -> Bool#
quotInt# Bool#
n# Bool#
d#)
integerQuot (IP ByteArray#
n)  (IS Bool#
d#)
  | Bool# -> Bool
isTrue# (Bool#
d# Bool# -> Bool# -> Bool#
>=# Bool#
0#) = ByteArray# -> Integer
integerFromBigNat#    (ByteArray# -> Word# -> ByteArray#
bigNatQuotWord# ByteArray#
n (Bool# -> Word#
int2Word# Bool#
d#))
  | Bool
True                = ByteArray# -> Integer
integerFromBigNatNeg# (ByteArray# -> Word# -> ByteArray#
bigNatQuotWord# ByteArray#
n
                                              (Bool# -> Word#
int2Word# (Bool# -> Bool#
negateInt# Bool#
d#)))
integerQuot (IN ByteArray#
n)   (IS Bool#
d#)
  | Bool# -> Bool
isTrue# (Bool#
d# Bool# -> Bool# -> Bool#
>=# Bool#
0#) = ByteArray# -> Integer
integerFromBigNatNeg# (ByteArray# -> Word# -> ByteArray#
bigNatQuotWord# ByteArray#
n (Bool# -> Word#
int2Word# Bool#
d#))
  | Bool
True                = ByteArray# -> Integer
integerFromBigNat#    (ByteArray# -> Word# -> ByteArray#
bigNatQuotWord# ByteArray#
n
                                              (Bool# -> Word#
int2Word# (Bool# -> Bool#
negateInt# Bool#
d#)))
integerQuot (IP ByteArray#
n) (IP ByteArray#
d) = ByteArray# -> Integer
integerFromBigNat#    (ByteArray# -> ByteArray# -> ByteArray#
bigNatQuot ByteArray#
n ByteArray#
d)
integerQuot (IP ByteArray#
n) (IN ByteArray#
d) = ByteArray# -> Integer
integerFromBigNatNeg# (ByteArray# -> ByteArray# -> ByteArray#
bigNatQuot ByteArray#
n ByteArray#
d)
integerQuot (IN ByteArray#
n) (IP ByteArray#
d) = ByteArray# -> Integer
integerFromBigNatNeg# (ByteArray# -> ByteArray# -> ByteArray#
bigNatQuot ByteArray#
n ByteArray#
d)
integerQuot (IN ByteArray#
n) (IN ByteArray#
d) = ByteArray# -> Integer
integerFromBigNat#    (ByteArray# -> ByteArray# -> ByteArray#
bigNatQuot ByteArray#
n ByteArray#
d)
integerQuot Integer
n Integer
d = case Integer -> Integer -> (# Integer, Integer #)
integerQuotRem# Integer
n Integer
d of (# Integer
q, Integer
_ #) -> Integer
q

integerRem :: Integer -> Integer -> Integer
{-# NOINLINE integerRem #-}
integerRem :: Integer -> Integer -> Integer
integerRem !Integer
_       (IS Bool#
1#) = Bool# -> Integer
IS Bool#
0#   -- Note [Bangs in Integer functions]
integerRem Integer
_       (IS Bool#
-1#) = Bool# -> Integer
IS Bool#
0#
integerRem Integer
_        (IS Bool#
0#) = Bool# -> Integer
IS (Bool# -> Bool# -> Bool#
remInt# Bool#
0# Bool#
0#)
integerRem (IS Bool#
0#) Integer
_        = Bool# -> Integer
IS Bool#
0#
integerRem (IS Bool#
n#) (IS Bool#
d#) = Bool# -> Integer
IS (Bool# -> Bool# -> Bool#
remInt# Bool#
n# Bool#
d#)
integerRem (IP ByteArray#
n)  (IS Bool#
d#)
    = Word# -> Integer
integerFromWord#    (ByteArray# -> Word# -> Word#
bigNatRemWord# ByteArray#
n (Bool# -> Word#
int2Word# (Bool# -> Bool#
absI# Bool#
d#)))
integerRem (IN ByteArray#
n)  (IS Bool#
d#)
    = Word# -> Integer
integerFromWordNeg# (ByteArray# -> Word# -> Word#
bigNatRemWord# ByteArray#
n (Bool# -> Word#
int2Word# (Bool# -> Bool#
absI# Bool#
d#)))
integerRem (IP ByteArray#
n)  (IP ByteArray#
d)  = ByteArray# -> Integer
integerFromBigNat#    (ByteArray# -> ByteArray# -> ByteArray#
bigNatRem ByteArray#
n ByteArray#
d)
integerRem (IP ByteArray#
n)  (IN ByteArray#
d)  = ByteArray# -> Integer
integerFromBigNat#    (ByteArray# -> ByteArray# -> ByteArray#
bigNatRem ByteArray#
n ByteArray#
d)
integerRem (IN ByteArray#
n)  (IP ByteArray#
d)  = ByteArray# -> Integer
integerFromBigNatNeg# (ByteArray# -> ByteArray# -> ByteArray#
bigNatRem ByteArray#
n ByteArray#
d)
integerRem (IN ByteArray#
n)  (IN ByteArray#
d)  = ByteArray# -> Integer
integerFromBigNatNeg# (ByteArray# -> ByteArray# -> ByteArray#
bigNatRem ByteArray#
n ByteArray#
d)
integerRem Integer
n Integer
d = case Integer -> Integer -> (# Integer, Integer #)
integerQuotRem# Integer
n Integer
d of (# Integer
_, Integer
r #) -> Integer
r


-- | 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 #)
{-# NOINLINE integerDivMod# #-}
integerDivMod# :: Integer -> Integer -> (# Integer, Integer #)
integerDivMod# !Integer
n !Integer
d    -- Note [Bangs in Integer functions]
  | Bool# -> Bool
isTrue# (Integer -> Bool#
integerSignum# Integer
r Bool# -> Bool# -> Bool#
==# Bool# -> Bool#
negateInt# (Integer -> Bool#
integerSignum# Integer
d))
     = let !q' :: Integer
q' = Integer -> Integer -> Integer
integerSub Integer
q (Bool# -> Integer
IS Bool#
1#)
           !r' :: Integer
r' = Integer -> Integer -> Integer
integerAdd Integer
r Integer
d
       in (# Integer
q', Integer
r' #)
  | Bool
True = (# Integer, Integer #)
qr
  where
    !qr :: (# Integer, Integer #)
qr@(# Integer
q, Integer
r #) = Integer -> Integer -> (# Integer, Integer #)
integerQuotRem# Integer
n Integer
d

-- | 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 !Integer
n !Integer
d = case Integer -> Integer -> (# Integer, Integer #)
integerDivMod# Integer
n Integer
d of
   -- Note [Bangs in Integer functions]
   (# Integer
q,Integer
r #) -> (Integer
q,Integer
r)


integerDiv :: Integer -> Integer -> Integer
{-# NOINLINE integerDiv #-}
integerDiv :: Integer -> Integer -> Integer
integerDiv !Integer
n !Integer
d  -- Note [Bangs in Integer functions]
   -- same-sign ops can be handled by more efficient 'integerQuot'
   | Bool# -> Bool
isTrue# (Integer -> Bool#
integerIsNegative# Integer
n Bool# -> Bool# -> Bool#
==# Integer -> Bool#
integerIsNegative# Integer
d) = Integer -> Integer -> Integer
integerQuot Integer
n Integer
d
   | Bool
True = case Integer -> Integer -> (# Integer, Integer #)
integerDivMod# Integer
n Integer
d of (# Integer
q, Integer
_ #) -> Integer
q


integerMod :: Integer -> Integer -> Integer
{-# NOINLINE integerMod #-}
integerMod :: Integer -> Integer -> Integer
integerMod !Integer
n !Integer
d  -- Note [Bangs in Integer functions]
   -- same-sign ops can be handled by more efficient 'integerRem'
   | Bool# -> Bool
isTrue# (Integer -> Bool#
integerIsNegative# Integer
n Bool# -> Bool# -> Bool#
==# Integer -> Bool#
integerIsNegative# Integer
d) = Integer -> Integer -> Integer
integerRem Integer
n Integer
d
   | Bool
True = case Integer -> Integer -> (# Integer, Integer #)
integerDivMod# Integer
n Integer
d of (# Integer
_, Integer
r #) -> Integer
r

-- | Compute greatest common divisor.
integerGcd :: Integer -> Integer -> Integer
{-# NOINLINE integerGcd #-}
integerGcd :: Integer -> Integer -> Integer
integerGcd (IS Bool#
0#)  !Integer
b       = Integer -> Integer
integerAbs Integer
b
integerGcd Integer
a        (IS Bool#
0#)  = Integer -> Integer
integerAbs Integer
a
integerGcd (IS Bool#
1#)  Integer
_        = Bool# -> Integer
IS Bool#
1#
integerGcd (IS Bool#
-1#) Integer
_        = Bool# -> Integer
IS Bool#
1#
integerGcd Integer
_        (IS Bool#
1#)  = Bool# -> Integer
IS Bool#
1#
integerGcd Integer
_        (IS Bool#
-1#) = Bool# -> Integer
IS Bool#
1#
integerGcd (IS Bool#
a)   (IS Bool#
b)   = Word# -> Integer
integerFromWord# (Word# -> Word# -> Word#
gcdWord#
                                 (Bool# -> Word#
int2Word# (Bool# -> Bool#
absI# Bool#
a))
                                 (Bool# -> Word#
int2Word# (Bool# -> Bool#
absI# Bool#
b)))
integerGcd a :: Integer
a@(IS Bool#
_) Integer
b        = Integer -> Integer -> Integer
integerGcd Integer
b Integer
a
integerGcd (IN ByteArray#
a)   Integer
b        = Integer -> Integer -> Integer
integerGcd (ByteArray# -> Integer
IP ByteArray#
a) Integer
b
integerGcd (IP ByteArray#
a)   (IP ByteArray#
b)   = ByteArray# -> Integer
integerFromBigNat# (ByteArray# -> ByteArray# -> ByteArray#
bigNatGcd ByteArray#
a ByteArray#
b)
integerGcd (IP ByteArray#
a)   (IN ByteArray#
b)   = ByteArray# -> Integer
integerFromBigNat# (ByteArray# -> ByteArray# -> ByteArray#
bigNatGcd ByteArray#
a ByteArray#
b)
integerGcd (IP ByteArray#
a)   (IS Bool#
b)   = Word# -> Integer
integerFromWord# (ByteArray# -> Word# -> Word#
bigNatGcdWord# ByteArray#
a (Bool# -> Word#
int2Word# (Bool# -> Bool#
absI# Bool#
b)))

-- | Compute least common multiple.
integerLcm :: Integer -> Integer -> Integer
{-# NOINLINE integerLcm #-}
integerLcm :: Integer -> Integer -> Integer
integerLcm (IS Bool#
0#) !Integer
_  = Bool# -> Integer
IS Bool#
0#
integerLcm (IS Bool#
1#)  Integer
b  = Integer -> Integer
integerAbs Integer
b
integerLcm (IS Bool#
-1#) Integer
b  = Integer -> Integer
integerAbs Integer
b
integerLcm Integer
_ (IS Bool#
0#)   = Bool# -> Integer
IS Bool#
0#
integerLcm Integer
a (IS Bool#
1#)   = Integer -> Integer
integerAbs Integer
a
integerLcm Integer
a (IS Bool#
-1#)  = Integer -> Integer
integerAbs Integer
a
integerLcm Integer
a Integer
b         = (Integer
aa Integer -> Integer -> Integer
`integerQuot` (Integer
aa Integer -> Integer -> Integer
`integerGcd` Integer
ab)) Integer -> Integer -> Integer
`integerMul` Integer
ab
  where                   -- TODO: use extended GCD to get a's factor directly
    aa :: Integer
aa = Integer -> Integer
integerAbs Integer
a
    ab :: Integer
ab = Integer -> Integer
integerAbs Integer
b

-- | Square a Integer
integerSqr :: Integer -> Integer
integerSqr :: Integer -> Integer
integerSqr !Integer
a = Integer -> Integer -> Integer
integerMul Integer
a Integer
a


-- | Base 2 logarithm (floor)
--
-- For numbers <= 0, return 0
integerLog2# :: Integer -> Word#
integerLog2# :: Integer -> Word#
integerLog2# (IS Bool#
i)
   | Bool# -> Bool
isTrue# (Bool#
i Bool# -> Bool# -> Bool#
<=# Bool#
0#) = Word#
0##
   | Bool
True               = Word# -> Word#
wordLog2# (Bool# -> Word#
int2Word# Bool#
i)
integerLog2# (IN ByteArray#
_)     = Word#
0##
integerLog2# (IP ByteArray#
b)     = ByteArray# -> Word#
bigNatLog2# ByteArray#
b

-- | Base 2 logarithm (floor)
--
-- For numbers <= 0, return 0
integerLog2 :: Integer -> Word
integerLog2 :: Integer -> Word
integerLog2 !Integer
i = Word# -> Word
W# (Integer -> Word#
integerLog2# Integer
i)

-- | Logarithm (floor) for an arbitrary base
--
-- For numbers <= 0, return 0
integerLogBaseWord# :: Word# -> Integer -> Word#
integerLogBaseWord# :: Word# -> Integer -> Word#
integerLogBaseWord# Word#
base !Integer
i
   | Integer -> Bool
integerIsNegative Integer
i = Word#
0##
   | Bool
True                = Word# -> Natural -> Word#
naturalLogBaseWord# Word#
base (Integer -> Natural
integerToNatural Integer
i)

-- | Logarithm (floor) for an arbitrary base
--
-- For numbers <= 0, return 0
integerLogBaseWord :: Word -> Integer -> Word
integerLogBaseWord :: Word -> Integer -> Word
integerLogBaseWord (W# Word#
base) !Integer
i = Word# -> Word
W# (Word# -> Integer -> Word#
integerLogBaseWord# Word#
base Integer
i)

-- | Logarithm (floor) for an arbitrary base
--
-- For numbers <= 0, return 0
integerLogBase# :: Integer -> Integer -> Word#
integerLogBase# :: Integer -> Integer -> Word#
integerLogBase# !Integer
base !Integer
i
   | Integer -> Bool
integerIsNegative Integer
i = Word#
0##
   | Bool
True                = Natural -> Natural -> Word#
naturalLogBase# (Integer -> Natural
integerToNatural Integer
base)
                                           (Integer -> Natural
integerToNatural Integer
i)

-- | Logarithm (floor) for an arbitrary base
--
-- For numbers <= 0, return 0
integerLogBase :: Integer -> Integer -> Word
integerLogBase :: Integer -> Integer -> Word
integerLogBase !Integer
base !Integer
i = Word# -> Word
W# (Integer -> Integer -> Word#
integerLogBase# Integer
base Integer
i)

-- | Indicate if the value is a power of two and which one
integerIsPowerOf2# :: Integer -> (# (# #) | Word# #)
integerIsPowerOf2# :: Integer -> (# (# #) | Word# #)
integerIsPowerOf2# (IS Bool#
i)
   | Bool# -> Bool
isTrue# (Bool#
i Bool# -> Bool# -> Bool#
<=# Bool#
0#) = (# (# #) | #)
   | Bool
True               = Word# -> (# (# #) | Word# #)
wordIsPowerOf2# (Bool# -> Word#
int2Word# Bool#
i)
integerIsPowerOf2# (IN ByteArray#
_) = (# (# #) | #)
integerIsPowerOf2# (IP ByteArray#
w) = ByteArray# -> (# (# #) | Word# #)
bigNatIsPowerOf2# ByteArray#
w

-- | Convert an Int64# into an Integer
integerFromInt64# :: Int64# -> Integer
{-# NOINLINE integerFromInt64# #-}
integerFromInt64# :: Int64# -> Integer
integerFromInt64# Int64#
i
  | Bool# -> Bool
isTrue# ((Int64#
i Int64# -> Int64# -> Bool#
`leInt64#` Bool# -> Int64#
intToInt64#  INT_MAXBOUND#)
      Bool# -> Bool# -> Bool#
&&# (Int64#
i Int64# -> Int64# -> Bool#
`geInt64#` Bool# -> Int64#
intToInt64# INT_MINBOUND#))
  = Bool# -> Integer
IS (Int64# -> Bool#
int64ToInt# Int64#
i)

  | Bool# -> Bool
isTrue# (Int64#
i Int64# -> Int64# -> Bool#
`geInt64#` Bool# -> Int64#
intToInt64# Bool#
0#)
  = ByteArray# -> Integer
IP (Word64# -> ByteArray#
bigNatFromWord64# (Int64# -> Word64#
int64ToWord64# Int64#
i))

  | Bool
True
  = ByteArray# -> Integer
IN (Word64# -> ByteArray#
bigNatFromWord64# (Int64# -> Word64#
int64ToWord64# (Int64# -> Int64#
negateInt64# Int64#
i)))

-- | Convert a Word64# into an Integer
integerFromWord64# :: Word64# -> Integer
{-# NOINLINE integerFromWord64# #-}
integerFromWord64# :: Word64# -> Integer
integerFromWord64# !Word64#
w
  | Bool# -> Bool
isTrue# (Word64#
w Word64# -> Word64# -> Bool#
`leWord64#` Word# -> Word64#
wordToWord64# INT_MAXBOUND##)
  = Bool# -> Integer
IS (Int64# -> Bool#
int64ToInt# (Word64# -> Int64#
word64ToInt64# Word64#
w))
  | Bool
True
  = ByteArray# -> Integer
IP (Word64# -> ByteArray#
bigNatFromWord64# Word64#
w)

-- | Convert an Integer into an Int64#
integerToInt64# :: Integer -> Int64#
{-# NOINLINE integerToInt64# #-}
integerToInt64# :: Integer -> Int64#
integerToInt64# (IS Bool#
i) = Bool# -> Int64#
intToInt64# Bool#
i
integerToInt64# (IP ByteArray#
b) = Word64# -> Int64#
word64ToInt64# (ByteArray# -> Word64#
bigNatToWord64# ByteArray#
b)
integerToInt64# (IN ByteArray#
b) = Int64# -> Int64#
negateInt64# (Word64# -> Int64#
word64ToInt64# (ByteArray# -> Word64#
bigNatToWord64# ByteArray#
b))

-- | Convert an Integer into a Word64#
integerToWord64# :: Integer -> Word64#
{-# NOINLINE integerToWord64# #-}
integerToWord64# :: Integer -> Word64#
integerToWord64# (IS Bool#
i) = Int64# -> Word64#
int64ToWord64# (Bool# -> Int64#
intToInt64# Bool#
i)
integerToWord64# (IP ByteArray#
b) = ByteArray# -> Word64#
bigNatToWord64# ByteArray#
b
integerToWord64# (IN ByteArray#
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# #)
{-# INLINE integerDecodeDouble# #-} -- decodeDouble_Int64# is constant-folded
                                    -- in GHC.Core.Opt.ConstantFold
integerDecodeDouble# :: Double# -> (# Integer, Bool# #)
integerDecodeDouble# !Double#
x = case Double# -> (# Int64#, Bool# #)
decodeDouble_Int64# Double#
x of
                            (# Int64#
m, Bool#
e #) -> (# Int64# -> Integer
integerFromInt64# Int64#
m, Bool#
e #)

-- | Encode (# Integer mantissa, Int# exponent #) into a Double#
integerEncodeDouble# :: Integer -> Int# -> Double#
{-# NOINLINE integerEncodeDouble# #-}
integerEncodeDouble# :: Integer -> Bool# -> Double#
integerEncodeDouble# (IS Bool#
i) Bool#
0# = Bool# -> Double#
int2Double# Bool#
i
integerEncodeDouble# (IS Bool#
i) Bool#
e  = Bool# -> Bool# -> Double#
intEncodeDouble# Bool#
i Bool#
e
integerEncodeDouble# (IP ByteArray#
b) Bool#
e  = ByteArray# -> Bool# -> Double#
bigNatEncodeDouble# ByteArray#
b Bool#
e
integerEncodeDouble# (IN ByteArray#
b) Bool#
e  = Double# -> Double#
negateDouble# (ByteArray# -> Bool# -> Double#
bigNatEncodeDouble# ByteArray#
b Bool#
e)

-- | Encode (Integer mantissa, Int exponent) into a Double
integerEncodeDouble :: Integer -> Int -> Double
integerEncodeDouble :: Integer -> Int -> Double
integerEncodeDouble !Integer
m (I# Bool#
e)  = Double# -> Double
D# (Integer -> Bool# -> Double#
integerEncodeDouble# Integer
m Bool#
e)

-- | Encode (# Integer mantissa, Int# exponent #) into a Float#
--
-- TODO: Not sure if it's worth to write 'Float' optimized versions here
integerEncodeFloat# :: Integer -> Int# -> Float#
{-# NOINLINE integerEncodeFloat# #-}
integerEncodeFloat# :: Integer -> Bool# -> Float#
integerEncodeFloat# !Integer
m Bool#
e  = Double# -> Float#
double2Float# (Integer -> Bool# -> Double#
integerEncodeDouble# Integer
m Bool#
e)

-- | Compute the number of digits of the Integer (without the sign) in the given base.
--
-- `base` must be > 1
integerSizeInBase# :: Word# -> Integer -> Word#
integerSizeInBase# :: Word# -> Integer -> Word#
integerSizeInBase# Word#
base (IS Bool#
i) = Word# -> Word# -> Word#
wordSizeInBase# Word#
base (Bool# -> Word#
int2Word# (Bool# -> Bool#
absI# Bool#
i))
integerSizeInBase# Word#
base (IP ByteArray#
n) = Word# -> ByteArray# -> Word#
bigNatSizeInBase# Word#
base ByteArray#
n
integerSizeInBase# Word#
base (IN ByteArray#
n) = Word# -> ByteArray# -> Word#
bigNatSizeInBase# Word#
base 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# -> State# s -> (# State# s, Word# #)
integerToAddr# :: forall s.
Integer -> Addr# -> Bool# -> State# s -> (# State# s, Word# #)
integerToAddr# (IS Bool#
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# (IP ByteArray#
n) = ByteArray# -> Addr# -> Bool# -> State# s -> (# State# s, Word# #)
forall s.
ByteArray# -> Addr# -> Bool# -> State# s -> (# State# s, Word# #)
bigNatToAddr# ByteArray#
n
integerToAddr# (IN ByteArray#
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# -> IO Word
integerToAddr :: Integer -> Addr# -> Bool# -> IO Word
integerToAddr Integer
a Addr#
addr Bool#
e = (State# RealWorld -> (# State# RealWorld, Word #)) -> IO Word
forall a. (State# RealWorld -> (# State# RealWorld, a #)) -> IO a
IO \State# RealWorld
s -> case Integer
-> Addr#
-> Bool#
-> State# RealWorld
-> (# State# RealWorld, Word# #)
forall s.
Integer -> Addr# -> Bool# -> State# s -> (# State# s, Word# #)
integerToAddr# Integer
a Addr#
addr Bool#
e State# RealWorld
s of
   (# State# RealWorld
s', Word#
w #) -> (# State# RealWorld
s', Word# -> Word
W# 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#
sz Addr#
addr Bool#
e State# s
s =
   case Word# -> Addr# -> Bool# -> State# s -> (# State# s, ByteArray# #)
forall s.
Word# -> Addr# -> Bool# -> State# s -> (# State# s, ByteArray# #)
bigNatFromAddr# Word#
sz Addr#
addr Bool#
e State# s
s of
      (# State# s
s', ByteArray#
n #) -> (# State# s
s', ByteArray# -> Integer
integerFromBigNat# 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# -> IO Integer
integerFromAddr :: Word# -> Addr# -> Bool# -> IO Integer
integerFromAddr Word#
sz Addr#
addr Bool#
e = (State# RealWorld -> (# State# RealWorld, Integer #)) -> IO Integer
forall a. (State# RealWorld -> (# State# RealWorld, a #)) -> IO a
IO (Word#
-> Addr#
-> Bool#
-> State# RealWorld
-> (# State# RealWorld, Integer #)
forall s.
Word# -> Addr# -> Bool# -> State# s -> (# State# s, Integer #)
integerFromAddr# Word#
sz Addr#
addr Bool#
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# (IS Bool#
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# (IP ByteArray#
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
integerToMutableByteArray# (IN ByteArray#
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# -> IO Word
integerToMutableByteArray :: Integer -> MutableByteArray# RealWorld -> Word# -> Bool# -> IO Word
integerToMutableByteArray Integer
i MutableByteArray# RealWorld
mba Word#
w Bool#
e = (State# RealWorld -> (# State# RealWorld, Word #)) -> IO Word
forall a. (State# RealWorld -> (# State# RealWorld, a #)) -> IO a
IO \State# RealWorld
s -> case Integer
-> MutableByteArray# RealWorld
-> Word#
-> Bool#
-> State# RealWorld
-> (# State# RealWorld, Word# #)
forall s.
Integer
-> MutableByteArray# s
-> Word#
-> Bool#
-> State# s
-> (# State# s, Word# #)
integerToMutableByteArray# Integer
i MutableByteArray# RealWorld
mba Word#
w Bool#
e State# RealWorld
s of
   (# State# RealWorld
s', Word#
r #) -> (# State# RealWorld
s', Word# -> Word
W# 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#
sz ByteArray#
ba Word#
off Bool#
e State# s
s = case Word#
-> ByteArray#
-> Word#
-> Bool#
-> State# s
-> (# State# s, ByteArray# #)
forall s.
Word#
-> ByteArray#
-> Word#
-> Bool#
-> State# s
-> (# State# s, ByteArray# #)
bigNatFromByteArray# Word#
sz ByteArray#
ba Word#
off Bool#
e State# s
s of
   (# State# s
s', ByteArray#
a #) -> (# State# s
s', ByteArray# -> Integer
integerFromBigNat# 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# -> Integer
integerFromByteArray :: Word# -> ByteArray# -> Word# -> Bool# -> Integer
integerFromByteArray Word#
sz ByteArray#
ba Word#
off Bool#
e = case (State# RealWorld -> (# State# RealWorld, Integer #))
-> (# State# RealWorld, Integer #)
forall o. (State# RealWorld -> o) -> o
runRW# (Word#
-> ByteArray#
-> Word#
-> Bool#
-> State# RealWorld
-> (# State# RealWorld, Integer #)
forall s.
Word#
-> ByteArray#
-> Word#
-> Bool#
-> State# s
-> (# State# s, Integer #)
integerFromByteArray# Word#
sz ByteArray#
ba Word#
off Bool#
e) of
   (# State# RealWorld
_, Integer
i #) -> Integer
i


-- | 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# Integer
a Integer
b
   | Integer -> Bool
integerIsZero Integer
a Bool -> Bool -> Bool
&& Integer -> Bool
integerIsZero Integer
b    =     (# Integer
integerZero, Integer
integerZero, Integer
integerZero #)
   | Integer -> Bool
integerIsZero Integer
a                       = (# Integer, Integer, Integer #) -> (# Integer, Integer, Integer #)
fix (# Integer
b          , Integer
integerZero, Integer
integerOne #)
   | Integer -> Bool
integerIsZero Integer
b                       = (# Integer, Integer, Integer #) -> (# Integer, Integer, Integer #)
fix (# Integer
a          , Integer
integerOne,  Integer
integerZero #)
   | Integer -> Integer
integerAbs Integer
a Integer -> Integer -> Bool
`integerEq` Integer -> Integer
integerAbs Integer
b = (# Integer, Integer, Integer #) -> (# Integer, Integer, Integer #)
fix (# Integer
b          , Integer
integerZero, Integer
integerOne #)
   | Bool
True                                  = Integer -> Integer -> (# Integer, Integer, Integer #)
Backend.integer_gcde Integer
a Integer
b
   where
      -- returned "g" must be positive
      fix :: (# Integer, Integer, Integer #) -> (# Integer, Integer, Integer #)
fix (# Integer
g, Integer
x, Integer
y #)
         | Integer -> Bool
integerIsNegative Integer
g = (# Integer -> Integer
integerNegate Integer
g, Integer -> Integer
integerNegate Integer
x, Integer -> Integer
integerNegate Integer
y #)
         | Bool
True                = (# Integer
g,Integer
x,Integer
y #)

-- | 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 Integer
a Integer
b = case Integer -> Integer -> (# Integer, Integer, Integer #)
integerGcde# Integer
a Integer
b of
   (# Integer
g,Integer
x,Integer
y #) -> (Integer
g,Integer
x,Integer
y)


-- | Computes the modular inverse.
--
-- @integerRecipMod# x m@ behaves as follows:
--
--   * If m > 1 and gcd x m = 1, it returns an integer y with 0 < y < m such
--     that x*y is congruent to 1 modulo m.
--
--   * If m > 1 and gcd x m > 1, it fails.
--
--   * If m = 1, it returns @0@ for all x.  The computation effectively takes
--     place in the zero ring, which has a single element 0 with 0+0 = 0*0 = 0:
--     the element 0 is the multiplicative identity element and is its own
--     multiplicative inverse.
--
--   * If m = 0, it fails.
--
-- NB. Successful evaluation returns a value of the form @(# n | #)@; failure is
-- indicated by returning @(# | () #)@.
integerRecipMod#
   :: Integer
   -> Natural
   -> (# Natural | () #)
integerRecipMod# :: Integer -> Natural -> (# Natural | () #)
integerRecipMod# Integer
x Natural
m
   | Natural -> Bool
naturalIsZero Natural
m = (# | () #)
   | Natural -> Bool
naturalIsOne  Natural
m = (# Natural
naturalZero | #)
   | Integer -> Bool
integerIsZero Integer
x = (# | () #)
   | Bool
True            = Integer -> Natural -> (# Natural | () #)
Backend.integer_recip_mod Integer
x Natural
m


-- | Computes the modular exponentiation.
--
-- @integerPowMod# b e m@ behaves as follows:
--
--   * If m > 1 and e >= 0, it returns an integer y with 0 <= y < m
--     and y congruent to b^e modulo m.
--
--   * If m > 1 and e < 0, it uses `integerRecipMod#` to try to find a modular
--     multiplicative inverse b' (which only exists if gcd b m = 1) and then
--     caculates (b')^(-e) modulo m (note that -e > 0); if the inverse does not
--     exist then it fails.
--
--   * If m = 1, it returns @0@ for all b and e.
--
--   * If m = 0, it fails.
--
-- NB. Successful evaluation returns a value of the form @(# n | #)@; failure is
-- indicated by returning @(# | () #)@.

integerPowMod# :: Integer -> Integer -> Natural -> (# Natural | () #)
integerPowMod# :: Integer -> Integer -> Natural -> (# Natural | () #)
integerPowMod# !Integer
b !Integer
e !Natural
m
   | Natural -> Bool
naturalIsZero Natural
m  = (# | () #)
   | Natural -> Bool
naturalIsOne  Natural
m  = (# Natural
naturalZero | #)
   | Integer -> Bool
integerIsZero Integer
e  = (# Natural
naturalOne  | #)
   | Integer -> Bool
integerIsZero Integer
b
     Bool -> Bool -> Bool
&& Integer -> Integer -> Bool
integerGt Integer
e Integer
0 = (# Natural
naturalZero | #)
   | Integer -> Bool
integerIsOne  Integer
b  = (# Natural
naturalOne  | #)
     -- when the exponent is negative, try to find the modular multiplicative
     -- inverse and use it instead
   | Integer -> Bool
integerIsNegative Integer
e = case Integer -> Natural -> (# Natural | () #)
integerRecipMod# Integer
b Natural
m of
      (#    | () #) -> (# | () #)
      (# Natural
b' |    #) -> Integer -> Integer -> Natural -> (# Natural | () #)
integerPowMod#
                        (Natural -> Integer
integerFromNatural Natural
b')
                        (Integer -> Integer
integerNegate Integer
e)
                        Natural
m

     -- e > 0 by cases above
   | Bool
True = (# Integer -> Natural -> Natural -> Natural
Backend.integer_powmod Integer
b (Integer -> Natural
integerToNatural Integer
e) Natural
m | #)


{-
Note [Optimising conversions between numeric types]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Converting between numeric types is very common in Haskell codes.  Suppose that
we 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 that
would require N^2 functions: wordToWord8, wordToInt, word8ToWord32...

- The following kind of class would allow us to have a single conversion
function but at the price of N^2 instances and of the use of
MultiParamTypeClasses extension.

    class Convert a b where
      convert :: a -> b

So what we do instead is that we use the Integer type (signed, unbounded) as a
passthrough type to perform every conversion. Hence we only need to define two
functions per numeric type:

  class Integral a where
    toInteger :: a -> Integer

  class Num a where
    fromInteger :: Integer -> a

These classes have a single parameter and can be derived automatically (e.g. for
newtypes). So we don't even have to define 2*N instances. For example, all the
instances 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 . toInteger

Efficient 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, becomes
costly when performed via `fromIntegral` or any similar function because an
intermediate Integer has to be allocated in the heap to perform the conversion.

A solution is to bless one particular `fromIntegral`-like function and to use
rewrite rules to replace it with a more efficient function when both types are
known. This is what was done in the past, see next section. We use another
approach nowadays:

Notice that the set of primitive operations to convert from and to Integer and
Natural 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 concrete
types that can be converted from and to Natural/Integer. All the other ones
necessarily pass through these concrete types!

For example we have the following rules:
    integerToWord# (integerFromWord# x) ===> x
    integerToInt# (integerFromWord# x)  ===> word2Int# x

But we don't need rules to handle conversion from/to e.g. Word32# because there
is no Word32#-to-Integer primitive: Word32# must be converted into something
else 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 many
rewrite rules were mentioning it explicitly. For example to replace a call to
`fromIntegral :: Int -> Word`, which allocates an intermediate Integer, with a
call 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 would
need N^2 pragmas to cover every case and it wouldn't cover user defined numeric
types which don't belong to base.

- `-fwarn-identities` enables a warning to detect useless conversions via
fromIntegral (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 transformations
explicitly (to allow more fromIntegral rules to fire) and to replace some
fromIntegral 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 and
to only rely on rewrite rules for bignum functions.

-}

-- See Note [Optimising conversions between numeric types]
{-# RULES
"Word# -> Natural -> Integer"
  forall x. integerFromNatural (NS x) = integerFromWord# x

"BigNat# -> Natural -> Integer"
  forall x. integerFromNatural (NB x) = IP x

"Int# -> Integer -> Int#"
  forall x. integerToInt# (IS x) = x

"Word# -> Integer -> Word#"
  forall x. integerToWord# (integerFromWord# x) = x

"Natural -> Integer -> Natural (wrap)"
  forall x. integerToNatural (integerFromNatural x) = x

"Natural -> Integer -> Natural (throw)"
  forall x. integerToNaturalThrow (integerFromNatural x) = x

"Natural -> Integer -> Natural (clamp)"
  forall x. integerToNaturalClamp (integerFromNatural x) = x

"Natural -> Integer -> Word#"
  forall x. integerToWord# (integerFromNatural x) = naturalToWord# x

"Int# -> Integer -> Word#"
  forall x. integerToWord# (IS x) = int2Word# x

"Word# -> Integer -> Int#"
  forall x. integerToInt# (integerFromWord# x) = word2Int# x

"Word# -> Integer -> Natural (wrap)"
  forall x. integerToNatural (integerFromWord# x) = NS x

"Word# -> Integer -> Natural (throw)"
  forall x. integerToNaturalThrow (integerFromWord# x) = NS x

"Word# -> Integer -> Natural (clamp)"
  forall x. integerToNaturalClamp (integerFromWord# x) = NS x

#-}

{-# RULES

"Int64# -> Integer -> Int64#"
  forall x. integerToInt64# (integerFromInt64# x) = x

"Word64# -> Integer -> Word64#"
  forall x. integerToWord64# (integerFromWord64# x) = x

"Int64# -> Integer -> Word64#"
  forall x. integerToWord64# (integerFromInt64# x) = int64ToWord64# x

"Word64# -> Integer -> Int64#"
  forall x. integerToInt64# (integerFromWord64# x) = word64ToInt64# x

"Word# -> Integer -> Word64#"
  forall x. integerToWord64# (integerFromWord# x) = wordToWord64# x

"Word64# -> Integer -> Word#"
  forall x. integerToWord# (integerFromWord64# x) = word64ToWord# x

"Int# -> Integer -> Int64#"
  forall x. integerToInt64# (IS x) = intToInt64# x

"Int64# -> Integer -> Int#"
  forall x. integerToInt# (integerFromInt64# x) = int64ToInt# x

"Int# -> Integer -> Word64#"
  forall x. integerToWord64# (IS x) = int64ToWord64# (intToInt64# x)

"Int64# -> Integer -> Word#"
  forall x. integerToWord# (integerFromInt64# x) = int2Word# (int64ToInt# x)

"Word# -> Integer -> Int64#"
  forall x. integerToInt64# (integerFromWord# x) = word64ToInt64# (wordToWord64# x)

"Word64# -> Integer -> Int#"
  forall x. integerToInt# (integerFromWord64# x) = word2Int# (word64ToWord# x)

#-}