Is there a pure python implementation of MurmurHash?
Here goes a pure Python implementation of MurmurHash3 32, it hashes strings only but can be easily adapted to take byte arrays instead. This is a port from the Java version of the algorithm.
def murmur3_x86_32(data, seed = 0):
c1 = 0xcc9e2d51
c2 = 0x1b873593
length = len(data)
h1 = seed
roundedEnd = (length & 0xfffffffc) # round down to 4 byte block
for i in range(0, roundedEnd, 4):
# little endian load order
k1 = (ord(data[i]) & 0xff) | ((ord(data[i + 1]) & 0xff) << 8) | \
((ord(data[i + 2]) & 0xff) << 16) | (ord(data[i + 3]) << 24)
k1 *= c1
k1 = (k1 << 15) | ((k1 & 0xffffffff) >> 17) # ROTL32(k1,15)
k1 *= c2
h1 ^= k1
h1 = (h1 << 13) | ((h1 & 0xffffffff) >> 19) # ROTL32(h1,13)
h1 = h1 * 5 + 0xe6546b64
# tail
k1 = 0
val = length & 0x03
if val == 3:
k1 = (ord(data[roundedEnd + 2]) & 0xff) << 16
# fallthrough
if val in [2, 3]:
k1 |= (ord(data[roundedEnd + 1]) & 0xff) << 8
# fallthrough
if val in [1, 2, 3]:
k1 |= ord(data[roundedEnd]) & 0xff
k1 *= c1
k1 = (k1 << 15) | ((k1 & 0xffffffff) >> 17) # ROTL32(k1,15)
k1 *= c2
h1 ^= k1
# finalization
h1 ^= length
# fmix(h1)
h1 ^= ((h1 & 0xffffffff) >> 16)
h1 *= 0x85ebca6b
h1 ^= ((h1 & 0xffffffff) >> 13)
h1 *= 0xc2b2ae35
h1 ^= ((h1 & 0xffffffff) >> 16)
return h1 & 0xffffffff
fix the bugs in Nikolas's version
def bytes_to_long(bytes):
assert len(bytes) == 8
return sum((b << (k * 8) for k, b in enumerate(bytes)))
def murmur64(data, seed = 19820125):
m = 0xc6a4a7935bd1e995
r = 47
MASK = 2 ** 64 - 1
data_as_bytes = bytearray(data)
h = seed ^ ((m * len(data_as_bytes)) & MASK)
off = len(data_as_bytes)/8*8
for ll in range(0, off, 8):
k = bytes_to_long(data_as_bytes[ll:ll + 8])
k = (k * m) & MASK
k = k ^ ((k >> r) & MASK)
k = (k * m) & MASK
h = (h ^ k)
h = (h * m) & MASK
l = len(data_as_bytes) & 7
if l >= 7:
h = (h ^ (data_as_bytes[off+6] << 48))
if l >= 6:
h = (h ^ (data_as_bytes[off+5] << 40))
if l >= 5:
h = (h ^ (data_as_bytes[off+4] << 32))
if l >= 4:
h = (h ^ (data_as_bytes[off+3] << 24))
if l >= 3:
h = (h ^ (data_as_bytes[off+2] << 16))
if l >= 2:
h = (h ^ (data_as_bytes[off+1] << 8))
if l >= 1:
h = (h ^ data_as_bytes[off])
h = (h * m) & MASK
h = h ^ ((h >> r) & MASK)
h = (h * m) & MASK
h = h ^ ((h >> r) & MASK)
return h
Another pure python implementation of MurmurHash3 that is totally compatible and replaceable by the mmh3 wrapper, but still limited to 32-bits Murmur3: https://github.com/wc-duck/pymmh3
this is untested (sorry!), but here is a version I came up with. Python allows for arbitrarily large integers, so I created a mask for the first 8 bytes (or 64 bits) that I then apply (via bitwise AND) to all arithmetic results that could produce integers larger than 64bits. Maybe somebody else could comment on the general approach and possible issues with endianness, etc.
def bytes_to_long(bytes):
assert len(bytes) == 8
return sum((b << (k * 8) for k, b in enumerate(bytes)))
def murmur(data, seed):
m = 0xc6a4a7935bd1e995
r = 47
MASK = 2 ** 64 - 1
data_as_bytes = bytearray(data)
h = seed ^ ((m * len(data_as_bytes)) & MASK)
for ll in range(0, len(data_as_bytes), 8):
k = bytes_to_long(data_as_bytes[ll:ll + 8])
k = (k * m) & MASK
k = k ^ ((k >> r) & MASK)
k = (k * m) & MASK
h = (h ^ k)
h = (h * m) & MASK
l = len(data_as_bytes) & 7
if l >= 7:
h = (h ^ (data_as_bytes[6] << 48))
if l >= 6:
h = (h ^ (data_as_bytes[5] << 40))
if l >= 5:
h = (h ^ (data_as_bytes[4] << 32))
if l >= 4:
h = (h ^ (data_as_bytes[3] << 24))
if l >= 3:
h = (h ^ (data_as_bytes[4] << 16))
if l >= 2:
h = (h ^ (data_as_bytes[4] << 8))
if l >= 1:
h = (h ^ data_as_bytes[4])
h = (h * m) & MASK
h = h ^ ((h >> r) & MASK)
h = (h * m) & MASK
h = h ^ ((h >> r) & MASK)
return h