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

212