-
Notifications
You must be signed in to change notification settings - Fork 2
/
Murmur3.purs
135 lines (117 loc) · 2.94 KB
/
Murmur3.purs
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
-- | Murmur 3 hash function for hashing strings
module Murmur3
( hashString
) where
import Prelude hiding (zero, one)
import Data.Array (foldl)
import Data.BigInt (BigInt, and, fromBase, or, xor)
import Data.BigInt as BigInt
import Data.Char (toCharCode)
import Data.Maybe (fromJust)
import Data.String (toCharArray)
import Partial.Unsafe (unsafePartial)
type HashData =
{ shift :: Number
, seed :: BigInt
, hash :: BigInt
, charsProcessed :: BigInt
}
-- | Takes a seed and a string. Produces a hash (integer).
-- |
-- | Given the same seed and string, it will always produce the same hash.
-- |
-- | ```purescript
-- | hashString 1234 "Turn me into a hash" == 4138100590
-- | ````
hashString :: BigInt -> String -> BigInt
hashString seed str =
str
# toCharArray
>>> map (toCharCode >>> BigInt.fromInt)
>>> foldl hashFold { shift: 0.0, seed, hash: zero, charsProcessed: zero }
>>> finalize
hashFold :: HashData -> BigInt -> HashData
hashFold data_ c =
let
res = c
# shl data_.shift
>>> or data_.hash
in
case data_.shift of
24.0 ->
let
newHash =
res
# mix data_.seed
>>> step
in
{ shift: 0.0
, seed: newHash
, hash: zero
, charsProcessed: data_.charsProcessed + one
}
_ ->
{ shift: data_.shift + 8.0
, seed: data_.seed
, hash: res
, charsProcessed: data_.charsProcessed + one
}
finalize :: HashData -> BigInt
finalize data_ =
let
acc =
if data_.hash /= zero
then mix data_.seed data_.hash
else data_.seed
h1 = acc `xor` data_.charsProcessed
h2 = h1
# shr 16.0 -- zshr
>>> xor h1
>>> mur x85EBCA6B
h3 = h2
# shr 13.0 -- zshr
>>> xor h2
>>> mur xC2B2AE35
in
h3
# shr 16.0 -- zshr
>>> xor h3
>>> shr 0.0 -- zshr
mix :: BigInt -> BigInt -> BigInt
mix h1 h2 =
let
k1 = mur xCC9E2D51 h2
in
k1
# shl 15.0
>>> or (shr 17.0 k1) -- zshr
>>> mur x1B873593
>>> xor h1
mur :: BigInt -> BigInt -> BigInt
mur c h =
and xFFFFFFFF ((and h xFFFF * c) + shl 16.0 (and xFFFF (shr 16.0 h * c))) -- zshr
step :: BigInt -> BigInt
step acc =
let
h1 = shl 13.0 acc
# or (shr 19.0 acc) -- zshr
>>> mur five
in
(and h1 xFFFF + x6B64) + shl 16.0 (and xFFFF (shr 16.0 h1 + xE654)) -- zshr
shl :: Number -> BigInt -> BigInt
shl = flip BigInt.shl
shr :: Number -> BigInt -> BigInt
shr = flip BigInt.shr
zero = BigInt.fromInt 0 :: BigInt
one = BigInt.fromInt 1 :: BigInt
five = BigInt.fromInt 5 :: BigInt
x :: String -> BigInt
x = unsafePartial $ fromJust <<< fromBase 16
x6B64 = x "6B64" :: BigInt
xE654 = x "E654" :: BigInt
xFFFF = x "FFFF" :: BigInt
x1B873593 = x "1B873593" :: BigInt
x85EBCA6B = x "85EBCA6B" :: BigInt
xC2B2AE35 = x "C2B2AE35" :: BigInt
xCC9E2D51 = x "CC9E2D51" :: BigInt
xFFFFFFFF = x "FFFFFFFF" :: BigInt