Skip to content

add murmur128 #180

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
mredolatti merged 4 commits into from
Sep 30, 2020
Merged

add murmur128 #180

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
4 commits
Select commit Hold shift + click to select a range
2be84bf
add murmur128
mredolatti Sep 30, 2020
af0952d
change cpphash branch
mredolatti Sep 30, 2020
1553fad
use install_requires
mredolatti Sep 30, 2020
274606b
remove ssh
mredolatti Sep 30, 2020
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
7 changes: 4 additions & 3 deletions setup.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -23,8 +23,7 @@
'futures>=3.0.5;python_version<"3"'
]

with open(path.join(path.abspath(path.dirname(__file__)),
'splitio', 'version.py')) as f:
with open(path.join(path.abspath(path.dirname(__file__)), 'splitio', 'version.py')) as f:
exec(f.read()) # pylint: disable=exec-used

setup(
Expand All @@ -38,11 +37,13 @@
license='Apache License 2.0',
install_requires=INSTALL_REQUIRES,
tests_require=TESTS_REQUIRES,
# dependency_links=['https://github.com/splitio/mmh3cffi/tarball/feature/development#egg=mmh3cffi-0.2.0'],
extras_require={
'test': TESTS_REQUIRES,
'redis': ['redis>=2.10.5'],
'uwsgi': ['uwsgi>=2.0.0'],
'cpphash': ['mmh3cffi>=0.1.5']
# 'cpphash': ['mmh3cffi==0.2.0']
'cpphash': ['mmh3cffi@git+https://github.com/splitio/mmh3cffi@development#egg=mmh3cffi']
},
setup_requires=['pytest-runner'],
classifiers=[
Expand Down
6 changes: 6 additions & 0 deletions splitio/engine/hashfns/__init__.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -17,17 +17,23 @@

def _murmur_hash(key, seed):
return mmh3cffi.hash_str(key, seed)

def _murmur_hash128(key, seed):
return mmh3cffi.hash_str_128(key, seed)[0]

except ImportError:
# Fallback to interpreted python hash algoritm (slower)
from splitio.engine.hashfns import murmur3py #pylint: disable=ungrouped-imports
_murmur_hash = murmur3py.murmur32_py #pylint: disable=invalid-name
_murmur_hash128 = lambda k, s: murmur3py.hash128_x64(k, s)[0] #pylint: disable=invalid-name


_HASH_ALGORITHMS = {
HashAlgorithm.LEGACY: legacy.legacy_hash,
HashAlgorithm.MURMUR: _murmur_hash
}

murmur_128 = _murmur_hash128 #pylint: disable=invalid-name

def get_hash_fn(algo):
"""
Expand Down
129 changes: 129 additions & 0 deletions splitio/engine/hashfns/murmur3py.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -74,3 +74,132 @@ def fmix(current_hash):

unsigned_val = fmix(hash1 ^ length)
return unsigned_val

def hash128_x64(key, seed):
"""
Pure python implementation of murmurhash3-128.

borrowed from: https://github.com/wc-duck/pymmh3/blob/master/pymmh3.py
"""
key = bytearray(key, 'utf-8')

def fmix(k):
k ^= k >> 33
k = (k * 0xff51afd7ed558ccd) & 0xFFFFFFFFFFFFFFFF
k ^= k >> 33
k = (k * 0xc4ceb9fe1a85ec53) & 0xFFFFFFFFFFFFFFFF
k ^= k >> 33
return k

length = len(key)
nblocks = int(length / 16)

h1 = seed
h2 = seed

c1 = 0x87c37b91114253d5
c2 = 0x4cf5ad432745937f

#body
for block_start in range(0, nblocks * 8, 8):
# ??? big endian?
k1 = key[2 * block_start + 7] << 56 | \
key[2 * block_start + 6] << 48 | \
key[2 * block_start + 5] << 40 | \
key[2 * block_start + 4] << 32 | \
key[2 * block_start + 3] << 24 | \
key[2 * block_start + 2] << 16 | \
key[2 * block_start + 1] << 8 | \
key[2 * block_start + 0]

k2 = key[2 * block_start + 15] << 56 | \
key[2 * block_start + 14] << 48 | \
key[2 * block_start + 13] << 40 | \
key[2 * block_start + 12] << 32 | \
key[2 * block_start + 11] << 24 | \
key[2 * block_start + 10] << 16 | \
key[2 * block_start + 9] << 8 | \
key[2 * block_start + 8]

k1 = (c1 * k1) & 0xFFFFFFFFFFFFFFFF
k1 = (k1 << 31 | k1 >> 33) & 0xFFFFFFFFFFFFFFFF # inlined ROTL64
k1 = (c2 * k1) & 0xFFFFFFFFFFFFFFFF
h1 ^= k1

h1 = (h1 << 27 | h1 >> 37) & 0xFFFFFFFFFFFFFFFF # inlined ROTL64
h1 = (h1 + h2) & 0xFFFFFFFFFFFFFFFF
h1 = (h1 * 5 + 0x52dce729) & 0xFFFFFFFFFFFFFFFF

k2 = (c2 * k2) & 0xFFFFFFFFFFFFFFFF
k2 = (k2 << 33 | k2 >> 31) & 0xFFFFFFFFFFFFFFFF # inlined ROTL64
k2 = (c1 * k2) & 0xFFFFFFFFFFFFFFFF
h2 ^= k2

h2 = (h2 << 31 | h2 >> 33) & 0xFFFFFFFFFFFFFFFF # inlined ROTL64
h2 = (h1 + h2) & 0xFFFFFFFFFFFFFFFF
h2 = (h2 * 5 + 0x38495ab5) & 0xFFFFFFFFFFFFFFFF

#tail
tail_index = nblocks * 16
k1 = 0
k2 = 0
tail_size = length & 15

if tail_size >= 15:
k2 ^= key[tail_index + 14] << 48
if tail_size >= 14:
k2 ^= key[tail_index + 13] << 40
if tail_size >= 13:
k2 ^= key[tail_index + 12] << 32
if tail_size >= 12:
k2 ^= key[tail_index + 11] << 24
if tail_size >= 11:
k2 ^= key[tail_index + 10] << 16
if tail_size >= 10:
k2 ^= key[tail_index + 9] << 8
if tail_size >= 9:
k2 ^= key[tail_index + 8]

if tail_size > 8:
k2 = (k2 * c2) & 0xFFFFFFFFFFFFFFFF
k2 = (k2 << 33 | k2 >> 31) & 0xFFFFFFFFFFFFFFFF # inlined ROTL64
k2 = (k2 * c1) & 0xFFFFFFFFFFFFFFFF
h2 ^= k2

if tail_size >= 8:
k1 ^= key[tail_index + 7] << 56
if tail_size >= 7:
k1 ^= key[tail_index + 6] << 48
if tail_size >= 6:
k1 ^= key[tail_index + 5] << 40
if tail_size >= 5:
k1 ^= key[tail_index + 4] << 32
if tail_size >= 4:
k1 ^= key[tail_index + 3] << 24
if tail_size >= 3:
k1 ^= key[tail_index + 2] << 16
if tail_size >= 2:
k1 ^= key[tail_index + 1] << 8
if tail_size >= 1:
k1 ^= key[tail_index + 0]

if tail_size > 0:
k1 = (k1 * c1) & 0xFFFFFFFFFFFFFFFF
k1 = (k1 << 31 | k1 >> 33) & 0xFFFFFFFFFFFFFFFF # inlined ROTL64
k1 = (k1 * c2) & 0xFFFFFFFFFFFFFFFF
h1 ^= k1

#finalization
h1 ^= length
h2 ^= length

h1 = (h1 + h2) & 0xFFFFFFFFFFFFFFFF
h2 = (h1 + h2) & 0xFFFFFFFFFFFFFFFF

h1 = fmix(h1)
h2 = fmix(h2)

h1 = (h1 + h2) & 0xFFFFFFFFFFFFFFFF
h2 = (h1 + h2) & 0xFFFFFFFFFFFFFFFF

return [h1, h2]
Loading