1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
-- |
-- 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 Data.Memory.Internal.Compat ()
import Data.Memory.Internal.CompatPrim
import Data.Memory.Internal.CompatPrim64
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 (Show,Eq,Ord,NFData)
-- | FNV1(a) hash (64 bit variants)
newtype FnvHash64 = FnvHash64 Word64
deriving (Show,Eq,Ord,NFData)
-- | compute FNV1 (32 bit variant) of a raw piece of memory
fnv1 :: Ptr Word8 -> Int -> IO FnvHash32
fnv1 (Ptr addr) (I# n) = IO $ \s -> loop 0x811c9dc5## 0# s
where
loop :: Word# -> Int# -> State# s -> (# State# s, FnvHash32 #)
loop !acc i s
| booleanPrim (i ==# n) = (# s, FnvHash32 $ W32# (narrow32Word# acc) #)
| otherwise =
case readWord8OffAddr# addr i s of
(# s2, v #) ->
let !nacc = (0x01000193## `timesWord#` acc) `xor#` v
in loop nacc (i +# 1#) s2
-- | compute FNV1a (32 bit variant) of a raw piece of memory
fnv1a :: Ptr Word8 -> Int -> IO FnvHash32
fnv1a (Ptr addr) (I# n) = IO $ \s -> loop 0x811c9dc5## 0# s
where
loop :: Word# -> Int# -> State# s -> (# State# s, FnvHash32 #)
loop !acc i s
| booleanPrim (i ==# n) = (# s, FnvHash32 $ W32# (narrow32Word# acc) #)
| otherwise =
case readWord8OffAddr# addr i s of
(# s2, v #) ->
let !nacc = 0x01000193## `timesWord#` (acc `xor#` v)
in loop nacc (i +# 1#) s2
-- | compute FNV1 (64 bit variant) of a raw piece of memory
fnv1_64 :: Ptr Word8 -> Int -> IO FnvHash64
fnv1_64 (Ptr addr) (I# n) = IO $ \s -> loop fnv64Const 0# s
where
loop :: Word64# -> Int# -> State# s -> (# State# s, FnvHash64 #)
loop !acc i s
| booleanPrim (i ==# n) = (# s, FnvHash64 $ W64# acc #)
| otherwise =
case readWord8OffAddr# addr i s of
(# s2, v #) ->
let !nacc = (fnv64Prime `timesWord64#` acc) `xor64#` (wordToWord64# v)
in loop nacc (i +# 1#) s2
fnv64Const :: Word64#
!fnv64Const = w64# 0xcbf29ce484222325## 0xcbf29ce4## 0x84222325##
fnv64Prime :: Word64#
!fnv64Prime = w64# 0x100000001b3## 0x100## 0x000001b3##
-- | compute FNV1a (64 bit variant) of a raw piece of memory
fnv1a_64 :: Ptr Word8 -> Int -> IO FnvHash64
fnv1a_64 (Ptr addr) (I# n) = IO $ \s -> loop fnv64Const 0# s
where
loop :: Word64# -> Int# -> State# s -> (# State# s, FnvHash64 #)
loop !acc i s
| booleanPrim (i ==# n) = (# s, FnvHash64 $ W64# acc #)
| otherwise =
case readWord8OffAddr# addr i s of
(# s2, v #) ->
let !nacc = fnv64Prime `timesWord64#` (acc `xor64#` wordToWord64# v)
in loop nacc (i +# 1#) s2
fnv64Const :: Word64#
!fnv64Const = w64# 0xcbf29ce484222325## 0xcbf29ce4## 0x84222325##
fnv64Prime :: Word64#
!fnv64Prime = w64# 0x100000001b3## 0x100## 0x000001b3##
|
