1/** 2 * @preserve 3 * JS Implementation of incremental MurmurHash3 (r150) (as of May 10, 2013) 4 * 5 * @author <a href="mailto:jensyt@gmail.com">Jens Taylor</a> 6 * @see http://github.com/homebrewing/brauhaus-diff 7 * @author <a href="mailto:gary.court@gmail.com">Gary Court</a> 8 * @see http://github.com/garycourt/murmurhash-js 9 * @author <a href="mailto:aappleby@gmail.com">Austin Appleby</a> 10 * @see http://sites.google.com/site/murmurhash/ 11 */ 12(function(){ 13 var cache; 14 15 // Call this function without `new` to use the cached object (good for 16 // single-threaded environments), or with `new` to create a new object. 17 // 18 // @param {string} key A UTF-16 or ASCII string 19 // @param {number} seed An optional positive integer 20 // @return {object} A MurmurHash3 object for incremental hashing 21 function MurmurHash3(key, seed) { 22 var m = this instanceof MurmurHash3 ? this : cache; 23 m.reset(seed) 24 if (typeof key === 'string' && key.length > 0) { 25 m.hash(key); 26 } 27 28 if (m !== this) { 29 return m; 30 } 31 }; 32 33 // Incrementally add a string to this hash 34 // 35 // @param {string} key A UTF-16 or ASCII string 36 // @return {object} this 37 MurmurHash3.prototype.hash = function(key) { 38 var h1, k1, i, top, len; 39 40 len = key.length; 41 this.len += len; 42 43 k1 = this.k1; 44 i = 0; 45 switch (this.rem) { 46 case 0: k1 ^= len > i ? (key.charCodeAt(i++) & 0xffff) : 0; 47 case 1: k1 ^= len > i ? (key.charCodeAt(i++) & 0xffff) << 8 : 0; 48 case 2: k1 ^= len > i ? (key.charCodeAt(i++) & 0xffff) << 16 : 0; 49 case 3: 50 k1 ^= len > i ? (key.charCodeAt(i) & 0xff) << 24 : 0; 51 k1 ^= len > i ? (key.charCodeAt(i++) & 0xff00) >> 8 : 0; 52 } 53 54 this.rem = (len + this.rem) & 3; // & 3 is same as % 4 55 len -= this.rem; 56 if (len > 0) { 57 h1 = this.h1; 58 while (1) { 59 k1 = (k1 * 0x2d51 + (k1 & 0xffff) * 0xcc9e0000) & 0xffffffff; 60 k1 = (k1 << 15) | (k1 >>> 17); 61 k1 = (k1 * 0x3593 + (k1 & 0xffff) * 0x1b870000) & 0xffffffff; 62 63 h1 ^= k1; 64 h1 = (h1 << 13) | (h1 >>> 19); 65 h1 = (h1 * 5 + 0xe6546b64) & 0xffffffff; 66 67 if (i >= len) { 68 break; 69 } 70 71 k1 = ((key.charCodeAt(i++) & 0xffff)) ^ 72 ((key.charCodeAt(i++) & 0xffff) << 8) ^ 73 ((key.charCodeAt(i++) & 0xffff) << 16); 74 top = key.charCodeAt(i++); 75 k1 ^= ((top & 0xff) << 24) ^ 76 ((top & 0xff00) >> 8); 77 } 78 79 k1 = 0; 80 switch (this.rem) { 81 case 3: k1 ^= (key.charCodeAt(i + 2) & 0xffff) << 16; 82 case 2: k1 ^= (key.charCodeAt(i + 1) & 0xffff) << 8; 83 case 1: k1 ^= (key.charCodeAt(i) & 0xffff); 84 } 85 86 this.h1 = h1; 87 } 88 89 this.k1 = k1; 90 return this; 91 }; 92 93 // Get the result of this hash 94 // 95 // @return {number} The 32-bit hash 96 MurmurHash3.prototype.result = function() { 97 var k1, h1; 98 99 k1 = this.k1; 100 h1 = this.h1; 101 102 if (k1 > 0) { 103 k1 = (k1 * 0x2d51 + (k1 & 0xffff) * 0xcc9e0000) & 0xffffffff; 104 k1 = (k1 << 15) | (k1 >>> 17); 105 k1 = (k1 * 0x3593 + (k1 & 0xffff) * 0x1b870000) & 0xffffffff; 106 h1 ^= k1; 107 } 108 109 h1 ^= this.len; 110 111 h1 ^= h1 >>> 16; 112 h1 = (h1 * 0xca6b + (h1 & 0xffff) * 0x85eb0000) & 0xffffffff; 113 h1 ^= h1 >>> 13; 114 h1 = (h1 * 0xae35 + (h1 & 0xffff) * 0xc2b20000) & 0xffffffff; 115 h1 ^= h1 >>> 16; 116 117 return h1 >>> 0; 118 }; 119 120 // Reset the hash object for reuse 121 // 122 // @param {number} seed An optional positive integer 123 MurmurHash3.prototype.reset = function(seed) { 124 this.h1 = typeof seed === 'number' ? seed : 0; 125 this.rem = this.k1 = this.len = 0; 126 return this; 127 }; 128 129 // A cached object to use. This can be safely used if you're in a single- 130 // threaded environment, otherwise you need to create new hashes to use. 131 cache = new MurmurHash3(); 132 133 if (typeof(module) != 'undefined') { 134 module.exports = MurmurHash3; 135 } else { 136 this.MurmurHash3 = MurmurHash3; 137 } 138}()); 139