| 1 |
// Copyright 2008 The Closure Library Authors. All Rights Reserved. |
| 2 |
// |
| 3 |
// Licensed under the Apache License, Version 2.0 (the "License"); |
| 4 |
// you may not use this file except in compliance with the License. |
| 5 |
// You may obtain a copy of the License at |
| 6 |
// |
| 7 |
// http://www.apache.org/licenses/LICENSE-2.0 |
| 8 |
// |
| 9 |
// Unless required by applicable law or agreed to in writing, software |
| 10 |
// distributed under the License is distributed on an "AS-IS" BASIS, |
| 11 |
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 12 |
// See the License for the specific language governing permissions and |
| 13 |
// limitations under the License. |
| 14 |
|
| 15 |
/** |
| 16 |
* @fileoverview Implementation of 32-bit hashing functions. |
| 17 |
* |
| 18 |
* This is a direct port from the Google Java Hash class |
| 19 |
* |
| 20 |
*/ |
| 21 |
|
| 22 |
goog.provide('goog.crypt.hash32'); |
| 23 |
|
| 24 |
goog.require('goog.crypt'); |
| 25 |
|
| 26 |
|
| 27 |
/** |
| 28 |
* Default seed used during hashing, digits of pie. |
| 29 |
* See SEED32 in http://go/base.hash.java |
| 30 |
* @type {number} |
| 31 |
*/ |
| 32 |
goog.crypt.hash32.SEED32 = 314159265; |
| 33 |
|
| 34 |
|
| 35 |
/** |
| 36 |
* Arbitrary constant used during hashing. |
| 37 |
* See CONSTANT32 in http://go/base.hash.java |
| 38 |
* @type {number} |
| 39 |
*/ |
| 40 |
goog.crypt.hash32.CONSTANT32 = -1640531527; |
| 41 |
|
| 42 |
|
| 43 |
/** |
| 44 |
* Hashes a string to a 32-bit value. |
| 45 |
* @param {string} str String to hash. |
| 46 |
* @return {number} 32-bit hash. |
| 47 |
*/ |
| 48 |
goog.crypt.hash32.encodeString = function(str) { |
| 49 |
return goog.crypt.hash32.encodeByteArray(goog.crypt.stringToByteArray(str)); |
| 50 |
}; |
| 51 |
|
| 52 |
|
| 53 |
/** |
| 54 |
* Hashes a string to a 32-bit value, converting the string to UTF-8 before |
| 55 |
* doing the encoding. |
| 56 |
* @param {string} str String to hash. |
| 57 |
* @return {number} 32-bit hash. |
| 58 |
*/ |
| 59 |
goog.crypt.hash32.encodeStringUtf8 = function(str) { |
| 60 |
return goog.crypt.hash32.encodeByteArray( |
| 61 |
goog.crypt.stringToUtf8ByteArray(str)); |
| 62 |
}; |
| 63 |
|
| 64 |
|
| 65 |
/** |
| 66 |
* Hashes an integer to a 32-bit value. |
| 67 |
* @param {number} value Number to hash. |
| 68 |
* @return {number} 32-bit hash. |
| 69 |
*/ |
| 70 |
goog.crypt.hash32.encodeInteger = function(value) { |
| 71 |
// TODO(user): Does this make sense in JavaScript with doubles? Should we |
| 72 |
// force the value to be in the correct range? |
| 73 |
return goog.crypt.hash32.mix32_( |
| 74 |
{a: value, b: goog.crypt.hash32.CONSTANT32, c: goog.crypt.hash32.SEED32}); |
| 75 |
}; |
| 76 |
|
| 77 |
|
| 78 |
/** |
| 79 |
* Hashes a "byte" array to a 32-bit value using the supplied seed. |
| 80 |
* @param {Array<number>} bytes Array of bytes. |
| 81 |
* @param {number=} opt_offset The starting position to use for hash |
| 82 |
* computation. |
| 83 |
* @param {number=} opt_length Number of bytes that are used for hashing. |
| 84 |
* @param {number=} opt_seed The seed. |
| 85 |
* @return {number} 32-bit hash. |
| 86 |
*/ |
| 87 |
goog.crypt.hash32.encodeByteArray = function( |
| 88 |
bytes, opt_offset, opt_length, opt_seed) { |
| 89 |
var offset = opt_offset || 0; |
| 90 |
var length = opt_length || bytes.length; |
| 91 |
var seed = opt_seed || goog.crypt.hash32.SEED32; |
| 92 |
|
| 93 |
var mix = { |
| 94 |
a: goog.crypt.hash32.CONSTANT32, |
| 95 |
b: goog.crypt.hash32.CONSTANT32, |
| 96 |
c: seed |
| 97 |
}; |
| 98 |
|
| 99 |
var keylen; |
| 100 |
for (keylen = length; keylen >= 12; keylen -= 12, offset += 12) { |
| 101 |
mix.a += goog.crypt.hash32.wordAt_(bytes, offset); |
| 102 |
mix.b += goog.crypt.hash32.wordAt_(bytes, offset + 4); |
| 103 |
mix.c += goog.crypt.hash32.wordAt_(bytes, offset + 8); |
| 104 |
goog.crypt.hash32.mix32_(mix); |
| 105 |
} |
| 106 |
// Hash any remaining bytes |
| 107 |
mix.c += length; |
| 108 |
switch (keylen) { // deal with rest. Some cases fall through |
| 109 |
case 11: |
| 110 |
mix.c += (bytes[offset + 10]) << 24; |
| 111 |
case 10: |
| 112 |
mix.c += (bytes[offset + 9] & 0xff) << 16; |
| 113 |
case 9: |
| 114 |
mix.c += (bytes[offset + 8] & 0xff) << 8; |
| 115 |
// the first byte of c is reserved for the length |
| 116 |
case 8: |
| 117 |
mix.b += goog.crypt.hash32.wordAt_(bytes, offset + 4); |
| 118 |
mix.a += goog.crypt.hash32.wordAt_(bytes, offset); |
| 119 |
break; |
| 120 |
case 7: |
| 121 |
mix.b += (bytes[offset + 6] & 0xff) << 16; |
| 122 |
case 6: |
| 123 |
mix.b += (bytes[offset + 5] & 0xff) << 8; |
| 124 |
case 5: |
| 125 |
mix.b += (bytes[offset + 4] & 0xff); |
| 126 |
case 4: |
| 127 |
mix.a += goog.crypt.hash32.wordAt_(bytes, offset); |
| 128 |
break; |
| 129 |
case 3: |
| 130 |
mix.a += (bytes[offset + 2] & 0xff) << 16; |
| 131 |
case 2: |
| 132 |
mix.a += (bytes[offset + 1] & 0xff) << 8; |
| 133 |
case 1: |
| 134 |
mix.a += (bytes[offset + 0] & 0xff); |
| 135 |
// case 0 : nothing left to add |
| 136 |
} |
| 137 |
return goog.crypt.hash32.mix32_(mix); |
| 138 |
}; |
| 139 |
|
| 140 |
|
| 141 |
/** |
| 142 |
* Performs an inplace mix of an object with the integer properties (a, b, c) |
| 143 |
* and returns the final value of c. |
| 144 |
* @param {Object} mix Object with properties, a, b, and c. |
| 145 |
* @return {number} The end c-value for the mixing. |
| 146 |
* @private |
| 147 |
*/ |
| 148 |
goog.crypt.hash32.mix32_ = function(mix) { |
| 149 |
var a = mix.a, b = mix.b, c = mix.c; |
| 150 |
a -= b; |
| 151 |
a -= c; |
| 152 |
a ^= c >>> 13; |
| 153 |
b -= c; |
| 154 |
b -= a; |
| 155 |
b ^= a << 8; |
| 156 |
c -= a; |
| 157 |
c -= b; |
| 158 |
c ^= b >>> 13; |
| 159 |
a -= b; |
| 160 |
a -= c; |
| 161 |
a ^= c >>> 12; |
| 162 |
b -= c; |
| 163 |
b -= a; |
| 164 |
b ^= a << 16; |
| 165 |
c -= a; |
| 166 |
c -= b; |
| 167 |
c ^= b >>> 5; |
| 168 |
a -= b; |
| 169 |
a -= c; |
| 170 |
a ^= c >>> 3; |
| 171 |
b -= c; |
| 172 |
b -= a; |
| 173 |
b ^= a << 10; |
| 174 |
c -= a; |
| 175 |
c -= b; |
| 176 |
c ^= b >>> 15; |
| 177 |
mix.a = a; |
| 178 |
mix.b = b; |
| 179 |
mix.c = c; |
| 180 |
return c; |
| 181 |
}; |
| 182 |
|
| 183 |
|
| 184 |
/** |
| 185 |
* Returns the word at a given offset. Treating an array of bytes a word at a |
| 186 |
* time is far more efficient than byte-by-byte. |
| 187 |
* @param {Array<number>} bytes Array of bytes. |
| 188 |
* @param {number} offset Offset in the byte array. |
| 189 |
* @return {number} Integer value for the word. |
| 190 |
* @private |
| 191 |
*/ |
| 192 |
goog.crypt.hash32.wordAt_ = function(bytes, offset) { |
| 193 |
var a = goog.crypt.hash32.toSigned_(bytes[offset + 0]); |
| 194 |
var b = goog.crypt.hash32.toSigned_(bytes[offset + 1]); |
| 195 |
var c = goog.crypt.hash32.toSigned_(bytes[offset + 2]); |
| 196 |
var d = goog.crypt.hash32.toSigned_(bytes[offset + 3]); |
| 197 |
return a + (b << 8) + (c << 16) + (d << 24); |
| 198 |
}; |
| 199 |
|
| 200 |
|
| 201 |
/** |
| 202 |
* Converts an unsigned "byte" to signed, that is, convert a value in the range |
| 203 |
* (0, 2^8-1) to (-2^7, 2^7-1) in order to be compatible with Java's byte type. |
| 204 |
* @param {number} n Unsigned "byte" value. |
| 205 |
* @return {number} Signed "byte" value. |
| 206 |
* @private |
| 207 |
*/ |
| 208 |
goog.crypt.hash32.toSigned_ = function(n) { |
| 209 |
return n > 127 ? n - 256 : n; |
| 210 |
}; |