-- |
-- 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
showList :: [FnvHash32] -> ShowS
$cshowList :: [FnvHash32] -> ShowS
show :: FnvHash32 -> String
$cshow :: FnvHash32 -> String
showsPrec :: Int -> FnvHash32 -> ShowS
$cshowsPrec :: Int -> FnvHash32 -> ShowS
Show,FnvHash32 -> FnvHash32 -> Bool
(FnvHash32 -> FnvHash32 -> Bool)
-> (FnvHash32 -> FnvHash32 -> Bool) -> Eq FnvHash32
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: FnvHash32 -> FnvHash32 -> Bool
$c/= :: FnvHash32 -> FnvHash32 -> Bool
== :: FnvHash32 -> FnvHash32 -> Bool
$c== :: 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
min :: FnvHash32 -> FnvHash32 -> FnvHash32
$cmin :: FnvHash32 -> FnvHash32 -> FnvHash32
max :: FnvHash32 -> FnvHash32 -> FnvHash32
$cmax :: FnvHash32 -> FnvHash32 -> FnvHash32
>= :: FnvHash32 -> FnvHash32 -> Bool
$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
compare :: FnvHash32 -> FnvHash32 -> Ordering
$ccompare :: FnvHash32 -> FnvHash32 -> Ordering
$cp1Ord :: Eq FnvHash32
Ord,FnvHash32 -> ()
(FnvHash32 -> ()) -> NFData FnvHash32
forall a. (a -> ()) -> NFData a
rnf :: FnvHash32 -> ()
$crnf :: 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
showList :: [FnvHash64] -> ShowS
$cshowList :: [FnvHash64] -> ShowS
show :: FnvHash64 -> String
$cshow :: FnvHash64 -> String
showsPrec :: Int -> FnvHash64 -> ShowS
$cshowsPrec :: Int -> FnvHash64 -> ShowS
Show,FnvHash64 -> FnvHash64 -> Bool
(FnvHash64 -> FnvHash64 -> Bool)
-> (FnvHash64 -> FnvHash64 -> Bool) -> Eq FnvHash64
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: FnvHash64 -> FnvHash64 -> Bool
$c/= :: FnvHash64 -> FnvHash64 -> Bool
== :: FnvHash64 -> FnvHash64 -> Bool
$c== :: 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
min :: FnvHash64 -> FnvHash64 -> FnvHash64
$cmin :: FnvHash64 -> FnvHash64 -> FnvHash64
max :: FnvHash64 -> FnvHash64 -> FnvHash64
$cmax :: FnvHash64 -> FnvHash64 -> FnvHash64
>= :: FnvHash64 -> FnvHash64 -> Bool
$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
compare :: FnvHash64 -> FnvHash64 -> Ordering
$ccompare :: FnvHash64 -> FnvHash64 -> Ordering
$cp1Ord :: Eq FnvHash64
Ord,FnvHash64 -> ()
(FnvHash64 -> ()) -> NFData FnvHash64
forall a. (a -> ()) -> NFData a
rnf :: FnvHash64 -> ()
$crnf :: 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 (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
                Word8
v <- Addr# -> Int -> IO Word8
read8 Addr#
addr Int
i
                FnvHash32 -> Int -> IO FnvHash32
loop (Word8 -> FnvHash32 -> FnvHash32
fnv1_32_Mix8 Word8
v FnvHash32
acc) (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
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 (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
                Word8
v <- Addr# -> Int -> IO Word8
read8 Addr#
addr Int
i
                FnvHash32 -> Int -> IO FnvHash32
loop (Word8 -> FnvHash32 -> FnvHash32
fnv1a_32_Mix8 Word8
v FnvHash32
acc) (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
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 (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
                Word8
v <- Addr# -> Int -> IO Word8
read8 Addr#
addr Int
i
                FnvHash64 -> Int -> IO FnvHash64
loop (Word8 -> FnvHash64 -> FnvHash64
fnv1_64_Mix8 Word8
v FnvHash64
acc) (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
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 (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
                Word8
v <- Addr# -> Int -> IO Word8
read8 Addr#
addr Int
i
                FnvHash64 -> Int -> IO FnvHash64
loop (Word8 -> FnvHash64 -> FnvHash64
fnv1a_64_Mix8 Word8
v FnvHash64
acc) (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
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, Word# #)
forall d. Addr# -> Int# -> State# d -> (# State# d, Word# #)
readWord8OffAddr# Addr#
addr Int#
i State# RealWorld
s of
    (# State# RealWorld
s2, Word#
e #) -> (# State# RealWorld
s2, Word# -> Word8
W8# Word#
e #)