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