{-# LANGUAGE CPP #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE NoImplicitPrelude #-}
{-# LANGUAGE UnboxedTuples #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE BlockArguments #-}

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

module GHC.Num.Natural where

import GHC.Prim
import GHC.Types
import GHC.Classes

import GHC.Num.BigNat
import GHC.Num.Primitives

default ()

-- | Natural number
--
-- Invariant: numbers <= WORD_MAXBOUND use the `NS` constructor
data Natural
   = NS !Word#
   | NB !BigNat#

instance Eq Natural where
   == :: Natural -> Natural -> Bool
(==) = Natural -> Natural -> Bool
naturalEq
   /= :: Natural -> Natural -> Bool
(/=) = Natural -> Natural -> Bool
naturalNe

instance Ord Natural where
   compare :: Natural -> Natural -> Ordering
compare = Natural -> Natural -> Ordering
naturalCompare
   > :: Natural -> Natural -> Bool
(>)     = Natural -> Natural -> Bool
naturalGt
   >= :: Natural -> Natural -> Bool
(>=)    = Natural -> Natural -> Bool
naturalGe
   < :: Natural -> Natural -> Bool
(<)     = Natural -> Natural -> Bool
naturalLt
   <= :: Natural -> Natural -> Bool
(<=)    = Natural -> Natural -> Bool
naturalLe


-- | Check Natural invariants
naturalCheck# :: Natural -> Bool#
naturalCheck# :: Natural -> Bool#
naturalCheck# (NS Word#
_)  = Bool#
1#
naturalCheck# (NB ByteArray#
bn) = ByteArray# -> Bool#
bigNatCheck# ByteArray#
bn Bool# -> Bool# -> Bool#
&&# ByteArray# -> Bool#
bigNatSize# ByteArray#
bn Bool# -> Bool# -> Bool#
># Bool#
1#

-- | Check Natural invariants
naturalCheck :: Natural -> Bool
naturalCheck :: Natural -> Bool
naturalCheck !Natural
n = Bool# -> Bool
isTrue# (Natural -> Bool#
naturalCheck# Natural
n)

-- | Zero Natural
naturalZero :: Natural
naturalZero :: Natural
naturalZero = Word# -> Natural
NS Word#
0##

-- | One Natural
naturalOne :: Natural
naturalOne :: Natural
naturalOne = Word# -> Natural
NS Word#
1##

-- | Test Zero Natural
naturalIsZero :: Natural -> Bool
naturalIsZero :: Natural -> Bool
naturalIsZero (NS Word#
0##) = Bool
True
naturalIsZero Natural
_        = Bool
False

-- | Test One Natural
naturalIsOne :: Natural -> Bool
naturalIsOne :: Natural -> Bool
naturalIsOne (NS Word#
1##) = Bool
True
naturalIsOne Natural
_        = Bool
False

-- | Indicate if the value is a power of two and which one
naturalIsPowerOf2# :: Natural -> (# (# #) | Word# #)
naturalIsPowerOf2# :: Natural -> (# (# #) | Word# #)
naturalIsPowerOf2# (NS Word#
w) = Word# -> (# (# #) | Word# #)
wordIsPowerOf2# Word#
w
naturalIsPowerOf2# (NB ByteArray#
w) = ByteArray# -> (# (# #) | Word# #)
bigNatIsPowerOf2# ByteArray#
w

-- | Create a Natural from a BigNat# (respect the invariants)
naturalFromBigNat# :: BigNat# -> Natural
naturalFromBigNat# :: ByteArray# -> Natural
naturalFromBigNat# ByteArray#
x = case ByteArray# -> Bool#
bigNatSize# ByteArray#
x of
   Bool#
0# -> Natural
naturalZero
   Bool#
1# -> Word# -> Natural
NS (ByteArray# -> Bool# -> Word#
bigNatIndex# ByteArray#
x Bool#
0#)
   Bool#
_  -> ByteArray# -> Natural
NB ByteArray#
x

-- | Convert a Natural into a BigNat#
naturalToBigNat# :: Natural -> BigNat#
naturalToBigNat# :: Natural -> ByteArray#
naturalToBigNat# (NS Word#
w)  = Word# -> ByteArray#
bigNatFromWord# Word#
w
naturalToBigNat# (NB ByteArray#
bn) = ByteArray#
bn

-- | Create a Natural from a Word#
naturalFromWord# :: Word# -> Natural
naturalFromWord# :: Word# -> Natural
naturalFromWord# Word#
x = Word# -> Natural
NS Word#
x

-- | Convert two Word# (most-significant first) into a Natural
naturalFromWord2# :: Word# -> Word# -> Natural
naturalFromWord2# :: Word# -> Word# -> Natural
naturalFromWord2# Word#
0## Word#
0## = Natural
naturalZero
naturalFromWord2# Word#
0## Word#
l   = Word# -> Natural
NS Word#
l
naturalFromWord2# Word#
h   Word#
l   = ByteArray# -> Natural
NB (Word# -> Word# -> ByteArray#
bigNatFromWord2# Word#
h Word#
l)

-- | Create a Natural from a Word
naturalFromWord :: Word -> Natural
naturalFromWord :: Word -> Natural
naturalFromWord (W# Word#
x) = Word# -> Natural
NS Word#
x

-- | Create a Natural from a list of Word
naturalFromWordList :: [Word] -> Natural
naturalFromWordList :: [Word] -> Natural
naturalFromWordList [Word]
xs = ByteArray# -> Natural
naturalFromBigNat# ([Word] -> ByteArray#
bigNatFromWordList [Word]
xs)

-- | Convert the lower bits of a Natural into a Word#
naturalToWord# :: Natural -> Word#
{-# NOINLINE naturalToWord# #-}
naturalToWord# :: Natural -> Word#
naturalToWord# (NS Word#
x) = Word#
x
naturalToWord# (NB ByteArray#
b) = ByteArray# -> Bool# -> Word#
bigNatIndex# ByteArray#
b Bool#
0#

-- | Convert the lower bits of a Natural into a Word
naturalToWord :: Natural -> Word
naturalToWord :: Natural -> Word
naturalToWord !Natural
n = Word# -> Word
W# (Natural -> Word#
naturalToWord# Natural
n)

-- | Convert a Natural into a Word# clamping to (maxBound :: Word#).
naturalToWordClamp# :: Natural -> Word#
{-# NOINLINE naturalToWordClamp #-}
naturalToWordClamp# :: Natural -> Word#
naturalToWordClamp# (NS Word#
x) = Word#
x
naturalToWordClamp# (NB ByteArray#
_) = WORD_MAXBOUND##

-- | Convert a Natural into a Word# clamping to (maxBound :: Word).
naturalToWordClamp :: Natural -> Word
naturalToWordClamp :: Natural -> Word
naturalToWordClamp !Natural
n = Word# -> Word
W# (Natural -> Word#
naturalToWordClamp# Natural
n)

-- | Try downcasting 'Natural' to 'Word' value.
-- Returns '(##)' if value doesn't fit in 'Word'.
naturalToWordMaybe# :: Natural -> (# (# #) | Word# #)
naturalToWordMaybe# :: Natural -> (# (# #) | Word# #)
naturalToWordMaybe# (NS Word#
w) = (#       | Word#
w #)
naturalToWordMaybe# Natural
_      = (# (# #) |   #)

-- | Encode (# Natural mantissa, Int# exponent #) into a Double#
naturalEncodeDouble# :: Natural -> Int# -> Double#
naturalEncodeDouble# :: Natural -> Bool# -> Double#
naturalEncodeDouble# (NS Word#
w) Bool#
0# = Word# -> Double#
word2Double# Word#
w
naturalEncodeDouble# (NS Word#
w) Bool#
e  = Word# -> Bool# -> Double#
wordEncodeDouble# Word#
w Bool#
e
naturalEncodeDouble# (NB ByteArray#
b) Bool#
e  = ByteArray# -> Bool# -> Double#
bigNatEncodeDouble# ByteArray#
b Bool#
e

-- | Encode (# Natural mantissa, Int# exponent #) into a Float#
--
-- TODO: Not sure if it's worth to write 'Float' optimized versions here
naturalEncodeFloat# :: Natural -> Int# -> Float#
naturalEncodeFloat# :: Natural -> Bool# -> Float#
naturalEncodeFloat# !Natural
m Bool#
e  = Double# -> Float#
double2Float# (Natural -> Bool# -> Double#
naturalEncodeDouble# Natural
m Bool#
e)

-- | Equality test for Natural
naturalEq# :: Natural -> Natural -> Bool#
{-# NOINLINE naturalEq# #-}
naturalEq# :: Natural -> Natural -> Bool#
naturalEq# (NS Word#
x) (NS Word#
y) = Word#
x Word# -> Word# -> Bool#
`eqWord#` Word#
y
naturalEq# (NB ByteArray#
x) (NB ByteArray#
y) = ByteArray# -> ByteArray# -> Bool#
bigNatEq# ByteArray#
x ByteArray#
y
naturalEq# Natural
_      Natural
_      = Bool#
0#

-- | Equality test for Natural
naturalEq :: Natural -> Natural -> Bool
naturalEq :: Natural -> Natural -> Bool
naturalEq !Natural
x !Natural
y = Bool# -> Bool
isTrue# (Natural -> Natural -> Bool#
naturalEq# Natural
x Natural
y)

-- | Inequality test for Natural
naturalNe# :: Natural -> Natural -> Bool#
{-# NOINLINE naturalNe# #-}
naturalNe# :: Natural -> Natural -> Bool#
naturalNe# (NS Word#
x) (NS Word#
y) = Word#
x Word# -> Word# -> Bool#
`neWord#` Word#
y
naturalNe# (NB ByteArray#
x) (NB ByteArray#
y) = ByteArray# -> ByteArray# -> Bool#
bigNatNe# ByteArray#
x ByteArray#
y
naturalNe# Natural
_      Natural
_      = Bool#
1#

-- | Inequality test for Natural
naturalNe :: Natural -> Natural -> Bool
naturalNe :: Natural -> Natural -> Bool
naturalNe !Natural
x !Natural
y = Bool# -> Bool
isTrue# (Natural -> Natural -> Bool#
naturalNe# Natural
x Natural
y)

-- | Greater or equal test for Natural
naturalGe# :: Natural -> Natural -> Bool#
{-# NOINLINE naturalGe# #-}
naturalGe# :: Natural -> Natural -> Bool#
naturalGe# (NS Word#
x) (NS Word#
y) = Word#
x Word# -> Word# -> Bool#
`geWord#` Word#
y
naturalGe# (NS Word#
_) (NB ByteArray#
_) = Bool#
0#
naturalGe# (NB ByteArray#
_) (NS Word#
_) = Bool#
1#
naturalGe# (NB ByteArray#
x) (NB ByteArray#
y) = ByteArray# -> ByteArray# -> Bool#
bigNatGe# ByteArray#
x ByteArray#
y

-- | Greater or equal test for Natural
naturalGe :: Natural -> Natural -> Bool
naturalGe :: Natural -> Natural -> Bool
naturalGe !Natural
x !Natural
y = Bool# -> Bool
isTrue# (Natural -> Natural -> Bool#
naturalGe# Natural
x Natural
y)

-- | Lower or equal test for Natural
naturalLe# :: Natural -> Natural -> Bool#
{-# NOINLINE naturalLe# #-}
naturalLe# :: Natural -> Natural -> Bool#
naturalLe# (NS Word#
x) (NS Word#
y) = Word#
x Word# -> Word# -> Bool#
`leWord#` Word#
y
naturalLe# (NS Word#
_) (NB ByteArray#
_) = Bool#
1#
naturalLe# (NB ByteArray#
_) (NS Word#
_) = Bool#
0#
naturalLe# (NB ByteArray#
x) (NB ByteArray#
y) = ByteArray# -> ByteArray# -> Bool#
bigNatLe# ByteArray#
x ByteArray#
y

-- | Lower or equal test for Natural
naturalLe :: Natural -> Natural -> Bool
naturalLe :: Natural -> Natural -> Bool
naturalLe !Natural
x !Natural
y = Bool# -> Bool
isTrue# (Natural -> Natural -> Bool#
naturalLe# Natural
x Natural
y)


-- | Greater test for Natural
naturalGt# :: Natural -> Natural -> Bool#
{-# NOINLINE naturalGt# #-}
naturalGt# :: Natural -> Natural -> Bool#
naturalGt# (NS Word#
x) (NS Word#
y) = Word#
x Word# -> Word# -> Bool#
`gtWord#` Word#
y
naturalGt# (NS Word#
_) (NB ByteArray#
_) = Bool#
0#
naturalGt# (NB ByteArray#
_) (NS Word#
_) = Bool#
1#
naturalGt# (NB ByteArray#
x) (NB ByteArray#
y) = ByteArray# -> ByteArray# -> Bool#
bigNatGt# ByteArray#
x ByteArray#
y

-- | Greater test for Natural
naturalGt :: Natural -> Natural -> Bool
naturalGt :: Natural -> Natural -> Bool
naturalGt !Natural
x !Natural
y = Bool# -> Bool
isTrue# (Natural -> Natural -> Bool#
naturalGt# Natural
x Natural
y)

-- | Lower test for Natural
naturalLt# :: Natural -> Natural -> Bool#
{-# NOINLINE naturalLt# #-}
naturalLt# :: Natural -> Natural -> Bool#
naturalLt# (NS Word#
x) (NS Word#
y) = Word#
x Word# -> Word# -> Bool#
`ltWord#` Word#
y
naturalLt# (NS Word#
_) (NB ByteArray#
_) = Bool#
1#
naturalLt# (NB ByteArray#
_) (NS Word#
_) = Bool#
0#
naturalLt# (NB ByteArray#
x) (NB ByteArray#
y) = ByteArray# -> ByteArray# -> Bool#
bigNatLt# ByteArray#
x ByteArray#
y

-- | Lower test for Natural
naturalLt :: Natural -> Natural -> Bool
naturalLt :: Natural -> Natural -> Bool
naturalLt !Natural
x !Natural
y = Bool# -> Bool
isTrue# (Natural -> Natural -> Bool#
naturalLt# Natural
x Natural
y)

-- | Compare two Natural
naturalCompare :: Natural -> Natural -> Ordering
{-# NOINLINE naturalCompare #-}
naturalCompare :: Natural -> Natural -> Ordering
naturalCompare (NS Word#
x) (NS Word#
y) = Word# -> Word# -> Ordering
cmpW# Word#
x Word#
y
naturalCompare (NB ByteArray#
x) (NB ByteArray#
y) = ByteArray# -> ByteArray# -> Ordering
bigNatCompare ByteArray#
x ByteArray#
y
naturalCompare (NS Word#
_) (NB ByteArray#
_) = Ordering
LT
naturalCompare (NB ByteArray#
_) (NS Word#
_) = Ordering
GT

-- | PopCount for Natural
naturalPopCount# :: Natural -> Word#
{-# NOINLINE naturalPopCount# #-}
naturalPopCount# :: Natural -> Word#
naturalPopCount# (NS Word#
x) = Word# -> Word#
popCnt# Word#
x
naturalPopCount# (NB ByteArray#
x) = ByteArray# -> Word#
bigNatPopCount# ByteArray#
x

-- | PopCount for Natural
naturalPopCount :: Natural -> Word
naturalPopCount :: Natural -> Word
naturalPopCount (NS Word#
x) = Word# -> Word
W# (Word# -> Word#
popCnt# Word#
x)
naturalPopCount (NB ByteArray#
x) = ByteArray# -> Word
bigNatPopCount ByteArray#
x

-- | Right shift for Natural
naturalShiftR# :: Natural -> Word# -> Natural
{-# NOINLINE naturalShiftR# #-}
naturalShiftR# :: Natural -> Word# -> Natural
naturalShiftR# (NS Word#
x) Word#
n = Word# -> Natural
NS (Word#
x Word# -> Word# -> Word#
`shiftRW#` Word#
n)
naturalShiftR# (NB ByteArray#
x) Word#
n = ByteArray# -> Natural
naturalFromBigNat# (ByteArray#
x ByteArray# -> Word# -> ByteArray#
`bigNatShiftR#` Word#
n)

-- | Right shift for Natural
naturalShiftR :: Natural -> Word -> Natural
naturalShiftR :: Natural -> Word -> Natural
naturalShiftR Natural
x (W# Word#
n) = Natural -> Word# -> Natural
naturalShiftR# Natural
x Word#
n

-- | Left shift
naturalShiftL# :: Natural -> Word# -> Natural
{-# NOINLINE naturalShiftL# #-}
naturalShiftL# :: Natural -> Word# -> Natural
naturalShiftL# v :: Natural
v@(NS Word#
x) Word#
n
   | Word#
0## <- Word#
x                     = Natural
v
   | Bool# -> Bool
isTrue# (Word# -> Word#
clz# Word#
x Word# -> Word# -> Bool#
`geWord#` Word#
n) = Word# -> Natural
NS (Word#
x Word# -> Bool# -> Word#
`uncheckedShiftL#` Word# -> Bool#
word2Int# Word#
n)
   | Bool
True                         = ByteArray# -> Natural
NB (Word# -> ByteArray#
bigNatFromWord# Word#
x ByteArray# -> Word# -> ByteArray#
`bigNatShiftL#` Word#
n)
naturalShiftL# (NB ByteArray#
x) Word#
n = ByteArray# -> Natural
NB (ByteArray#
x ByteArray# -> Word# -> ByteArray#
`bigNatShiftL#` Word#
n)

-- | Left shift
naturalShiftL :: Natural -> Word -> Natural
naturalShiftL :: Natural -> Word -> Natural
naturalShiftL !Natural
x (W# Word#
n) = Natural -> Word# -> Natural
naturalShiftL# Natural
x Word#
n

-- | Add two naturals
naturalAdd :: Natural -> Natural -> Natural
{-# NOINLINE naturalAdd #-}
naturalAdd :: Natural -> Natural -> Natural
naturalAdd (NS Word#
x) (NB ByteArray#
y) = ByteArray# -> Natural
NB (ByteArray# -> Word# -> ByteArray#
bigNatAddWord# ByteArray#
y Word#
x)
naturalAdd (NB ByteArray#
x) (NS Word#
y) = ByteArray# -> Natural
NB (ByteArray# -> Word# -> ByteArray#
bigNatAddWord# ByteArray#
x Word#
y)
naturalAdd (NB ByteArray#
x) (NB ByteArray#
y) = ByteArray# -> Natural
NB (ByteArray# -> ByteArray# -> ByteArray#
bigNatAdd ByteArray#
x ByteArray#
y)
naturalAdd (NS Word#
x) (NS Word#
y) =
   case Word# -> Word# -> (# Word#, Bool# #)
addWordC# Word#
x Word#
y of
      (# Word#
l,Bool#
0# #) -> Word# -> Natural
NS Word#
l
      (# Word#
l,Bool#
c  #) -> ByteArray# -> Natural
NB (Word# -> Word# -> ByteArray#
bigNatFromWord2# (Bool# -> Word#
int2Word# Bool#
c) Word#
l)

-- | Sub two naturals
naturalSub :: Natural -> Natural -> (# (# #) | Natural #)
{-# NOINLINE naturalSub #-}
naturalSub :: Natural -> Natural -> (# (# #) | Natural #)
naturalSub (NS Word#
_) (NB ByteArray#
_) = (# (# #) | #)
naturalSub (NB ByteArray#
x) (NS Word#
y) = (# | ByteArray# -> Natural
naturalFromBigNat# (ByteArray# -> Word# -> ByteArray#
bigNatSubWordUnsafe# ByteArray#
x Word#
y) #)
naturalSub (NS Word#
x) (NS Word#
y) =
   case Word# -> Word# -> (# Word#, Bool# #)
subWordC# Word#
x Word#
y of
      (# Word#
l,Bool#
0# #) -> (#       | Word# -> Natural
NS Word#
l #)
      (# Word#
_,Bool#
_  #) -> (# (# #) |      #)
naturalSub (NB ByteArray#
x) (NB ByteArray#
y) =
   case ByteArray# -> ByteArray# -> (# (# #) | ByteArray# #)
bigNatSub ByteArray#
x ByteArray#
y of
      (# (# #) |    #) -> (# (# #) | #)
      (#       | ByteArray#
z  #) -> (#       | ByteArray# -> Natural
naturalFromBigNat# ByteArray#
z #)

-- | Sub two naturals
--
-- Throw an Underflow exception if x < y
naturalSubThrow :: Natural -> Natural -> Natural
{-# NOINLINE naturalSubThrow #-}
naturalSubThrow :: Natural -> Natural -> Natural
naturalSubThrow (NS Word#
_) (NB ByteArray#
_) = forall a. a
raiseUnderflow
naturalSubThrow (NB ByteArray#
x) (NS Word#
y) = ByteArray# -> Natural
naturalFromBigNat# (ByteArray# -> Word# -> ByteArray#
bigNatSubWordUnsafe# ByteArray#
x Word#
y)
naturalSubThrow (NS Word#
x) (NS Word#
y) =
   case Word# -> Word# -> (# Word#, Bool# #)
subWordC# Word#
x Word#
y of
      (# Word#
l,Bool#
0# #) -> Word# -> Natural
NS Word#
l
      (# Word#
_,Bool#
_  #) -> forall a. a
raiseUnderflow
naturalSubThrow (NB ByteArray#
x) (NB ByteArray#
y) =
   case ByteArray# -> ByteArray# -> (# (# #) | ByteArray# #)
bigNatSub ByteArray#
x ByteArray#
y of
      (# (# #) |   #) -> forall a. a
raiseUnderflow
      (#       | ByteArray#
z #) -> ByteArray# -> Natural
naturalFromBigNat# ByteArray#
z

-- | Sub two naturals
--
-- Unsafe: don't check that x >= y
-- Undefined results if it happens
naturalSubUnsafe :: Natural -> Natural -> Natural
{-# NOINLINE naturalSubUnsafe #-}
naturalSubUnsafe :: Natural -> Natural -> Natural
naturalSubUnsafe (NS Word#
x) (NS Word#
y) = Word# -> Natural
NS (Word# -> Word# -> Word#
minusWord# Word#
x Word#
y)
naturalSubUnsafe (NS Word#
_) (NB ByteArray#
_) = Natural
naturalZero
naturalSubUnsafe (NB ByteArray#
x) (NS Word#
y) = ByteArray# -> Natural
naturalFromBigNat# (ByteArray# -> Word# -> ByteArray#
bigNatSubWordUnsafe# ByteArray#
x Word#
y)
naturalSubUnsafe (NB ByteArray#
x) (NB ByteArray#
y) =
   case ByteArray# -> ByteArray# -> (# (# #) | ByteArray# #)
bigNatSub ByteArray#
x ByteArray#
y of
      (# (# #) |   #) -> Natural
naturalZero
      (#       | ByteArray#
z #) -> ByteArray# -> Natural
naturalFromBigNat# ByteArray#
z

-- | Multiplication
naturalMul :: Natural -> Natural -> Natural
{-# NOINLINE naturalMul #-}
naturalMul :: Natural -> Natural -> Natural
naturalMul Natural
a Natural
b = case Natural
a of
   NS Word#
0## -> Word# -> Natural
NS Word#
0##
   NS Word#
1## -> Natural
b
   NS Word#
x   -> case Natural
b of
               NS Word#
0## -> Word# -> Natural
NS Word#
0##
               NS Word#
1## -> Natural
a
               NS Word#
y   -> case Word# -> Word# -> (# Word#, Word# #)
timesWord2# Word#
x Word#
y of
                           (# Word#
h,Word#
l #) -> Word# -> Word# -> Natural
naturalFromWord2# Word#
h Word#
l
               NB ByteArray#
y   -> ByteArray# -> Natural
NB (ByteArray# -> Word# -> ByteArray#
bigNatMulWord# ByteArray#
y Word#
x)
   NB ByteArray#
x   -> case Natural
b of
               NS Word#
0## -> Word# -> Natural
NS Word#
0##
               NS Word#
1## -> Natural
a
               NS Word#
y   -> ByteArray# -> Natural
NB (ByteArray# -> Word# -> ByteArray#
bigNatMulWord# ByteArray#
x Word#
y)
               NB ByteArray#
y   -> ByteArray# -> Natural
NB (ByteArray# -> ByteArray# -> ByteArray#
bigNatMul ByteArray#
x ByteArray#
y)

-- | Square a Natural
naturalSqr :: Natural -> Natural
naturalSqr :: Natural -> Natural
naturalSqr !Natural
a = Natural -> Natural -> Natural
naturalMul Natural
a Natural
a

-- | Signum for Natural
naturalSignum :: Natural -> Natural
{-# NOINLINE naturalSignum #-}
naturalSignum :: Natural -> Natural
naturalSignum (NS Word#
0##) = Word# -> Natural
NS Word#
0##
naturalSignum Natural
_        = Word# -> Natural
NS Word#
1##

-- | Negate for Natural
naturalNegate :: Natural -> Natural
{-# NOINLINE naturalNegate #-}
naturalNegate :: Natural -> Natural
naturalNegate (NS Word#
0##) = Word# -> Natural
NS Word#
0##
naturalNegate Natural
_        = forall a. a
raiseUnderflow

-- | Return division quotient and remainder
--
-- Division by zero is handled by BigNat
naturalQuotRem# :: Natural -> Natural -> (# Natural, Natural #)
{-# NOINLINE naturalQuotRem# #-}
naturalQuotRem# :: Natural -> Natural -> (# Natural, Natural #)
naturalQuotRem# (NS Word#
n) (NS Word#
d) = case Word# -> Word# -> (# Word#, Word# #)
quotRemWord# Word#
n Word#
d of
                                 (# Word#
q, Word#
r #) -> (# Word# -> Natural
NS Word#
q, Word# -> Natural
NS Word#
r #)
naturalQuotRem# (NB ByteArray#
n) (NS Word#
d) = case ByteArray# -> Word# -> (# ByteArray#, Word# #)
bigNatQuotRemWord# ByteArray#
n Word#
d of
                                 (# ByteArray#
q, Word#
r #) -> (# ByteArray# -> Natural
naturalFromBigNat# ByteArray#
q, Word# -> Natural
NS Word#
r #)
naturalQuotRem# (NS Word#
n) (NB ByteArray#
d) = case ByteArray# -> ByteArray# -> (# ByteArray#, ByteArray# #)
bigNatQuotRem# (Word# -> ByteArray#
bigNatFromWord# Word#
n) ByteArray#
d of
                                 (# ByteArray#
q, ByteArray#
r #) -> (# ByteArray# -> Natural
naturalFromBigNat# ByteArray#
q, ByteArray# -> Natural
naturalFromBigNat# ByteArray#
r #)
naturalQuotRem# (NB ByteArray#
n) (NB ByteArray#
d) = case ByteArray# -> ByteArray# -> (# ByteArray#, ByteArray# #)
bigNatQuotRem# ByteArray#
n ByteArray#
d of
                                 (# ByteArray#
q, ByteArray#
r #) -> (# ByteArray# -> Natural
naturalFromBigNat# ByteArray#
q, ByteArray# -> Natural
naturalFromBigNat# ByteArray#
r #)

-- | Return division quotient and remainder
naturalQuotRem :: Natural -> Natural -> (Natural, Natural)
naturalQuotRem :: Natural -> Natural -> (Natural, Natural)
naturalQuotRem !Natural
n !Natural
d = case Natural -> Natural -> (# Natural, Natural #)
naturalQuotRem# Natural
n Natural
d of
   (# Natural
q, Natural
r #) -> (Natural
q,Natural
r)

-- | Return division quotient
naturalQuot :: Natural -> Natural -> Natural
{-# NOINLINE naturalQuot #-}
naturalQuot :: Natural -> Natural -> Natural
naturalQuot (NS Word#
n) (NS Word#
d) = case Word# -> Word# -> Word#
quotWord# Word#
n Word#
d of
                             Word#
q -> Word# -> Natural
NS Word#
q
naturalQuot (NB ByteArray#
n) (NS Word#
d) = case ByteArray# -> Word# -> ByteArray#
bigNatQuotWord# ByteArray#
n Word#
d of
                             ByteArray#
q -> ByteArray# -> Natural
naturalFromBigNat# ByteArray#
q
naturalQuot (NS Word#
n) (NB ByteArray#
d) = case ByteArray# -> ByteArray# -> ByteArray#
bigNatQuot (Word# -> ByteArray#
bigNatFromWord# Word#
n) ByteArray#
d of
                             ByteArray#
q -> ByteArray# -> Natural
naturalFromBigNat# ByteArray#
q
naturalQuot (NB ByteArray#
n) (NB ByteArray#
d) = case ByteArray# -> ByteArray# -> ByteArray#
bigNatQuot ByteArray#
n ByteArray#
d of
                             ByteArray#
q -> ByteArray# -> Natural
naturalFromBigNat# ByteArray#
q

-- | Return division remainder
naturalRem :: Natural -> Natural -> Natural
{-# NOINLINE naturalRem #-}
naturalRem :: Natural -> Natural -> Natural
naturalRem (NS Word#
n) (NS Word#
d) = case Word# -> Word# -> Word#
remWord# Word#
n Word#
d of
                             Word#
r -> Word# -> Natural
NS Word#
r
naturalRem (NB ByteArray#
n) (NS Word#
d) = case ByteArray# -> Word# -> Word#
bigNatRemWord# ByteArray#
n Word#
d of
                             Word#
r -> Word# -> Natural
NS Word#
r
naturalRem (NS Word#
n) (NB ByteArray#
d) = case ByteArray# -> ByteArray# -> ByteArray#
bigNatRem (Word# -> ByteArray#
bigNatFromWord# Word#
n) ByteArray#
d of
                             ByteArray#
r -> ByteArray# -> Natural
naturalFromBigNat# ByteArray#
r
naturalRem (NB ByteArray#
n) (NB ByteArray#
d) = case ByteArray# -> ByteArray# -> ByteArray#
bigNatRem ByteArray#
n ByteArray#
d of
                             ByteArray#
r -> ByteArray# -> Natural
naturalFromBigNat# ByteArray#
r

naturalAnd :: Natural -> Natural -> Natural
{-# NOINLINE naturalAnd #-}
naturalAnd :: Natural -> Natural -> Natural
naturalAnd (NS Word#
n) (NS Word#
m) = Word# -> Natural
NS (Word#
n Word# -> Word# -> Word#
`and#` Word#
m)
naturalAnd (NS Word#
n) (NB ByteArray#
m) = Word# -> Natural
NS (Word#
n Word# -> Word# -> Word#
`and#` ByteArray# -> Word#
bigNatToWord# ByteArray#
m)
naturalAnd (NB ByteArray#
n) (NS Word#
m) = Word# -> Natural
NS (ByteArray# -> Word#
bigNatToWord# ByteArray#
n Word# -> Word# -> Word#
`and#` Word#
m)
naturalAnd (NB ByteArray#
n) (NB ByteArray#
m) = ByteArray# -> Natural
naturalFromBigNat# (ByteArray# -> ByteArray# -> ByteArray#
bigNatAnd ByteArray#
n ByteArray#
m)

naturalAndNot :: Natural -> Natural -> Natural
{-# NOINLINE naturalAndNot #-}
naturalAndNot :: Natural -> Natural -> Natural
naturalAndNot (NS Word#
n) (NS Word#
m) = Word# -> Natural
NS (Word#
n Word# -> Word# -> Word#
`and#` Word# -> Word#
not# Word#
m)
naturalAndNot (NS Word#
n) (NB ByteArray#
m) = Word# -> Natural
NS (Word#
n Word# -> Word# -> Word#
`and#` Word# -> Word#
not# (ByteArray# -> Word#
bigNatToWord# ByteArray#
m))
naturalAndNot (NB ByteArray#
n) (NS Word#
m) = Word# -> Natural
NS (ByteArray# -> Word#
bigNatToWord# ByteArray#
n Word# -> Word# -> Word#
`and#` Word# -> Word#
not# Word#
m)
naturalAndNot (NB ByteArray#
n) (NB ByteArray#
m) = ByteArray# -> Natural
naturalFromBigNat# (ByteArray# -> ByteArray# -> ByteArray#
bigNatAndNot ByteArray#
n ByteArray#
m)

naturalOr :: Natural -> Natural -> Natural
{-# NOINLINE naturalOr #-}
naturalOr :: Natural -> Natural -> Natural
naturalOr (NS Word#
n) (NS Word#
m) = Word# -> Natural
NS (Word#
n Word# -> Word# -> Word#
`or#` Word#
m)
naturalOr (NS Word#
n) (NB ByteArray#
m) = ByteArray# -> Natural
NB (ByteArray# -> Word# -> ByteArray#
bigNatOrWord# ByteArray#
m Word#
n)
naturalOr (NB ByteArray#
n) (NS Word#
m) = ByteArray# -> Natural
NB (ByteArray# -> Word# -> ByteArray#
bigNatOrWord# ByteArray#
n Word#
m)
naturalOr (NB ByteArray#
n) (NB ByteArray#
m) = ByteArray# -> Natural
NB (ByteArray# -> ByteArray# -> ByteArray#
bigNatOr ByteArray#
n ByteArray#
m)

naturalXor :: Natural -> Natural -> Natural
{-# NOINLINE naturalXor #-}
naturalXor :: Natural -> Natural -> Natural
naturalXor (NS Word#
n) (NS Word#
m) = Word# -> Natural
NS (Word#
n Word# -> Word# -> Word#
`xor#` Word#
m)
naturalXor (NS Word#
n) (NB ByteArray#
m) = ByteArray# -> Natural
NB (ByteArray# -> Word# -> ByteArray#
bigNatXorWord# ByteArray#
m Word#
n)
naturalXor (NB ByteArray#
n) (NS Word#
m) = ByteArray# -> Natural
NB (ByteArray# -> Word# -> ByteArray#
bigNatXorWord# ByteArray#
n Word#
m)
naturalXor (NB ByteArray#
n) (NB ByteArray#
m) = ByteArray# -> Natural
naturalFromBigNat# (ByteArray# -> ByteArray# -> ByteArray#
bigNatXor ByteArray#
n ByteArray#
m)

naturalTestBit# :: Natural -> Word# -> Bool#
{-# NOINLINE naturalTestBit# #-}
naturalTestBit# :: Natural -> Word# -> Bool#
naturalTestBit# (NS Word#
w) Word#
i  = (Word#
i Word# -> Word# -> Bool#
`ltWord#` WORD_SIZE_IN_BITS##) &&#
                            ((Word#
w Word# -> Word# -> Word#
`and#` (Word#
1## Word# -> Bool# -> Word#
`uncheckedShiftL#` Word# -> Bool#
word2Int# Word#
i)) Word# -> Word# -> Bool#
`neWord#` Word#
0##)
naturalTestBit# (NB ByteArray#
bn) Word#
i = ByteArray# -> Word# -> Bool#
bigNatTestBit# ByteArray#
bn Word#
i

naturalTestBit :: Natural -> Word -> Bool
naturalTestBit :: Natural -> Word -> Bool
naturalTestBit !Natural
n (W# Word#
i) = Bool# -> Bool
isTrue# (Natural -> Word# -> Bool#
naturalTestBit# Natural
n Word#
i)

naturalBit# :: Word# -> Natural
{-# NOINLINE naturalBit# #-}
naturalBit# :: Word# -> Natural
naturalBit# Word#
i
  | Bool# -> Bool
isTrue# (Word#
i Word# -> Word# -> Bool#
`ltWord#` WORD_SIZE_IN_BITS##) = NS (1## `uncheckedShiftL#` word2Int# i)
  | Bool
True                                      = ByteArray# -> Natural
NB (Word# -> ByteArray#
bigNatBit# Word#
i)

naturalBit :: Word -> Natural
naturalBit :: Word -> Natural
naturalBit (W# Word#
i) = Word# -> Natural
naturalBit# Word#
i

-- | Compute greatest common divisor.
naturalGcd :: Natural -> Natural -> Natural
{-# NOINLINE naturalGcd #-}
naturalGcd :: Natural -> Natural -> Natural
naturalGcd (NS Word#
0##) !Natural
y       = Natural
y
naturalGcd Natural
x        (NS Word#
0##) = Natural
x
naturalGcd (NS Word#
1##) Natural
_        = Word# -> Natural
NS Word#
1##
naturalGcd Natural
_        (NS Word#
1##) = Word# -> Natural
NS Word#
1##
naturalGcd (NB ByteArray#
x)   (NB ByteArray#
y)   = ByteArray# -> Natural
naturalFromBigNat# (ByteArray# -> ByteArray# -> ByteArray#
bigNatGcd ByteArray#
x ByteArray#
y)
naturalGcd (NB ByteArray#
x)   (NS Word#
y)   = Word# -> Natural
NS (ByteArray# -> Word# -> Word#
bigNatGcdWord# ByteArray#
x Word#
y)
naturalGcd (NS Word#
x)   (NB ByteArray#
y)   = Word# -> Natural
NS (ByteArray# -> Word# -> Word#
bigNatGcdWord# ByteArray#
y Word#
x)
naturalGcd (NS Word#
x)   (NS Word#
y)   = Word# -> Natural
NS (Word# -> Word# -> Word#
gcdWord# Word#
x Word#
y)

-- | Compute least common multiple.
naturalLcm :: Natural -> Natural -> Natural
{-# NOINLINE naturalLcm #-}
naturalLcm :: Natural -> Natural -> Natural
naturalLcm (NS Word#
0##) !Natural
_       = Word# -> Natural
NS Word#
0##
naturalLcm Natural
_        (NS Word#
0##) = Word# -> Natural
NS Word#
0##
naturalLcm (NS Word#
1##) Natural
y        = Natural
y
naturalLcm Natural
x        (NS Word#
1##) = Natural
x
naturalLcm (NS Word#
a  ) (NS Word#
b  ) = ByteArray# -> Natural
naturalFromBigNat# (Word# -> Word# -> ByteArray#
bigNatLcmWordWord# Word#
a Word#
b)
naturalLcm (NB ByteArray#
a  ) (NS Word#
b  ) = ByteArray# -> Natural
naturalFromBigNat# (ByteArray# -> Word# -> ByteArray#
bigNatLcmWord# ByteArray#
a Word#
b)
naturalLcm (NS Word#
a  ) (NB ByteArray#
b  ) = ByteArray# -> Natural
naturalFromBigNat# (ByteArray# -> Word# -> ByteArray#
bigNatLcmWord# ByteArray#
b Word#
a)
naturalLcm (NB ByteArray#
a  ) (NB ByteArray#
b  ) = ByteArray# -> Natural
naturalFromBigNat# (ByteArray# -> ByteArray# -> ByteArray#
bigNatLcm ByteArray#
a ByteArray#
b)

-- | Base 2 logarithm
naturalLog2# :: Natural -> Word#
{-# NOINLINE naturalLog2# #-}
naturalLog2# :: Natural -> Word#
naturalLog2# (NS Word#
w) = Word# -> Word#
wordLog2# Word#
w
naturalLog2# (NB ByteArray#
b) = ByteArray# -> Word#
bigNatLog2# ByteArray#
b

-- | Base 2 logarithm
naturalLog2 :: Natural -> Word
naturalLog2 :: Natural -> Word
naturalLog2 !Natural
n = Word# -> Word
W# (Natural -> Word#
naturalLog2# Natural
n)

-- | Logarithm for an arbitrary base
naturalLogBaseWord# :: Word# -> Natural -> Word#
{-# NOINLINE naturalLogBaseWord# #-}
naturalLogBaseWord# :: Word# -> Natural -> Word#
naturalLogBaseWord# Word#
base (NS Word#
a) = Word# -> Word# -> Word#
wordLogBase# Word#
base Word#
a
naturalLogBaseWord# Word#
base (NB ByteArray#
a) = Word# -> ByteArray# -> Word#
bigNatLogBaseWord# Word#
base ByteArray#
a

-- | Logarithm for an arbitrary base
naturalLogBaseWord :: Word -> Natural -> Word
naturalLogBaseWord :: Word -> Natural -> Word
naturalLogBaseWord (W# Word#
base) !Natural
a = Word# -> Word
W# (Word# -> Natural -> Word#
naturalLogBaseWord# Word#
base Natural
a)

-- | Logarithm for an arbitrary base
naturalLogBase# :: Natural -> Natural -> Word#
{-# NOINLINE naturalLogBase# #-}
naturalLogBase# :: Natural -> Natural -> Word#
naturalLogBase# (NS Word#
base) !Natural
a     = Word# -> Natural -> Word#
naturalLogBaseWord# Word#
base Natural
a
naturalLogBase# (NB ByteArray#
_   ) (NS Word#
_) = Word#
0##
naturalLogBase# (NB ByteArray#
base) (NB ByteArray#
a) = ByteArray# -> ByteArray# -> Word#
bigNatLogBase# ByteArray#
base ByteArray#
a

-- | Logarithm for an arbitrary base
naturalLogBase :: Natural -> Natural -> Word
naturalLogBase :: Natural -> Natural -> Word
naturalLogBase !Natural
base !Natural
a = Word# -> Word
W# (Natural -> Natural -> Word#
naturalLogBase# Natural
base Natural
a)

-- | \"@'naturalPowMod' /b/ /e/ /m/@\" computes base @/b/@ raised to
-- exponent @/e/@ modulo @/m/@.
naturalPowMod :: Natural -> Natural -> Natural -> Natural
{-# NOINLINE naturalPowMod #-}
naturalPowMod :: Natural -> Natural -> Natural -> Natural
naturalPowMod !Natural
_         !Natural
_       (NS Word#
0##) = forall a. a
raiseDivZero
naturalPowMod Natural
_          Natural
_        (NS Word#
1##) = Word# -> Natural
NS Word#
0##
naturalPowMod Natural
_          (NS Word#
0##) Natural
_        = Word# -> Natural
NS Word#
1##
naturalPowMod (NS Word#
0##)   Natural
_        Natural
_        = Word# -> Natural
NS Word#
0##
naturalPowMod (NS Word#
1##)   Natural
_        Natural
_        = Word# -> Natural
NS Word#
1##
naturalPowMod (NS Word#
b)    (NS Word#
e)   (NS Word#
m)    = Word# -> Natural
NS (Word# -> Word# -> Word# -> Word#
powModWord# Word#
b Word#
e Word#
m)
naturalPowMod Natural
b         Natural
e        (NS Word#
m)    = Word# -> Natural
NS (ByteArray# -> ByteArray# -> Word# -> Word#
bigNatPowModWord#
                                                   (Natural -> ByteArray#
naturalToBigNat# Natural
b)
                                                   (Natural -> ByteArray#
naturalToBigNat# Natural
e)
                                                    Word#
m)
naturalPowMod Natural
b         Natural
e        (NB ByteArray#
m)    = ByteArray# -> Natural
naturalFromBigNat#
                                                (ByteArray# -> ByteArray# -> ByteArray# -> ByteArray#
bigNatPowMod (Natural -> ByteArray#
naturalToBigNat# Natural
b)
                                                              (Natural -> ByteArray#
naturalToBigNat# Natural
e)
                                                              ByteArray#
m)

-- | Compute the number of digits of the Natural in the given base.
--
-- `base` must be > 1
naturalSizeInBase# :: Word# -> Natural -> Word#
{-# NOINLINE naturalSizeInBase# #-}
naturalSizeInBase# :: Word# -> Natural -> Word#
naturalSizeInBase# Word#
base (NS Word#
w) = Word# -> Word# -> Word#
wordSizeInBase# Word#
base Word#
w
naturalSizeInBase# Word#
base (NB ByteArray#
n) = Word# -> ByteArray# -> Word#
bigNatSizeInBase# Word#
base ByteArray#
n

-- | Write a 'Natural' 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#@.
naturalToAddr# :: Natural -> Addr# -> Bool# -> State# s -> (# State# s, Word# #)
{-# NOINLINE naturalToAddr# #-}
naturalToAddr# :: forall s.
Natural -> Addr# -> Bool# -> State# s -> (# State# s, Word# #)
naturalToAddr# (NS Word#
i) = forall s.
Word# -> Addr# -> Bool# -> State# s -> (# State# s, Word# #)
wordToAddr# Word#
i
naturalToAddr# (NB ByteArray#
n) = forall s.
ByteArray# -> Addr# -> Bool# -> State# s -> (# State# s, Word# #)
bigNatToAddr# ByteArray#
n

-- | Write a 'Natural' 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#@.
naturalToAddr :: Natural -> Addr# -> Bool# -> IO Word
naturalToAddr :: Natural -> Addr# -> Bool# -> IO Word
naturalToAddr Natural
a Addr#
addr Bool#
e = forall a. (State# RealWorld -> (# State# RealWorld, a #)) -> IO a
IO \State# RealWorld
s -> case forall s.
Natural -> Addr# -> Bool# -> State# s -> (# State# s, Word# #)
naturalToAddr# Natural
a Addr#
addr Bool#
e State# RealWorld
s of
   (# State# RealWorld
s', Word#
w #) -> (# State# RealWorld
s', Word# -> Word
W# Word#
w #)


-- | Read a Natural 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.
naturalFromAddr# :: Word# -> Addr# -> Bool# -> State# s -> (# State# s, Natural #)
{-# NOINLINE naturalFromAddr# #-}
naturalFromAddr# :: forall s.
Word# -> Addr# -> Bool# -> State# s -> (# State# s, Natural #)
naturalFromAddr# 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# -> Natural
naturalFromBigNat# ByteArray#
n #)

-- | Read a Natural 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.
naturalFromAddr :: Word# -> Addr# -> Bool# -> IO Natural
naturalFromAddr :: Word# -> Addr# -> Bool# -> IO Natural
naturalFromAddr 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, Natural #)
naturalFromAddr# Word#
sz Addr#
addr Bool#
e)


-- | Write a Natural 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#@.
naturalToMutableByteArray# :: Natural -> MutableByteArray# s -> Word# -> Bool# -> State# s -> (# State# s, Word# #)
{-# NOINLINE naturalToMutableByteArray# #-}
naturalToMutableByteArray# :: forall s.
Natural
-> MutableByteArray# s
-> Word#
-> Bool#
-> State# s
-> (# State# s, Word# #)
naturalToMutableByteArray# (NS Word#
w) = forall s.
Word#
-> MutableByteArray# s
-> Word#
-> Bool#
-> State# s
-> (# State# s, Word# #)
wordToMutableByteArray# Word#
w
naturalToMutableByteArray# (NB ByteArray#
a) = forall s.
ByteArray#
-> MutableByteArray# s
-> Word#
-> Bool#
-> State# s
-> (# State# s, Word# #)
bigNatToMutableByteArray# ByteArray#
a

-- | Read a Natural 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.
naturalFromByteArray# :: Word# -> ByteArray# -> Word# -> Bool# -> State# s -> (# State# s, Natural #)
{-# NOINLINE naturalFromByteArray# #-}
naturalFromByteArray# :: forall s.
Word#
-> ByteArray#
-> Word#
-> Bool#
-> State# s
-> (# State# s, Natural #)
naturalFromByteArray# 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# -> Natural
naturalFromBigNat# ByteArray#
a #)