Skip to content

Instantly share code, notes, and snippets.

@favila
Last active August 29, 2015 13:56
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save favila/9088146 to your computer and use it in GitHub Desktop.
Save favila/9088146 to your computer and use it in GitHub Desktop.
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