{-# OPTIONS_HADDOCK hide #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE UnboxedTuples #-}

-- |
-- Module: Crypto.Range
-- Copyright: (c) 2026 Jared Tobin
-- License: MIT
-- Maintainer: Jared Tobin <jared@ppad.tech>
--
-- Unbiased integers in a range, via Lemire's nearly-divisionless
-- method ("Fast Random Integer Generation in an Interval", 2019).

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#)

-- | A 128-bit product, as its high and low words.
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)

-- | The full 128-bit product of two words.
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 #-}

-- | The full 128-bit product of two words, via 32-bit limbs, for
--   platforms with 32-bit machine words.
_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 #-}

-- | A uniformly-distributed word in [0, n], given an action producing
--   uniformly-distributed words.
--
--   Each draw x is mapped to the high word of x * (n + 1); draws whose
--   low word falls below 2 ^ 64 mod (n + 1) are rejected, so that
--   every output is equally likely. Rejection is rare for small n, and
--   the remainder is only computed when it might occur.
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' for a pure generator, given its step function.
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 #-}