Debian Codegraph @

closure-library/closure/goog/crypt/hash32.js

raw
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 };