Реализация Murmurhash3 на Javascript, которая дает тот же результат, что и Murmurhash3.cpp, используемый преобразованием, доступным в скрипте Python

(Мне ОЧЕНЬ жаль, что мне не разрешают добавлять много URL-адресов, чтобы лучше объяснить мои проблемы в этом посте, потому что я новичок в StackOverflow и моя учетная запись StackOverflow имеет очень низкие привилегии).

Резюме

Может кто-нибудь, пожалуйста, сообщите мне о том, как изменить murmurhash3.js (ниже), так что он производит тот же хеш, что и MurmurHash3.cpp (ниже) делает? Я предоставляю простой код Python «simple_python_wrapper.py» для MurmurHash3.cpp на основе того, что мне нужно. Simple_python_wrapper.py должен работать на вашем компьютере, если у вас установлен sklearn.

Я сильно использовал Murmurhash3.cpp (показано ниже) при использовании transform от sklearn (Библиотека машинного обучения Python): from sklearn.feature_extraction._hashing import transform в одном из моих проектов машинного обучения. transform использования Murmurhash3.cpp глубоко в дереве реализации / импорта sklearn.

Подробнее

хэш% (2 ^ 18) {то есть «модуль хеша 2 ^ 18»}, основанный на MurmurHash3.cpp

"hello" gives 260679
"there" gives 45525

хеш% (2 ^ 18) {то есть «модуль хеша 2 ^ 18»}, основанный на murmurhash3.js

"hello" gives -58999
"there" gives 65775

murmurhash3.js

/*
*  The MurmurHash3 algorithm was created by Austin Appleby.  This JavaScript port was authored
*  by whitequark (based on Java port by Yonik Seeley) and is placed into the public domain.
*  The author hereby disclaims copyright to this source code.
*
*  This produces exactly the same hash values as the final C++ version of MurmurHash3 and
*  is thus suitable for producing the same hash values across platforms.
*
*  There are two versions of this hash implementation. First interprets the string as a
*  sequence of bytes, ignoring most significant byte of each codepoint. The second one
*  interprets the string as a UTF-16 codepoint sequence, and appends each 16-bit codepoint
*  to the hash independently. The latter mode was not written to be compatible with
*  any other implementation, but it should offer better performance for JavaScript-only
*  applications.
*
*  See http://github.com/whitequark/murmurhash3-js for future updates to this file.
*/

var MurmurHash3 = {
mul32: function(m, n) {
var nlo = n & 0xffff;
var nhi = n - nlo;
return ((nhi * m | 0) + (nlo * m | 0)) | 0;
},

hashBytes: function(data, len, seed) {
var c1 = 0xcc9e2d51, c2 = 0x1b873593;

var h1 = seed;
var roundedEnd = len & ~0x3;

for (var i = 0; i < roundedEnd; i += 4) {
var k1 = (data.charCodeAt(i)     & 0xff)        |
((data.charCodeAt(i + 1) & 0xff) << 8)  |
((data.charCodeAt(i + 2) & 0xff) << 16) |
((data.charCodeAt(i + 3) & 0xff) << 24);

k1 = this.mul32(k1, c1);
k1 = ((k1 & 0x1ffff) << 15) | (k1 >>> 17);  // ROTL32(k1,15);
k1 = this.mul32(k1, c2);

h1 ^= k1;
h1 = ((h1 & 0x7ffff) << 13) | (h1 >>> 19);  // ROTL32(h1,13);
h1 = (h1 * 5 + 0xe6546b64) | 0;
}

k1 = 0;

switch(len % 4) {
case 3:
k1 = (data.charCodeAt(roundedEnd + 2) & 0xff) << 16;
// fallthrough
case 2:
k1 |= (data.charCodeAt(roundedEnd + 1) & 0xff) << 8;
// fallthrough
case 1:
k1 |= (data.charCodeAt(roundedEnd) & 0xff);
k1 = this.mul32(k1, c1);
k1 = ((k1 & 0x1ffff) << 15) | (k1 >>> 17);  // ROTL32(k1,15);
k1 = this.mul32(k1, c2);
h1 ^= k1;
}

// finalization
h1 ^= len;

// fmix(h1);
h1 ^= h1 >>> 16;
h1  = this.mul32(h1, 0x85ebca6b);
h1 ^= h1 >>> 13;
h1  = this.mul32(h1, 0xc2b2ae35);
h1 ^= h1 >>> 16;

return h1;
},

hashString: function(data, len, seed) {
var c1 = 0xcc9e2d51, c2 = 0x1b873593;

var h1 = seed;
var roundedEnd = len & ~0x1;

for (var i = 0; i < roundedEnd; i += 2) {
var k1 = data.charCodeAt(i) | (data.charCodeAt(i + 1) << 16);

k1 = this.mul32(k1, c1);
k1 = ((k1 & 0x1ffff) << 15) | (k1 >>> 17);  // ROTL32(k1,15);
k1 = this.mul32(k1, c2);

h1 ^= k1;
h1 = ((h1 & 0x7ffff) << 13) | (h1 >>> 19);  // ROTL32(h1,13);
h1 = (h1 * 5 + 0xe6546b64) | 0;
}

if((len % 2) == 1) {
k1 = data.charCodeAt(roundedEnd);
k1 = this.mul32(k1, c1);
k1 = ((k1 & 0x1ffff) << 15) | (k1 >>> 17);  // ROTL32(k1,15);
k1 = this.mul32(k1, c2);
h1 ^= k1;
}

// finalization
h1 ^= (len << 1);

// fmix(h1);
h1 ^= h1 >>> 16;
h1  = this.mul32(h1, 0x85ebca6b);
h1 ^= h1 >>> 13;
h1  = this.mul32(h1, 0xc2b2ae35);
h1 ^= h1 >>> 16;

return h1;
}
};

if(typeof module !== "undefined" && typeof module.exports !== "undefined") {
module.exports = MurmurHash3;
}

Вот код HTML + Javascript, который я использую для проверки JavaScript

https://jsbin.com/gicomikike/edit?html,js,output

<html>
<head>

<script src="https://ajax.googleapis.com/ajax/libs/jquery/3.1.0/jquery.min.js"></script>
<script src="murmurhash3.js"></script>

<script>

function call_murmurhash3_32_gc () {
var key = $('textarea#textarea1').val();
var seed = 0;
var hash = MurmurHash3.hashString (key, key.length, seed);
$('div#div1').text(hash);
}
</script>

</head>
<body>
Body

<form>

<textarea rows="4" cols="50" id=textarea1></textarea>

<br>
<input type="button" value="Hash" onclick="call_murmurhash3_32_gc()"/>

</form><div id=div1>

</div>

</body>
</html>

simple_python_wrapper.py

Это использует MurmurHash3.cpp в дереве импорта sklearn.

from sklearn.feature_extraction._hashing import transform
import numpy as np

def getHashIndex (words):

raw_X = words
n_features = 262144 # 2 ** 18
dtype = np.float32 #np.float64

#transform(raw_X, Py_ssize_t n_features, dtype)
indices_a, indptr, values = transform (raw_X, n_features, dtype)

return indices_awords = [[("hello", 1), ("there", 1)]]

print getHashIndex (words)

Выход

[260679  45525]

MurmurHash3.cpp

I copied this code is available here
https://github.com/karanlyons/murmurHash3.js/blob/master/murmurHash3.js
//-----------------------------------------------------------------------------
// MurmurHash3 was written by Austin Appleby, and is placed in the public
// domain. The author hereby disclaims copyright to this source code.

// Note - The x86 and x64 versions do _not_ produce the same results, as the
// algorithms are optimized for their respective platforms. You can still
// compile and run any of them on any platform, but your performance with the
// non-native version will be less than optimal.

#include "MurmurHash3.h"
//-----------------------------------------------------------------------------
// Platform-specific functions and macros

// Microsoft Visual Studio

#if defined(_MSC_VER)

#define FORCE_INLINE    __forceinline

#include <stdlib.h>

#define ROTL32(x,y) _rotl(x,y)
#define ROTL64(x,y) _rotl64(x,y)

#define BIG_CONSTANT(x) (x)

// Other compilers

#else   // defined(_MSC_VER)

#if defined(GNUC) && ((GNUC > 4) || (GNUC == 4 && GNUC_MINOR >= 4))

/* gcc version >= 4.4 4.1 = RHEL 5, 4.4 = RHEL 6.
* Don't inline for RHEL 5 gcc which is 4.1 */
#define FORCE_INLINE attribute((always_inline))

#else

#define FORCE_INLINE

#endifinline uint32_t rotl32 ( uint32_t x, int8_t r )
{
return (x << r) | (x >> (32 - r));
}

inline uint64_t rotl64 ( uint64_t x, int8_t r )
{
return (x << r) | (x >> (64 - r));
}

#define ROTL32(x,y) rotl32(x,y)
#define ROTL64(x,y) rotl64(x,y)

#define BIG_CONSTANT(x) (x##LLU)

#endif // !defined(_MSC_VER)

//-----------------------------------------------------------------------------
// Block read - if your platform needs to do endian-swapping or can only
// handle aligned reads, do the conversion here

FORCE_INLINE uint32_t getblock ( const uint32_t * p, int i )
{
return p[i];
}

FORCE_INLINE uint64_t getblock ( const uint64_t * p, int i )
{
return p[i];
}

//-----------------------------------------------------------------------------
// Finalization mix - force all bits of a hash block to avalanche

FORCE_INLINE uint32_t fmix ( uint32_t h )
{
h ^= h >> 16;
h *= 0x85ebca6b;
h ^= h >> 13;
h *= 0xc2b2ae35;
h ^= h >> 16;

return h;
}

//----------

FORCE_INLINE uint64_t fmix ( uint64_t k )
{
k ^= k >> 33;
k *= BIG_CONSTANT(0xff51afd7ed558ccd);
k ^= k >> 33;
k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
k ^= k >> 33;

return k;
}

//-----------------------------------------------------------------------------

void MurmurHash3_x86_32 ( const void * key, int len,
uint32_t seed, void * out )
{
const uint8_t * data = (const uint8_t*)key;
const int nblocks = len / 4;

uint32_t h1 = seed;

uint32_t c1 = 0xcc9e2d51;
uint32_t c2 = 0x1b873593;

//----------
// body

const uint32_t * blocks = (const uint32_t *)(data + nblocks*4);

for(int i = -nblocks; i; i++)
{
uint32_t k1 = getblock(blocks,i);

k1 *= c1;
k1 = ROTL32(k1,15);
k1 *= c2;

h1 ^= k1;
h1 = ROTL32(h1,13);
h1 = h1*5+0xe6546b64;
}

//----------
// tail

const uint8_t * tail = (const uint8_t*)(data + nblocks*4);

uint32_t k1 = 0;

switch(len & 3)
{
case 3: k1 ^= tail[2] << 16;
case 2: k1 ^= tail[1] << 8;
case 1: k1 ^= tail[0];
k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
};

//----------
// finalization

h1 ^= len;

h1 = fmix(h1);

*(uint32_t*)out = h1;
}

//-----------------------------------------------------------------------------

void MurmurHash3_x86_128 ( const void * key, const int len,
uint32_t seed, void * out )
{
const uint8_t * data = (const uint8_t*)key;
const int nblocks = len / 16;

uint32_t h1 = seed;
uint32_t h2 = seed;
uint32_t h3 = seed;
uint32_t h4 = seed;

uint32_t c1 = 0x239b961b;
uint32_t c2 = 0xab0e9789;
uint32_t c3 = 0x38b34ae5;
uint32_t c4 = 0xa1e38b93;

//----------
// body

const uint32_t * blocks = (const uint32_t *)(data + nblocks*16);

for(int i = -nblocks; i; i++)
{
uint32_t k1 = getblock(blocks,i*4+0);
uint32_t k2 = getblock(blocks,i*4+1);
uint32_t k3 = getblock(blocks,i*4+2);
uint32_t k4 = getblock(blocks,i*4+3);

k1 *= c1; k1  = ROTL32(k1,15); k1 *= c2; h1 ^= k1;

h1 = ROTL32(h1,19); h1 += h2; h1 = h1*5+0x561ccd1b;

k2 *= c2; k2  = ROTL32(k2,16); k2 *= c3; h2 ^= k2;

h2 = ROTL32(h2,17); h2 += h3; h2 = h2*5+0x0bcaa747;

k3 *= c3; k3  = ROTL32(k3,17); k3 *= c4; h3 ^= k3;

h3 = ROTL32(h3,15); h3 += h4; h3 = h3*5+0x96cd1c35;

k4 *= c4; k4  = ROTL32(k4,18); k4 *= c1; h4 ^= k4;

h4 = ROTL32(h4,13); h4 += h1; h4 = h4*5+0x32ac3b17;
}

//----------
// tail

const uint8_t * tail = (const uint8_t*)(data + nblocks*16);

uint32_t k1 = 0;
uint32_t k2 = 0;
uint32_t k3 = 0;
uint32_t k4 = 0;

switch(len & 15)
{
case 15: k4 ^= tail[14] << 16;
case 14: k4 ^= tail[13] << 8;
case 13: k4 ^= tail[12] << 0;
k4 *= c4; k4  = ROTL32(k4,18); k4 *= c1; h4 ^= k4;

case 12: k3 ^= tail[11] << 24;
case 11: k3 ^= tail[10] << 16;
case 10: k3 ^= tail[ 9] << 8;
case  9: k3 ^= tail[ 8] << 0;
k3 *= c3; k3  = ROTL32(k3,17); k3 *= c4; h3 ^= k3;

case  8: k2 ^= tail[ 7] << 24;
case  7: k2 ^= tail[ 6] << 16;
case  6: k2 ^= tail[ 5] << 8;
case  5: k2 ^= tail[ 4] << 0;
k2 *= c2; k2  = ROTL32(k2,16); k2 *= c3; h2 ^= k2;

case  4: k1 ^= tail[ 3] << 24;
case  3: k1 ^= tail[ 2] << 16;
case  2: k1 ^= tail[ 1] << 8;
case  1: k1 ^= tail[ 0] << 0;
k1 *= c1; k1  = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
};

//----------
// finalization

h1 ^= len; h2 ^= len; h3 ^= len; h4 ^= len;

h1 += h2; h1 += h3; h1 += h4;
h2 += h1; h3 += h1; h4 += h1;

h1 = fmix(h1);
h2 = fmix(h2);
h3 = fmix(h3);
h4 = fmix(h4);

h1 += h2; h1 += h3; h1 += h4;
h2 += h1; h3 += h1; h4 += h1;

((uint32_t*)out)[0] = h1;
((uint32_t*)out)[1] = h2;
((uint32_t*)out)[2] = h3;
((uint32_t*)out)[3] = h4;
}

//-----------------------------------------------------------------------------

void MurmurHash3_x64_128 ( const void * key, const int len,
const uint32_t seed, void * out )
{
const uint8_t * data = (const uint8_t*)key;
const int nblocks = len / 16;

uint64_t h1 = seed;
uint64_t h2 = seed;

uint64_t c1 = BIG_CONSTANT(0x87c37b91114253d5);
uint64_t c2 = BIG_CONSTANT(0x4cf5ad432745937f);

//----------
// body

const uint64_t * blocks = (const uint64_t *)(data);

for(int i = 0; i < nblocks; i++)
{
uint64_t k1 = getblock(blocks,i*2+0);
uint64_t k2 = getblock(blocks,i*2+1);

k1 *= c1; k1  = ROTL64(k1,31); k1 *= c2; h1 ^= k1;

h1 = ROTL64(h1,27); h1 += h2; h1 = h1*5+0x52dce729;

k2 *= c2; k2  = ROTL64(k2,33); k2 *= c1; h2 ^= k2;

h2 = ROTL64(h2,31); h2 += h1; h2 = h2*5+0x38495ab5;
}

//----------
// tail

const uint8_t * tail = (const uint8_t*)(data + nblocks*16);

uint64_t k1 = 0;
uint64_t k2 = 0;

switch(len & 15)
{
case 15: k2 ^= uint64_t(tail[14]) << 48;
case 14: k2 ^= uint64_t(tail[13]) << 40;
case 13: k2 ^= uint64_t(tail[12]) << 32;
case 12: k2 ^= uint64_t(tail[11]) << 24;
case 11: k2 ^= uint64_t(tail[10]) << 16;
case 10: k2 ^= uint64_t(tail[ 9]) << 8;
case  9: k2 ^= uint64_t(tail[ 8]) << 0;
k2 *= c2; k2  = ROTL64(k2,33); k2 *= c1; h2 ^= k2;

case  8: k1 ^= uint64_t(tail[ 7]) << 56;
case  7: k1 ^= uint64_t(tail[ 6]) << 48;
case  6: k1 ^= uint64_t(tail[ 5]) << 40;
case  5: k1 ^= uint64_t(tail[ 4]) << 32;
case  4: k1 ^= uint64_t(tail[ 3]) << 24;
case  3: k1 ^= uint64_t(tail[ 2]) << 16;
case  2: k1 ^= uint64_t(tail[ 1]) << 8;
case  1: k1 ^= uint64_t(tail[ 0]) << 0;
k1 *= c1; k1  = ROTL64(k1,31); k1 *= c2; h1 ^= k1;
};

//----------
// finalization

h1 ^= len; h2 ^= len;

h1 += h2;
h2 += h1;

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

h1 += h2;
h2 += h1;

((uint64_t*)out)[0] = h1;
((uint64_t*)out)[1] = h2;
}

//-----------------------------------------------------------------------------

Позвольте мне объяснить это немного подробнее.

from sklearn.feature_extraction._hashing import transform
использует этот код https://github.com/scikit-learn/scikit-learn/blob/412996f09b6756752dfd3736c306d46fca8f1aa1/sklearn/feature_extraction/_hashing.pyx
который использует это
from sklearn.utils.murmurhash cimport murmurhash3_bytes_s32
который в свою очередь использует это
https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/utils/murmurhash.pyx
который построен на этом
https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/utils/src/MurmurHash3.cpp . Итак, MurmurHash3.cpp очень важен. Мне нужна версия Javascript этого точного MurmurHash3.cpp, чтобы код Javascript и MurmurHash3.cpp давали одинаковый результат.

Мне это нужно, потому что я хочу сделать некоторые из своих инструментов машинного обучения доступными в Интернете, а хеширование должно выполняться в веб-браузере клиента.

До сих пор я нашел несколько реализаций Jurascript MurmurHash3. Тем не менее, murmurhash3.js https://github.com/whitequark/murmurhash3-js/blob/master/murmurhash3.js кажется наиболее близким (с точки зрения структуры кодов) к MurmurHash3.cpp, используемому sklearn. Но я все еще не получил тот же самый хэш от них обоих.

Может кто-нибудь, пожалуйста, сообщите мне о том, как изменить murmurhash3.js (выше), так что он производит тот же хеш, что и MurmurHash3.cpp (выше) делает?

<script>
function call_murmurhash3_32_gc () {
var key = $('textarea#textarea1').val();
var seed = 0;
var hash = MurmurHash3.hashBytes (key, key.length, seed);
$('div#div1').text(Math.abs (hash) % 262144);
}
</script>

npm install murmurhash3js-revisited

import MurmurHash3 from 'murmurhash3js-revisited';

const str = "My hovercraft is full of eels.";
// get utf-8 bytes
const bytes = new TextEncoder().encode(str);

MurmurHash3.x86.hash32(bytes);
// output: 2953494853

MurmurHash3.x86.hash128(bytes);
// output: "e3a186aee169ba6c6a8bd9343c68fa9c"
MurmurHash3.x64.hash128(bytes);
// output: "03e5e14d358c16d1e5ae86df7ed5cfcb"
MurmurHash3.x86.hash32("any string");
// output: undefined
// (x86.hash128 and x64.hash128 also return undefined)