Line data Source code
1 : // SPDX-License-Identifier: GPL-3.0-or-later
2 : // Copyright (C) 2011 Andrea Mazzoleni
3 :
4 : /*
5 : * Derivative work from MurmorHash3.cpp revision r136
6 : *
7 : * SMHasher & MurmurHash
8 : * http://code.google.com/p/smhasher/
9 : *
10 : * Exact source used as reference:
11 : * http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp?spec=svn136&r=136
12 : */
13 :
14 : // MurmurHash3 was written by Austin Appleby, and is placed in the public
15 : // domain. The author hereby disclaims copyright to this source code.
16 :
17 : /* Finalization mix - force all bits of a hash block to avalanche */
18 9032580 : static inline uint32_t fmix32(uint32_t h)
19 : {
20 9032580 : h ^= h >> 16;
21 9032580 : h *= 0x85ebca6b;
22 9032580 : h ^= h >> 13;
23 9032580 : h *= 0xc2b2ae35;
24 9032580 : h ^= h >> 16;
25 9032580 : return h;
26 : }
27 :
28 : /*
29 : * Warning!
30 : * Don't declare these variables static, otherwise the gcc optimizer
31 : * may generate very slow code for multiplication with these constants,
32 : * like:
33 :
34 : -> .cpp
35 : k1 *= c1;
36 : -> .asm
37 : 152: 8d 14 80 lea (%eax,%eax,4),%edx
38 : 155: 8d 14 90 lea (%eax,%edx,4),%edx
39 : 158: c1 e2 03 shl $0x3,%edx
40 : 15b: 29 c2 sub %eax,%edx
41 : 15d: 8d 14 d2 lea (%edx,%edx,8),%edx
42 : 160: 8d 14 90 lea (%eax,%edx,4),%edx
43 : 163: 8d 14 d0 lea (%eax,%edx,8),%edx
44 : 166: 8d 14 90 lea (%eax,%edx,4),%edx
45 : 169: 8d 14 50 lea (%eax,%edx,2),%edx
46 : 16c: 8d 14 90 lea (%eax,%edx,4),%edx
47 : 16f: 8d 14 92 lea (%edx,%edx,4),%edx
48 : 172: 8d 14 50 lea (%eax,%edx,2),%edx
49 : 175: 8d 04 d0 lea (%eax,%edx,8),%eax
50 : 178: 8d 14 c5 00 00 00 00 lea 0x0(,%eax,8),%edx
51 : 17f: 29 d0 sub %edx,%eax
52 :
53 : * resulting in speeds of 500 MB/s instead of 3000 MB/s.
54 : *
55 : * Verified with gcc 4.4.4 compiling with :
56 : *
57 : * g++ -g -c -O2 MurmurHash3.cpp -o MurmurHash3.o
58 : */
59 : uint32_t c1 = 0x239b961b;
60 : uint32_t c2 = 0xab0e9789;
61 : uint32_t c3 = 0x38b34ae5;
62 : uint32_t c4 = 0xa1e38b93;
63 :
64 2258145 : void MurmurHash3_x86_128(const void* data, size_t size, const uint8_t* seed, void* digest)
65 : {
66 : size_t nblocks;
67 : const uint32_t* blocks;
68 : const uint32_t* end;
69 : size_t size_remainder;
70 : uint32_t h1, h2, h3, h4;
71 :
72 2258145 : h1 = util_read32(seed + 0);
73 2258145 : h2 = util_read32(seed + 4);
74 2258145 : h3 = util_read32(seed + 8);
75 2258145 : h4 = util_read32(seed + 12);
76 :
77 2258145 : nblocks = size / 16;
78 2258145 : blocks = data;
79 2258145 : end = blocks + nblocks * 4;
80 :
81 : /* body */
82 118033901 : while (blocks < end) {
83 115775756 : uint32_t k1 = blocks[0];
84 115775756 : uint32_t k2 = blocks[1];
85 115775756 : uint32_t k3 = blocks[2];
86 115775756 : uint32_t k4 = blocks[3];
87 :
88 : #if WORDS_BIGENDIAN
89 : k1 = util_swap32(k1);
90 : k2 = util_swap32(k2);
91 : k3 = util_swap32(k3);
92 : k4 = util_swap32(k4);
93 : #endif
94 :
95 115775756 : k1 *= c1; k1 = util_rotl32(k1, 15); k1 *= c2; h1 ^= k1;
96 :
97 115775756 : h1 = util_rotl32(h1, 19); h1 += h2; h1 = h1 * 5 + 0x561ccd1b;
98 :
99 115775756 : k2 *= c2; k2 = util_rotl32(k2, 16); k2 *= c3; h2 ^= k2;
100 :
101 115775756 : h2 = util_rotl32(h2, 17); h2 += h3; h2 = h2 * 5 + 0x0bcaa747;
102 :
103 115775756 : k3 *= c3; k3 = util_rotl32(k3, 17); k3 *= c4; h3 ^= k3;
104 :
105 115775756 : h3 = util_rotl32(h3, 15); h3 += h4; h3 = h3 * 5 + 0x96cd1c35;
106 :
107 115775756 : k4 *= c4; k4 = util_rotl32(k4, 18); k4 *= c1; h4 ^= k4;
108 :
109 115775756 : h4 = util_rotl32(h4, 13); h4 += h1; h4 = h4 * 5 + 0x32ac3b17;
110 :
111 115775756 : blocks += 4;
112 : }
113 :
114 : /* tail */
115 2258145 : size_remainder = size & 15;
116 2258145 : if (size_remainder != 0) {
117 853473 : const uint8_t* tail = (const uint8_t*)blocks;
118 :
119 853473 : uint32_t k1 = 0;
120 853473 : uint32_t k2 = 0;
121 853473 : uint32_t k3 = 0;
122 853473 : uint32_t k4 = 0;
123 :
124 853473 : switch (size_remainder) {
125 56117 : case 15 : k4 ^= (uint32_t)tail[14] << 16; /* fallthrough */
126 113916 : case 14 : k4 ^= (uint32_t)tail[13] << 8; /* fallthrough */
127 171059 : case 13 : k4 ^= (uint32_t)tail[12] << 0; /* fallthrough */
128 171059 : k4 *= c4; k4 = util_rotl32(k4, 18); k4 *= c1; h4 ^= k4;
129 : /* fallthrough */
130 228878 : case 12 : k3 ^= (uint32_t)tail[11] << 24; /* fallthrough */
131 286403 : case 11 : k3 ^= (uint32_t)tail[10] << 16; /* fallthrough */
132 343506 : case 10 : k3 ^= (uint32_t)tail[ 9] << 8; /* fallthrough */
133 401724 : case 9 : k3 ^= (uint32_t)tail[ 8] << 0; /* fallthrough */
134 401724 : k3 *= c3; k3 = util_rotl32(k3, 17); k3 *= c4; h3 ^= k3;
135 : /* fallthrough */
136 460637 : case 8 : k2 ^= (uint32_t)tail[ 7] << 24; /* fallthrough */
137 514804 : case 7 : k2 ^= (uint32_t)tail[ 6] << 16; /* fallthrough */
138 572532 : case 6 : k2 ^= (uint32_t)tail[ 5] << 8; /* fallthrough */
139 627944 : case 5 : k2 ^= (uint32_t)tail[ 4] << 0; /* fallthrough */
140 627944 : k2 *= c2; k2 = util_rotl32(k2, 16); k2 *= c3; h2 ^= k2;
141 : /* fallthrough */
142 685049 : case 4 : k1 ^= (uint32_t)tail[ 3] << 24; /* fallthrough */
143 740465 : case 3 : k1 ^= (uint32_t)tail[ 2] << 16; /* fallthrough */
144 796211 : case 2 : k1 ^= (uint32_t)tail[ 1] << 8; /* fallthrough */
145 853473 : case 1 : k1 ^= (uint32_t)tail[ 0] << 0; /* fallthrough */
146 853473 : k1 *= c1; k1 = util_rotl32(k1, 15); k1 *= c2; h1 ^= k1;
147 : /* fallthrough */
148 : }
149 : }
150 :
151 : /* finalization */
152 2258145 : h1 ^= size; h2 ^= size; h3 ^= size; h4 ^= size;
153 :
154 2258145 : h1 += h2; h1 += h3; h1 += h4;
155 2258145 : h2 += h1; h3 += h1; h4 += h1;
156 :
157 2258145 : h1 = fmix32(h1);
158 2258145 : h2 = fmix32(h2);
159 2258145 : h3 = fmix32(h3);
160 2258145 : h4 = fmix32(h4);
161 :
162 2258145 : h1 += h2; h1 += h3; h1 += h4;
163 2258145 : h2 += h1; h3 += h1; h4 += h1;
164 :
165 2258145 : util_write32(digest + 0, h1);
166 2258145 : util_write32(digest + 4, h2);
167 2258145 : util_write32(digest + 8, h3);
168 2258145 : util_write32(digest + 12, h4);
169 2258145 : }
170 :
|
