Skip to content

@favila /murmur3_32.js
Last active

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Port just enough of Murmur3 32bit to javascript for clojurescript. Goal is to produce identical results and capabilities as this class: https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/Murmur3.java
/**
* Javascript port of Clojure's flavor of Murmur3.
* See https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/Murmur3.java
*
* Find at: https://gist.github.com/favila/9088146
* By favila (Francis Avila) 2014-02-19
*/
goog.provide('cljs.lang.murmur3');
goog.require('cljs.core');
goog.scope(function(){
"use strict";
var murmur3 = cljs.lang.murmur3;
/**
* imul polyfill
*
* @param {number} a
* @param {number} b
* @return {number}
* @nosideeffects
*/
murmur3.imul = Math['imul'] ||
// Using bracket notation for Math.imul because goog compiler lacks an extern for it.
function (a, b) {
var c = a & 65535, d = b & 65535;
return c * d + ((a >>> 16 & 65535) * d + c * (b >>> 16 & 65535) << 16 >>> 0) | 0;
};
/** @const */
murmur3.SEED = 0;
/** @const */
murmur3.C1 = 0xcc9e2d51;
/** @const */
murmur3.C2 = 0x1b873593;
/**
* @param {number} k1 32-bit signed int
* @return {number} 32-bit signed int
*/
murmur3.mixK1 = function(k1) {
// Mask-and-shifts are to emulate multiplication overflow. Otherwise we
// could lose some bits of the significand if k1 is large enough.
// k1 *= murmur3.C1
k1 = murmur3.imul(k1, murmur3.C1);
k1 = (k1 << 15) | (k1 >>> 17); // rotateLeft(k1, 15)
// k1 *= murmur3.C2
k1 = murmur3.imul(k1, murmur3.C2);
return k1;
};
/**
* @param {number} h1 32-bit signed int
* @param {number} k1 32-bit signed int
* @return {number} 32-bit signed int
*/
murmur3.mixH1 = function(h1, k1) {
h1 ^= k1;
h1 = (h1 << 13) | (h1 >>> 19); // rotateLeft(h1, 13)
// h1 = h1 * 5 + 0xe6546b64
h1 = (murmur3.imul(h1, 5) + 0xe6546b64) | 0;
return h1;
};
/**
* @param {number} h1 32-bit signed int
* @param {number} length 32-bit signed int
* @return {number} 32-bit signed int
*/
murmur3.fmix = function(h1, length) {
h1 ^= length;
h1 ^= h1 >>> 16;
// h1 *= 0x85ebca6b
h1 = murmur3.imul(h1, 0x85ebca6b);
h1 ^= h1 >>> 13;
// h1 *= 0xc2b2ae35
h1 = murmur3.imul(h1, 0xc2b2ae35);
h1 ^= h1 >>> 16;
return h1;
};
/**
* @param {number} hash 32-bit signed int
* @param {number} count 32-bit signed int
* @return {number} 32-bit signed int
*/
murmur3.mixCollHash = function(hash, count){
var h1 = murmur3.SEED;
var k1 = murmur3.mixK1(hash);
h1 = murmur3.mixH1(h1, k1);
return murmur3.fmix(h1, count);
};
/**
* @param {number} input 32-bit signed int
* @return {number} 32-bit signed int
*/
murmur3.hashInt = function(input){
if (input === 0) return 0;
var k1 = murmur3.mixK1(input);
var h1 = murmur3.mixH1(murmur3.SEED, k1);
return murmur3.fmix(h1, 4);
};
// FIXME: No murmur3.hashLong() because no 64-bit longs in js. However, we may
// get up to 6.5 byte ints by retrieving the high 2.5 bytes with division.
// Should we try to hash the upper int range as if it were a full long? If so,
// should it replace hashInt() for all JS-number hashing, or only be used if
// we are out of 4-byte range?
/**
* Hash a string.
*
* @param {string} input input string
* @return {number}
*/
murmur3.hashUnencodedChars = function(input){
var h1 = murmur3.SEED, k1 = 0, i = 1, l = input.length;
while(i < l) {
k1 = input.charCodeAt(i - 1) | (input.charCodeAt(i) << 16);
i += 2;
k1 = murmur3.mixK1(k1);
h1 = murmur3.mixH1(h1, k1);
}
if (i === l) {
k1 = input.charCodeAt(i - 1);
k1 = murmur3.mixK1(k1);
h1 ^= k1;
}
return murmur3.fmix(h1, (l + l) |0);
};
//FIXME: Probably hashOrdered and hashUnordered should be implemented in clojurescript?
/**
* @param {*} xs seqable
* @return {number} 32-bit signed int
*/
murmur3.hashOrdered = function(xs){
var n = 0, hash = 1;
xs = cljs.core.seq(xs);
while (xs !== null) {
// hash = 31 * hash + cljs.core.hash(cljs.core.first(xs));
hash = (murmur3.imul(31, hash) + cljs.core.hash(cljs.core.first(xs))) | 0;
++n;
xs = cljs.core.next(xs);
}
return murmur3.mixCollHash(hash, n);
};
/**
* @param {*} xs seqable
* @return {number} 32-bit signed int
*/
murmur3.hashUnordered = function(xs) {
var hash = 0, n = 0;
xs = cljs.core.seq(xs);
while (xs !== null) {
hash = (hash + cljs.core.hash(cljs.core.first(xs))) | 0;
++n;
xs = cljs.core.next(xs);
}
return murmur3.mixCollHash(hash, n);
}
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.