|
1
|
|
|
<?php |
|
2
|
|
|
|
|
3
|
|
|
namespace Z38\MurmurHash; |
|
4
|
|
|
|
|
5
|
|
|
class Murmur3F implements HashInterface |
|
6
|
|
|
{ |
|
7
|
|
|
private $seed; |
|
8
|
|
|
private $h1; |
|
9
|
|
|
private $h2; |
|
10
|
|
|
private $len; |
|
11
|
|
|
private $tail; |
|
12
|
|
|
private static $c1; |
|
13
|
|
|
private static $c2; |
|
14
|
|
|
private static $m1; |
|
15
|
|
|
private static $m2; |
|
16
|
|
|
private static $fmix1; |
|
17
|
|
|
private static $fmix2; |
|
18
|
|
|
private static $mask64; |
|
19
|
|
|
|
|
20
|
14 |
|
public function __construct($seed = 0) |
|
21
|
|
|
{ |
|
22
|
14 |
|
self::init(); |
|
23
|
14 |
|
$this->seed = $seed; |
|
24
|
14 |
|
$this->reset(); |
|
25
|
14 |
|
} |
|
26
|
|
|
|
|
27
|
14 |
|
public function reset() |
|
28
|
|
|
{ |
|
29
|
14 |
|
$this->h1 = $this->seed; |
|
30
|
14 |
|
$this->h2 = $this->seed; |
|
31
|
14 |
|
$this->len = 0; |
|
32
|
14 |
|
$this->tail = ''; |
|
33
|
14 |
|
} |
|
34
|
|
|
|
|
35
|
14 |
|
public function write($data) |
|
36
|
|
|
{ |
|
37
|
14 |
|
$this->len += strlen($data); |
|
38
|
14 |
|
$this->tail .= $data; |
|
39
|
14 |
|
while (strlen($this->tail) >= 16) { |
|
40
|
5 |
|
$k1 = gmp_init(bin2hex(strrev(substr($this->tail, 0, 8))), 16); |
|
41
|
5 |
|
$k2 = gmp_init(bin2hex(strrev(substr($this->tail, 8, 8))), 16); |
|
42
|
5 |
|
$this->tail = substr($this->tail, 16); |
|
43
|
|
|
|
|
44
|
5 |
|
$h1 = $this->h1; |
|
45
|
5 |
|
$h2 = $this->h2; |
|
46
|
|
|
|
|
47
|
5 |
|
$k1 = self::mul64($k1, self::$c1); |
|
48
|
5 |
|
$k1 = self::rotl64($k1, 31); |
|
49
|
5 |
|
$k1 = self::mul64($k1, self::$c2); |
|
50
|
5 |
|
$h1 = gmp_xor($h1, $k1); |
|
51
|
|
|
|
|
52
|
5 |
|
$h1 = self::rotl64($h1, 27); |
|
53
|
5 |
|
$h1 = self::add64($h1, $h2); |
|
54
|
5 |
|
$h1 = self::add64(gmp_mul(5, $h1), self::$m1); |
|
55
|
|
|
|
|
56
|
5 |
|
$k2 = self::mul64($k2, self::$c2); |
|
57
|
5 |
|
$k2 = self::rotl64($k2, 33); |
|
58
|
5 |
|
$k2 = self::mul64($k2, self::$c1); |
|
59
|
5 |
|
$h2 = gmp_xor($h2, $k2); |
|
60
|
|
|
|
|
61
|
5 |
|
$h2 = self::rotl64($h2, 31); |
|
62
|
5 |
|
$h2 = self::add64($h2, $h1); |
|
63
|
5 |
|
$h2 = self::add64(gmp_mul(5, $h2), self::$m2); |
|
64
|
|
|
|
|
65
|
5 |
|
$this->h1 = $h1; |
|
66
|
5 |
|
$this->h2 = $h2; |
|
67
|
5 |
|
} |
|
68
|
14 |
|
} |
|
69
|
|
|
|
|
70
|
14 |
|
public function sum() |
|
71
|
|
|
{ |
|
72
|
14 |
|
$h1 = $this->h1; |
|
73
|
14 |
|
$h2 = $this->h2; |
|
74
|
|
|
|
|
75
|
14 |
|
$k1 = 0; |
|
76
|
14 |
|
$k2 = 0; |
|
77
|
|
|
|
|
78
|
14 |
|
$tail = array_values(unpack('C*', $this->tail)); |
|
79
|
14 |
|
$len = count($tail); |
|
80
|
14 |
|
for ($i = $len; $i > 8; --$i) { |
|
81
|
7 |
|
$k2 = gmp_xor($k2, self::shiftl64($tail[$i - 1], ($i - 9) * 8)); |
|
82
|
7 |
|
} |
|
83
|
14 |
|
if ($len > 8) { |
|
84
|
7 |
|
$k2 = self::mul64($k2, self::$c2); |
|
85
|
7 |
|
$k2 = self::rotl64($k2, 33); |
|
86
|
7 |
|
$k2 = self::mul64($k2, self::$c1); |
|
87
|
7 |
|
$h2 = gmp_xor($h2, $k2); |
|
88
|
7 |
|
} |
|
89
|
14 |
|
for ($i = min($len, 8); $i > 0; --$i) { |
|
90
|
13 |
|
$k1 = gmp_xor($k1, self::shiftl64($tail[$i - 1], ($i - 1) * 8)); |
|
91
|
13 |
|
} |
|
92
|
14 |
|
if ($len > 0) { |
|
93
|
13 |
|
$k1 = self::mul64($k1, self::$c1); |
|
94
|
13 |
|
$k1 = self::rotl64($k1, 31); |
|
95
|
13 |
|
$k1 = self::mul64($k1, self::$c2); |
|
96
|
13 |
|
$h1 = gmp_xor($h1, $k1); |
|
97
|
13 |
|
} |
|
98
|
|
|
|
|
99
|
14 |
|
$h1 = gmp_xor($h1, $this->len); |
|
100
|
14 |
|
$h2 = gmp_xor($h2, $this->len); |
|
101
|
14 |
|
$h1 = self::add64($h1, $h2); |
|
102
|
14 |
|
$h2 = self::add64($h2, $h1); |
|
103
|
14 |
|
$h1 = self::fmix64($h1); |
|
104
|
14 |
|
$h2 = self::fmix64($h2); |
|
105
|
14 |
|
$h1 = self::add64($h1, $h2); |
|
106
|
14 |
|
$h2 = self::add64($h2, $h1); |
|
107
|
|
|
|
|
108
|
14 |
|
return self::export64($h1).self::export64($h2); |
|
109
|
|
|
} |
|
110
|
|
|
|
|
111
|
14 |
|
private static function init() |
|
112
|
|
|
{ |
|
113
|
14 |
|
if (self::$c1 !== null) { |
|
114
|
13 |
|
return; |
|
115
|
|
|
} |
|
116
|
|
|
|
|
117
|
1 |
|
self::$c1 = gmp_init('0x87c37b91114253d5'); |
|
118
|
1 |
|
self::$c2 = gmp_init('0x4cf5ad432745937f'); |
|
119
|
1 |
|
self::$m1 = gmp_init('0x52dce729'); |
|
120
|
1 |
|
self::$m2 = gmp_init('0x38495ab5'); |
|
121
|
1 |
|
self::$fmix1 = gmp_init('0xff51afd7ed558ccd'); |
|
122
|
1 |
|
self::$fmix2 = gmp_init('0xc4ceb9fe1a85ec53'); |
|
123
|
1 |
|
self::$mask64 = gmp_init('0xffffffffffffffff'); |
|
124
|
1 |
|
} |
|
125
|
|
|
|
|
126
|
14 |
|
private static function fmix64($x) |
|
127
|
|
|
{ |
|
128
|
14 |
|
$x = gmp_xor($x, self::shiftr($x, 33)); |
|
129
|
14 |
|
$x = self::mul64($x, self::$fmix1); |
|
130
|
14 |
|
$x = gmp_xor($x, self::shiftr($x, 33)); |
|
131
|
14 |
|
$x = self::mul64($x, self::$fmix2); |
|
132
|
14 |
|
$x = gmp_xor($x, self::shiftr($x, 33)); |
|
133
|
|
|
|
|
134
|
14 |
|
return $x; |
|
135
|
|
|
} |
|
136
|
|
|
|
|
137
|
13 |
|
private static function rotl64($x, $r) |
|
138
|
|
|
{ |
|
139
|
13 |
|
return gmp_and(gmp_or( |
|
140
|
13 |
|
self::shiftl($x, $r), |
|
141
|
13 |
|
self::shiftr($x, 64 - $r) |
|
142
|
13 |
|
), self::$mask64); |
|
143
|
|
|
} |
|
144
|
|
|
|
|
145
|
14 |
|
private static function export64($x) |
|
146
|
|
|
{ |
|
147
|
14 |
|
return strrev(pack('H*', str_pad(gmp_strval($x, 16), 16, '0', STR_PAD_LEFT))); |
|
148
|
|
|
} |
|
149
|
|
|
|
|
150
|
13 |
|
private static function shiftl64($x, $shift) |
|
151
|
|
|
{ |
|
152
|
13 |
|
return gmp_and(self::shiftl($x, $shift), self::$mask64); |
|
153
|
|
|
} |
|
154
|
|
|
|
|
155
|
13 |
|
private static function shiftl($x, $shift) |
|
156
|
|
|
{ |
|
157
|
13 |
|
return gmp_mul($x, gmp_pow(2, $shift)); |
|
158
|
|
|
} |
|
159
|
|
|
|
|
160
|
14 |
|
private static function shiftr($x, $shift) |
|
161
|
|
|
{ |
|
162
|
14 |
|
return gmp_div($x, gmp_pow(2, $shift)); |
|
163
|
|
|
} |
|
164
|
|
|
|
|
165
|
14 |
|
private static function mul64($a, $b) |
|
166
|
|
|
{ |
|
167
|
14 |
|
return gmp_and(gmp_mul($a, $b), self::$mask64); |
|
168
|
|
|
} |
|
169
|
|
|
|
|
170
|
14 |
|
private static function add64($a, $b) |
|
171
|
|
|
{ |
|
172
|
14 |
|
return gmp_and(gmp_add($a, $b), self::$mask64); |
|
173
|
|
|
} |
|
174
|
|
|
} |
|
175
|
|
|
|
z38 /
murmurhash
