Line data Source code
1 : /*
2 : * Copyright (C) 2011 Andrea Mazzoleni
3 : *
4 : * This program is free software: you can redistribute it and/or modify
5 : * it under the terms of the GNU General Public License as published by
6 : * the Free Software Foundation, either version 3 of the License, or
7 : * (at your option) any later version.
8 : *
9 : * This program is distributed in the hope that it will be useful,
10 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 : * GNU General Public License for more details.
13 : *
14 : * You should have received a copy of the GNU General Public License
15 : * along with this program. If not, see <http://www.gnu.org/licenses/>.
16 : */
17 :
18 : /*
19 : * Derivative work from MurmorHash3.cpp revision r136
20 : *
21 : * SMHasher & MurmurHash
22 : * http://code.google.com/p/smhasher/
23 : *
24 : * Exact source used as reference:
25 : * http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp?spec=svn136&r=136
26 : */
27 :
28 : // MurmurHash3 was written by Austin Appleby, and is placed in the public
29 : // domain. The author hereby disclaims copyright to this source code.
30 :
31 : /* Finalization mix - force all bits of a hash block to avalanche */
32 8135804 : static inline uint32_t fmix32(uint32_t h)
33 : {
34 8135804 : h ^= h >> 16;
35 8135804 : h *= 0x85ebca6b;
36 8135804 : h ^= h >> 13;
37 8135804 : h *= 0xc2b2ae35;
38 8135804 : h ^= h >> 16;
39 8135804 : return h;
40 : }
41 :
42 : /*
43 : * Warning!
44 : * Don't declare these variables static, otherwise the gcc optimizer
45 : * may generate very slow code for multiplication with these constants,
46 : * like:
47 :
48 : -> .cpp
49 : k1 *= c1;
50 : -> .asm
51 : 152: 8d 14 80 lea (%eax,%eax,4),%edx
52 : 155: 8d 14 90 lea (%eax,%edx,4),%edx
53 : 158: c1 e2 03 shl $0x3,%edx
54 : 15b: 29 c2 sub %eax,%edx
55 : 15d: 8d 14 d2 lea (%edx,%edx,8),%edx
56 : 160: 8d 14 90 lea (%eax,%edx,4),%edx
57 : 163: 8d 14 d0 lea (%eax,%edx,8),%edx
58 : 166: 8d 14 90 lea (%eax,%edx,4),%edx
59 : 169: 8d 14 50 lea (%eax,%edx,2),%edx
60 : 16c: 8d 14 90 lea (%eax,%edx,4),%edx
61 : 16f: 8d 14 92 lea (%edx,%edx,4),%edx
62 : 172: 8d 14 50 lea (%eax,%edx,2),%edx
63 : 175: 8d 04 d0 lea (%eax,%edx,8),%eax
64 : 178: 8d 14 c5 00 00 00 00 lea 0x0(,%eax,8),%edx
65 : 17f: 29 d0 sub %edx,%eax
66 :
67 : * resulting in speeds of 500 MB/s instead of 3000 MB/s.
68 : *
69 : * Verified with gcc 4.4.4 compiling with :
70 : *
71 : * g++ -g -c -O2 MurmurHash3.cpp -o MurmurHash3.o
72 : */
73 : uint32_t c1 = 0x239b961b;
74 : uint32_t c2 = 0xab0e9789;
75 : uint32_t c3 = 0x38b34ae5;
76 : uint32_t c4 = 0xa1e38b93;
77 :
78 2033951 : void MurmurHash3_x86_128(const void* data, size_t size, const uint8_t* seed, void* digest)
79 : {
80 : size_t nblocks;
81 : const uint32_t* blocks;
82 : const uint32_t* end;
83 : size_t size_remainder;
84 : uint32_t h1, h2, h3, h4;
85 :
86 2033951 : h1 = util_read32(seed + 0);
87 2033951 : h2 = util_read32(seed + 4);
88 2033951 : h3 = util_read32(seed + 8);
89 2033951 : h4 = util_read32(seed + 12);
90 :
91 2033951 : nblocks = size / 16;
92 2033951 : blocks = data;
93 2033951 : end = blocks + nblocks * 4;
94 :
95 : /* body */
96 106154521 : while (blocks < end) {
97 104120570 : uint32_t k1 = blocks[0];
98 104120570 : uint32_t k2 = blocks[1];
99 104120570 : uint32_t k3 = blocks[2];
100 104120570 : uint32_t k4 = blocks[3];
101 :
102 : #if WORDS_BIGENDIAN
103 : k1 = util_swap32(k1);
104 : k2 = util_swap32(k2);
105 : k3 = util_swap32(k3);
106 : k4 = util_swap32(k4);
107 : #endif
108 :
109 104120570 : k1 *= c1; k1 = util_rotl32(k1, 15); k1 *= c2; h1 ^= k1;
110 :
111 104120570 : h1 = util_rotl32(h1, 19); h1 += h2; h1 = h1 * 5 + 0x561ccd1b;
112 :
113 104120570 : k2 *= c2; k2 = util_rotl32(k2, 16); k2 *= c3; h2 ^= k2;
114 :
115 104120570 : h2 = util_rotl32(h2, 17); h2 += h3; h2 = h2 * 5 + 0x0bcaa747;
116 :
117 104120570 : k3 *= c3; k3 = util_rotl32(k3, 17); k3 *= c4; h3 ^= k3;
118 :
119 104120570 : h3 = util_rotl32(h3, 15); h3 += h4; h3 = h3 * 5 + 0x96cd1c35;
120 :
121 104120570 : k4 *= c4; k4 = util_rotl32(k4, 18); k4 *= c1; h4 ^= k4;
122 :
123 104120570 : h4 = util_rotl32(h4, 13); h4 += h1; h4 = h4 * 5 + 0x32ac3b17;
124 :
125 104120570 : blocks += 4;
126 : }
127 :
128 : /* tail */
129 2033951 : size_remainder = size & 15;
130 2033951 : if (size_remainder != 0) {
131 769615 : const uint8_t* tail = (const uint8_t*)blocks;
132 :
133 769615 : uint32_t k1 = 0;
134 769615 : uint32_t k2 = 0;
135 769615 : uint32_t k3 = 0;
136 769615 : uint32_t k4 = 0;
137 :
138 769615 : switch (size_remainder) {
139 50644 : case 15 : k4 ^= (uint32_t)tail[14] << 16; /* fallthrough */
140 102746 : case 14 : k4 ^= (uint32_t)tail[13] << 8; /* fallthrough */
141 154329 : case 13 : k4 ^= (uint32_t)tail[12] << 0; /* fallthrough */
142 154329 : k4 *= c4; k4 = util_rotl32(k4, 18); k4 *= c1; h4 ^= k4;
143 : /* fallthrough */
144 206462 : case 12 : k3 ^= (uint32_t)tail[11] << 24; /* fallthrough */
145 258318 : case 11 : k3 ^= (uint32_t)tail[10] << 16; /* fallthrough */
146 309833 : case 10 : k3 ^= (uint32_t)tail[ 9] << 8; /* fallthrough */
147 362420 : case 9 : k3 ^= (uint32_t)tail[ 8] << 0; /* fallthrough */
148 362420 : k3 *= c3; k3 = util_rotl32(k3, 17); k3 *= c4; h3 ^= k3;
149 : /* fallthrough */
150 415641 : case 8 : k2 ^= (uint32_t)tail[ 7] << 24; /* fallthrough */
151 464527 : case 7 : k2 ^= (uint32_t)tail[ 6] << 16; /* fallthrough */
152 516561 : case 6 : k2 ^= (uint32_t)tail[ 5] << 8; /* fallthrough */
153 566435 : case 5 : k2 ^= (uint32_t)tail[ 4] << 0; /* fallthrough */
154 566435 : k2 *= c2; k2 = util_rotl32(k2, 16); k2 *= c3; h2 ^= k2;
155 : /* fallthrough */
156 617740 : case 4 : k1 ^= (uint32_t)tail[ 3] << 24; /* fallthrough */
157 667511 : case 3 : k1 ^= (uint32_t)tail[ 2] << 16; /* fallthrough */
158 717963 : case 2 : k1 ^= (uint32_t)tail[ 1] << 8; /* fallthrough */
159 769615 : case 1 : k1 ^= (uint32_t)tail[ 0] << 0; /* fallthrough */
160 769615 : k1 *= c1; k1 = util_rotl32(k1, 15); k1 *= c2; h1 ^= k1;
161 : /* fallthrough */
162 : }
163 : }
164 :
165 : /* finalization */
166 2033951 : h1 ^= size; h2 ^= size; h3 ^= size; h4 ^= size;
167 :
168 2033951 : h1 += h2; h1 += h3; h1 += h4;
169 2033951 : h2 += h1; h3 += h1; h4 += h1;
170 :
171 2033951 : h1 = fmix32(h1);
172 2033951 : h2 = fmix32(h2);
173 2033951 : h3 = fmix32(h3);
174 2033951 : h4 = fmix32(h4);
175 :
176 2033951 : h1 += h2; h1 += h3; h1 += h4;
177 2033951 : h2 += h1; h3 += h1; h4 += h1;
178 :
179 2033951 : util_write32(digest + 0, h1);
180 2033951 : util_write32(digest + 4, h2);
181 2033951 : util_write32(digest + 8, h3);
182 2033951 : util_write32(digest + 12, h4);
183 2033951 : }
184 :
|
