murmur3_32.js

/**
 * 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);
}

});