{-# LANGUAGE BangPatterns, MagicHash, TypeOperators #-}

module Data.BloomFilter.Util
    (
      FastShift(..)
    , nextPowerOfTwo
    , (:*)(..)
    ) where

import Data.Bits ((.|.))
import qualified Data.Bits as Bits
import GHC.Base
import GHC.Word

-- | A strict pair type.
data a :* b = !a :* !b
            deriving ((a :* b) -> (a :* b) -> Bool
((a :* b) -> (a :* b) -> Bool)
-> ((a :* b) -> (a :* b) -> Bool) -> Eq (a :* b)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall a b. (Eq a, Eq b) => (a :* b) -> (a :* b) -> Bool
/= :: (a :* b) -> (a :* b) -> Bool
$c/= :: forall a b. (Eq a, Eq b) => (a :* b) -> (a :* b) -> Bool
== :: (a :* b) -> (a :* b) -> Bool
$c== :: forall a b. (Eq a, Eq b) => (a :* b) -> (a :* b) -> Bool
Eq, Eq (a :* b)
Eq (a :* b)
-> ((a :* b) -> (a :* b) -> Ordering)
-> ((a :* b) -> (a :* b) -> Bool)
-> ((a :* b) -> (a :* b) -> Bool)
-> ((a :* b) -> (a :* b) -> Bool)
-> ((a :* b) -> (a :* b) -> Bool)
-> ((a :* b) -> (a :* b) -> a :* b)
-> ((a :* b) -> (a :* b) -> a :* b)
-> Ord (a :* b)
(a :* b) -> (a :* b) -> Bool
(a :* b) -> (a :* b) -> Ordering
(a :* b) -> (a :* b) -> a :* b
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall {a} {b}. (Ord a, Ord b) => Eq (a :* b)
forall a b. (Ord a, Ord b) => (a :* b) -> (a :* b) -> Bool
forall a b. (Ord a, Ord b) => (a :* b) -> (a :* b) -> Ordering
forall a b. (Ord a, Ord b) => (a :* b) -> (a :* b) -> a :* b
min :: (a :* b) -> (a :* b) -> a :* b
$cmin :: forall a b. (Ord a, Ord b) => (a :* b) -> (a :* b) -> a :* b
max :: (a :* b) -> (a :* b) -> a :* b
$cmax :: forall a b. (Ord a, Ord b) => (a :* b) -> (a :* b) -> a :* b
>= :: (a :* b) -> (a :* b) -> Bool
$c>= :: forall a b. (Ord a, Ord b) => (a :* b) -> (a :* b) -> Bool
> :: (a :* b) -> (a :* b) -> Bool
$c> :: forall a b. (Ord a, Ord b) => (a :* b) -> (a :* b) -> Bool
<= :: (a :* b) -> (a :* b) -> Bool
$c<= :: forall a b. (Ord a, Ord b) => (a :* b) -> (a :* b) -> Bool
< :: (a :* b) -> (a :* b) -> Bool
$c< :: forall a b. (Ord a, Ord b) => (a :* b) -> (a :* b) -> Bool
compare :: (a :* b) -> (a :* b) -> Ordering
$ccompare :: forall a b. (Ord a, Ord b) => (a :* b) -> (a :* b) -> Ordering
Ord, Int -> (a :* b) -> ShowS
[a :* b] -> ShowS
(a :* b) -> String
(Int -> (a :* b) -> ShowS)
-> ((a :* b) -> String) -> ([a :* b] -> ShowS) -> Show (a :* b)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall a b. (Show a, Show b) => Int -> (a :* b) -> ShowS
forall a b. (Show a, Show b) => [a :* b] -> ShowS
forall a b. (Show a, Show b) => (a :* b) -> String
showList :: [a :* b] -> ShowS
$cshowList :: forall a b. (Show a, Show b) => [a :* b] -> ShowS
show :: (a :* b) -> String
$cshow :: forall a b. (Show a, Show b) => (a :* b) -> String
showsPrec :: Int -> (a :* b) -> ShowS
$cshowsPrec :: forall a b. (Show a, Show b) => Int -> (a :* b) -> ShowS
Show)

-- | Compute the nearest power of two greater to or equal than the
-- given number.
nextPowerOfTwo :: Int -> Int
{-# INLINE nextPowerOfTwo #-}
nextPowerOfTwo :: Int -> Int
nextPowerOfTwo Int
n =
    let a :: Int
a = Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1
        b :: Int
b = Int
a Int -> Int -> Int
forall a. Bits a => a -> a -> a
.|. (Int
a Int -> Int -> Int
forall a. FastShift a => a -> Int -> a
`shiftR` Int
1)
        c :: Int
c = Int
b Int -> Int -> Int
forall a. Bits a => a -> a -> a
.|. (Int
b Int -> Int -> Int
forall a. FastShift a => a -> Int -> a
`shiftR` Int
2)
        d :: Int
d = Int
c Int -> Int -> Int
forall a. Bits a => a -> a -> a
.|. (Int
c Int -> Int -> Int
forall a. FastShift a => a -> Int -> a
`shiftR` Int
4)
        e :: Int
e = Int
d Int -> Int -> Int
forall a. Bits a => a -> a -> a
.|. (Int
d Int -> Int -> Int
forall a. FastShift a => a -> Int -> a
`shiftR` Int
8)
        f :: Int
f = Int
e Int -> Int -> Int
forall a. Bits a => a -> a -> a
.|. (Int
e Int -> Int -> Int
forall a. FastShift a => a -> Int -> a
`shiftR` Int
16)
        g :: Int
g = Int
f Int -> Int -> Int
forall a. Bits a => a -> a -> a
.|. (Int
f Int -> Int -> Int
forall a. FastShift a => a -> Int -> a
`shiftR` Int
32)  -- in case we're on a 64-bit host
        !h :: Int
h = Int
g Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
    in Int
h

-- | This is a workaround for poor optimisation in GHC 6.8.2.  It
-- fails to notice constant-width shifts, and adds a test and branch
-- to every shift.  This imposes about a 10% performance hit.
class FastShift a where
    shiftL :: a -> Int -> a
    shiftR :: a -> Int -> a

instance FastShift Word32 where
    {-# INLINE shiftL #-}
    shiftL :: Word32 -> Int -> Word32
shiftL (W32# Word#
x#) (I# Int#
i#) = Word# -> Word32
W32# (Word#
x# Word# -> Int# -> Word#
`uncheckedShiftL#` Int#
i#)

    {-# INLINE shiftR #-}
    shiftR :: Word32 -> Int -> Word32
shiftR (W32# Word#
x#) (I# Int#
i#) = Word# -> Word32
W32# (Word#
x# Word# -> Int# -> Word#
`uncheckedShiftRL#` Int#
i#)

instance FastShift Word64 where
    {-# INLINE shiftL #-}
    shiftL :: Word64 -> Int -> Word64
shiftL (W64# Word#
x#) (I# Int#
i#) = Word# -> Word64
W64# (Word#
x# Word# -> Int# -> Word#
`uncheckedShiftL64#` Int#
i#)

    {-# INLINE shiftR #-}
    shiftR :: Word64 -> Int -> Word64
shiftR (W64# Word#
x#) (I# Int#
i#) = Word# -> Word64
W64# (Word#
x# Word# -> Int# -> Word#
`uncheckedShiftRL64#` Int#
i#)

instance FastShift Int where
    {-# INLINE shiftL #-}
    shiftL :: Int -> Int -> Int
shiftL (I# Int#
x#) (I# Int#
i#) = Int# -> Int
I# (Int#
x# Int# -> Int# -> Int#
`iShiftL#` Int#
i#)

    {-# INLINE shiftR #-}
    shiftR :: Int -> Int -> Int
shiftR (I# Int#
x#) (I# Int#
i#) = Int# -> Int
I# (Int#
x# Int# -> Int# -> Int#
`iShiftRA#` Int#
i#)

instance FastShift Integer where
    {-# INLINE shiftL #-}
    shiftL :: Integer -> Int -> Integer
shiftL = Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
Bits.shiftL

    {-# INLINE shiftR #-}
    shiftR :: Integer -> Int -> Integer
shiftR = Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
Bits.shiftR