    -- |
    -- Module      : Data.Memory.Hash.FNV
    -- License     : BSD-style
    -- Maintainer  : Vincent Hanquez <vincent@snarc.org>
    -- Stability   : experimental
    -- Portability : good
    --
    -- Fowler Noll Vo Hash (1 and 1a / 32 / 64 bits versions)
    -- <http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function>
    --
    {-# LANGUAGE GeneralizedNewtypeDeriving #-}
    {-# LANGUAGE MagicHash                  #-}
    {-# LANGUAGE UnboxedTuples              #-}
    {-# LANGUAGE BangPatterns               #-}
    module Data.Memory.Hash.FNV
        (
        -- * types
          FnvHash32(..)
        , FnvHash64(..)
        -- * methods
        , fnv1
        , fnv1a
        , fnv1_64
        , fnv1a_64
        ) where

    import           Basement.Bits
    import           Basement.IntegralConv
    import           Data.Memory.Internal.Compat ()
    import           Data.Memory.Internal.Imports
    import           GHC.Word
    import           GHC.Prim hiding (Word64#, Int64#)
    import           GHC.Types
    import           GHC.Ptr

    -- | FNV1(a) hash (32 bit variants)
    newtype FnvHash32 = FnvHash32 Word32
        deriving (Int -> FnvHash32 -> ShowS
    [FnvHash32] -> ShowS
    FnvHash32 -> String
    (Int -> FnvHash32 -> ShowS)
    -> (FnvHash32 -> String)
    -> ([FnvHash32] -> ShowS)
    -> Show FnvHash32
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: Int -> FnvHash32 -> ShowS
    showsPrec :: Int -> FnvHash32 -> ShowS
    $cshow :: FnvHash32 -> String
    show :: FnvHash32 -> String
    $cshowList :: [FnvHash32] -> ShowS
    showList :: [FnvHash32] -> ShowS
    Show,FnvHash32 -> FnvHash32 -> Bool
    (FnvHash32 -> FnvHash32 -> Bool)
    -> (FnvHash32 -> FnvHash32 -> Bool) -> Eq FnvHash32
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: FnvHash32 -> FnvHash32 -> Bool
    == :: FnvHash32 -> FnvHash32 -> Bool
    $c/= :: FnvHash32 -> FnvHash32 -> Bool
    /= :: FnvHash32 -> FnvHash32 -> Bool
    Eq,Eq FnvHash32
    Eq FnvHash32 =>
    (FnvHash32 -> FnvHash32 -> Ordering)
    -> (FnvHash32 -> FnvHash32 -> Bool)
    -> (FnvHash32 -> FnvHash32 -> Bool)
    -> (FnvHash32 -> FnvHash32 -> Bool)
    -> (FnvHash32 -> FnvHash32 -> Bool)
    -> (FnvHash32 -> FnvHash32 -> FnvHash32)
    -> (FnvHash32 -> FnvHash32 -> FnvHash32)
    -> Ord FnvHash32
    FnvHash32 -> FnvHash32 -> Bool
    FnvHash32 -> FnvHash32 -> Ordering
    FnvHash32 -> FnvHash32 -> FnvHash32
    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
    $ccompare :: FnvHash32 -> FnvHash32 -> Ordering
    compare :: FnvHash32 -> FnvHash32 -> Ordering
    $c< :: FnvHash32 -> FnvHash32 -> Bool
    < :: FnvHash32 -> FnvHash32 -> Bool
    $c<= :: FnvHash32 -> FnvHash32 -> Bool
    <= :: FnvHash32 -> FnvHash32 -> Bool
    $c> :: FnvHash32 -> FnvHash32 -> Bool
    > :: FnvHash32 -> FnvHash32 -> Bool
    $c>= :: FnvHash32 -> FnvHash32 -> Bool
    >= :: FnvHash32 -> FnvHash32 -> Bool
    $cmax :: FnvHash32 -> FnvHash32 -> FnvHash32
    max :: FnvHash32 -> FnvHash32 -> FnvHash32
    $cmin :: FnvHash32 -> FnvHash32 -> FnvHash32
    min :: FnvHash32 -> FnvHash32 -> FnvHash32
    Ord,FnvHash32 -> ()
    (FnvHash32 -> ()) -> NFData FnvHash32
    forall a. (a -> ()) -> NFData a
    $crnf :: FnvHash32 -> ()
    rnf :: FnvHash32 -> ()
    NFData)

    -- | FNV1(a) hash (64 bit variants)
    newtype FnvHash64 = FnvHash64 Word64
        deriving (Int -> FnvHash64 -> ShowS
    [FnvHash64] -> ShowS
    FnvHash64 -> String
    (Int -> FnvHash64 -> ShowS)
    -> (FnvHash64 -> String)
    -> ([FnvHash64] -> ShowS)
    -> Show FnvHash64
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: Int -> FnvHash64 -> ShowS
    showsPrec :: Int -> FnvHash64 -> ShowS
    $cshow :: FnvHash64 -> String
    show :: FnvHash64 -> String
    $cshowList :: [FnvHash64] -> ShowS
    showList :: [FnvHash64] -> ShowS
    Show,FnvHash64 -> FnvHash64 -> Bool
    (FnvHash64 -> FnvHash64 -> Bool)
    -> (FnvHash64 -> FnvHash64 -> Bool) -> Eq FnvHash64
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: FnvHash64 -> FnvHash64 -> Bool
    == :: FnvHash64 -> FnvHash64 -> Bool
    $c/= :: FnvHash64 -> FnvHash64 -> Bool
    /= :: FnvHash64 -> FnvHash64 -> Bool
    Eq,Eq FnvHash64
    Eq FnvHash64 =>
    (FnvHash64 -> FnvHash64 -> Ordering)
    -> (FnvHash64 -> FnvHash64 -> Bool)
    -> (FnvHash64 -> FnvHash64 -> Bool)
    -> (FnvHash64 -> FnvHash64 -> Bool)
    -> (FnvHash64 -> FnvHash64 -> Bool)
    -> (FnvHash64 -> FnvHash64 -> FnvHash64)
    -> (FnvHash64 -> FnvHash64 -> FnvHash64)
    -> Ord FnvHash64
    FnvHash64 -> FnvHash64 -> Bool
    FnvHash64 -> FnvHash64 -> Ordering
    FnvHash64 -> FnvHash64 -> FnvHash64
    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
    $ccompare :: FnvHash64 -> FnvHash64 -> Ordering
    compare :: FnvHash64 -> FnvHash64 -> Ordering
    $c< :: FnvHash64 -> FnvHash64 -> Bool
    < :: FnvHash64 -> FnvHash64 -> Bool
    $c<= :: FnvHash64 -> FnvHash64 -> Bool
    <= :: FnvHash64 -> FnvHash64 -> Bool
    $c> :: FnvHash64 -> FnvHash64 -> Bool
    > :: FnvHash64 -> FnvHash64 -> Bool
    $c>= :: FnvHash64 -> FnvHash64 -> Bool
    >= :: FnvHash64 -> FnvHash64 -> Bool
    $cmax :: FnvHash64 -> FnvHash64 -> FnvHash64
    max :: FnvHash64 -> FnvHash64 -> FnvHash64
    $cmin :: FnvHash64 -> FnvHash64 -> FnvHash64
    min :: FnvHash64 -> FnvHash64 -> FnvHash64
    Ord,FnvHash64 -> ()
    (FnvHash64 -> ()) -> NFData FnvHash64
    forall a. (a -> ()) -> NFData a
    $crnf :: FnvHash64 -> ()
    rnf :: FnvHash64 -> ()
    NFData)

    fnv1_32_Mix8 :: Word8 -> FnvHash32 -> FnvHash32
    fnv1_32_Mix8 :: Word8 -> FnvHash32 -> FnvHash32
    fnv1_32_Mix8 !Word8
    w (FnvHash32 Word32
    acc) = Word32 -> FnvHash32
    FnvHash32 ((Word32
    0x01000193 Word32 -> Word32 -> Word32
    forall a. Num a => a -> a -> a
    * Word32
    acc) Word32 -> Word32 -> Word32
    forall bits. BitOps bits => bits -> bits -> bits
    .^. Word8 -> Word32
    forall a b. IntegralUpsize a b => a -> b
    integralUpsize Word8
    w)
    {-# INLINE fnv1_32_Mix8 #-}

    fnv1a_32_Mix8 :: Word8 -> FnvHash32 -> FnvHash32
    fnv1a_32_Mix8 :: Word8 -> FnvHash32 -> FnvHash32
    fnv1a_32_Mix8 !Word8
    w (FnvHash32 Word32
    acc) = Word32 -> FnvHash32
    FnvHash32 (Word32
    0x01000193 Word32 -> Word32 -> Word32
    forall a. Num a => a -> a -> a
    * (Word32
    acc Word32 -> Word32 -> Word32
    forall bits. BitOps bits => bits -> bits -> bits
    .^. Word8 -> Word32
    forall a b. IntegralUpsize a b => a -> b
    integralUpsize Word8
    w))
    {-# INLINE fnv1a_32_Mix8 #-}

    fnv1_64_Mix8 :: Word8 -> FnvHash64 -> FnvHash64
    fnv1_64_Mix8 :: Word8 -> FnvHash64 -> FnvHash64
    fnv1_64_Mix8 !Word8
    w (FnvHash64 Word64
    acc) = Word64 -> FnvHash64
    FnvHash64 ((Word64
    0x100000001b3 Word64 -> Word64 -> Word64
    forall a. Num a => a -> a -> a
    * Word64
    acc) Word64 -> Word64 -> Word64
    forall bits. BitOps bits => bits -> bits -> bits
    .^. Word8 -> Word64
    forall a b. IntegralUpsize a b => a -> b
    integralUpsize Word8
    w)
    {-# INLINE fnv1_64_Mix8 #-}

    fnv1a_64_Mix8 :: Word8 -> FnvHash64 -> FnvHash64
    fnv1a_64_Mix8 :: Word8 -> FnvHash64 -> FnvHash64
    fnv1a_64_Mix8 !Word8
    w (FnvHash64 Word64
    acc) = Word64 -> FnvHash64
    FnvHash64 (Word64
    0x100000001b3 Word64 -> Word64 -> Word64
    forall a. Num a => a -> a -> a
    * (Word64
    acc Word64 -> Word64 -> Word64
    forall bits. BitOps bits => bits -> bits -> bits
    .^. Word8 -> Word64
    forall a b. IntegralUpsize a b => a -> b
    integralUpsize Word8
    w))
    {-# INLINE fnv1a_64_Mix8 #-}

    -- | compute FNV1 (32 bit variant) of a raw piece of memory
    fnv1 :: Ptr Word8 -> Int -> IO FnvHash32
    fnv1 :: Ptr Word8 -> Int -> IO FnvHash32
    fnv1 (Ptr Addr#
    addr) Int
    n = FnvHash32 -> Int -> IO FnvHash32
    loop (Word32 -> FnvHash32
    FnvHash32 Word32
    0x811c9dc5) Int
    0
      where
            loop :: FnvHash32 -> Int -> IO FnvHash32
            loop :: FnvHash32 -> Int -> IO FnvHash32
    loop !FnvHash32
    acc !Int
    i
                | Int
    i Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == Int
    n    = FnvHash32 -> IO FnvHash32
    forall a. a -> IO a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure (FnvHash32 -> IO FnvHash32) -> FnvHash32 -> IO FnvHash32
    forall a b. (a -> b) -> a -> b
    $ FnvHash32
    acc
                | Bool
    otherwise = do
                    v <- Addr# -> Int -> IO Word8
    read8 Addr#
    addr Int
    i
                    loop (fnv1_32_Mix8 v acc) (i + 1)

    -- | compute FNV1a (32 bit variant) of a raw piece of memory
    fnv1a :: Ptr Word8 -> Int -> IO FnvHash32
    fnv1a :: Ptr Word8 -> Int -> IO FnvHash32
    fnv1a (Ptr Addr#
    addr) Int
    n = FnvHash32 -> Int -> IO FnvHash32
    loop (Word32 -> FnvHash32
    FnvHash32 Word32
    0x811c9dc5) Int
    0
      where
            loop :: FnvHash32 -> Int -> IO FnvHash32
            loop :: FnvHash32 -> Int -> IO FnvHash32
    loop !FnvHash32
    acc !Int
    i
                | Int
    i Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == Int
    n    = FnvHash32 -> IO FnvHash32
    forall a. a -> IO a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure (FnvHash32 -> IO FnvHash32) -> FnvHash32 -> IO FnvHash32
    forall a b. (a -> b) -> a -> b
    $ FnvHash32
    acc
                | Bool
    otherwise = do
                    v <- Addr# -> Int -> IO Word8
    read8 Addr#
    addr Int
    i
                    loop (fnv1a_32_Mix8 v acc) (i + 1)

    -- | compute FNV1 (64 bit variant) of a raw piece of memory
    fnv1_64 :: Ptr Word8 -> Int -> IO FnvHash64
    fnv1_64 :: Ptr Word8 -> Int -> IO FnvHash64
    fnv1_64 (Ptr Addr#
    addr) Int
    n = FnvHash64 -> Int -> IO FnvHash64
    loop (Word64 -> FnvHash64
    FnvHash64 Word64
    0xcbf29ce484222325) Int
    0
      where
            loop :: FnvHash64 -> Int -> IO FnvHash64
            loop :: FnvHash64 -> Int -> IO FnvHash64
    loop !FnvHash64
    acc !Int
    i
                | Int
    i Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == Int
    n    = FnvHash64 -> IO FnvHash64
    forall a. a -> IO a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure (FnvHash64 -> IO FnvHash64) -> FnvHash64 -> IO FnvHash64
    forall a b. (a -> b) -> a -> b
    $ FnvHash64
    acc
                | Bool
    otherwise = do
                    v <- Addr# -> Int -> IO Word8
    read8 Addr#
    addr Int
    i
                    loop (fnv1_64_Mix8 v acc) (i + 1)

    -- | compute FNV1a (64 bit variant) of a raw piece of memory
    fnv1a_64 :: Ptr Word8 -> Int -> IO FnvHash64
    fnv1a_64 :: Ptr Word8 -> Int -> IO FnvHash64
    fnv1a_64 (Ptr Addr#
    addr) Int
    n = FnvHash64 -> Int -> IO FnvHash64
    loop (Word64 -> FnvHash64
    FnvHash64 Word64
    0xcbf29ce484222325) Int
    0
      where
            loop :: FnvHash64 -> Int -> IO FnvHash64
            loop :: FnvHash64 -> Int -> IO FnvHash64
    loop !FnvHash64
    acc !Int
    i
                | Int
    i Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == Int
    n    = FnvHash64 -> IO FnvHash64
    forall a. a -> IO a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure (FnvHash64 -> IO FnvHash64) -> FnvHash64 -> IO FnvHash64
    forall a b. (a -> b) -> a -> b
    $ FnvHash64
    acc
                | Bool
    otherwise = do
                    v <- Addr# -> Int -> IO Word8
    read8 Addr#
    addr Int
    i
                    loop (fnv1a_64_Mix8 v acc) (i + 1)

    read8 :: Addr# -> Int -> IO Word8
    read8 :: Addr# -> Int -> IO Word8
    read8 Addr#
    addr (I# Int#
    i) = (State# RealWorld -> (# State# RealWorld, Word8 #)) -> IO Word8
    forall a. (State# RealWorld -> (# State# RealWorld, a #)) -> IO a
    IO ((State# RealWorld -> (# State# RealWorld, Word8 #)) -> IO Word8)
    -> (State# RealWorld -> (# State# RealWorld, Word8 #)) -> IO Word8
    forall a b. (a -> b) -> a -> b
    $ \State# RealWorld
    s -> case Addr# -> Int# -> State# RealWorld -> (# State# RealWorld, Word8# #)
    forall d. Addr# -> Int# -> State# d -> (# State# d, Word8# #)
    readWord8OffAddr# Addr#
    addr Int#
    i State# RealWorld
    s of
        (# State# RealWorld
    s2, Word8#
    e #) -> (# State# RealWorld
    s2, Word8# -> Word8
    W8# Word8#
    e #)