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

-- |
-- Module      :  GHC.Num.Integer
-- Copyright   :  (c) Sylvain Henry 2019,
--                (c) Herbert Valerio Riedel 2014
-- License     :  BSD3
--
-- Maintainer  :  sylvain@haskus.fr
-- Stability   :  provisional
-- Portability :  non-portable (GHC Extensions)
--
-- The 'Integer' type.

module GHC.Num.Integer where

#include "MachDeps.h"
#include "WordSize.h"

import GHC.Prim
import GHC.Types
import GHC.Classes
import GHC.Magic
import GHC.Num.Primitives
import GHC.Num.BigNat
import GHC.Num.Natural
import qualified GHC.Num.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 (fit into an 'Int'), 'IS' constructor is used.
-- Otherwise 'IP' and 'IN' constructors are used to store a 'BigNat'
-- representing respectively the positive or the negative value magnitude.
--
-- Invariant: 'IP' and 'IN' are used iff value doesn't 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
integerFromBigNat# 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#) = 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#
_) = forall a. a
raiseUnderflow

---------------------------------------------------------------------
-- Predicates
---------------------------------------------------------------------

-- | 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)

-- | 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)

-- | 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)

-- | 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)

-- | 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)

-- | 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)

-- | 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)

-- | Equal predicate.
integerEq# :: Integer -> Integer -> Bool#
{-# NOINLINE integerEq# #-}
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#
{-# NOINLINE integerNe# #-}
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#
{-# NOINLINE integerGt# #-}
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#
{-# NOINLINE integerLe# #-}
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#
{-# NOINLINE integerLt# #-}
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#
{-# NOINLINE integerGe# #-}
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
{-# NOINLINE integerCompare #-}
integerCompare :: Integer -> Integer -> Ordering
integerCompare = Integer -> Integer -> Ordering
integerCompare'

integerCompare' :: Integer -> Integer -> Ordering
{-# INLINE 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
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#
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
#if __GLASGOW_HASKELL__ < 811
integerMul (IS x)   (IS y)   = case mulIntMayOflo# x y of
   0# -> IS (x *# y)
   _  -> case (# isTrue# (x >=# 0#), isTrue# (y >=# 0#) #) of
      (# False, False #) -> case timesWord2# (int2Word# (negateInt# x))
                                       (int2Word# (negateInt# y)) of
          (# 0##,l #) -> integerFromWord# l
          (# h  ,l #) -> IP (bigNatFromWord2# h l)

      (#  True, False #) -> case timesWord2# (int2Word# x)
                                       (int2Word# (negateInt# y)) of
          (# 0##,l #) -> integerFromWordNeg# l
          (# h  ,l #) -> IN (bigNatFromWord2# h l)

      (# False,  True #) -> case timesWord2# (int2Word# (negateInt# x))
                                       (int2Word# y) of
          (# 0##,l #) -> integerFromWordNeg# l
          (# h  ,l #) -> IN (bigNatFromWord2# h l)

      (#  True,  True #) -> case timesWord2# (int2Word# x)
                                       (int2Word# y) of
          (# 0##,l #) -> integerFromWord# l
          (# h  ,l #) -> IP (bigNatFromWord2# h l)
#else
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')
#endif
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
{-# NOINLINE integerSignum #-}
integerSignum :: Integer -> Integer
integerSignum !Integer
j = Bool# -> Integer
IS (Integer -> Bool#
integerSignum# Integer
j)

-- | Return @-1#@, @0#@, and @1#@ depending on whether argument is
-- negative, zero, or positive, respectively
integerSignum# :: Integer -> Int#
{-# NOINLINE integerSignum# #-}
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
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

-- | Shift-left operation
integerShiftL# :: Integer -> Word# -> Integer
{-# NOINLINE integerShiftL# #-}
integerShiftL# :: Integer -> Word# -> Integer
integerShiftL# !Integer
x      Word#
0## = Integer
x
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

-- | 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
integerFromBigNat# (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
integerFromBigNat# (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# #)
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 forall a. a
raiseDivZero of
                                    !Any
_ -> (# Bool# -> Integer
IS Bool#
0#, Bool# -> Integer
IS Bool#
0# #)
                                    -- see Note [ghc-bignum exceptions] in GHC.Num.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
   (# 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
integerQuot !Integer
n      (IS Bool#
-1#) = Integer -> Integer
integerNegate Integer
n
integerQuot !Integer
_      (IS Bool#
0#)  = 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#
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
  | 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
   (# Integer
q,Integer
r #) -> (Integer
q,Integer
r)


integerDiv :: Integer -> Integer -> Integer
{-# NOINLINE integerDiv #-}
integerDiv :: Integer -> Integer -> Integer
integerDiv !Integer
n !Integer
d
   -- 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
   -- 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

#if WORD_SIZE_IN_BITS == 32

-- | Convert an Int64# into an Integer on 32-bit architectures
integerFromInt64# :: Int64# -> Integer
{-# NOINLINE integerFromInt64# #-}
integerFromInt64# !i
  | isTrue# ((i `leInt64#` intToInt64#  0x7FFFFFFF#)
      &&# (i `geInt64#` intToInt64# -0x80000000#))
  = IS (int64ToInt# i)

  | isTrue# (i `geInt64#` intToInt64# 0#)
  = IP (bigNatFromWord64# (int64ToWord64# i))

  | True
  = IN (bigNatFromWord64# (int64ToWord64# (negateInt64# i)))

-- | Convert a Word64# into an Integer on 32-bit architectures
integerFromWord64# :: Word64# -> Integer
{-# NOINLINE integerFromWord64# #-}
integerFromWord64# !w
  | isTrue# (w `leWord64#` wordToWord64# 0x7FFFFFFF##)
  = IS (int64ToInt# (word64ToInt64# w))
  | True
  = IP (bigNatFromWord64# w)

-- | Convert an Integer into an Int64# on 32-bit architectures
integerToInt64# :: Integer -> Int64#
{-# NOINLINE integerToInt64# #-}
integerToInt64# (IS i) = intToInt64# i
integerToInt64# (IP b) = word64ToInt64# (bigNatToWord64# b)
integerToInt64# (IN b) = negateInt64# (word64ToInt64# (bigNatToWord64# b))

-- | Convert an Integer into a Word64# on 32-bit architectures
integerToWord64# :: Integer -> Word64#
{-# NOINLINE integerToWord64# #-}
integerToWord64# (IS i) = int64ToWord64# (intToInt64# i)
integerToWord64# (IP b) = bigNatToWord64# b
integerToWord64# (IN b) = int64ToWord64# (negateInt64# (word64ToInt64# (bigNatToWord64# b)))

#else

-- | Convert an Int64# into an Integer on 64-bit architectures
integerFromInt64# :: Int# -> Integer
integerFromInt64# :: Bool# -> Integer
integerFromInt64# !Bool#
x = Bool# -> Integer
IS Bool#
x

#endif

----------------------------------------------------------------------------
-- 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# -> (# Bool#, Bool# #)
decodeDouble_Int64# Double#
x of
                            (# Bool#
m, Bool#
e #) -> (# Bool# -> Integer
integerFromInt64# Bool#
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) = forall s.
Word# -> Addr# -> Bool# -> State# s -> (# State# s, Word# #)
wordToAddr# (Bool# -> Word#
int2Word# (Bool# -> Bool#
absI# Bool#
i))
integerToAddr# (IP ByteArray#
n) = forall s.
ByteArray# -> Addr# -> Bool# -> State# s -> (# State# s, Word# #)
bigNatToAddr# ByteArray#
n
integerToAddr# (IN ByteArray#
n) = 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 = forall a. (State# RealWorld -> (# State# RealWorld, a #)) -> IO a
IO \State# RealWorld
s -> case 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 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 = forall a. (State# RealWorld -> (# State# RealWorld, a #)) -> IO a
IO (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) = 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) = forall s.
ByteArray#
-> MutableByteArray# s
-> Word#
-> Bool#
-> State# s
-> (# State# s, Word# #)
bigNatToMutableByteArray# ByteArray#
a
integerToMutableByteArray# (IN ByteArray#
a) = 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 = forall a. (State# RealWorld -> (# State# RealWorld, a #)) -> IO a
IO \State# RealWorld
s -> case 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 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 forall o. (State# RealWorld -> o) -> o
runRW# (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.
--
-- I.e. y = integerRecipMod# x m
--        = x^(-1) `mod` m
--
-- with 0 < y < |m|
--
integerRecipMod#
   :: Integer
   -> Natural
   -> (# Natural | () #)
integerRecipMod# :: Integer -> Natural -> (# Natural | () #)
integerRecipMod# Integer
x Natural
m
   | Integer -> Bool
integerIsZero Integer
x = (# | () #)
   | Natural -> Bool
naturalIsZero Natural
m = (# | () #)
   | Natural -> Bool
naturalIsOne  Natural
m = (# | () #)
   | Bool
True            = Integer -> Natural -> (# Natural | () #)
Backend.integer_recip_mod Integer
x Natural
m


-- | Computes the modular exponentiation.
--
-- I.e. y = integer_powmod b e m
--        = b^e `mod` m
--
-- with 0 <= y < abs m
--
-- If e is negative, we use `integerRecipMod#` to try to find a modular
-- multiplicative inverse (which may not exist).
integerPowMod# :: Integer -> Integer -> Natural -> (# Natural | () #)
integerPowMod# :: Integer -> Integer -> Natural -> (# Natural | () #)
integerPowMod# !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     = (# 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 | #)