1 /** 2 * The Render Engine 3 * FNV1 Hashing 4 * 5 * @fileoverview A class for quickly generating a hash for the provided input string. 6 * 7 * @author: Brett Fattori (brettf@renderengine.com) 8 * @author: $Author: bfattori $ 9 * @version: $Revision: 1555 $ 10 * 11 * Copyright (c) 2011 Brett Fattori (brettf@renderengine.com) 12 * 13 * Permission is hereby granted, free of charge, to any person obtaining a copy 14 * of this software and associated documentation files (the "Software"), to deal 15 * in the Software without restriction, including without limitation the rights 16 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 17 * copies of the Software, and to permit persons to whom the Software is 18 * furnished to do so, subject to the following conditions: 19 * 20 * The above copyright notice and this permission notice shall be included in 21 * all copies or substantial portions of the Software. 22 * 23 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 24 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 25 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 26 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 27 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 28 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 29 * THE SOFTWARE 30 */ 31 32 // The class this file defines and its required classes 33 R.Engine.define({ 34 "class":"R.util.FNV1Hash", 35 "requires":[ 36 "R.engine.PooledObject" 37 ] 38 }); 39 40 /* 41 * A family of fast hash functions, originally created by Glenn Fowler, Phong Vo, 42 * and improved by Landon Curt Noll. Implemented in Javascript by Brett Fattori. 43 * 44 * <p>FNV1 hashes are designed to be fast while maintaining a low collision rate. 45 * The FNV1 speed allows one to quickly hash lots of data while maintaining a 46 * reasonable collision rate. The high dispersion of the FNV1 hashes makes them 47 * well suited for hashing nearly identical strings such as URLs, hostnames, 48 * filenames, text, IP addresses, etc.</p> 49 * 50 * <p>FNV1a is a variant of FNV1, which is slightly better suited for hashing 51 * short values (< 4 octets).</p> 52 * 53 * <p>This is a straightforward port of the public domain C version, 54 * written by Landon Curt Noll (one of the authors), available from 55 * <a href="http://www.isthe.com/chongo/tech/comp/fnv/">his website</a>.</p> 56 * 57 * <p>The usage pattern is as follows: to compute the initial hash value 58 * you call one of the <code>init(...)</code> methods. After that you may 59 * update the hash zero or more times with additional values using the 60 * <code>update(...)</code> methods. When you are done, you can retrieve the 61 * final hash value with {@link #getHash()}.</p> 62 * <p>Individual instances of FNV1 are reusable after you call one of 63 * the <code>init(...)</code> methods. However, these implementations are NOT 64 * synchronized, so proper care should be taken when using this hash in a multi-threaded 65 * environment.</p> 66 * 67 * @author Brett Fattori <bfattori AT gmail DOT com> 68 * @private 69 */ 70 R.util.FNV1 = function (algo) { 71 72 // Create the linkage to the hashing algorithm 73 var fnv = algo.fnv; 74 var getHashValue = algo.getHash || function (h) { 75 return Number(h).toString(16); 76 }; 77 var INIT = algo.INIT; 78 79 return { 80 81 /** 82 * Initialize this hash instance. Any previous state is reset, and the new 83 * hash value is computed. 84 */ 85 init:function (buf, offset, len) { 86 if (typeof buf == "string") { 87 buf = buf.split(""); 88 offset = 0; 89 len = buf.length; 90 } 91 return fnv(buf, offset, len, INIT); 92 }, 93 94 /** 95 * Update the hash value. Repeated calls to this method update the hash 96 * value accordingly, and they are equivalent to calling the <code>init(...)</code> 97 * method once with a concatenated value of all parameters. 98 */ 99 update:function (hash, buf, offset, len) { 100 if (typeof buf == "string") { 101 buf = buf.split(""); 102 offset = 0; 103 len = buf.length; 104 } 105 hash = fnv(buf, offset, len, hash); 106 }, 107 108 /** 109 * Retrieve the hash value 110 * @return hash value 111 */ 112 getHash:function () { 113 return getHashValue(hash); 114 } 115 }; 116 }; 117 118 /** 119 * @class Implementation of FNV1 - a fast hash function. 120 * 121 * <p>This implementation uses 32-bit operations, and the values returned from 122 * {@link #getHash()} are limited to the lower 32 bits.</p> 123 * 124 * @author Andrzej Bialecki <ab@getopt.org> 125 */ 126 R.util.FNV132 = (function () { 127 return { 128 fnv:function (buf, offset, len, seed) { 129 for (var i = offset; i < offset + len; i++) { 130 seed += (seed << 1) + (seed << 4) + (seed << 7) + (seed << 8) + (seed << 24); 131 seed ^= String(buf[i]).charCodeAt(0); 132 } 133 return seed; 134 }, 135 136 INIT:0x811c9dc5 137 }; 138 })(); 139 140 /** 141 * @class Implementation of FNV1a - a fast hash function. The FNV1a variant provides a 142 * slightly better dispersion for short (< 4 bytes) values than plain FNV1. 143 * 144 * <p>This implementation uses 32-bit operations, and the values returned from 145 * {@link #getHash()} are limited to the lower 32 bits.</p> 146 * 147 * @author Andrzej Bialecki <ab@getopt.org> 148 */ 149 R.util.FNV1a32 = (function () { 150 return { 151 fnv:function (buf, offset, len, seed) { 152 for (var i = offset; i < offset + len; i++) { 153 seed ^= String(buf[i]).charCodeAt(0); 154 seed += (seed << 1) + (seed << 4) + (seed << 7) + (seed << 8) + (seed << 24); 155 } 156 return seed; 157 }, 158 159 INIT:0x811c9dc5 160 }; 161 })(); 162 163 /** 164 * @class A class for creating a hash value from a string. Calling the {@link #getHash} method resets 165 * the hash each time a new source string is provided, whereas evolving the hash will build upon 166 * previous hashes. The hash for a string will always be the same. Hashing a set of strings, in 167 * order, will always result in the same evolved hash. Uses the {@link R.lang.FNV1a32} hashing 168 * routine by default. 169 * 170 * @constructor 171 * @param [hashRoutine=R.lang.FNV1a32] {FNV1} The hash routine to use. 172 * @extends R.engine.PooledObject 173 */ 174 R.util.FNV1Hash = function () { 175 return R.engine.PooledObject.extend(/** @scope R.util.FNV1Hash.prototype */{ 176 177 fnv:null, 178 gotten:null, 179 lastHash:0, 180 181 /** @private */ 182 constructor:function (hashRoutine) { 183 this.base("FNV1Hash"); 184 this.fnv = new R.util.FNV1(hashRoutine || R.util.FNV1a32); 185 this.gotten = false; 186 this.lastHash = 0; 187 }, 188 189 /** 190 * Release the hash back into the pool for later use. 191 */ 192 release:function () { 193 this.base(); 194 this.fnv = null; 195 this.gotten = null; 196 this.lastHash = 0; 197 }, 198 199 /** 200 * Initialize the hasher with the provided string. To instead evolve the hash 201 * use the {@link #updateHash} to update the hash with new data. 202 * 203 * @param str {String} The value to get the hash for 204 * @return {String} A hexadecimal hash value 205 */ 206 getHash:function (str) { 207 this.gotten = true; 208 this.lastHash = this.fnv.init(str); 209 return this.getLastHash(); 210 }, 211 212 /** 213 * Get the last returned hash value without evolving the hash. 214 * @return {String} A hexadecimal hash value 215 */ 216 getLastHash:function () { 217 return Number(this.lastHash).toString(16); 218 }, 219 220 /** 221 * Evolves the existing hash. 222 * @param str {String} The value to get the hash for 223 * @return {String} A hexadecimal hash value 224 */ 225 updateHash:function (str) { 226 if (this.gotten) { 227 this.lastHash = this.fnv.update(this.lastHash, str); 228 return this.getLastHash(); 229 } else { 230 return this.getHash(str); 231 } 232 } 233 234 }, /** @scope R.util.FNV1Hash.prototype */{ 235 236 getClassName:function () { 237 return "R.util.FNV1Hash"; 238 } 239 }); 240 241 }; 242