{-# OPTIONS_HADDOCK prune #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE NumericUnderscores #-}
{-# LANGUAGE PatternSynonyms #-}
{-# 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_vartime
  , from_vartime

  -- * Comparison
  , eq_vartime
  , cmp_vartime
  , 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#
  , or
  , or#
  , xor
  , xor#
  , 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(..), Word#, 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 ----------------------------------------------------------------

type Limb4 = (# Limb, Limb, Limb, Limb #)

pattern L4 :: Word# -> Word# -> Word# -> Word# -> Limb4
pattern $mL4 :: forall {r}.
Limb4
-> (Word# -> Word# -> Word# -> Word# -> r) -> ((# #) -> r) -> r
$bL4 :: Word# -> Word# -> Word# -> Word# -> Limb4
L4 w0 w1 w2 w3 = (# Limb w0, Limb w1, Limb w2, Limb w3 #)
{-# COMPLETE L4 #-}

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

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_vartime

-- | Note that 'fromInteger' necessarily runs in variable time due
--   to conversion from the variable-size, potentially heap-allocated
--   'Integer' type.
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_vartime
  negate :: Wider -> Wider
negate Wider
w = Wider -> Wider -> Wider
add (Wider -> Wider
not Wider
w) (Limb4 -> Wider
Wider (Word# -> Word# -> Word# -> Word# -> Limb4
L4 Word#
1## Word#
0## Word#
0## Word#
0##))
  signum :: Wider -> Wider
signum (Wider (# Limb
l0, Limb
l1, Limb
l2, Limb
l3 #)) =
    let !(Limb Word#
l) = Limb
l0 Limb -> Limb -> Limb
`L.or#` Limb
l1 Limb -> Limb -> Limb
`L.or#` Limb
l2 Limb -> Limb -> Limb
`L.or#` Limb
l3
        !n :: Choice
n = Word# -> Choice
C.from_word_nonzero# Word#
l
        !b :: Word#
b = Choice -> Word#
C.to_word# Choice
n
    in  Limb4 -> Wider
Wider (Word# -> Word# -> Word# -> Word# -> Limb4
L4 Word#
b Word#
0## Word#
0## Word#
0##)

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

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

eq#
  :: Limb4
  -> Limb4
  -> C.Choice
eq# :: Limb4 -> Limb4 -> Choice
eq# Limb4
a Limb4
b =
  let !(L4 Word#
a0 Word#
a1 Word#
a2 Word#
a3) = Limb4
a
      !(L4 Word#
b0 Word#
b1 Word#
b2 Word#
b3) = Limb4
b
  in  Limb4 -> Limb4 -> 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)
{-# INLINABLE eq_vartime #-}

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

-- | Constant-time less-than comparison between 'Wider' values.
--
--   >>> import qualified Data.Choice as CT
--   >>> CT.decide (lt 1 2)
--   True
--   >>> CT.decide (lt 1 1)
--   False
lt :: Wider -> Wider -> C.Choice
lt :: Wider -> Wider -> Choice
lt (Wider Limb4
a) (Wider Limb4
b) = Limb4 -> Limb4 -> Choice
lt# Limb4
a Limb4
b
{-# INLINABLE lt #-}

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

-- | Constant-time greater-than comparison between 'Wider' values.
--
--   >>> import qualified Data.Choice as CT
--   >>> CT.decide (gt 1 2)
--   False
--   >>> CT.decide (gt 2 1)
--   True
gt :: Wider -> Wider -> C.Choice
gt :: Wider -> Wider -> Choice
gt (Wider Limb4
a) (Wider Limb4
b) = Limb4 -> Limb4 -> Choice
gt# Limb4
a Limb4
b
{-# INLINABLE gt #-}

cmp#
  :: Limb4
  -> Limb4
  -> Int#
cmp# :: Limb4 -> Limb4 -> 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# #-}

-- | Variable-time comparison between 'Wider' words.
--
--   The actual comparison here is performed in constant time, but we must
--   branch to return an 'Ordering'.
--
--   >>> cmp_vartime 1 2
--   LT
--   >>> cmp_vartime 2 1
--   GT
--   >>> cmp_vartime 2 2
--   EQ
cmp_vartime :: Wider -> Wider -> Ordering
cmp_vartime :: Wider -> Wider -> Ordering
cmp_vartime (Wider Limb4
a) (Wider Limb4
b) = case Limb4 -> Limb4 -> Int#
cmp# Limb4
a Limb4
b of
  Int#
1#  -> Ordering
GT
  Int#
0#  -> Ordering
EQ
  Int#
_   -> Ordering
LT
{-# INLINABLE cmp_vartime #-}

-- 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) = Limb4 -> Wider
Wider (Word# -> Word# -> Word# -> Word# -> Limb4
L4 Word#
w0 Word#
w1 Word#
w2 Word#
w3)
{-# INLINABLE wider #-}

-- | Convert an 'Integer' to a 'Wider' word.
--
--   >>> to_vartime 1
--   1
to_vartime :: Integer -> Wider
to_vartime :: Integer -> Wider
to_vartime 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  Limb4 -> Wider
Wider (Word# -> Word# -> Word# -> Word# -> Limb4
L4 Word#
w0 Word#
w1 Word#
w2 Word#
w3)
{-# INLINABLE to_vartime #-}

-- | Convert a 'Wider' word to an 'Integer'.
--
--   >>> from_vartime 1
--   1
from_vartime :: Wider -> Integer
from_vartime :: Wider -> Integer
from_vartime (Wider (L4 Word#
w0 Word#
w1 Word#
w2 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)
{-# INLINABLE from_vartime #-}

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

select#
  :: Limb4    -- ^ a
  -> Limb4    -- ^ b
  -> C.Choice -- ^ c
  -> Limb4    -- ^ result
select# :: Limb4 -> Limb4 -> Choice -> Limb4
select# (L4 Word#
a0 Word#
a1 Word#
a2 Word#
a3) (L4 Word#
b0 Word#
b1 Word#
b2 Word#
b3) Choice
c =
  let !(# Word#
w0, Word#
w1, Word#
w2, Word#
w3 #) =
        Limb4 -> Limb4 -> Choice -> Limb4
C.select_wider# (# Word#
a0, Word#
a1, Word#
a2, Word#
a3 #) (# Word#
b0, Word#
b1, Word#
b2, Word#
b3 #) Choice
c
  in  Word# -> Word# -> Word# -> Word# -> Limb4
L4 Word#
w0 Word#
w1 Word#
w2 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 Limb4
a) (Wider Limb4
b) Choice
c = Limb4 -> Wider
Wider (Limb4 -> Limb4 -> Choice -> Limb4
select# Limb4
a Limb4
b Choice
c)
{-# INLINABLE select #-}

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

shr1_c#
  :: Limb4                 -- ^ argument
  -> (# Limb4, C.Choice #) -- ^ result, carry
shr1_c# :: Limb4 -> (# Limb4, 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_bit# 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 Limb4
w) =
  let !(# Limb4
r, Choice
c #) = Limb4 -> (# Limb4, Choice #)
shr1_c# Limb4
w
  in  (# Limb4 -> Wider
Wider Limb4
r, Choice
c #)
{-# INLINABLE shr1_c #-}

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

shl1_c#
  :: Limb4                 -- ^ argument
  -> (# Limb4, C.Choice #) -- ^ result, carry
shl1_c# :: Limb4 -> (# Limb4, 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_bit# 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 Limb4
w) =
  let !(# Limb4
r, Choice
c #) = Limb4 -> (# Limb4, Choice #)
shl1_c# Limb4
w
  in  (# Limb4 -> Wider
Wider Limb4
r, Choice
c #)
{-# INLINABLE shl1_c #-}

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

shr_limb#
  :: Limb4
  -> Int#
  -> (# Limb4, Limb #)
shr_limb# :: Limb4 -> Int# -> (# Limb4, Limb #)
shr_limb# (# Limb
a0, Limb
a1, Limb
a2, Limb
a3 #) Int#
rs =
  let !ls :: Int#
ls = 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#
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 Limb4
w) (I# Int#
s) =
  let !(# Limb4
r, Limb
_ #) = Limb4 -> Int# -> (# Limb4, Limb #)
shr_limb# Limb4
w Int#
s
  in  Limb4 -> Wider
Wider Limb4
r
{-# INLINABLE shr_limb #-}

shl_limb#
  :: Limb4
  -> Int#
  -> (# Limb4, Limb #)
shl_limb# :: Limb4 -> Int# -> (# Limb4, Limb #)
shl_limb# (# Limb
a0, Limb
a1, Limb
a2, Limb
a3 #) Int#
ls =
  let !rs :: Int#
rs = 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#
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 Limb4
w) (I# Int#
s) =
  let !(# Limb4
r, Limb
_ #) = Limb4 -> Int# -> (# Limb4, Limb #)
shl_limb# Limb4
w Int#
s
  in  Limb4 -> Wider
Wider Limb4
r
{-# INLINABLE shl_limb #-}

and#
  :: Limb4
  -> Limb4
  -> Limb4
and# :: Limb4 -> Limb4 -> Limb4
and# (# 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# #-}

-- | Binary /and/.
--
--   >>> and 1 1
--   1
--   >>> and 1 0
--   0
and
  :: Wider -- ^ a
  -> Wider -- ^ b
  -> Wider -- ^ a & b
and :: Wider -> Wider -> Wider
and (Wider Limb4
a) (Wider Limb4
b) = Limb4 -> Wider
Wider (Limb4 -> Limb4 -> Limb4
and# Limb4
a Limb4
b)
{-# INLINABLE and #-}

or#
  :: Limb4
  -> Limb4
  -> Limb4
or# :: Limb4 -> Limb4 -> Limb4
or# (# 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# #-}

-- | Binary /or/.
--
--   >>> or 1 1
--   1
--   >>> or 1 0
--   1
or
  :: Wider -- ^ a
  -> Wider -- ^ b
  -> Wider -- ^ a | b
or :: Wider -> Wider -> Wider
or (Wider Limb4
a) (Wider Limb4
b) = Limb4 -> Wider
Wider (Limb4 -> Limb4 -> Limb4
or# Limb4
a Limb4
b)
{-# INLINABLE or #-}

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

-- | Binary /xor/.
--
--   >>> xor 1 1
--   0
--   >>> xor 1 0
--   1
xor
  :: Wider -- ^ a
  -> Wider -- ^ b
  -> Wider -- ^ a ^ b
xor :: Wider -> Wider -> Wider
xor (Wider Limb4
a) (Wider Limb4
b) = Limb4 -> Wider
Wider (Limb4 -> Limb4 -> Limb4
xor# Limb4
a Limb4
b)
{-# INLINABLE xor #-}

not#
  :: Limb4
  -> Limb4
not# :: Limb4 -> Limb4
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 Limb4
w) = Limb4 -> Wider
Wider (Limb4 -> Limb4
not# Limb4
w)
{-# INLINABLE not #-}

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

add_o#
  :: Limb4             -- ^ augend
  -> Limb4             -- ^ addend
  -> (# Limb4, Limb #) -- ^ (# sum, carry bit #)
add_o# :: Limb4 -> Limb4 -> (# Limb4, 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          -- ^ augend
  -> Wider          -- ^ addend
  -> (Wider, Word)  -- ^ (sum, carry bit)
add_o :: Wider -> Wider -> (Wider, Word)
add_o (Wider Limb4
a) (Wider Limb4
b) =
  let !(# Limb4
s, Limb Word#
c #) = Limb4 -> Limb4 -> (# Limb4, Limb #)
add_o# Limb4
a Limb4
b
  in  (Limb4 -> Wider
Wider Limb4
s, Word# -> Word
W# Word#
c)
{-# INLINABLE add_o #-}

add_w#
  :: Limb4 -- ^ augend
  -> Limb4 -- ^ addend
  -> Limb4 -- ^ sum
add_w# :: Limb4 -> Limb4 -> Limb4
add_w# Limb4
a Limb4
b =
  let !(# Limb4
c, Limb
_ #) = Limb4 -> Limb4 -> (# Limb4, Limb #)
add_o# Limb4
a Limb4
b
  in  Limb4
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 Limb4
a) (Wider Limb4
b) = Limb4 -> Wider
Wider (Limb4 -> Limb4 -> Limb4
add_w# Limb4
a Limb4
b)
{-# INLINE add #-}

add_mod#
  :: Limb4 -- ^ augend
  -> Limb4 -- ^ addend
  -> Limb4 -- ^ modulus
  -> Limb4 -- ^ sum
add_mod# :: Limb4 -> Limb4 -> Limb4 -> Limb4
add_mod# Limb4
a Limb4
b Limb4
m =
  let !(# Limb4
w, Limb
c #) = Limb4 -> Limb4 -> (# Limb4, Limb #)
add_o# Limb4
a Limb4
b
  in  Limb4 -> Limb -> Limb4 -> Limb4 -> Limb4
sub_mod_c# Limb4
w Limb
c Limb4
m Limb4
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 Limb4
a) (Wider Limb4
b) (Wider Limb4
m) = Limb4 -> Wider
Wider (Limb4 -> Limb4 -> Limb4 -> Limb4
add_mod# Limb4
a Limb4
b Limb4
m)
{-# INLINABLE add_mod #-}

sub_b#
  :: Limb4              -- ^ minuend
  -> Limb4              -- ^ subtrahend
  -> (# Limb4, Limb #) -- ^ (# diff, borrow mask #)
sub_b# :: Limb4 -> Limb4 -> (# Limb4, 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 Limb4
l) (Wider Limb4
r) =
  let !(# Limb4
d, Limb Word#
b #) = Limb4 -> Limb4 -> (# Limb4, Limb #)
sub_b# Limb4
l Limb4
r
  in  (Limb4 -> Wider
Wider Limb4
d, Word# -> Word
W# Word#
b)
{-# INLINABLE sub_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 Limb4
a) (Wider Limb4
b) =
  let !(# Limb4
d, Limb
_ #) = Limb4 -> Limb4 -> (# Limb4, Limb #)
sub_b# Limb4
a Limb4
b
  in  Limb4 -> Wider
Wider Limb4
d
{-# INLINABLE sub #-}

sub_mod#
  :: Limb4 -- ^ minuend
  -> Limb4 -- ^ subtrahend
  -> Limb4 -- ^ modulus
  -> Limb4 -- ^ difference
sub_mod# :: Limb4 -> Limb4 -> Limb4 -> Limb4
sub_mod# Limb4
a Limb4
b (# Limb
p0, Limb
p1, Limb
p2, Limb
p3 #) =
  let !(# Limb4
o, Limb
m #) = Limb4 -> Limb4 -> (# Limb4, Limb #)
sub_b# Limb4
a Limb4
b
      !ba :: Limb4
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  Limb4 -> Limb4 -> Limb4
add_w# Limb4
o Limb4
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 Limb4
a) (Wider Limb4
b) (Wider Limb4
p) = Limb4 -> Wider
Wider (Limb4 -> Limb4 -> Limb4 -> Limb4
sub_mod# Limb4
a Limb4
b Limb4
p)
{-# INLINABLE sub_mod #-}

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

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

mul_c#
  :: Limb4
  -> Limb4
  -> (# Limb4, Limb4 #)
mul_c# :: Limb4 -> Limb4 -> (# Limb4, Limb4 #)
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 Limb4
a) (Wider Limb4
b) =
  let !(# Limb4
l, Limb4
h #) = Limb4 -> Limb4 -> (# Limb4, Limb4 #)
mul_c# Limb4
a Limb4
b
  in  (Limb4 -> Wider
Wider Limb4
l, Limb4 -> Wider
Wider Limb4
h)
{-# INLINABLE mul_c #-}

-- | 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 Limb4
a) (Wider Limb4
b) =
  let !(# Limb4
l, Limb4
_ #) = Limb4 -> Limb4 -> (# Limb4, Limb4 #)
mul_c# Limb4
a Limb4
b
  in  Limb4 -> Wider
Wider Limb4
l
{-# INLINABLE mul #-}

sqr#
  :: Limb4
  -> (# Limb4, Limb4 #)
sqr# :: Limb4 -> (# Limb4, Limb4 #)
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 Limb4
w) =
  let !(# Limb4
l, Limb4
h #) = Limb4 -> (# Limb4, Limb4 #)
sqr# Limb4
w
  in  (Limb4 -> Wider
Wider Limb4
l, Limb4 -> Wider
Wider Limb4
h)
{-# INLINABLE sqr #-}

odd# :: Limb4 -> C.Choice
odd# :: Limb4 -> Choice
odd# (# Limb
l, Limb
_, Limb
_, Limb
_ #) =
  let !(Limb Word#
w) = Limb -> Limb -> Limb
L.and# Limb
l (Word# -> Limb
Limb Word#
1##)
  in  Word# -> Choice
C.from_bit# Word#
w
{-# INLINE odd# #-}

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