{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE NumericUnderscores #-}
{-# LANGUAGE ViewPatterns #-}
{-# LANGUAGE UnboxedSums #-}
{-# LANGUAGE UnboxedTuples #-}
{-# LANGUAGE UnliftedNewtypes #-}

-- |
-- Module: Data.Word.Wider
-- Copyright: (c) 2025 Jared Tobin
-- License: MIT
-- Maintainer: Jared Tobin <jared@ppad.tech>
--
-- Wider words, consisting of four 'Limb's.

module Data.Word.Wider (
  -- * Four-limb words
    Wider(..)
  , wider
  , to
  , from

  -- * Comparison
  , eq_vartime
  , cmp
  , cmp#
  , eq#
  , lt
  , lt#
  , gt
  , gt#

  -- * Parity
  , odd#
  , odd

  -- * Constant-time selection
  , select
  , select#

  -- * Bit manipulation
  , shl1
  , shr1
  , shl1_c
  , shr1_c
  , shr_limb
  , shl_limb
  , shl1_c#
  , shr1_c#
  , shr_limb#
  , shl_limb#
  , and
  , and_w#
  , or
  , or_w#
  , not
  , not#

  -- * Arithmetic
  , add_o
  , add_o#
  , add
  , add_w#
  , add_mod
  , add_mod#
  , sub
  , sub_b
  , sub_b#
  , sub_mod
  , sub_mod#
  , sub_mod_c#
  , mul
  , mul_c
  , mul_c#
  , sqr
  , sqr#
  ) where

import Control.DeepSeq
import Data.Bits ((.|.), (.&.), (.<<.), (.>>.))
import qualified Data.Bits as B
import qualified Data.Choice as C
import Data.Word.Limb (Limb(..))
import qualified Data.Word.Limb as L
import GHC.Exts (Word(..), Int(..), Int#)
import qualified GHC.Exts as Exts
import Prelude hiding (div, mod, or, and, not, quot, rem, recip, odd)

-- utilities ------------------------------------------------------------------

fi :: (Integral a, Num b) => a -> b
fi :: forall a b. (Integral a, Num b) => a -> b
fi = a -> b
forall a b. (Integral a, Num b) => a -> b
fromIntegral
{-# INLINE fi #-}

-- wider words ----------------------------------------------------------------

-- | Little-endian wider words, consisting of four 'Limbs'.
--
--   >>> 1 :: Wider
--   1
data Wider = Wider !(# Limb, Limb, Limb, Limb #)

instance Show Wider where
  show :: Wider -> String
show = Integer -> String
forall a. Show a => a -> String
show (Integer -> String) -> (Wider -> Integer) -> Wider -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Wider -> Integer
from

instance Eq Wider where
  Wider (# Limb, Limb, Limb, Limb #)
a == :: Wider -> Wider -> Bool
== Wider (# Limb, Limb, Limb, Limb #)
b = Choice -> Bool
C.decide ((# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #) -> Choice
eq# (# Limb, Limb, Limb, Limb #)
a (# Limb, Limb, Limb, Limb #)
b)

instance Ord Wider where
  compare :: Wider -> Wider -> Ordering
compare = Wider -> Wider -> Ordering
cmp

instance Num Wider where
  + :: Wider -> Wider -> Wider
(+) = Wider -> Wider -> Wider
add
  (-) = Wider -> Wider -> Wider
sub
  * :: Wider -> Wider -> Wider
(*) = Wider -> Wider -> Wider
mul
  abs :: Wider -> Wider
abs = Wider -> Wider
forall a. a -> a
id
  fromInteger :: Integer -> Wider
fromInteger = Integer -> Wider
to
  negate :: Wider -> Wider
negate Wider
w = Wider -> Wider -> Wider
add (Wider -> Wider
not Wider
w) ((# Limb, Limb, Limb, Limb #) -> Wider
Wider (# Word# -> Limb
Limb Word#
1##, Word# -> Limb
Limb Word#
0##, Word# -> Limb
Limb Word#
0##, Word# -> Limb
Limb Word#
0## #))
  signum :: Wider -> Wider
signum Wider
a = case Wider
a of
    Wider (# Limb Word#
0##, Limb Word#
0##, Limb Word#
0##, Limb Word#
0## #) -> Wider
0
    Wider
_ -> Wider
1

instance NFData Wider where
  rnf :: Wider -> ()
rnf (Wider (# Limb, Limb, Limb, Limb #)
a) = case (# Limb, Limb, Limb, Limb #)
a of
    (# Limb
_, Limb
_, Limb
_, Limb
_ #) -> ()

-- comparison -----------------------------------------------------------------

eq#
  :: (# Limb, Limb, Limb, Limb #)
  -> (# Limb, Limb, Limb, Limb #)
  -> C.Choice
eq# :: (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #) -> Choice
eq# (# Limb, Limb, Limb, Limb #)
a (# Limb, Limb, Limb, Limb #)
b =
  let !(# Limb Word#
a0, Limb Word#
a1, Limb Word#
a2, Limb Word#
a3 #) = (# Limb, Limb, Limb, Limb #)
a
      !(# Limb Word#
b0, Limb Word#
b1, Limb Word#
b2, Limb Word#
b3 #) = (# Limb, Limb, Limb, Limb #)
b
  in  (# Word#, Word#, Word#, Word# #)
-> (# Word#, Word#, Word#, Word# #) -> Choice
C.eq_wider# (# Word#
a0, Word#
a1, Word#
a2, Word#
a3 #) (# Word#
b0, Word#
b1, Word#
b2, Word#
b3 #)
{-# INLINE eq# #-}

-- | Compare 'Wider' words for equality in variable time.
--
--   >>> eq_vartime 1 0
--   False
--   >>> eq_vartime 1 1
--   True
eq_vartime :: Wider -> Wider -> Bool
eq_vartime :: Wider -> Wider -> Bool
eq_vartime Wider
a Wider
b =
  let !(Wider (# Limb
a0, Limb
a1, Limb
a2, Limb
a3 #)) = Wider
a
      !(Wider (# Limb
b0, Limb
b1, Limb
b2, Limb
b3 #)) = Wider
b
  in     (Limb -> Limb -> Bool
L.eq_vartime# Limb
a0 Limb
b0)
      Bool -> Bool -> Bool
&& (Limb -> Limb -> Bool
L.eq_vartime# Limb
a1 Limb
b1)
      Bool -> Bool -> Bool
&& (Limb -> Limb -> Bool
L.eq_vartime# Limb
a2 Limb
b2)
      Bool -> Bool -> Bool
&& (Limb -> Limb -> Bool
L.eq_vartime# Limb
a3 Limb
b3)

lt#
  :: (# Limb, Limb, Limb, Limb #)
  -> (# Limb, Limb, Limb, Limb #)
  -> C.Choice
lt# :: (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #) -> Choice
lt# (# Limb, Limb, Limb, Limb #)
a (# Limb, Limb, Limb, Limb #)
b =
  let !(# (# Limb, Limb, Limb, Limb #)
_, Limb Word#
bor #) = (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
-> (# (# Limb, Limb, Limb, Limb #), Limb #)
sub_b# (# Limb, Limb, Limb, Limb #)
a (# Limb, Limb, Limb, Limb #)
b
  in  Word# -> Choice
C.from_word_mask# Word#
bor
{-# INLINE lt# #-}

lt :: Wider -> Wider -> C.Choice
lt :: Wider -> Wider -> Choice
lt (Wider (# Limb, Limb, Limb, Limb #)
a) (Wider (# Limb, Limb, Limb, Limb #)
b) = (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #) -> Choice
lt# (# Limb, Limb, Limb, Limb #)
a (# Limb, Limb, Limb, Limb #)
b

gt#
  :: (# Limb, Limb, Limb, Limb #)
  -> (# Limb, Limb, Limb, Limb #)
  -> C.Choice
gt# :: (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #) -> Choice
gt# (# Limb, Limb, Limb, Limb #)
a (# Limb, Limb, Limb, Limb #)
b =
  let !(# (# Limb, Limb, Limb, Limb #)
_, Limb Word#
bor #) = (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
-> (# (# Limb, Limb, Limb, Limb #), Limb #)
sub_b# (# Limb, Limb, Limb, Limb #)
b (# Limb, Limb, Limb, Limb #)
a
  in  Word# -> Choice
C.from_word_mask# Word#
bor
{-# INLINE gt# #-}

gt :: Wider -> Wider -> C.Choice
gt :: Wider -> Wider -> Choice
gt (Wider (# Limb, Limb, Limb, Limb #)
a) (Wider (# Limb, Limb, Limb, Limb #)
b) = (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #) -> Choice
gt# (# Limb, Limb, Limb, Limb #)
a (# Limb, Limb, Limb, Limb #)
b

cmp#
  :: (# Limb, Limb, Limb, Limb #)
  -> (# Limb, Limb, Limb, Limb #)
  -> Int#
cmp# :: (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #) -> Int#
cmp# (# Limb
l0, Limb
l1, Limb
l2, Limb
l3 #) (# Limb
r0, Limb
r1, Limb
r2, Limb
r3 #) =
  let !(# Limb
w0, Limb
b0 #) = Limb -> Limb -> Limb -> (# Limb, Limb #)
L.sub_b# Limb
r0 Limb
l0 (Word# -> Limb
Limb Word#
0##)
      !d0 :: Limb
d0           = Limb -> Limb -> Limb
L.or# (Word# -> Limb
Limb Word#
0##) Limb
w0
      !(# Limb
w1, Limb
b1 #) = Limb -> Limb -> Limb -> (# Limb, Limb #)
L.sub_b# Limb
r1 Limb
l1 Limb
b0
      !d1 :: Limb
d1           = Limb -> Limb -> Limb
L.or# Limb
d0 Limb
w1
      !(# Limb
w2, Limb
b2 #) = Limb -> Limb -> Limb -> (# Limb, Limb #)
L.sub_b# Limb
r2 Limb
l2 Limb
b1
      !d2 :: Limb
d2           = Limb -> Limb -> Limb
L.or# Limb
d1 Limb
w2
      !(# Limb
w3, Limb
b3 #) = Limb -> Limb -> Limb -> (# Limb, Limb #)
L.sub_b# Limb
r3 Limb
l3 Limb
b2
      !d3 :: Limb
d3           = Limb -> Limb -> Limb
L.or# Limb
d2 Limb
w3
      !(Limb Word#
w)     = Limb -> Limb -> Limb
L.and# Limb
b3 (Word# -> Limb
Limb Word#
2##)
      !s :: Int#
s            = Word# -> Int#
Exts.word2Int# Word#
w Int# -> Int# -> Int#
Exts.-# Int#
1#
  in  (Word# -> Int#
Exts.word2Int# (Choice -> Word#
C.to_word# (Limb -> Choice
L.nonzero# Limb
d3))) Int# -> Int# -> Int#
Exts.*# Int#
s
{-# INLINE cmp# #-}

-- | Constant-time comparison between 'Wider' words.
--
--   >>> cmp 1 2
--   LT
--   >>> cmp 2 1
--   GT
--   >>> cmp 2 2
--   EQ
cmp :: Wider -> Wider -> Ordering
cmp :: Wider -> Wider -> Ordering
cmp (Wider (# Limb, Limb, Limb, Limb #)
a) (Wider (# Limb, Limb, Limb, Limb #)
b) = case (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #) -> Int#
cmp# (# Limb, Limb, Limb, Limb #)
a (# Limb, Limb, Limb, Limb #)
b of
  Int#
1#  -> Ordering
GT
  Int#
0#  -> Ordering
EQ
  Int#
_   -> Ordering
LT
{-# INLINABLE cmp #-}

-- construction / conversion --------------------------------------------------

-- | Construct a 'Wider' word from four 'Words', provided in
--   little-endian order.
--
--   >>> wider 1 0 0 0
--   1
wider :: Word -> Word -> Word -> Word -> Wider
wider :: Word -> Word -> Word -> Word -> Wider
wider (W# Word#
w0) (W# Word#
w1) (W# Word#
w2) (W# Word#
w3) = (# Limb, Limb, Limb, Limb #) -> Wider
Wider
  (# Word# -> Limb
Limb Word#
w0, Word# -> Limb
Limb Word#
w1, Word# -> Limb
Limb Word#
w2, Word# -> Limb
Limb Word#
w3 #)

-- | Convert an 'Integer' to a 'Wider' word.
--
--   >>> to 1
--   1
to :: Integer -> Wider
to :: Integer -> Wider
to Integer
n =
  let !size :: Int
size = Word -> Int
forall b. FiniteBits b => b -> Int
B.finiteBitSize (Word
0 :: Word)
      !mask :: Integer
mask = Word -> Integer
forall a b. (Integral a, Num b) => a -> b
fi (Word
forall a. Bounded a => a
maxBound :: Word) :: Integer
      !(W# Word#
w0) = Integer -> Word
forall a b. (Integral a, Num b) => a -> b
fi (Integer
n Integer -> Integer -> Integer
forall a. Bits a => a -> a -> a
.&. Integer
mask)
      !(W# Word#
w1) = Integer -> Word
forall a b. (Integral a, Num b) => a -> b
fi ((Integer
n Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
.>>. Int
size) Integer -> Integer -> Integer
forall a. Bits a => a -> a -> a
.&. Integer
mask)
      !(W# Word#
w2) = Integer -> Word
forall a b. (Integral a, Num b) => a -> b
fi ((Integer
n Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
.>>. (Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
size)) Integer -> Integer -> Integer
forall a. Bits a => a -> a -> a
.&. Integer
mask)
      !(W# Word#
w3) = Integer -> Word
forall a b. (Integral a, Num b) => a -> b
fi ((Integer
n Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
.>>. (Int
3 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
size)) Integer -> Integer -> Integer
forall a. Bits a => a -> a -> a
.&. Integer
mask)
  in  (# Limb, Limb, Limb, Limb #) -> Wider
Wider (# Word# -> Limb
Limb Word#
w0, Word# -> Limb
Limb Word#
w1, Word# -> Limb
Limb Word#
w2, Word# -> Limb
Limb Word#
w3 #)

-- | Convert a 'Wider' word to an 'Integer'.
--
--   >>> from 1
--   1
from :: Wider -> Integer
from :: Wider -> Integer
from (Wider (# Limb Word#
w0, Limb Word#
w1, Limb Word#
w2, Limb Word#
w3 #)) =
        Word -> Integer
forall a b. (Integral a, Num b) => a -> b
fi (Word# -> Word
W# Word#
w3) Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
.<<. (Int
3 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
size)
    Integer -> Integer -> Integer
forall a. Bits a => a -> a -> a
.|. Word -> Integer
forall a b. (Integral a, Num b) => a -> b
fi (Word# -> Word
W# Word#
w2) Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
.<<. (Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
size)
    Integer -> Integer -> Integer
forall a. Bits a => a -> a -> a
.|. Word -> Integer
forall a b. (Integral a, Num b) => a -> b
fi (Word# -> Word
W# Word#
w1) Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
.<<. Int
size
    Integer -> Integer -> Integer
forall a. Bits a => a -> a -> a
.|. Word -> Integer
forall a b. (Integral a, Num b) => a -> b
fi (Word# -> Word
W# Word#
w0)
  where
    !size :: Int
size = Word -> Int
forall b. FiniteBits b => b -> Int
B.finiteBitSize (Word
0 :: Word)

-- constant-time selection-----------------------------------------------------

select#
  :: (# Limb, Limb, Limb, Limb #) -- ^ a
  -> (# Limb, Limb, Limb, Limb #) -- ^ b
  -> C.Choice                     -- ^ c
  -> (# Limb, Limb, Limb, Limb #) -- ^ result
select# :: (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
-> Choice
-> (# Limb, Limb, Limb, Limb #)
select# (# Limb, Limb, Limb, Limb #)
a (# Limb, Limb, Limb, Limb #)
b Choice
c =
  let !(# Limb Word#
a0, Limb Word#
a1, Limb Word#
a2, Limb Word#
a3 #) = (# Limb, Limb, Limb, Limb #)
a
      !(# Limb Word#
b0, Limb Word#
b1, Limb Word#
b2, Limb Word#
b3 #) = (# Limb, Limb, Limb, Limb #)
b
      !(# Word#
w0, Word#
w1, Word#
w2, Word#
w3 #) =
        (# Word#, Word#, Word#, Word# #)
-> (# Word#, Word#, Word#, Word# #)
-> Choice
-> (# Word#, Word#, Word#, Word# #)
C.select_wider# (# Word#
a0, Word#
a1, Word#
a2, Word#
a3 #) (# Word#
b0, Word#
b1, Word#
b2, Word#
b3 #) Choice
c
  in  (# Word# -> Limb
Limb Word#
w0, Word# -> Limb
Limb Word#
w1, Word# -> Limb
Limb Word#
w2, Word# -> Limb
Limb Word#
w3 #)
{-# INLINE select# #-}

-- | Return a if c is truthy, otherwise return b.
--
--   >>> import qualified Data.Choice as C
--   >>> select 0 1 (C.true# ())
--   1
select
  :: Wider    -- ^ a
  -> Wider    -- ^ b
  -> C.Choice -- ^ c
  -> Wider    -- ^ result
select :: Wider -> Wider -> Choice -> Wider
select (Wider (# Limb, Limb, Limb, Limb #)
a) (Wider (# Limb, Limb, Limb, Limb #)
b) Choice
c = (# Limb, Limb, Limb, Limb #) -> Wider
Wider ((# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
-> Choice
-> (# Limb, Limb, Limb, Limb #)
select# (# Limb, Limb, Limb, Limb #)
a (# Limb, Limb, Limb, Limb #)
b Choice
c)

-- bit manipulation -----------------------------------------------------------

shr1_c#
  :: (# Limb, Limb, Limb, Limb #)                 -- ^ argument
  -> (# (# Limb, Limb, Limb, Limb #), C.Choice #) -- ^ result, carry
shr1_c# :: (# Limb, Limb, Limb, Limb #)
-> (# (# Limb, Limb, Limb, Limb #), Choice #)
shr1_c# (# Limb
w0, Limb
w1, Limb
w2, Limb
w3 #) =
  let !s :: Int#
s = case Word -> Int
forall b. FiniteBits b => b -> Int
B.finiteBitSize (Word
0 :: Word) of I# Int#
m -> Int#
m Int# -> Int# -> Int#
Exts.-# Int#
1#
      !(# Limb
s3, Limb
c3 #) = (# Limb -> Int# -> Limb
L.shr# Limb
w3 Int#
1#, Limb -> Int# -> Limb
L.shl# Limb
w3 Int#
s #)
      !r3 :: Limb
r3           = Limb -> Limb -> Limb
L.or# Limb
s3 (Word# -> Limb
Limb Word#
0##)
      !(# Limb
s2, Limb
c2 #) = (# Limb -> Int# -> Limb
L.shr# Limb
w2 Int#
1#, Limb -> Int# -> Limb
L.shl# Limb
w2 Int#
s #)
      !r2 :: Limb
r2           = Limb -> Limb -> Limb
L.or# Limb
s2 Limb
c3
      !(# Limb
s1, Limb
c1 #) = (# Limb -> Int# -> Limb
L.shr# Limb
w1 Int#
1#, Limb -> Int# -> Limb
L.shl# Limb
w1 Int#
s #)
      !r1 :: Limb
r1           = Limb -> Limb -> Limb
L.or# Limb
s1 Limb
c2
      !(# Limb
s0, Limb
c0 #) = (# Limb -> Int# -> Limb
L.shr# Limb
w0 Int#
1#, Limb -> Int# -> Limb
L.shl# Limb
w0 Int#
s #)
      !r0 :: Limb
r0           = Limb -> Limb -> Limb
L.or# Limb
s0 Limb
c1
      !(Limb Word#
w)     = Limb -> Int# -> Limb
L.shr# Limb
c0 Int#
s
  in  (# (# Limb
r0, Limb
r1, Limb
r2, Limb
r3 #), Word# -> Choice
C.from_word# Word#
w #)
{-# INLINE shr1_c# #-}

-- | Constant-time 1-bit shift-right with carry, with a 'Choice'
--   indicating whether the lowest bit was set.
shr1_c :: Wider -> (# Wider, C.Choice #)
shr1_c :: Wider -> (# Wider, Choice #)
shr1_c (Wider (# Limb, Limb, Limb, Limb #)
w) =
  let !(# (# Limb, Limb, Limb, Limb #)
r, Choice
c #) = (# Limb, Limb, Limb, Limb #)
-> (# (# Limb, Limb, Limb, Limb #), Choice #)
shr1_c# (# Limb, Limb, Limb, Limb #)
w
  in  (# (# Limb, Limb, Limb, Limb #) -> Wider
Wider (# Limb, Limb, Limb, Limb #)
r, Choice
c #)

-- | Constant-time 1-bit shift-right.
--
--   >>> shr1 2
--   1
--   >>> shr1 1
--   0
shr1 :: Wider -> Wider
shr1 :: Wider -> Wider
shr1 (Wider (# Limb, Limb, Limb, Limb #)
w) =
  let !(# (# Limb, Limb, Limb, Limb #)
r, Choice
_ #) = (# Limb, Limb, Limb, Limb #)
-> (# (# Limb, Limb, Limb, Limb #), Choice #)
shr1_c# (# Limb, Limb, Limb, Limb #)
w
  in  (# Limb, Limb, Limb, Limb #) -> Wider
Wider (# Limb, Limb, Limb, Limb #)
r

shl1_c#
  :: (# Limb, Limb, Limb, Limb #)                 -- ^ argument
  -> (# (# Limb, Limb, Limb, Limb #), C.Choice #) -- ^ result, carry
shl1_c# :: (# Limb, Limb, Limb, Limb #)
-> (# (# Limb, Limb, Limb, Limb #), Choice #)
shl1_c# (# Limb
w0, Limb
w1, Limb
w2, Limb
w3 #) =
  let !s :: Int#
s = case Word -> Int
forall b. FiniteBits b => b -> Int
B.finiteBitSize (Word
0 :: Word) of I# Int#
m -> Int#
m Int# -> Int# -> Int#
Exts.-# Int#
1#
      !(# Limb
s0, Limb
c0 #) = (# Limb -> Int# -> Limb
L.shl# Limb
w0 Int#
1#, Limb -> Int# -> Limb
L.shr# Limb
w0 Int#
s #)
      !r0 :: Limb
r0           = Limb -> Limb -> Limb
L.or# Limb
s0 (Word# -> Limb
Limb Word#
0##)
      !(# Limb
s1, Limb
c1 #) = (# Limb -> Int# -> Limb
L.shl# Limb
w1 Int#
1#, Limb -> Int# -> Limb
L.shr# Limb
w1 Int#
s #)
      !r1 :: Limb
r1           = Limb -> Limb -> Limb
L.or# Limb
s1 Limb
c0
      !(# Limb
s2, Limb
c2 #) = (# Limb -> Int# -> Limb
L.shl# Limb
w2 Int#
1#, Limb -> Int# -> Limb
L.shr# Limb
w2 Int#
s #)
      !r2 :: Limb
r2           = Limb -> Limb -> Limb
L.or# Limb
s2 Limb
c1
      !(# Limb
s3, Limb
c3 #) = (# Limb -> Int# -> Limb
L.shl# Limb
w3 Int#
1#, Limb -> Int# -> Limb
L.shr# Limb
w3 Int#
s #)
      !r3 :: Limb
r3           = Limb -> Limb -> Limb
L.or# Limb
s3 Limb
c2
      !(Limb Word#
w)     = Limb -> Int# -> Limb
L.shl# Limb
c3 Int#
s
  in  (# (# Limb
r0, Limb
r1, Limb
r2, Limb
r3 #), Word# -> Choice
C.from_word# Word#
w #)
{-# INLINE shl1_c# #-}

-- | Constant-time 1-bit shift-left with carry, with a 'Choice' indicating
--   whether the highest bit was set.
shl1_c :: Wider -> (# Wider, C.Choice #)
shl1_c :: Wider -> (# Wider, Choice #)
shl1_c (Wider (# Limb, Limb, Limb, Limb #)
w) =
  let !(# (# Limb, Limb, Limb, Limb #)
r, Choice
c #) = (# Limb, Limb, Limb, Limb #)
-> (# (# Limb, Limb, Limb, Limb #), Choice #)
shl1_c# (# Limb, Limb, Limb, Limb #)
w
  in  (# (# Limb, Limb, Limb, Limb #) -> Wider
Wider (# Limb, Limb, Limb, Limb #)
r, Choice
c #)

-- | Constant-time 1-bit shift-left.
--
--   >>> shl1 1
--   2
--   >>> shl1 (2 ^ (255 :: Word))
--   0
shl1 :: Wider -> Wider
shl1 :: Wider -> Wider
shl1 (Wider (# Limb, Limb, Limb, Limb #)
w) =
  let !(# (# Limb, Limb, Limb, Limb #)
r, Choice
_ #) = (# Limb, Limb, Limb, Limb #)
-> (# (# Limb, Limb, Limb, Limb #), Choice #)
shl1_c# (# Limb, Limb, Limb, Limb #)
w
  in  (# Limb, Limb, Limb, Limb #) -> Wider
Wider (# Limb, Limb, Limb, Limb #)
r

shr_limb#
  :: (# Limb, Limb, Limb, Limb #)
  -> Int#
  -> (# (# Limb, Limb, Limb, Limb #), Limb #)
shr_limb# :: (# Limb, Limb, Limb, Limb #)
-> Int# -> (# (# Limb, Limb, Limb, Limb #), Limb #)
shr_limb# (# Limb
a0, Limb
a1, Limb
a2, Limb
a3 #) Int#
rs =
  let !size :: Int#
size = case Word -> Int
forall b. FiniteBits b => b -> Int
B.finiteBitSize (Word
0 :: Word) of I# Int#
m -> Int#
m
      !ls :: Int#
ls = Int#
size Int# -> Int# -> Int#
Exts.-# Int#
rs
      !(# Limb
l3, Limb
c3 #) = (# Limb -> Int# -> Limb
L.shr# Limb
a3 Int#
rs, Limb -> Int# -> Limb
L.shl# Limb
a3 Int#
ls #)
      !(# Limb
l2, Limb
c2 #) = (# Limb -> Limb -> Limb
L.or# (Limb -> Int# -> Limb
L.shr# Limb
a2 Int#
rs) Limb
c3, Limb -> Int# -> Limb
L.shl# Limb
a2 Int#
ls #)
      !(# Limb
l1, Limb
c1 #) = (# Limb -> Limb -> Limb
L.or# (Limb -> Int# -> Limb
L.shr# Limb
a1 Int#
rs) Limb
c2, Limb -> Int# -> Limb
L.shl# Limb
a1 Int#
ls #)
      !(# Limb
l0, Limb
c0 #) = (# Limb -> Limb -> Limb
L.or# (Limb -> Int# -> Limb
L.shr# Limb
a0 Int#
rs) Limb
c1, Limb -> Int# -> Limb
L.shl# Limb
a0 Int#
ls #)
  in  (# (# Limb
l0, Limb
l1, Limb
l2, Limb
l3 #), Limb
c0 #)
{-# INLINE shr_limb# #-}

-- | Shift right by less than the number of bits in a 'Limb' (e.g., by
--   a maximum of 63 bits on 64-bit architectures). The shift amount is
--   unchecked.
--
--   >>> shr_limb 2 1
--   1
shr_limb
  :: Wider -- ^ value
  -> Int   -- ^ right-shift amount (0 < s < WORD_SIZE)
  -> Wider -- ^ right-shifted value
shr_limb :: Wider -> Int -> Wider
shr_limb (Wider (# Limb, Limb, Limb, Limb #)
w) (I# Int#
s) =
  let !(# (# Limb, Limb, Limb, Limb #)
r, Limb
_ #) = (# Limb, Limb, Limb, Limb #)
-> Int# -> (# (# Limb, Limb, Limb, Limb #), Limb #)
shr_limb# (# Limb, Limb, Limb, Limb #)
w Int#
s
  in  (# Limb, Limb, Limb, Limb #) -> Wider
Wider (# Limb, Limb, Limb, Limb #)
r

shl_limb#
  :: (# Limb, Limb, Limb, Limb #)
  -> Int#
  -> (# (# Limb, Limb, Limb, Limb #), Limb #)
shl_limb# :: (# Limb, Limb, Limb, Limb #)
-> Int# -> (# (# Limb, Limb, Limb, Limb #), Limb #)
shl_limb# (# Limb
a0, Limb
a1, Limb
a2, Limb
a3 #) Int#
ls =
  let !size :: Int#
size = case Word -> Int
forall b. FiniteBits b => b -> Int
B.finiteBitSize (Word
0 :: Word) of I# Int#
m -> Int#
m
      !rs :: Int#
rs = Int#
size Int# -> Int# -> Int#
Exts.-# Int#
ls
      !(# Limb
l0, Limb
c0 #) = (# Limb -> Int# -> Limb
L.shl# Limb
a0 Int#
ls, Limb -> Int# -> Limb
L.shr# Limb
a0 Int#
rs #)
      !(# Limb
l1, Limb
c1 #) = (# Limb -> Limb -> Limb
L.or# (Limb -> Int# -> Limb
L.shl# Limb
a1 Int#
ls) Limb
c0, Limb -> Int# -> Limb
L.shr# Limb
a1 Int#
rs #)
      !(# Limb
l2, Limb
c2 #) = (# Limb -> Limb -> Limb
L.or# (Limb -> Int# -> Limb
L.shl# Limb
a2 Int#
ls) Limb
c1, Limb -> Int# -> Limb
L.shr# Limb
a2 Int#
rs #)
      !(# Limb
l3, Limb
c3 #) = (# Limb -> Limb -> Limb
L.or# (Limb -> Int# -> Limb
L.shl# Limb
a3 Int#
ls) Limb
c2, Limb -> Int# -> Limb
L.shr# Limb
a3 Int#
rs #)
  in  (# (# Limb
l0, Limb
l1, Limb
l2, Limb
l3 #), Limb
c3 #)
{-# INLINE shl_limb# #-}

-- | Shift left by less than the number of bits in a 'Limb' (e.g., by
--   a maximum of 63 bits on 64-bit architectures). The shift amount is
--   unchecked.
--
--   >>> shl_limb 2 1
--   1
--   >>> shl_limb 1 63
--   9223372036854775808
shl_limb
  :: Wider -- ^ value
  -> Int   -- ^ left-shift amount (0 < s < WORD_SIZE)
  -> Wider -- ^ left-shifted value
shl_limb :: Wider -> Int -> Wider
shl_limb (Wider (# Limb, Limb, Limb, Limb #)
w) (I# Int#
s) =
  let !(# (# Limb, Limb, Limb, Limb #)
r, Limb
_ #) = (# Limb, Limb, Limb, Limb #)
-> Int# -> (# (# Limb, Limb, Limb, Limb #), Limb #)
shl_limb# (# Limb, Limb, Limb, Limb #)
w Int#
s
  in  (# Limb, Limb, Limb, Limb #) -> Wider
Wider (# Limb, Limb, Limb, Limb #)
r

and_w#
  :: (# Limb, Limb, Limb, Limb #)
  -> (# Limb, Limb, Limb, Limb #)
  -> (# Limb, Limb, Limb, Limb #)
and_w# :: (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #) -> (# Limb, Limb, Limb, Limb #)
and_w# (# Limb
a0, Limb
a1, Limb
a2, Limb
a3 #) (# Limb
b0, Limb
b1, Limb
b2, Limb
b3 #) =
  (# Limb -> Limb -> Limb
L.and# Limb
a0 Limb
b0, Limb -> Limb -> Limb
L.and# Limb
a1 Limb
b1, Limb -> Limb -> Limb
L.and# Limb
a2 Limb
b2, Limb -> Limb -> Limb
L.and# Limb
a3 Limb
b3 #)
{-# INLINE and_w# #-}

-- | Binary /and/.
--
--   >>> and 1 1
--   1
--   >>> and 1 0
--   0
and
  :: Wider -- ^ a
  -> Wider -- ^ b
  -> Wider -- ^ a & b
and :: Wider -> Wider -> Wider
and (Wider (# Limb, Limb, Limb, Limb #)
a) (Wider (# Limb, Limb, Limb, Limb #)
b) = (# Limb, Limb, Limb, Limb #) -> Wider
Wider ((# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #) -> (# Limb, Limb, Limb, Limb #)
and_w# (# Limb, Limb, Limb, Limb #)
a (# Limb, Limb, Limb, Limb #)
b)

or_w#
  :: (# Limb, Limb, Limb, Limb #)
  -> (# Limb, Limb, Limb, Limb #)
  -> (# Limb, Limb, Limb, Limb #)
or_w# :: (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #) -> (# Limb, Limb, Limb, Limb #)
or_w# (# Limb
a0, Limb
a1, Limb
a2, Limb
a3 #) (# Limb
b0, Limb
b1, Limb
b2, Limb
b3 #) =
  (# Limb -> Limb -> Limb
L.or# Limb
a0 Limb
b0, Limb -> Limb -> Limb
L.or# Limb
a1 Limb
b1, Limb -> Limb -> Limb
L.or# Limb
a2 Limb
b2, Limb -> Limb -> Limb
L.or# Limb
a3 Limb
b3 #)
{-# INLINE or_w# #-}

-- | Binary /or/.
--
--   >>> or 1 1
--   1
--   >>> or 1 0
--   1
or
  :: Wider -- ^ a
  -> Wider -- ^ b
  -> Wider -- ^ a | b
or :: Wider -> Wider -> Wider
or (Wider (# Limb, Limb, Limb, Limb #)
a) (Wider (# Limb, Limb, Limb, Limb #)
b) = (# Limb, Limb, Limb, Limb #) -> Wider
Wider ((# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #) -> (# Limb, Limb, Limb, Limb #)
or_w# (# Limb, Limb, Limb, Limb #)
a (# Limb, Limb, Limb, Limb #)
b)

not#
  :: (# Limb, Limb, Limb, Limb #)
  -> (# Limb, Limb, Limb, Limb #)
not# :: (# Limb, Limb, Limb, Limb #) -> (# Limb, Limb, Limb, Limb #)
not# (# Limb
l0, Limb
l1, Limb
l2, Limb
l3 #) = (# Limb -> Limb
L.not# Limb
l0, Limb -> Limb
L.not# Limb
l1, Limb -> Limb
L.not# Limb
l2, Limb -> Limb
L.not# Limb
l3 #)
{-# INLINE not# #-}

-- | Binary /not/.
--
--   >>> not 0
--   115792089237316195423570985008687907853269984665640564039457584007913129639935
--   >>> not (not 0)
--   0
not
  :: Wider -- ^ value
  -> Wider -- ^ not value
not :: Wider -> Wider
not (Wider (# Limb, Limb, Limb, Limb #)
w) = (# Limb, Limb, Limb, Limb #) -> Wider
Wider ((# Limb, Limb, Limb, Limb #) -> (# Limb, Limb, Limb, Limb #)
not# (# Limb, Limb, Limb, Limb #)
w)

-- addition, subtraction ------------------------------------------------------

add_o#
  :: (# Limb, Limb, Limb, Limb #)             -- ^ augend
  -> (# Limb, Limb, Limb, Limb #)             -- ^ addend
  -> (# (# Limb, Limb, Limb, Limb #), Limb #) -- ^ (# sum, carry bit #)
add_o# :: (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
-> (# (# Limb, Limb, Limb, Limb #), Limb #)
add_o# (# Limb
a0, Limb
a1, Limb
a2, Limb
a3 #) (# Limb
b0, Limb
b1, Limb
b2, Limb
b3 #) =
  let !(# Limb
s0, Limb
c0 #) = Limb -> Limb -> (# Limb, Limb #)
L.add_o# Limb
a0 Limb
b0
      !(# Limb
s1, Limb
c1 #) = Limb -> Limb -> Limb -> (# Limb, Limb #)
L.add_c# Limb
a1 Limb
b1 Limb
c0
      !(# Limb
s2, Limb
c2 #) = Limb -> Limb -> Limb -> (# Limb, Limb #)
L.add_c# Limb
a2 Limb
b2 Limb
c1
      !(# Limb
s3, Limb
c3 #) = Limb -> Limb -> Limb -> (# Limb, Limb #)
L.add_c# Limb
a3 Limb
b3 Limb
c2
  in  (# (# Limb
s0, Limb
s1, Limb
s2, Limb
s3 #), Limb
c3 #)
{-# INLINE add_o# #-}

-- | Overflowing addition, computing 'a + b', returning the sum and a
--   carry bit.
--
--   >>> add_o 1 1
--   (2,0)
--   >>> add_o 1 (2 ^ (256 :: Word) - 1)
--   (0,1)
add_o
  :: Wider
  -> Wider
  -> (Wider, Word)
add_o :: Wider -> Wider -> (Wider, Word)
add_o (Wider (# Limb, Limb, Limb, Limb #)
a) (Wider (# Limb, Limb, Limb, Limb #)
b) =
  let !(# (# Limb, Limb, Limb, Limb #)
s, Limb Word#
c #) = (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
-> (# (# Limb, Limb, Limb, Limb #), Limb #)
add_o# (# Limb, Limb, Limb, Limb #)
a (# Limb, Limb, Limb, Limb #)
b
  in  ((# Limb, Limb, Limb, Limb #) -> Wider
Wider (# Limb, Limb, Limb, Limb #)
s, Word# -> Word
W# Word#
c)

add_w#
  :: (# Limb, Limb, Limb, Limb #) -- ^ augend
  -> (# Limb, Limb, Limb, Limb #) -- ^ addend
  -> (# Limb, Limb, Limb, Limb #) -- ^ sum
add_w# :: (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #) -> (# Limb, Limb, Limb, Limb #)
add_w# (# Limb, Limb, Limb, Limb #)
a (# Limb, Limb, Limb, Limb #)
b =
  let !(# (# Limb, Limb, Limb, Limb #)
c, Limb
_ #) = (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
-> (# (# Limb, Limb, Limb, Limb #), Limb #)
add_o# (# Limb, Limb, Limb, Limb #)
a (# Limb, Limb, Limb, Limb #)
b
  in  (# Limb, Limb, Limb, Limb #)
c
{-# INLINE add_w# #-}

-- | Wrapping addition, computing 'a + b'.
--
--   Note that as 'Wider' is an instance of 'Num', you can use '+' to apply
--   this function.
--
--   >>> add 1 (2 ^ (256 :: Word) - 1)
--   0
add
  :: Wider
  -> Wider
  -> Wider
add :: Wider -> Wider -> Wider
add (Wider (# Limb, Limb, Limb, Limb #)
a) (Wider (# Limb, Limb, Limb, Limb #)
b) = (# Limb, Limb, Limb, Limb #) -> Wider
Wider ((# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #) -> (# Limb, Limb, Limb, Limb #)
add_w# (# Limb, Limb, Limb, Limb #)
a (# Limb, Limb, Limb, Limb #)
b)
{-# INLINE add #-}

add_mod#
  :: (# Limb, Limb, Limb, Limb #) -- ^ augend
  -> (# Limb, Limb, Limb, Limb #) -- ^ addend
  -> (# Limb, Limb, Limb, Limb #) -- ^ modulus
  -> (# Limb, Limb, Limb, Limb #) -- ^ sum
add_mod# :: (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
add_mod# (# Limb, Limb, Limb, Limb #)
a (# Limb, Limb, Limb, Limb #)
b (# Limb, Limb, Limb, Limb #)
m =
  let !(# (# Limb, Limb, Limb, Limb #)
w, Limb
c #) = (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
-> (# (# Limb, Limb, Limb, Limb #), Limb #)
add_o# (# Limb, Limb, Limb, Limb #)
a (# Limb, Limb, Limb, Limb #)
b
  in  (# Limb, Limb, Limb, Limb #)
-> Limb
-> (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
sub_mod_c# (# Limb, Limb, Limb, Limb #)
w Limb
c (# Limb, Limb, Limb, Limb #)
m (# Limb, Limb, Limb, Limb #)
m
{-# INLINE add_mod# #-}

-- | Modular addition.
--
--   Assumes that the sum is less than twice the modulus; this is not
--   checked.
--
--   >>> add_mod 1 1 3
--   2
--   >>> add_mod 1 2 3
--   0
add_mod
  :: Wider -- ^ augend
  -> Wider -- ^ addend
  -> Wider -- ^ modulus
  -> Wider -- ^ sum
add_mod :: Wider -> Wider -> Wider -> Wider
add_mod (Wider (# Limb, Limb, Limb, Limb #)
a) (Wider (# Limb, Limb, Limb, Limb #)
b) (Wider (# Limb, Limb, Limb, Limb #)
m) = (# Limb, Limb, Limb, Limb #) -> Wider
Wider ((# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
add_mod# (# Limb, Limb, Limb, Limb #)
a (# Limb, Limb, Limb, Limb #)
b (# Limb, Limb, Limb, Limb #)
m)

sub_b#
  :: (# Limb, Limb, Limb, Limb #)              -- ^ minuend
  -> (# Limb, Limb, Limb, Limb #)              -- ^ subtrahend
  -> (# (# Limb, Limb, Limb, Limb #), Limb #) -- ^ (# diff, borrow mask #)
sub_b# :: (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
-> (# (# Limb, Limb, Limb, Limb #), Limb #)
sub_b# (# Limb
a0, Limb
a1, Limb
a2, Limb
a3 #) (# Limb
b0, Limb
b1, Limb
b2, Limb
b3 #) =
  let !(# Limb
s0, Limb
c0 #) = Limb -> Limb -> Limb -> (# Limb, Limb #)
L.sub_b# Limb
a0 Limb
b0 (Word# -> Limb
Limb Word#
0##)
      !(# Limb
s1, Limb
c1 #) = Limb -> Limb -> Limb -> (# Limb, Limb #)
L.sub_b# Limb
a1 Limb
b1 Limb
c0
      !(# Limb
s2, Limb
c2 #) = Limb -> Limb -> Limb -> (# Limb, Limb #)
L.sub_b# Limb
a2 Limb
b2 Limb
c1
      !(# Limb
s3, Limb
c3 #) = Limb -> Limb -> Limb -> (# Limb, Limb #)
L.sub_b# Limb
a3 Limb
b3 Limb
c2
  in  (# (# Limb
s0, Limb
s1, Limb
s2, Limb
s3 #), Limb
c3 #)
{-# INLINE sub_b# #-}

-- | Borrowing subtraction, computing 'a - b' and returning the
--   difference with a borrow mask.
--
--   >>> sub_b 1 1
--   (0,0)
--   >>> sub_b 0 (2 ^ (256 :: Word) - 1)
--   (1,18446744073709551615)
sub_b
  :: Wider         -- ^ minuend
  -> Wider         -- ^ subtrahend
  -> (Wider, Word) -- ^ (difference, borrow mask)
sub_b :: Wider -> Wider -> (Wider, Word)
sub_b (Wider (# Limb, Limb, Limb, Limb #)
l) (Wider (# Limb, Limb, Limb, Limb #)
r) =
  let !(# (# Limb, Limb, Limb, Limb #)
d, Limb Word#
b #) = (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
-> (# (# Limb, Limb, Limb, Limb #), Limb #)
sub_b# (# Limb, Limb, Limb, Limb #)
l (# Limb, Limb, Limb, Limb #)
r
  in  ((# Limb, Limb, Limb, Limb #) -> Wider
Wider (# Limb, Limb, Limb, Limb #)
d, Word# -> Word
W# Word#
b)

-- | Wrapping subtraction, computing 'a - b' and returning the
--   difference.
--
--   Note that as 'Wider' is an instance of 'Num', you can use '-' to apply
--   this function.
--
--   >>> sub 1 1
--   0
--   >>> sub 0 (2 ^ (256 :: Word) - 1)
--   1
sub
  :: Wider -- ^ minuend
  -> Wider -- ^ subtrahend
  -> Wider -- ^ difference
sub :: Wider -> Wider -> Wider
sub (Wider (# Limb, Limb, Limb, Limb #)
a) (Wider (# Limb, Limb, Limb, Limb #)
b) =
  let !(# (# Limb, Limb, Limb, Limb #)
d, Limb
_ #) = (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
-> (# (# Limb, Limb, Limb, Limb #), Limb #)
sub_b# (# Limb, Limb, Limb, Limb #)
a (# Limb, Limb, Limb, Limb #)
b
  in  (# Limb, Limb, Limb, Limb #) -> Wider
Wider (# Limb, Limb, Limb, Limb #)
d

sub_mod#
  :: (# Limb, Limb, Limb, Limb #) -- ^ minuend
  -> (# Limb, Limb, Limb, Limb #) -- ^ subtrahend
  -> (# Limb, Limb, Limb, Limb #) -- ^ modulus
  -> (# Limb, Limb, Limb, Limb #) -- ^ difference
sub_mod# :: (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
sub_mod# (# Limb, Limb, Limb, Limb #)
a (# Limb, Limb, Limb, Limb #)
b (# Limb
p0, Limb
p1, Limb
p2, Limb
p3 #) =
  let !(# (# Limb, Limb, Limb, Limb #)
o, Limb
m #) = (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
-> (# (# Limb, Limb, Limb, Limb #), Limb #)
sub_b# (# Limb, Limb, Limb, Limb #)
a (# Limb, Limb, Limb, Limb #)
b
      !ba :: (# Limb, Limb, Limb, Limb #)
ba = (# Limb -> Limb -> Limb
L.and# Limb
p0 Limb
m, Limb -> Limb -> Limb
L.and# Limb
p1 Limb
m, Limb -> Limb -> Limb
L.and# Limb
p2 Limb
m, Limb -> Limb -> Limb
L.and# Limb
p3 Limb
m #)
  in  (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #) -> (# Limb, Limb, Limb, Limb #)
add_w# (# Limb, Limb, Limb, Limb #)
o (# Limb, Limb, Limb, Limb #)
ba
{-# INLINE sub_mod# #-}

-- | Modular subtraction. Computes a - b mod m.
--
--   Assumes that the magnitude of the difference is less than the
--   modulus (this is unchecked).
--
--   >>> sub_mod 1 1 4
--   0
--   >>> sub_mod 2 3 4
--   3
sub_mod
  :: Wider
  -> Wider
  -> Wider
  -> Wider
sub_mod :: Wider -> Wider -> Wider -> Wider
sub_mod (Wider (# Limb, Limb, Limb, Limb #)
a) (Wider (# Limb, Limb, Limb, Limb #)
b) (Wider (# Limb, Limb, Limb, Limb #)
p) = (# Limb, Limb, Limb, Limb #) -> Wider
Wider ((# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
sub_mod# (# Limb, Limb, Limb, Limb #)
a (# Limb, Limb, Limb, Limb #)
b (# Limb, Limb, Limb, Limb #)
p)

-- | Modular subtraction with carry. Computes (# a, c #) - b mod m.
sub_mod_c#
  :: (# Limb, Limb, Limb, Limb #) -- ^ minuend
  -> Limb                         -- ^ carry bit
  -> (# Limb, Limb, Limb, Limb #) -- ^ subtrahend
  -> (# Limb, Limb, Limb, Limb #) -- ^ modulus
  -> (# Limb, Limb, Limb, Limb #) -- ^ difference
sub_mod_c# :: (# Limb, Limb, Limb, Limb #)
-> Limb
-> (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
sub_mod_c# (# Limb, Limb, Limb, Limb #)
a Limb
c (# Limb, Limb, Limb, Limb #)
b (# Limb
p0, Limb
p1, Limb
p2, Limb
p3 #) =
  let !(# (# Limb
o0, Limb
o1, Limb
o2, Limb
o3 #), Limb
bb #) = (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
-> (# (# Limb, Limb, Limb, Limb #), Limb #)
sub_b# (# Limb, Limb, Limb, Limb #)
a (# Limb, Limb, Limb, Limb #)
b
      !(# Limb
_, Limb
m #) = Limb -> Limb -> Limb -> (# Limb, Limb #)
L.sub_b# Limb
c (Word# -> Limb
Limb Word#
0##) Limb
bb
      !ba :: (# Limb, Limb, Limb, Limb #)
ba = (# Limb -> Limb -> Limb
L.and# Limb
p0 Limb
m, Limb -> Limb -> Limb
L.and# Limb
p1 Limb
m, Limb -> Limb -> Limb
L.and# Limb
p2 Limb
m, Limb -> Limb -> Limb
L.and# Limb
p3 Limb
m #)
  in  (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #) -> (# Limb, Limb, Limb, Limb #)
add_w# (# Limb
o0, Limb
o1, Limb
o2, Limb
o3 #) (# Limb, Limb, Limb, Limb #)
ba
{-# INLINE sub_mod_c# #-}

-- multiplication -------------------------------------------------------------

mul_c#
  :: (# Limb, Limb, Limb, Limb #)
  -> (# Limb, Limb, Limb, Limb #)
  -> (# (# Limb, Limb, Limb, Limb #), (# Limb, Limb, Limb, Limb #) #)
mul_c# :: (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
-> (# (# Limb, Limb, Limb, Limb #), (# Limb, Limb, Limb, Limb #) #)
mul_c# (# Limb
x0, Limb
x1, Limb
x2, Limb
x3 #) (# Limb
y0, Limb
y1, Limb
y2, Limb
y3 #) =
  let !(# Limb
z0, Limb
c0_0 #)   = Limb -> Limb -> Limb -> Limb -> (# Limb, Limb #)
L.mac# Limb
x0 Limb
y0 (Word# -> Limb
Limb Word#
0##) (Word# -> Limb
Limb Word#
0##)
      !(# Limb
s1_0, Limb
c1_0 #) = Limb -> Limb -> Limb -> Limb -> (# Limb, Limb #)
L.mac# Limb
x0 Limb
y1 (Word# -> Limb
Limb Word#
0##) Limb
c0_0
      !(# Limb
z1, Limb
c1_1 #)   = Limb -> Limb -> Limb -> Limb -> (# Limb, Limb #)
L.mac# Limb
x1 Limb
y0 Limb
s1_0 (Word# -> Limb
Limb Word#
0##)
      !(# Limb
s2_0, Limb
c2_0 #) = Limb -> Limb -> Limb -> Limb -> (# Limb, Limb #)
L.mac# Limb
x0 Limb
y2 (Word# -> Limb
Limb Word#
0##) Limb
c1_0
      !(# Limb
s2_1, Limb
c2_1 #) = Limb -> Limb -> Limb -> Limb -> (# Limb, Limb #)
L.mac# Limb
x1 Limb
y1 Limb
s2_0 Limb
c1_1
      !(# Limb
z2, Limb
c2_2 #)   = Limb -> Limb -> Limb -> Limb -> (# Limb, Limb #)
L.mac# Limb
x2 Limb
y0 Limb
s2_1 (Word# -> Limb
Limb Word#
0##)
      !(# Limb
s3_0, Limb
c3_0 #) = Limb -> Limb -> Limb -> Limb -> (# Limb, Limb #)
L.mac# Limb
x0 Limb
y3 (Word# -> Limb
Limb Word#
0##) Limb
c2_0
      !(# Limb
s3_1, Limb
c3_1 #) = Limb -> Limb -> Limb -> Limb -> (# Limb, Limb #)
L.mac# Limb
x1 Limb
y2 Limb
s3_0 Limb
c2_1
      !(# Limb
s3_2, Limb
c3_2 #) = Limb -> Limb -> Limb -> Limb -> (# Limb, Limb #)
L.mac# Limb
x2 Limb
y1 Limb
s3_1 Limb
c2_2
      !(# Limb
z3, Limb
c3_3 #)   = Limb -> Limb -> Limb -> Limb -> (# Limb, Limb #)
L.mac# Limb
x3 Limb
y0 Limb
s3_2 (Word# -> Limb
Limb Word#
0##)
      !(# Limb
s4_0, Limb
c4_0 #) = Limb -> Limb -> Limb -> Limb -> (# Limb, Limb #)
L.mac# Limb
x1 Limb
y3 (Word# -> Limb
Limb Word#
0##) Limb
c3_0
      !(# Limb
s4_1, Limb
c4_1 #) = Limb -> Limb -> Limb -> Limb -> (# Limb, Limb #)
L.mac# Limb
x2 Limb
y2 Limb
s4_0 Limb
c3_1
      !(# Limb
s4_2, Limb
c4_2 #) = Limb -> Limb -> Limb -> Limb -> (# Limb, Limb #)
L.mac# Limb
x3 Limb
y1 Limb
s4_1 Limb
c3_2
      !(# Limb
w4, Limb
c4_3 #)   = Limb -> Limb -> Limb -> (# Limb, Limb #)
L.add_c# Limb
s4_2 Limb
c3_3 (Word# -> Limb
Limb Word#
0##)
      !(# Limb
s5_0, Limb
c5_0 #) = Limb -> Limb -> Limb -> Limb -> (# Limb, Limb #)
L.mac# Limb
x2 Limb
y3 (Word# -> Limb
Limb Word#
0##) Limb
c4_0
      !(# Limb
s5_1, Limb
c5_1 #) = Limb -> Limb -> Limb -> Limb -> (# Limb, Limb #)
L.mac# Limb
x3 Limb
y2 Limb
s5_0 Limb
c4_1
      !(# Limb
w5, Limb
c5_2 #)   = Limb -> Limb -> Limb -> (# Limb, Limb #)
L.add_c# Limb
s5_1 Limb
c4_2 (Word# -> Limb
Limb Word#
0##)
      !(# Limb
w5f, Limb
c5_3 #)  = Limb -> Limb -> Limb -> (# Limb, Limb #)
L.add_c# Limb
w5 Limb
c4_3 (Word# -> Limb
Limb Word#
0##)
      !(# Limb
s6_0, Limb
c6_0 #) = Limb -> Limb -> Limb -> Limb -> (# Limb, Limb #)
L.mac# Limb
x3 Limb
y3 (Word# -> Limb
Limb Word#
0##) Limb
c5_0
      !(# Limb
w6, Limb
c6_1 #)   = Limb -> Limb -> Limb -> (# Limb, Limb #)
L.add_c# Limb
s6_0 Limb
c5_1 (Word# -> Limb
Limb Word#
0##)
      !(# Limb
w6f, Limb
c6_2 #)  = Limb -> Limb -> Limb -> (# Limb, Limb #)
L.add_c# Limb
w6 Limb
c5_2 (Word# -> Limb
Limb Word#
0##)
      !(# Limb
w6ff, Limb
c6_3 #) = Limb -> Limb -> Limb -> (# Limb, Limb #)
L.add_c# Limb
w6f Limb
c5_3 (Word# -> Limb
Limb Word#
0##)
      !(# Limb
w7, Limb
_ #)      = Limb -> Limb -> Limb -> (# Limb, Limb #)
L.add_c# Limb
c6_0 Limb
c6_1 (Word# -> Limb
Limb Word#
0##)
      !(# Limb
w7f, Limb
_ #)     = Limb -> Limb -> Limb -> (# Limb, Limb #)
L.add_c# Limb
w7 Limb
c6_2 (Word# -> Limb
Limb Word#
0##)
      !(# Limb
w7ff, Limb
_ #)    = Limb -> Limb -> Limb -> (# Limb, Limb #)
L.add_c# Limb
w7f Limb
c6_3 (Word# -> Limb
Limb Word#
0##)
  in  (# (# Limb
z0, Limb
z1, Limb
z2, Limb
z3 #), (# Limb
w4, Limb
w5f, Limb
w6ff, Limb
w7ff #) #)
{-# INLINE mul_c# #-}

-- | Widening multiplication.
--
--   Returns the low and high 'Wider' words of the product, in that
--   order.
--
--   >>> mul_c 2 3
--   (6,0)
--   >>> mul_c (2 ^ (256 :: Word) - 1)  2
--   (115792089237316195423570985008687907853269984665640564039457584007913129639934,1)
mul_c
  :: Wider
  -> Wider
  -> (Wider, Wider)
mul_c :: Wider -> Wider -> (Wider, Wider)
mul_c (Wider (# Limb, Limb, Limb, Limb #)
a) (Wider (# Limb, Limb, Limb, Limb #)
b) =
  let !(# (# Limb, Limb, Limb, Limb #)
l, (# Limb, Limb, Limb, Limb #)
h #) = (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
-> (# (# Limb, Limb, Limb, Limb #), (# Limb, Limb, Limb, Limb #) #)
mul_c# (# Limb, Limb, Limb, Limb #)
a (# Limb, Limb, Limb, Limb #)
b
  in  ((# Limb, Limb, Limb, Limb #) -> Wider
Wider (# Limb, Limb, Limb, Limb #)
l, (# Limb, Limb, Limb, Limb #) -> Wider
Wider (# Limb, Limb, Limb, Limb #)
h)

-- | Wrapping multiplication.
--
--   Note that as 'Wider' is an instance of 'Num', you can use '*' to apply
--   this function.
--
--   >>> mul 1 1
--   1
--   >>> mul 1 2
--   2
mul
  :: Wider
  -> Wider
  -> Wider
mul :: Wider -> Wider -> Wider
mul (Wider (# Limb, Limb, Limb, Limb #)
a) (Wider (# Limb, Limb, Limb, Limb #)
b) =
  let !(# (# Limb, Limb, Limb, Limb #)
l, (# Limb, Limb, Limb, Limb #)
_ #) = (# Limb, Limb, Limb, Limb #)
-> (# Limb, Limb, Limb, Limb #)
-> (# (# Limb, Limb, Limb, Limb #), (# Limb, Limb, Limb, Limb #) #)
mul_c# (# Limb, Limb, Limb, Limb #)
a (# Limb, Limb, Limb, Limb #)
b
  in  (# Limb, Limb, Limb, Limb #) -> Wider
Wider (# Limb, Limb, Limb, Limb #)
l

sqr#
  :: (# Limb, Limb, Limb, Limb #)
  -> (# (# Limb, Limb, Limb, Limb #), (# Limb, Limb, Limb, Limb #) #)
sqr# :: (# Limb, Limb, Limb, Limb #)
-> (# (# Limb, Limb, Limb, Limb #), (# Limb, Limb, Limb, Limb #) #)
sqr# (# Limb
x0, Limb
x1, Limb
x2, Limb
x3 #) =
  let !sh :: Int#
sh = case Word -> Int
forall b. FiniteBits b => b -> Int
B.finiteBitSize (Word
0 :: Word) of I# Int#
m -> Int#
m Int# -> Int# -> Int#
Exts.-# Int#
1#
      !(# Limb
q1_0, Limb
c1_0 #)  = Limb -> Limb -> Limb -> Limb -> (# Limb, Limb #)
L.mac# Limb
x1 Limb
x0 (Word# -> Limb
Limb Word#
0##) (Word# -> Limb
Limb Word#
0##)
      !r1 :: Limb
r1                = Limb
c1_0
      !(# Limb
r2_0, Limb
c2_0 #)  = Limb -> Limb -> Limb -> Limb -> (# Limb, Limb #)
L.mac# Limb
x2 Limb
x0 Limb
r1 (Word# -> Limb
Limb Word#
0##)
      !(# Limb
s2_1, Limb
c2_1 #)  = Limb -> Limb -> Limb -> Limb -> (# Limb, Limb #)
L.mac# Limb
x2 Limb
x1 (Word# -> Limb
Limb Word#
0##) Limb
c2_0
      !t2 :: Limb
t2                = Limb
c2_1
      !(# Limb
s3_0, Limb
c3_0 #)  = Limb -> Limb -> Limb -> Limb -> (# Limb, Limb #)
L.mac# Limb
x3 Limb
x0 Limb
s2_1 (Word# -> Limb
Limb Word#
0##)
      !(# Limb
t3, Limb
c3_1 #)    = Limb -> Limb -> Limb -> Limb -> (# Limb, Limb #)
L.mac# Limb
x3 Limb
x1 Limb
t2 Limb
c3_0
      !(# Limb
u3, Limb
c3_2 #)    = Limb -> Limb -> Limb -> Limb -> (# Limb, Limb #)
L.mac# Limb
x3 Limb
x2 (Word# -> Limb
Limb Word#
0##) Limb
c3_1
      !v3 :: Limb
v3                = Limb
c3_2
      !(# Limb
lo1, Limb
car0_1 #) = (# Limb -> Int# -> Limb
L.shl# Limb
q1_0 Int#
1#, Limb -> Int# -> Limb
L.shr# Limb
q1_0 Int#
sh #)
      !(# Limb
lo2, Limb
car0_2 #) = (# Limb -> Limb -> Limb
L.or# (Limb -> Int# -> Limb
L.shl# Limb
r2_0 Int#
1#) Limb
car0_1, Limb -> Int# -> Limb
L.shr# Limb
r2_0 Int#
sh #)
      !(# Limb
lo3, Limb
car0_3 #) = (# Limb -> Limb -> Limb
L.or# (Limb -> Int# -> Limb
L.shl# Limb
s3_0 Int#
1#) Limb
car0_2, Limb -> Int# -> Limb
L.shr# Limb
s3_0 Int#
sh #)
      !(# Limb
hi0, Limb
car1_0 #) = (# Limb -> Limb -> Limb
L.or# (Limb -> Int# -> Limb
L.shl# Limb
t3 Int#
1#) Limb
car0_3, Limb -> Int# -> Limb
L.shr# Limb
t3 Int#
sh #)
      !(# Limb
hi1, Limb
car1_1 #) = (# Limb -> Limb -> Limb
L.or# (Limb -> Int# -> Limb
L.shl# Limb
u3 Int#
1#) Limb
car1_0, Limb -> Int# -> Limb
L.shr# Limb
u3 Int#
sh #)
      !(# Limb
hi2, Limb
car1_2 #) = (# Limb -> Limb -> Limb
L.or# (Limb -> Int# -> Limb
L.shl# Limb
v3 Int#
1#) Limb
car1_1, Limb -> Int# -> Limb
L.shr# Limb
v3 Int#
sh #)
      !hi3 :: Limb
hi3               = Limb
car1_2
      !(# Limb
pf, Limb
car2_0 #)  = Limb -> Limb -> Limb -> Limb -> (# Limb, Limb #)
L.mac# Limb
x0 Limb
x0 (Word# -> Limb
Limb Word#
0##) (Word# -> Limb
Limb Word#
0##)
      !(# Limb
qf, Limb
car2_1 #)  = Limb -> Limb -> Limb -> (# Limb, Limb #)
L.add_c# Limb
lo1 Limb
car2_0 (Word# -> Limb
Limb Word#
0##)
      !(# Limb
rf, Limb
car2_2 #)  = Limb -> Limb -> Limb -> Limb -> (# Limb, Limb #)
L.mac# Limb
x1 Limb
x1 Limb
lo2 Limb
car2_1
      !(# Limb
sf, Limb
car2_3 #)  = Limb -> Limb -> Limb -> (# Limb, Limb #)
L.add_c# Limb
lo3 Limb
car2_2 (Word# -> Limb
Limb Word#
0##)
      !(# Limb
tf, Limb
car2_4 #)  = Limb -> Limb -> Limb -> Limb -> (# Limb, Limb #)
L.mac# Limb
x2 Limb
x2 Limb
hi0 Limb
car2_3
      !(# Limb
uf, Limb
car2_5 #)  = Limb -> Limb -> Limb -> (# Limb, Limb #)
L.add_c# Limb
hi1 Limb
car2_4 (Word# -> Limb
Limb Word#
0##)
      !(# Limb
vf, Limb
car2_6 #)  = Limb -> Limb -> Limb -> Limb -> (# Limb, Limb #)
L.mac# Limb
x3 Limb
x3 Limb
hi2 Limb
car2_5
      !(# Limb
wf, Limb
_      #)  = Limb -> Limb -> Limb -> (# Limb, Limb #)
L.add_c# Limb
hi3 Limb
car2_6 (Word# -> Limb
Limb Word#
0##)
  in  (# (# Limb
pf, Limb
qf, Limb
rf, Limb
sf #), (# Limb
tf, Limb
uf, Limb
vf, Limb
wf #) #)
{-# INLINE sqr# #-}

-- | Widening square.
--
--   >>> sqr 2
--   (4,0)
--   >>> sqr (2 ^ (256 :: Word) - 1)
--   (1,115792089237316195423570985008687907853269984665640564039457584007913129639934)
sqr :: Wider -> (Wider, Wider)
sqr :: Wider -> (Wider, Wider)
sqr (Wider (# Limb, Limb, Limb, Limb #)
w) =
  let !(# (# Limb, Limb, Limb, Limb #)
l, (# Limb, Limb, Limb, Limb #)
h #) = (# Limb, Limb, Limb, Limb #)
-> (# (# Limb, Limb, Limb, Limb #), (# Limb, Limb, Limb, Limb #) #)
sqr# (# Limb, Limb, Limb, Limb #)
w
  in  ((# Limb, Limb, Limb, Limb #) -> Wider
Wider (# Limb, Limb, Limb, Limb #)
l, (# Limb, Limb, Limb, Limb #) -> Wider
Wider (# Limb, Limb, Limb, Limb #)
h)

odd# :: (# Limb, Limb, Limb, Limb #) -> C.Choice
odd# :: (# Limb, Limb, Limb, Limb #) -> Choice
odd# (# Limb Word#
w, Limb
_, Limb
_, Limb
_ #) = Word# -> Choice
C.from_word# (Word# -> Word# -> Word#
Exts.and# Word#
w Word#
1##)
{-# INLINE odd# #-}

-- | Check if a 'Wider' is odd, returning a 'Choice'.
odd
  :: Wider
  -> C.Choice
odd :: Wider -> Choice
odd (Wider (# Limb, Limb, Limb, Limb #)
w) = (# Limb, Limb, Limb, Limb #) -> Choice
odd# (# Limb, Limb, Limb, Limb #)
w