{-# LANGUAGE ConstraintKinds #-}
{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE UndecidableInstances #-}
module Data.Array.Accelerate.Internal.BigWord (
Word96,
Word128,
Word160,
Word192,
Word224,
Word256,
Word512,
BigWord(..)
) where
import Data.Bits
import Data.Ratio
import Data.Word
import GHC.Generics
import {-# SOURCE #-} Data.Array.Accelerate.Internal.BigInt
import Data.Array.Accelerate.Internal.Num2
type Word96 = BigWord Word32 Word64
type Word128 = BigWord Word64 Word64
type Word160 = BigWord Word32 Word128
type Word192 = BigWord Word64 Word128
type Word224 = BigWord Word32 Word192
type Word256 = BigWord Word128 Word128
type Word512 = BigWord Word256 Word256
data BigWord hi lo = W2 !hi !lo deriving (forall x. BigWord hi lo -> Rep (BigWord hi lo) x)
-> (forall x. Rep (BigWord hi lo) x -> BigWord hi lo)
-> Generic (BigWord hi lo)
forall x. Rep (BigWord hi lo) x -> BigWord hi lo
forall x. BigWord hi lo -> Rep (BigWord hi lo) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall hi lo x. Rep (BigWord hi lo) x -> BigWord hi lo
forall hi lo x. BigWord hi lo -> Rep (BigWord hi lo) x
$cto :: forall hi lo x. Rep (BigWord hi lo) x -> BigWord hi lo
$cfrom :: forall hi lo x. BigWord hi lo -> Rep (BigWord hi lo) x
Generic
type BigWordCtx hi lo = (hi ~ Unsigned hi, lo ~ Unsigned lo)
instance Integral (BigWord a b) => Show (BigWord a b) where
show :: BigWord a b -> String
show = Integer -> String
forall a. Show a => a -> String
show (Integer -> String)
-> (BigWord a b -> Integer) -> BigWord a b -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. BigWord a b -> Integer
forall a. Integral a => a -> Integer
toInteger
instance (Bounded a, Bounded b) => Bounded (BigWord a b) where
minBound :: BigWord a b
minBound = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
forall a. Bounded a => a
minBound b
forall a. Bounded a => a
minBound
maxBound :: BigWord a b
maxBound = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
forall a. Bounded a => a
maxBound b
forall a. Bounded a => a
maxBound
instance (Num a, Enum a, Bits a, Num b, Enum b, Bounded b, Eq b)
=> Enum (BigWord a b) where
succ :: BigWord a b -> BigWord a b
succ (W2 a
hi b
lo)
| b
lo b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
forall a. Bounded a => a
maxBound = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 (a -> a
forall a. Enum a => a -> a
succ a
hi) b
forall a. Bounded a => a
minBound
| Bool
otherwise = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
hi (b -> b
forall a. Enum a => a -> a
succ b
lo)
pred :: BigWord a b -> BigWord a b
pred (W2 a
hi b
lo)
| b
lo b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
forall a. Bounded a => a
minBound = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 (a -> a
forall a. Enum a => a -> a
pred a
hi) b
forall a. Bounded a => a
maxBound
| Bool
otherwise = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
hi (b -> b
forall a. Enum a => a -> a
pred b
lo)
toEnum :: Int -> BigWord a b
toEnum Int
x
| Int
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 = String -> BigWord a b
forall a. HasCallStack => String -> a
error String
"Enum.toEnum: negative value"
| Bool
otherwise = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
0 (Int -> b
forall a. Enum a => Int -> a
toEnum Int
x)
fromEnum :: BigWord a b -> Int
fromEnum (W2 a
0 b
lo) = b -> Int
forall a. Enum a => a -> Int
fromEnum b
lo
fromEnum BigWord a b
_ = String -> Int
forall a. HasCallStack => String -> a
error String
"Enum.fromEnum: bad value"
instance (Ord a, Ord b) => Ord (BigWord a b) where
compare :: BigWord a b -> BigWord a b -> Ordering
compare (W2 a
xh b
xl) (W2 a
yh b
yl) =
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
xh a
yh of
Ordering
EQ -> b -> b -> Ordering
forall a. Ord a => a -> a -> Ordering
compare b
xl b
yl
Ordering
r -> Ordering
r
instance (Eq a, Eq b) => Eq (BigWord a b) where
W2 a
xh b
xl == :: BigWord a b -> BigWord a b -> Bool
== W2 a
yh b
yl = a
xh a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
yh Bool -> Bool -> Bool
&& b
xl b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
yl
W2 a
xh b
xl /= :: BigWord a b -> BigWord a b -> Bool
/= W2 a
yh b
yl = a
xh a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
yh Bool -> Bool -> Bool
|| b
xl b -> b -> Bool
forall a. Eq a => a -> a -> Bool
/= b
yl
instance (Num a, Eq a, Integral b, Bounded b, Num2 b, BigWordCtx a b)
=> Num (BigWord a b) where
negate :: BigWord a b -> BigWord a b
negate (W2 a
hi b
lo)
| b
lo b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
0 = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 (a -> a
forall a. Num a => a -> a
negate a
hi) b
0
| Bool
otherwise = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 (a -> a
forall a. Num a => a -> a
negate (a
hia -> a -> a
forall a. Num a => a -> a -> a
+a
1)) (b -> b
forall a. Num a => a -> a
negate b
lo)
abs :: BigWord a b -> BigWord a b
abs = BigWord a b -> BigWord a b
forall a. a -> a
id
signum :: BigWord a b -> BigWord a b
signum (W2 a
0 b
0) = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
0 b
0
signum BigWord a b
_ = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
0 b
1
W2 a
xh b
xl + :: BigWord a b -> BigWord a b -> BigWord a b
+ W2 a
yh b
yl = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
hi b
lo
where
lo :: b
lo = b
xl b -> b -> b
forall a. Num a => a -> a -> a
+ b
yl
hi :: a
hi = a
xh a -> a -> a
forall a. Num a => a -> a -> a
+ a
yh a -> a -> a
forall a. Num a => a -> a -> a
+ if b
lo b -> b -> Bool
forall a. Ord a => a -> a -> Bool
< b
xl then a
1
else a
0
W2 a
xh b
xl * :: BigWord a b -> BigWord a b -> BigWord a b
* W2 a
yh b
yl = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
hi b
lo
where
hi :: a
hi = a
xh a -> a -> a
forall a. Num a => a -> a -> a
* b -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral b
yl a -> a -> a
forall a. Num a => a -> a -> a
+ a
yh a -> a -> a
forall a. Num a => a -> a -> a
* b -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral b
xl a -> a -> a
forall a. Num a => a -> a -> a
+ b -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral b
c
(b
c,b
lo) = b -> b -> (b, Unsigned b)
forall w. Num2 w => w -> w -> (w, Unsigned w)
mulWithCarry b
xl b
yl
fromInteger :: Integer -> BigWord a b
fromInteger Integer
x = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 (Integer -> a
forall a. Num a => Integer -> a
fromInteger Integer
hi) (Integer -> b
forall a. Num a => Integer -> a
fromInteger Integer
lo)
where
(Integer
hi,Integer
lo) = Integer
x Integer -> Integer -> (Integer, Integer)
forall a. Integral a => a -> a -> (a, a)
`divMod` (b -> Integer
forall a. Integral a => a -> Integer
toInteger (b
forall a. Bounded a => a
maxBound :: b) Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
1)
instance (Integral (BigWord a b), Num (BigWord a b), Ord (BigWord a b))
=> Real (BigWord a b) where
toRational :: BigWord a b -> Rational
toRational BigWord a b
x = BigWord a b -> Integer
forall a. Integral a => a -> Integer
toInteger BigWord a b
x Integer -> Integer -> Rational
forall a. Integral a => a -> a -> Ratio a
% Integer
1
instance ( Integral a, FiniteBits a, Num2 a, Bounded a
, Integral b, FiniteBits b, Num2 b, Bounded b
, BigWordCtx a b
)
=> Integral (BigWord a b) where
toInteger :: BigWord a b -> Integer
toInteger (W2 a
hi b
lo) =
a -> Integer
forall a. Integral a => a -> Integer
toInteger a
hi Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* (b -> Integer
forall a. Integral a => a -> Integer
toInteger (b
forall a. Bounded a => a
maxBound :: b) Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
1) Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ b -> Integer
forall a. Integral a => a -> Integer
toInteger b
lo
divMod :: BigWord a b -> BigWord a b -> (BigWord a b, BigWord a b)
divMod = BigWord a b -> BigWord a b -> (BigWord a b, BigWord a b)
forall a. Integral a => a -> a -> (a, a)
quotRem
quotRem :: BigWord a b -> BigWord a b -> (BigWord a b, BigWord a b)
quotRem x :: BigWord a b
x@(W2 a
xh b
xl) y :: BigWord a b
y@(W2 a
yh b
yl)
| a
yh a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
0 Bool -> Bool -> Bool
&& b
yl b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
0 = String -> (BigWord a b, BigWord a b)
forall a. HasCallStack => String -> a
error String
"divide by zero"
| Bool
otherwise =
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
xh a
yh of
Ordering
LT -> (BigWord a b
0, BigWord a b
x)
Ordering
EQ -> case b -> b -> Ordering
forall a. Ord a => a -> a -> Ordering
compare b
xl b
yl of
Ordering
LT -> (BigWord a b
0, BigWord a b
x)
Ordering
EQ -> (BigWord a b
1, BigWord a b
0)
Ordering
GT | a
yh a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
0 ->
let (b
t2, b
t1) = b -> b -> (b, b)
forall a. Integral a => a -> a -> (a, a)
quotRem b
xl b
yl
in (a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
0 b
t2, a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
0 b
t1)
Ordering
GT -> (BigWord a b
1, a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
0 (b
xl b -> b -> b
forall a. Num a => a -> a -> a
- b
yl))
Ordering
GT | b
yl b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
0
-> let (a
t2, a
t1) = a -> a -> (a, a)
forall a. Integral a => a -> a -> (a, a)
quotRem a
xh a
yh
in (a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
0 (a -> b
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
t2), a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
t1 b
xl)
Ordering
GT | a
yh a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
0 Bool -> Bool -> Bool
&& b
yl b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
forall a. Bounded a => a
maxBound
-> let z :: b
z = a -> b
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
xh
(b
t2, b
t1) = b -> b -> (b, Unsigned b)
forall w. Num2 w => w -> w -> (w, Unsigned w)
addWithCarry b
z b
xl
in
if b
t2 b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
0
then if b
t1 b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
forall a. Bounded a => a
maxBound
then ((a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
0 b
z) BigWord a b -> BigWord a b -> BigWord a b
forall a. Num a => a -> a -> a
+ BigWord a b
1, BigWord a b
0)
else (a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
0 b
z, a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
0 b
t1)
else if b
t1 b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
forall a. Bounded a => a
maxBound
then ((a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
0 b
z) BigWord a b -> BigWord a b -> BigWord a b
forall a. Num a => a -> a -> a
+ BigWord a b
2, BigWord a b
1)
else if b
t1 b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b -> b -> b
forall a. Bits a => a -> a -> a
xor b
forall a. Bounded a => a
maxBound b
1
then ((a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
0 b
z) BigWord a b -> BigWord a b -> BigWord a b
forall a. Num a => a -> a -> a
+ BigWord a b
2, BigWord a b
0)
else ((a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
0 b
z) BigWord a b -> BigWord a b -> BigWord a b
forall a. Num a => a -> a -> a
+ BigWord a b
1, a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
0 (b
t1 b -> b -> b
forall a. Num a => a -> a -> a
+ b
1))
Ordering
GT | a
yh a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
0
-> let (BigWord a b
t2, b
t1) = a -> b -> b -> (BigWord a b, b)
div1 a
xh b
xl b
yl
in (BigWord a b
t2, a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
0 b
t1)
Ordering
GT | Int
t1 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
t2 -> (BigWord a b
1, BigWord a b
x BigWord a b -> BigWord a b -> BigWord a b
forall a. Num a => a -> a -> a
- BigWord a b
y)
| Bool
otherwise -> (a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
0 (a -> b
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
q2), BigWord a b -> Int -> BigWord a b
forall a. Bits a => a -> Int -> a
shiftR BigWord a b
r2 Int
t2)
where
t1 :: Int
t1 = a -> Int
forall b. FiniteBits b => b -> Int
countLeadingZeros a
xh
t2 :: Int
t2 = a -> Int
forall b. FiniteBits b => b -> Int
countLeadingZeros a
yh
z :: a
z = a -> Int -> a
forall a. Bits a => a -> Int -> a
shiftR a
xh (a -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (a
forall a. HasCallStack => a
undefined::a) Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
t2)
W2 a
hhh b
hll = BigWord a b -> Int -> BigWord a b
forall a. Bits a => a -> Int -> a
shiftL BigWord a b
x Int
t2
v :: BigWord a b
v@(W2 a
lhh b
lll) = BigWord a b -> Int -> BigWord a b
forall a. Bits a => a -> Int -> a
shiftL BigWord a b
y Int
t2
((a
0, a
q1), a
r1) = a -> a -> a -> ((a, a), a)
div2 a
z a
hhh a
lhh
(b
t4, b
t3) = b -> b -> (b, Unsigned b)
forall w. Num2 w => w -> w -> (w, Unsigned w)
mulWithCarry (a -> b
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
q1) b
lll
t5 :: BigWord a b
t5 = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 (b -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral b
t4) b
t3
t6 :: BigWord a b
t6 = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
r1 b
hll
(BigWord a b
t8, BigWord a b
t7) = BigWord a b -> BigWord a b -> (BigWord a b, Unsigned (BigWord a b))
forall w. Num2 w => w -> w -> (w, Unsigned w)
addWithCarry BigWord a b
t6 BigWord a b
v
(BigWord a b
t10, BigWord a b
t9) = BigWord a b -> BigWord a b -> (BigWord a b, Unsigned (BigWord a b))
forall w. Num2 w => w -> w -> (w, Unsigned w)
addWithCarry BigWord a b
t7 BigWord a b
v
loWord :: BigWord hi lo -> lo
loWord (W2 hi
_ lo
l) = lo
l
(a
q2, BigWord a b
r2) =
if BigWord a b
t5 BigWord a b -> BigWord a b -> Bool
forall a. Ord a => a -> a -> Bool
> BigWord a b
t6
then if BigWord a b -> b
forall hi lo. BigWord hi lo -> lo
loWord BigWord a b
t8 b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
0
then if BigWord a b
t7 BigWord a b -> BigWord a b -> Bool
forall a. Ord a => a -> a -> Bool
>= BigWord a b
t5
then (a
q1 a -> a -> a
forall a. Num a => a -> a -> a
- a
1, BigWord a b
t7 BigWord a b -> BigWord a b -> BigWord a b
forall a. Num a => a -> a -> a
- BigWord a b
t5)
else if BigWord a b -> b
forall hi lo. BigWord hi lo -> lo
loWord BigWord a b
t10 b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
0
then (a
q1 a -> a -> a
forall a. Num a => a -> a -> a
- a
2, BigWord a b
t9 BigWord a b -> BigWord a b -> BigWord a b
forall a. Num a => a -> a -> a
- BigWord a b
t5)
else (a
q1 a -> a -> a
forall a. Num a => a -> a -> a
- a
2, (BigWord a b
forall a. Bounded a => a
maxBound BigWord a b -> BigWord a b -> BigWord a b
forall a. Num a => a -> a -> a
- BigWord a b
t5) BigWord a b -> BigWord a b -> BigWord a b
forall a. Num a => a -> a -> a
+ BigWord a b
t9 BigWord a b -> BigWord a b -> BigWord a b
forall a. Num a => a -> a -> a
+ BigWord a b
1)
else (a
q1 a -> a -> a
forall a. Num a => a -> a -> a
- a
1, (BigWord a b
forall a. Bounded a => a
maxBound BigWord a b -> BigWord a b -> BigWord a b
forall a. Num a => a -> a -> a
- BigWord a b
t5) BigWord a b -> BigWord a b -> BigWord a b
forall a. Num a => a -> a -> a
+ BigWord a b
t7 BigWord a b -> BigWord a b -> BigWord a b
forall a. Num a => a -> a -> a
+ BigWord a b
1)
else (a
q1, BigWord a b
t6 BigWord a b -> BigWord a b -> BigWord a b
forall a. Num a => a -> a -> a
- BigWord a b
t5)
where
div1 :: a -> b -> b -> (BigWord a b, b)
div1 :: a -> b -> b -> (BigWord a b, b)
div1 a
hhh b
hll b
by = a -> b -> BigWord a b -> (BigWord a b, b)
go a
hhh b
hll BigWord a b
0
where
(b
t2, b
t1) = b -> b -> (b, b)
forall a. Integral a => a -> a -> (a, a)
quotRem b
forall a. Bounded a => a
maxBound b
by
go :: a -> b -> BigWord a b -> (BigWord a b, b)
go a
h b
l BigWord a b
c
| b
z b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
0 = (BigWord a b
c BigWord a b -> BigWord a b -> BigWord a b
forall a. Num a => a -> a -> a
+ a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 (b -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral b
t8) b
t7 BigWord a b -> BigWord a b -> BigWord a b
forall a. Num a => a -> a -> a
+ a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
0 b
t10, b
t9)
| Bool
otherwise = a -> b -> BigWord a b -> (BigWord a b, b)
go (b -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral b
z) b
t5 (BigWord a b
c BigWord a b -> BigWord a b -> BigWord a b
forall a. Num a => a -> a -> a
+ (a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 (b -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral b
t8) b
t7))
where
h1 :: b
h1 = a -> b
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
h
(b
t4, b
t3) = b -> b -> (b, Unsigned b)
forall w. Num2 w => w -> w -> (w, Unsigned w)
mulWithCarry b
h1 (b
t1 b -> b -> b
forall a. Num a => a -> a -> a
+ b
1)
(b
t6, b
t5) = b -> b -> (b, Unsigned b)
forall w. Num2 w => w -> w -> (w, Unsigned w)
addWithCarry b
t3 b
l
z :: b
z = b
t4 b -> b -> b
forall a. Num a => a -> a -> a
+ b
t6
(b
t8, b
t7) = b -> b -> (b, Unsigned b)
forall w. Num2 w => w -> w -> (w, Unsigned w)
mulWithCarry b
h1 b
t2
(b
t10, b
t9) = b -> b -> (b, b)
forall a. Integral a => a -> a -> (a, a)
quotRem b
t5 b
by
div2 :: a -> a -> a -> ((a,a), a)
div2 :: a -> a -> a -> ((a, a), a)
div2 a
hhh a
hll a
by = a -> a -> (a, a) -> ((a, a), a)
go a
hhh a
hll (a
0, a
0)
where
(a
t2, a
t1) = a -> a -> (a, a)
forall a. Integral a => a -> a -> (a, a)
quotRem a
forall a. Bounded a => a
maxBound a
by
go :: a -> a -> (a, a) -> ((a, a), a)
go a
h a
l (a, a)
c
| a
z a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
0 = ((a, a) -> (a, a) -> (a, Unsigned a)
forall a. (Num2 a, Num a) => (a, a) -> (a, a) -> (a, Unsigned a)
addT ((a, a) -> (a, a) -> (a, Unsigned a)
forall a. (Num2 a, Num a) => (a, a) -> (a, a) -> (a, Unsigned a)
addT (a, a)
c (a
t8, a
t7)) (a
0, a
t10), a
t9)
| Bool
otherwise = a -> a -> (a, a) -> ((a, a), a)
go a
z a
t5 ((a, a) -> (a, a) -> (a, Unsigned a)
forall a. (Num2 a, Num a) => (a, a) -> (a, a) -> (a, Unsigned a)
addT (a, a)
c (a
t8, a
t7))
where
(a
t4, a
t3) = a -> a -> (a, Unsigned a)
forall w. Num2 w => w -> w -> (w, Unsigned w)
mulWithCarry a
h (a
t1 a -> a -> a
forall a. Num a => a -> a -> a
+ a
1)
(a
t6, a
t5) = a -> a -> (a, Unsigned a)
forall w. Num2 w => w -> w -> (w, Unsigned w)
addWithCarry a
t3 a
l
z :: a
z = a
t4 a -> a -> a
forall a. Num a => a -> a -> a
+ a
t6
(a
t8, a
t7) = a -> a -> (a, Unsigned a)
forall w. Num2 w => w -> w -> (w, Unsigned w)
mulWithCarry a
h a
t2
(a
t10, a
t9) = a -> a -> (a, a)
forall a. Integral a => a -> a -> (a, a)
quotRem a
t5 a
by
addT :: (a, a) -> (a, a) -> (a, Unsigned a)
addT (a
lhh, a
lhl) (a
llh, a
lll) =
let (a
t4', Unsigned a
t3') = a -> a -> (a, Unsigned a)
forall w. Num2 w => w -> w -> (w, Unsigned w)
addWithCarry a
lhl a
lll
in (a
lhh a -> a -> a
forall a. Num a => a -> a -> a
+ a
llh a -> a -> a
forall a. Num a => a -> a -> a
+ a
t4', Unsigned a
t3')
instance ( Integral a, FiniteBits a, Num2 a
, Integral b, FiniteBits b, Num2 b
, BigWordCtx a b
)
=> Num2 (BigWord a b) where
type Signed (BigWord a b) = BigInt (Signed a) b
type Unsigned (BigWord a b) = BigWord (Unsigned a) b
signed :: BigWord a b -> Signed (BigWord a b)
signed (W2 a
hi b
lo) = Signed a -> b -> BigInt (Signed a) b
forall hi lo. hi -> lo -> BigInt hi lo
I2 (a -> Signed a
forall w. Num2 w => w -> Signed w
signed a
hi) b
lo
unsigned :: BigWord a b -> Unsigned (BigWord a b)
unsigned = BigWord a b -> Unsigned (BigWord a b)
forall a. a -> a
id
addWithCarry :: BigWord a b -> BigWord a b -> (BigWord a b, Unsigned (BigWord a b))
addWithCarry (W2 a
xh b
xl) (W2 a
yh b
yl) = (a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
0 b
w, a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
v b
u)
where
(b
t1, b
u) = b -> b -> (b, Unsigned b)
forall w. Num2 w => w -> w -> (w, Unsigned w)
addWithCarry b
xl b
yl
(a
t3, a
t2) = a -> a -> (a, Unsigned a)
forall w. Num2 w => w -> w -> (w, Unsigned w)
addWithCarry a
xh (b -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral b
t1)
(a
t4, a
v) = a -> a -> (a, Unsigned a)
forall w. Num2 w => w -> w -> (w, Unsigned w)
addWithCarry a
t2 a
yh
w :: b
w = a -> b
forall a b. (Integral a, Num b) => a -> b
fromIntegral (a
t3 a -> a -> a
forall a. Num a => a -> a -> a
+ a
t4)
mulWithCarry :: BigWord a b -> BigWord a b -> (BigWord a b, Unsigned (BigWord a b))
mulWithCarry (W2 a
xh b
xl) (W2 a
yh b
yl) =
( a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 (a
hhh a -> a -> a
forall a. Num a => a -> a -> a
+ b -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral (b -> Int -> b
forall a. Bits a => a -> Int -> a
shiftR b
t9 Int
y) a -> a -> a
forall a. Num a => a -> a -> a
+ a -> Int -> a
forall a. Bits a => a -> Int -> a
shiftL a
x Int
z) (b -> Int -> b
forall a. Bits a => a -> Int -> a
shiftL b
t9 Int
z b -> b -> b
forall a. Bits a => a -> a -> a
.|. b -> Int -> b
forall a. Bits a => a -> Int -> a
shiftR b
t3 Int
y)
, a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 (b -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral b
t3) b
lll)
where
(b
llh, b
lll) = b -> b -> (b, Unsigned b)
forall w. Num2 w => w -> w -> (w, Unsigned w)
mulWithCarry b
xl b
yl
(b
hlh, b
hll) = b -> b -> (b, Unsigned b)
forall w. Num2 w => w -> w -> (w, Unsigned w)
mulWithCarry (a -> b
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
xh) b
yl
(b
lhh, b
lhl) = b -> b -> (b, Unsigned b)
forall w. Num2 w => w -> w -> (w, Unsigned w)
mulWithCarry b
xl (a -> b
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
yh)
(a
hhh, a
hhl) = a -> a -> (a, Unsigned a)
forall w. Num2 w => w -> w -> (w, Unsigned w)
mulWithCarry a
xh a
yh
(b
t2, b
t1) = b -> b -> (b, Unsigned b)
forall w. Num2 w => w -> w -> (w, Unsigned w)
addWithCarry b
llh b
hll
(b
t4, b
t3) = b -> b -> (b, Unsigned b)
forall w. Num2 w => w -> w -> (w, Unsigned w)
addWithCarry b
t1 b
lhl
(b
t6, b
t5) = b -> b -> (b, Unsigned b)
forall w. Num2 w => w -> w -> (w, Unsigned w)
addWithCarry (a -> b
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
hhl) (b
t2 b -> b -> b
forall a. Num a => a -> a -> a
+ b
t4)
(b
t8, b
t7) = b -> b -> (b, Unsigned b)
forall w. Num2 w => w -> w -> (w, Unsigned w)
addWithCarry b
t5 b
lhh
(b
t10, b
t9) = b -> b -> (b, Unsigned b)
forall w. Num2 w => w -> w -> (w, Unsigned w)
addWithCarry b
t7 b
hlh
x :: a
x = b -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral (b
t6 b -> b -> b
forall a. Num a => a -> a -> a
+ b
t8 b -> b -> b
forall a. Num a => a -> a -> a
+ b
t10)
y :: Int
y = a -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (a
forall a. HasCallStack => a
undefined::a)
z :: Int
z = b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (b
forall a. HasCallStack => a
undefined::b) Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
y
instance ( Integral a, FiniteBits a
, Integral b, FiniteBits b
, BigWordCtx a b
)
=> Bits (BigWord a b) where
isSigned :: BigWord a b -> Bool
isSigned BigWord a b
_ = Bool
False
bitSize :: BigWord a b -> Int
bitSize = BigWord a b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize
bitSizeMaybe :: BigWord a b -> Maybe Int
bitSizeMaybe = Int -> Maybe Int
forall a. a -> Maybe a
Just (Int -> Maybe Int)
-> (BigWord a b -> Int) -> BigWord a b -> Maybe Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. BigWord a b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize
W2 a
xh b
xl .&. :: BigWord a b -> BigWord a b -> BigWord a b
.&. W2 a
yh b
yl = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 (a
xh a -> a -> a
forall a. Bits a => a -> a -> a
.&. a
yh) (b
xl b -> b -> b
forall a. Bits a => a -> a -> a
.&. b
yl)
W2 a
xh b
xl .|. :: BigWord a b -> BigWord a b -> BigWord a b
.|. W2 a
yh b
yl = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 (a
xh a -> a -> a
forall a. Bits a => a -> a -> a
.|. a
yh) (b
xl b -> b -> b
forall a. Bits a => a -> a -> a
.|. b
yl)
W2 a
xh b
xl xor :: BigWord a b -> BigWord a b -> BigWord a b
`xor` W2 a
yh b
yl = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 (a
xh a -> a -> a
forall a. Bits a => a -> a -> a
`xor` a
yh) (b
xl b -> b -> b
forall a. Bits a => a -> a -> a
`xor` b
yl)
complement :: BigWord a b -> BigWord a b
complement (W2 a
hi b
lo) = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 (a -> a
forall a. Bits a => a -> a
complement a
hi) (b -> b
forall a. Bits a => a -> a
complement b
lo)
shiftL :: BigWord a b -> Int -> BigWord a b
shiftL (W2 a
hi b
lo) Int
x
| Int
y Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0 = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 (a -> Int -> a
forall a. Bits a => a -> Int -> a
shiftL a
hi Int
x a -> a -> a
forall a. Bits a => a -> a -> a
.|. b -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral (b -> Int -> b
forall a. Bits a => a -> Int -> a
shiftR b
lo Int
y)) (b -> Int -> b
forall a. Bits a => a -> Int -> a
shiftL b
lo Int
x)
| Bool
otherwise = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 (b -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral (b -> Int -> b
forall a. Bits a => a -> Int -> a
shiftL b
lo (Int -> Int
forall a. Num a => a -> a
negate Int
y))) b
0
where
y :: Int
y = b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (b
forall a. HasCallStack => a
undefined::b) Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
x
shiftR :: BigWord a b -> Int -> BigWord a b
shiftR (W2 a
hi b
lo) Int
x = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
hi' b
lo'
where
hi' :: a
hi' = a -> Int -> a
forall a. Bits a => a -> Int -> a
shiftR a
hi Int
x
lo' :: b
lo' | Int
y Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0 = b -> Int -> b
forall a. Bits a => a -> Int -> a
shiftL (a -> b
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
hi) Int
y b -> b -> b
forall a. Bits a => a -> a -> a
.|. b -> Int -> b
forall a. Bits a => a -> Int -> a
shiftR b
lo Int
x
| Bool
otherwise = b
z
y :: Int
y = b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (b
forall a. HasCallStack => a
undefined::b) Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
x
z :: b
z = b -> Int -> b
forall a. Bits a => a -> Int -> a
shiftR (a -> b
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
hi) (Int -> Int
forall a. Num a => a -> a
negate Int
y)
rotateL :: BigWord a b -> Int -> BigWord a b
rotateL (W2 a
hi b
lo) Int
x
| Int
y Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0 = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 (b -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral (b -> Int -> b
forall a. Bits a => a -> Int -> a
shiftL b
lo Int
y) a -> a -> a
forall a. Bits a => a -> a -> a
.|. a -> Int -> a
forall a. Bits a => a -> Int -> a
shiftR a
hi Int
z)
(b -> Int -> b
forall a. Bits a => a -> Int -> a
shiftL (a -> b
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
hi) (b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (b
forall a. HasCallStack => a
undefined::b) Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
z) b -> b -> b
forall a. Bits a => a -> a -> a
.|. b -> Int -> b
forall a. Bits a => a -> Int -> a
shiftR b
lo Int
z)
| Bool
otherwise = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 (b -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral (b -> Int -> b
forall a. Bits a => a -> Int -> a
shiftR b
lo (Int -> Int
forall a. Num a => a -> a
negate Int
y)) a -> a -> a
forall a. Bits a => a -> a -> a
.|. a -> Int -> a
forall a. Bits a => a -> Int -> a
shiftL a
hi Int
x)
(b -> Int -> b
forall a. Bits a => a -> Int -> a
shift (a -> b
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
hi) (b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (b
forall a. HasCallStack => a
undefined::b) Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
z) b -> b -> b
forall a. Bits a => a -> a -> a
.|. b -> Int -> b
forall a. Bits a => a -> Int -> a
shiftL b
lo Int
x b -> b -> b
forall a. Bits a => a -> a -> a
.|. b -> Int -> b
forall a. Bits a => a -> Int -> a
shiftR b
lo Int
z)
where
y :: Int
y = Int
x Int -> Int -> Int
forall a. Num a => a -> a -> a
- b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (b
forall a. HasCallStack => a
undefined::b)
z :: Int
z = BigWord a b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (BigWord a b
forall a. HasCallStack => a
undefined::BigWord a b) Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
x
rotateR :: BigWord a b -> Int -> BigWord a b
rotateR BigWord a b
x Int
y = BigWord a b -> Int -> BigWord a b
forall a. Bits a => a -> Int -> a
rotateL BigWord a b
x (BigWord a b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (BigWord a b
forall a. HasCallStack => a
undefined::BigWord a b) Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
y)
bit :: Int -> BigWord a b
bit Int
n
| Int
m Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0 = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 (Int -> a
forall a. Bits a => Int -> a
bit Int
m) b
0
| Bool
otherwise = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
0 (Int -> b
forall a. Bits a => Int -> a
bit Int
n)
where
m :: Int
m = Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (b
forall a. HasCallStack => a
undefined::b)
testBit :: BigWord a b -> Int -> Bool
testBit (W2 a
hi b
lo) Int
n
| Int
m Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0 = a -> Int -> Bool
forall a. Bits a => a -> Int -> Bool
testBit a
hi Int
m
| Bool
otherwise = b -> Int -> Bool
forall a. Bits a => a -> Int -> Bool
testBit b
lo Int
n
where
m :: Int
m = Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (b
forall a. HasCallStack => a
undefined::b)
setBit :: BigWord a b -> Int -> BigWord a b
setBit (W2 a
hi b
lo) Int
n
| Int
m Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0 = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 (a -> Int -> a
forall a. Bits a => a -> Int -> a
setBit a
hi Int
m) b
lo
| Bool
otherwise = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
hi (b -> Int -> b
forall a. Bits a => a -> Int -> a
setBit b
lo Int
n)
where
m :: Int
m = Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (b
forall a. HasCallStack => a
undefined::b)
clearBit :: BigWord a b -> Int -> BigWord a b
clearBit (W2 a
hi b
lo) Int
n
| Int
m Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0 = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 (a -> Int -> a
forall a. Bits a => a -> Int -> a
clearBit a
hi Int
m) b
lo
| Bool
otherwise = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
hi (b -> Int -> b
forall a. Bits a => a -> Int -> a
clearBit b
lo Int
n)
where
m :: Int
m = Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (b
forall a. HasCallStack => a
undefined::b)
complementBit :: BigWord a b -> Int -> BigWord a b
complementBit (W2 a
hi b
lo) Int
n
| Int
m Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0 = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 (a -> Int -> a
forall a. Bits a => a -> Int -> a
complementBit a
hi Int
m) b
lo
| Bool
otherwise = a -> b -> BigWord a b
forall hi lo. hi -> lo -> BigWord hi lo
W2 a
hi (b -> Int -> b
forall a. Bits a => a -> Int -> a
complementBit b
lo Int
n)
where
m :: Int
m = Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (b
forall a. HasCallStack => a
undefined::b)
popCount :: BigWord a b -> Int
popCount (W2 a
hi b
lo) = a -> Int
forall a. Bits a => a -> Int
popCount a
hi Int -> Int -> Int
forall a. Num a => a -> a -> a
+ b -> Int
forall a. Bits a => a -> Int
popCount b
lo
instance ( Integral a, FiniteBits a
, Integral b, FiniteBits b
, BigWordCtx a b
)
=> FiniteBits (BigWord a b) where
finiteBitSize :: BigWord a b -> Int
finiteBitSize BigWord a b
_ = a -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (a
forall a. HasCallStack => a
undefined::a)
Int -> Int -> Int
forall a. Num a => a -> a -> a
+ b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (b
forall a. HasCallStack => a
undefined::b)
countLeadingZeros :: BigWord a b -> Int
countLeadingZeros (W2 a
hi b
lo)
| Int
x Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
wsib = Int
wsib Int -> Int -> Int
forall a. Num a => a -> a -> a
+ b -> Int
forall b. FiniteBits b => b -> Int
countLeadingZeros b
lo
| Bool
otherwise = Int
x
where
x :: Int
x = a -> Int
forall b. FiniteBits b => b -> Int
countLeadingZeros a
hi
wsib :: Int
wsib = a -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (a
forall a. HasCallStack => a
undefined::a)
countTrailingZeros :: BigWord a b -> Int
countTrailingZeros (W2 a
hi b
lo)
| Int
x Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
wsib = Int
wsib Int -> Int -> Int
forall a. Num a => a -> a -> a
+ a -> Int
forall b. FiniteBits b => b -> Int
countTrailingZeros a
hi
| Bool
otherwise = Int
x
where
x :: Int
x = b -> Int
forall b. FiniteBits b => b -> Int
countTrailingZeros b
lo
wsib :: Int
wsib = b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (b
forall a. HasCallStack => a
undefined::b)