{-# OPTIONS_HADDOCK hide #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE UnboxedTuples #-}
module Crypto.Range (
upto
, upto_pure
, W2(..)
, mul_wide
, _mul_wide_limbs
) where
import Data.Bits ((.&.), (.>>.))
import qualified Data.Bits as B
import Data.Word (Word64)
import GHC.Exts (Word(..), timesWord2#)
data W2 = W2 {-# UNPACK #-} !Word64 {-# UNPACK #-} !Word64
deriving (W2 -> W2 -> Bool
(W2 -> W2 -> Bool) -> (W2 -> W2 -> Bool) -> Eq W2
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: W2 -> W2 -> Bool
== :: W2 -> W2 -> Bool
$c/= :: W2 -> W2 -> Bool
/= :: W2 -> W2 -> Bool
Eq, Int -> W2 -> ShowS
[W2] -> ShowS
W2 -> String
(Int -> W2 -> ShowS)
-> (W2 -> String) -> ([W2] -> ShowS) -> Show W2
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> W2 -> ShowS
showsPrec :: Int -> W2 -> ShowS
$cshow :: W2 -> String
show :: W2 -> String
$cshowList :: [W2] -> ShowS
showList :: [W2] -> ShowS
Show)
mul_wide :: Word64 -> Word64 -> W2
mul_wide :: Word64 -> Word64 -> W2
mul_wide Word64
a Word64
b
| Word -> Int
forall b. FiniteBits b => b -> Int
B.finiteBitSize (Word
0 :: Word) Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
64 =
let !(W# Word#
x) = Word64 -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
a
!(W# Word#
y) = Word64 -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
b
!(# Word#
h, Word#
l #) = Word# -> Word# -> (# Word#, Word# #)
timesWord2# Word#
x Word#
y
in Word64 -> Word64 -> W2
W2 (Word -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word# -> Word
W# Word#
h)) (Word -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word# -> Word
W# Word#
l))
| Bool
otherwise = Word64 -> Word64 -> W2
_mul_wide_limbs Word64
a Word64
b
{-# INLINE mul_wide #-}
_mul_wide_limbs :: Word64 -> Word64 -> W2
_mul_wide_limbs :: Word64 -> Word64 -> W2
_mul_wide_limbs Word64
a Word64
b =
let !a0 :: Word64
a0 = Word64
a Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0xffffffff
!a1 :: Word64
a1 = Word64
a Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
.>>. Int
32
!b0 :: Word64
b0 = Word64
b Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0xffffffff
!b1 :: Word64
b1 = Word64
b Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
.>>. Int
32
!p00 :: Word64
p00 = Word64
a0 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
b0
!p01 :: Word64
p01 = Word64
a0 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
b1
!p10 :: Word64
p10 = Word64
a1 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
b0
!p11 :: Word64
p11 = Word64
a1 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
b1
!mid :: Word64
mid = (Word64
p00 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
.>>. Int
32) Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ (Word64
p01 Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0xffffffff) Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ (Word64
p10 Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0xffffffff)
!hi :: Word64
hi = Word64
p11 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ (Word64
p01 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
.>>. Int
32) Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ (Word64
p10 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
.>>. Int
32) Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ (Word64
mid Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
.>>. Int
32)
in Word64 -> Word64 -> W2
W2 Word64
hi (Word64
a Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
b)
{-# INLINE _mul_wide_limbs #-}
upto :: Monad m => m Word64 -> Word64 -> m Word64
upto :: forall (m :: * -> *). Monad m => m Word64 -> Word64 -> m Word64
upto m Word64
gen Word64
n
| Word64
n Word64 -> Word64 -> Bool
forall a. Eq a => a -> a -> Bool
== Word64
forall a. Bounded a => a
maxBound = m Word64
gen
| Bool
otherwise = do
!x <- m Word64
gen
let !(W2 h l) = mul_wide x s
if l >= s
then pure h
else reject (negate s `rem` s) h l
where
!s :: Word64
s = Word64
n Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
1
reject :: Word64 -> Word64 -> Word64 -> m Word64
reject !Word64
t = Word64 -> Word64 -> m Word64
loop where
loop :: Word64 -> Word64 -> m Word64
loop !Word64
h !Word64
l
| Word64
l Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
>= Word64
t = Word64 -> m Word64
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Word64
h
| Bool
otherwise = do
!x <- m Word64
gen
let !(W2 nh nl) = mul_wide x s
loop nh nl
{-# INLINE upto #-}
upto_pure :: (g -> (Word64, g)) -> Word64 -> g -> (Word64, g)
upto_pure :: forall g. (g -> (Word64, g)) -> Word64 -> g -> (Word64, g)
upto_pure g -> (Word64, g)
step Word64
n g
g0
| Word64
n Word64 -> Word64 -> Bool
forall a. Eq a => a -> a -> Bool
== Word64
forall a. Bounded a => a
maxBound = g -> (Word64, g)
step g
g0
| Bool
otherwise =
let !(Word64
x, g
g1) = g -> (Word64, g)
step g
g0
!(W2 Word64
h Word64
l) = Word64 -> Word64 -> W2
mul_wide Word64
x Word64
s
in if Word64
l Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
>= Word64
s
then (Word64
h, g
g1)
else Word64 -> Word64 -> Word64 -> g -> (Word64, g)
reject (Word64 -> Word64
forall a. Num a => a -> a
negate Word64
s Word64 -> Word64 -> Word64
forall a. Integral a => a -> a -> a
`rem` Word64
s) Word64
h Word64
l g
g1
where
!s :: Word64
s = Word64
n Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
1
reject :: Word64 -> Word64 -> Word64 -> g -> (Word64, g)
reject !Word64
t = Word64 -> Word64 -> g -> (Word64, g)
loop where
loop :: Word64 -> Word64 -> g -> (Word64, g)
loop !Word64
h !Word64
l !g
g
| Word64
l Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
>= Word64
t = (Word64
h, g
g)
| Bool
otherwise =
let !(Word64
x, g
ng) = g -> (Word64, g)
step g
g
!(W2 Word64
nh Word64
nl) = Word64 -> Word64 -> W2
mul_wide Word64
x Word64
s
in Word64 -> Word64 -> g -> (Word64, g)
loop Word64
nh Word64
nl g
ng
{-# INLINE upto_pure #-}