1//-----------------------------------------------------------------------------
2// MurmurHash was written by Austin Appleby, and is placed in the public
3// domain. The author hereby disclaims copyright to this source code.
4
5// Note - This code makes a few assumptions about how your machine behaves -
6
7// 1. We can read a 4-byte value from any address without crashing
8// 2. sizeof(int) == 4
9
10// And it has a few limitations -
11
12// 1. It will not work incrementally.
13// 2. It will not produce the same results on little-endian and big-endian
14//    machines.
15
16#include "MurmurHash1.h"
17
18//-----------------------------------------------------------------------------
19
20uint32_t MurmurHash1 ( const void * key, int len, uint32_t seed )
21{
22  const unsigned int m = 0xc6a4a793;
23
24  const int r = 16;
25
26  unsigned int h = seed ^ (len * m);
27
28  //----------
29
30  const unsigned char * data = (const unsigned char *)key;
31
32  while(len >= 4)
33  {
34    unsigned int k = *(unsigned int *)data;
35
36    h += k;
37    h *= m;
38    h ^= h >> 16;
39
40    data += 4;
41    len -= 4;
42  }
43
44  //----------
45
46  switch(len)
47  {
48  case 3:
49    h += data[2] << 16;
50  case 2:
51    h += data[1] << 8;
52  case 1:
53    h += data[0];
54    h *= m;
55    h ^= h >> r;
56  };
57
58  //----------
59
60  h *= m;
61  h ^= h >> 10;
62  h *= m;
63  h ^= h >> 17;
64
65  return h;
66}
67
68//-----------------------------------------------------------------------------
69// MurmurHash1Aligned, by Austin Appleby
70
71// Same algorithm as MurmurHash1, but only does aligned reads - should be safer
72// on certain platforms.
73
74// Performance should be equal to or better than the simple version.
75
76unsigned int MurmurHash1Aligned ( const void * key, int len, unsigned int seed )
77{
78  const unsigned int m = 0xc6a4a793;
79  const int r = 16;
80
81  const unsigned char * data = (const unsigned char *)key;
82
83  unsigned int h = seed ^ (len * m);
84
85  int align = (uint64_t)data & 3;
86
87  if(align && (len >= 4))
88  {
89    // Pre-load the temp registers
90
91    unsigned int t = 0, d = 0;
92
93    switch(align)
94    {
95      case 1: t |= data[2] << 16;
96      case 2: t |= data[1] << 8;
97      case 3: t |= data[0];
98    }
99
100    t <<= (8 * align);
101
102    data += 4-align;
103    len -= 4-align;
104
105    int sl = 8 * (4-align);
106    int sr = 8 * align;
107
108    // Mix
109
110    while(len >= 4)
111    {
112      d = *(unsigned int *)data;
113      t = (t >> sr) | (d << sl);
114      h += t;
115      h *= m;
116      h ^= h >> r;
117      t = d;
118
119      data += 4;
120      len -= 4;
121    }
122
123    // Handle leftover data in temp registers
124
125    int pack = len < align ? len : align;
126
127    d = 0;
128
129    switch(pack)
130    {
131    case 3: d |= data[2] << 16;
132    case 2: d |= data[1] << 8;
133    case 1: d |= data[0];
134    case 0: h += (t >> sr) | (d << sl);
135        h *= m;
136        h ^= h >> r;
137    }
138
139    data += pack;
140    len -= pack;
141  }
142  else
143  {
144    while(len >= 4)
145    {
146      h += *(unsigned int *)data;
147      h *= m;
148      h ^= h >> r;
149
150      data += 4;
151      len -= 4;
152    }
153  }
154
155  //----------
156  // Handle tail bytes
157
158  switch(len)
159  {
160  case 3: h += data[2] << 16;
161  case 2: h += data[1] << 8;
162  case 1: h += data[0];
163      h *= m;
164      h ^= h >> r;
165  };
166
167  h *= m;
168  h ^= h >> 10;
169  h *= m;
170  h ^= h >> 17;
171
172  return h;
173}
174
175