Skip to content

Commit bb78895

Browse files
aholmbergaholmberg
committed
Add missing cmurmur3.c, update .gitignore
1 parent d97562d commit bb78895

2 files changed

Lines changed: 276 additions & 1 deletion

File tree

‎.gitignore‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -18,7 +18,7 @@ setuptools*.tar.gz
1818
setuptools*.egg
1919

2020
cassandra/*.c
21-
!cassandra/murmur3.c
21+
!cassandra/cmurmur3.c
2222

2323
# OSX
2424
.DS_Store

‎cassandra/cmurmur3.c‎

Lines changed: 275 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,275 @@
1+
/*
2+
* The majority of this code was taken from the python-smhasher library,
3+
* which can be found here: https://github.com/phensley/python-smhasher
4+
*
5+
* That library is under the MIT license with the following copyright:
6+
*
7+
* Copyright (c) 2011 Austin Appleby (Murmur3 routine)
8+
* Copyright (c) 2011 Patrick Hensley (Python wrapper, packaging)
9+
* Copyright 2013 DataStax (Minor modifications to match Cassandra's MM3 hashes)
10+
*
11+
*/
12+
13+
#define PY_SSIZE_T_CLEAN 1
14+
#include <Python.h>
15+
#include <stdio.h>
16+
17+
#if PY_VERSION_HEX < 0x02050000
18+
typedef int Py_ssize_t;
19+
#define PY_SSIZE_T_MAX INT_MAX
20+
#define PY_SSIZE_T_MIN INT_MIN
21+
#endif
22+
23+
#ifdef PYPY_VERSION
24+
#define COMPILING_IN_PYPY 1
25+
#define COMPILING_IN_CPYTHON 0
26+
#else
27+
#define COMPILING_IN_PYPY 0
28+
#define COMPILING_IN_CPYTHON 1
29+
#endif
30+
//-----------------------------------------------------------------------------
31+
// Platform-specific functions and macros
32+
33+
// Microsoft Visual Studio
34+
35+
#if defined(_MSC_VER)
36+
37+
typedef unsigned char uint8_t;
38+
typedef unsigned long uint32_t;
39+
typedef unsigned __int64 uint64_t;
40+
41+
typedef char int8_t;
42+
typedef long int32_t;
43+
typedef __int64 int64_t;
44+
45+
#define FORCE_INLINE __forceinline
46+
47+
#include <stdlib.h>
48+
49+
#define ROTL32(x,y) _rotl(x,y)
50+
#define ROTL64(x,y) _rotl64(x,y)
51+
52+
#define BIG_CONSTANT(x) (x)
53+
54+
// Other compilers
55+
56+
#else // defined(_MSC_VER)
57+
58+
#include <stdint.h>
59+
60+
#define FORCE_INLINE inline __attribute__((always_inline))
61+
62+
inline uint32_t rotl32 ( int32_t x, int8_t r )
63+
{
64+
// cast to unsigned for logical right bitshift (to match C* MM3 implementation)
65+
return (x << r) | ((int32_t) (((uint32_t) x) >> (32 - r)));
66+
}
67+
68+
inline int64_t rotl64 ( int64_t x, int8_t r )
69+
{
70+
// cast to unsigned for logical right bitshift (to match C* MM3 implementation)
71+
return (x << r) | ((int64_t) (((uint64_t) x) >> (64 - r)));
72+
}
73+
74+
#define ROTL32(x,y) rotl32(x,y)
75+
#define ROTL64(x,y) rotl64(x,y)
76+
77+
#define BIG_CONSTANT(x) (x##LL)
78+
79+
#endif // !defined(_MSC_VER)
80+
81+
//-----------------------------------------------------------------------------
82+
// Block read - if your platform needs to do endian-swapping or can only
83+
// handle aligned reads, do the conversion here
84+
85+
// TODO 32bit?
86+
87+
FORCE_INLINE int64_t getblock ( const int64_t * p, int i )
88+
{
89+
return p[i];
90+
}
91+
92+
//-----------------------------------------------------------------------------
93+
// Finalization mix - force all bits of a hash block to avalanche
94+
95+
FORCE_INLINE int64_t fmix ( int64_t k )
96+
{
97+
// cast to unsigned for logical right bitshift (to match C* MM3 implementation)
98+
k ^= ((uint64_t) k) >> 33;
99+
k *= BIG_CONSTANT(0xff51afd7ed558ccd);
100+
k ^= ((uint64_t) k) >> 33;
101+
k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
102+
k ^= ((uint64_t) k) >> 33;
103+
104+
return k;
105+
}
106+
107+
int64_t MurmurHash3_x64_128 (const void * key, const int len,
108+
const uint32_t seed)
109+
{
110+
const int8_t * data = (const int8_t*)key;
111+
const int nblocks = len / 16;
112+
113+
int64_t h1 = seed;
114+
int64_t h2 = seed;
115+
116+
int64_t c1 = BIG_CONSTANT(0x87c37b91114253d5);
117+
int64_t c2 = BIG_CONSTANT(0x4cf5ad432745937f);
118+
int64_t k1 = 0;
119+
int64_t k2 = 0;
120+
121+
const int64_t * blocks = (const int64_t *)(data);
122+
const int8_t * tail = (const int8_t*)(data + nblocks*16);
123+
124+
//----------
125+
// body
126+
127+
int i;
128+
for(i = 0; i < nblocks; i++)
129+
{
130+
int64_t k1 = getblock(blocks,i*2+0);
131+
int64_t k2 = getblock(blocks,i*2+1);
132+
133+
k1 *= c1; k1 = ROTL64(k1,31); k1 *= c2; h1 ^= k1;
134+
135+
h1 = ROTL64(h1,27); h1 += h2; h1 = h1*5+0x52dce729;
136+
137+
k2 *= c2; k2 = ROTL64(k2,33); k2 *= c1; h2 ^= k2;
138+
139+
h2 = ROTL64(h2,31); h2 += h1; h2 = h2*5+0x38495ab5;
140+
}
141+
142+
//----------
143+
// tail
144+
switch(len & 15)
145+
{
146+
case 15: k2 ^= ((int64_t) (tail[14])) << 48;
147+
case 14: k2 ^= ((int64_t) (tail[13])) << 40;
148+
case 13: k2 ^= ((int64_t) (tail[12])) << 32;
149+
case 12: k2 ^= ((int64_t) (tail[11])) << 24;
150+
case 11: k2 ^= ((int64_t) (tail[10])) << 16;
151+
case 10: k2 ^= ((int64_t) (tail[ 9])) << 8;
152+
case 9: k2 ^= ((int64_t) (tail[ 8])) << 0;
153+
k2 *= c2; k2 = ROTL64(k2,33); k2 *= c1; h2 ^= k2;
154+
155+
case 8: k1 ^= ((int64_t) (tail[ 7])) << 56;
156+
case 7: k1 ^= ((int64_t) (tail[ 6])) << 48;
157+
case 6: k1 ^= ((int64_t) (tail[ 5])) << 40;
158+
case 5: k1 ^= ((int64_t) (tail[ 4])) << 32;
159+
case 4: k1 ^= ((int64_t) (tail[ 3])) << 24;
160+
case 3: k1 ^= ((int64_t) (tail[ 2])) << 16;
161+
case 2: k1 ^= ((int64_t) (tail[ 1])) << 8;
162+
case 1: k1 ^= ((int64_t) (tail[ 0])) << 0;
163+
k1 *= c1; k1 = ROTL64(k1,31); k1 *= c2; h1 ^= k1;
164+
};
165+
166+
//----------
167+
// finalization
168+
169+
h1 ^= len; h2 ^= len;
170+
171+
h1 += h2;
172+
h2 += h1;
173+
174+
h1 = fmix(h1);
175+
h2 = fmix(h2);
176+
177+
h1 += h2;
178+
h2 += h1;
179+
180+
return h1;
181+
}
182+
183+
184+
struct module_state {
185+
PyObject *error;
186+
};
187+
188+
// pypy3 doesn't have GetState yet.
189+
#if COMPILING_IN_CPYTHON && PY_MAJOR_VERSION >= 3
190+
#define GETSTATE(m) ((struct module_state*)PyModule_GetState(m))
191+
#else
192+
#define GETSTATE(m) (&_state)
193+
static struct module_state _state;
194+
#endif
195+
196+
static PyObject *
197+
murmur3(PyObject *self, PyObject *args)
198+
{
199+
const char *key;
200+
Py_ssize_t len;
201+
uint32_t seed = 0;
202+
int64_t result = 0;
203+
204+
205+
if (!PyArg_ParseTuple(args, "s#|I", &key, &len, &seed)) {
206+
return NULL;
207+
}
208+
209+
// TODO handle x86 version?
210+
result = MurmurHash3_x64_128((void *)key, len, seed);
211+
return (PyObject *) PyLong_FromLongLong(result);
212+
}
213+
214+
static PyMethodDef cmurmur3_methods[] = {
215+
{"murmur3", murmur3, METH_VARARGS, "Make an x64 murmur3 64-bit hash value"},
216+
{NULL, NULL, 0, NULL}
217+
};
218+
219+
#if PY_MAJOR_VERSION >= 3
220+
221+
static int cmurmur3_traverse(PyObject *m, visitproc visit, void *arg) {
222+
Py_VISIT(GETSTATE(m)->error);
223+
return 0;
224+
}
225+
226+
static int cmurmur3_clear(PyObject *m) {
227+
Py_CLEAR(GETSTATE(m)->error);
228+
return 0;
229+
}
230+
231+
static struct PyModuleDef moduledef = {
232+
PyModuleDef_HEAD_INIT,
233+
"cmurmur3",
234+
NULL,
235+
sizeof(struct module_state),
236+
cmurmur3_methods,
237+
NULL,
238+
cmurmur3_traverse,
239+
cmurmur3_clear,
240+
NULL
241+
};
242+
243+
#define INITERROR return NULL
244+
245+
PyObject *
246+
PyInit_cmurmur3(void)
247+
248+
#else
249+
#define INITERROR return
250+
251+
void
252+
initcmurmur3(void)
253+
#endif
254+
{
255+
#if PY_MAJOR_VERSION >= 3
256+
PyObject *module = PyModule_Create(&moduledef);
257+
#else
258+
PyObject *module = Py_InitModule("cmurmur3", cmurmur3_methods);
259+
#endif
260+
struct module_state *st = NULL;
261+
262+
if (module == NULL)
263+
INITERROR;
264+
st = GETSTATE(module);
265+
266+
st->error = PyErr_NewException("cmurmur3.Error", NULL, NULL);
267+
if (st->error == NULL) {
268+
Py_DECREF(module);
269+
INITERROR;
270+
}
271+
272+
#if PY_MAJOR_VERSION >= 3
273+
return module;
274+
#endif
275+
}

0 commit comments

Comments
 (0)