Branch data Line data Source code
1 : : /* This file is based on the public domain MurmurHash3 from Austin Appleby:
2 : : * http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp
3 : : *
4 : : * We use only the 32 bit variant because the 2 produce different result while
5 : : * we need to produce the same result regardless of the architecture as
6 : : * clients can be both 64 or 32 bit at the same time.
7 : : */
8 : :
9 : : #include <stdlib.h>
10 : : #include <stdint.h>
11 : : #include <endian.h>
12 : : #include <string.h>
13 : : #include <byteswap.h>
14 : :
15 : : /* support RHEL5 lack of definitions */
16 : : #ifndef le32toh
17 : : # if __BYTE_ORDER == __LITTLE_ENDIAN
18 : : # define le32toh(x) (x)
19 : : # else
20 : : # define le32toh(x) bswap_32 (x)
21 : : # endif
22 : : #endif
23 : :
24 : :
25 : : static uint32_t rotl(uint32_t x, int8_t r)
26 : : {
27 : 57 : return (x << r) | (x >> (32 - r));
28 : : }
29 : :
30 : : /* slower than original but is endian neutral and handles platforms that
31 : : * do only aligned reads */
32 : : __attribute__((always_inline))
33 : : static inline uint32_t getblock(const uint8_t *p, int i)
34 : : {
35 : : uint32_t r;
36 : 24 : size_t size = sizeof(uint32_t);
37 : :
38 : 24 : memcpy(&r, &p[i * size], size);
39 : :
40 : : return le32toh(r);
41 : : }
42 : :
43 : : /*
44 : : * Finalization mix - force all bits of a hash block to avalanche
45 : : */
46 : :
47 : : __attribute__((always_inline))
48 : : static inline uint32_t fmix(uint32_t h)
49 : : {
50 : 9 : h ^= h >> 16;
51 : 9 : h *= 0x85ebca6b;
52 : 9 : h ^= h >> 13;
53 : 9 : h *= 0xc2b2ae35;
54 : 9 : h ^= h >> 16;
55 : :
56 : : return h;
57 : : }
58 : :
59 : :
60 : 9 : uint32_t murmurhash3(const char *key, int len, uint32_t seed)
61 : : {
62 : : const uint8_t *blocks;
63 : : const uint8_t *tail;
64 : : int nblocks;
65 : : uint32_t h1;
66 : : uint32_t k1;
67 : : uint32_t c1;
68 : : uint32_t c2;
69 : : int i;
70 : :
71 : 9 : blocks = (const uint8_t *)key;
72 : 9 : nblocks = len / 4;
73 : 9 : h1 = seed;
74 : 9 : c1 = 0xcc9e2d51;
75 : 9 : c2 = 0x1b873593;
76 : :
77 : : /* body */
78 : :
79 [ + + ]: 33 : for (i = 0; i < nblocks; i++) {
80 : :
81 : 24 : k1 = getblock(blocks, i);
82 : :
83 : 24 : k1 *= c1;
84 : 24 : k1 = rotl(k1, 15);
85 : 24 : k1 *= c2;
86 : :
87 : 24 : h1 ^= k1;
88 : 24 : h1 = rotl(h1, 13);
89 : 24 : h1 = h1 * 5 + 0xe6546b64;
90 : : }
91 : :
92 : : /* tail */
93 : :
94 : 9 : tail = (const uint8_t *)key + nblocks * 4;
95 : :
96 : 9 : k1 = 0;
97 : :
98 [ + + + - ]: 9 : switch (len & 3) {
99 : : case 3:
100 : 5 : k1 ^= tail[2] << 16;
101 : : case 2:
102 : 8 : k1 ^= tail[1] << 8;
103 : : case 1:
104 : 9 : k1 ^= tail[0];
105 : 9 : k1 *= c1;
106 : 9 : k1 = rotl(k1, 15);
107 : 9 : k1 *= c2;
108 : 9 : h1 ^= k1;
109 : : default:
110 : : break;
111 : : }
112 : :
113 : : /* finalization */
114 : :
115 : 9 : h1 ^= len;
116 : 9 : h1 = fmix(h1);
117 : :
118 : 9 : return h1;
119 : : }
120 : :
121 : :
|
