View Javadoc
1   /*
2    * Copyright (C) 2011 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5    * in compliance with the License. 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 distributed under the License
10   * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11   * or implied. See the License for the specific language governing permissions and limitations under
12   * the License.
13   */
14  
15  package com.google.common.hash;
16  
17  import static com.google.common.base.Preconditions.checkArgument;
18  import static com.google.common.base.Preconditions.checkNotNull;
19  import static com.google.common.base.Preconditions.checkState;
20  
21  import com.google.common.annotations.Beta;
22  import com.google.common.base.Preconditions;
23  import com.google.common.primitives.Ints;
24  import com.google.common.primitives.UnsignedInts;
25  import com.google.errorprone.annotations.CanIgnoreReturnValue;
26  import java.io.Serializable;
27  import javax.annotation.Nullable;
28  
29  /**
30   * An immutable hash code of arbitrary bit length.
31   *
32   * @author Dimitris Andreou
33   * @author Kurt Alfred Kluever
34   * @since 11.0
35   */
36  @Beta
37  public abstract class HashCode {
38    HashCode() {}
39  
40    /**
41     * Returns the number of bits in this hash code; a positive multiple of 8.
42     */
43    public abstract int bits();
44  
45    /**
46     * Returns the first four bytes of {@linkplain #asBytes() this hashcode's bytes}, converted to an
47     * {@code int} value in little-endian order.
48     *
49     * @throws IllegalStateException if {@code bits() < 32}
50     */
51    public abstract int asInt();
52  
53    /**
54     * Returns the first eight bytes of {@linkplain #asBytes() this hashcode's bytes}, converted to a
55     * {@code long} value in little-endian order.
56     *
57     * @throws IllegalStateException if {@code bits() < 64}
58     */
59    public abstract long asLong();
60  
61    /**
62     * If this hashcode has enough bits, returns {@code asLong()}, otherwise returns a {@code long}
63     * value with {@code asBytes()} as the least-significant bytes and {@code 0x00} as the remaining
64     * most-significant bytes.
65     *
66     * @since 14.0 (since 11.0 as {@code Hashing.padToLong(HashCode)})
67     */
68    public abstract long padToLong();
69  
70    /**
71     * Returns the value of this hash code as a byte array. The caller may modify the byte array;
72     * changes to it will <i>not</i> be reflected in this {@code HashCode} object or any other arrays
73     * returned by this method.
74     */
75    // TODO(user): consider ByteString here, when that is available
76    public abstract byte[] asBytes();
77  
78    /**
79     * Copies bytes from this hash code into {@code dest}.
80     *
81     * @param dest the byte array into which the hash code will be written
82     * @param offset the start offset in the data
83     * @param maxLength the maximum number of bytes to write
84     * @return the number of bytes written to {@code dest}
85     * @throws IndexOutOfBoundsException if there is not enough room in {@code dest}
86     */
87    @CanIgnoreReturnValue
88    public int writeBytesTo(byte[] dest, int offset, int maxLength) {
89      maxLength = Ints.min(maxLength, bits() / 8);
90      Preconditions.checkPositionIndexes(offset, offset + maxLength, dest.length);
91      writeBytesToImpl(dest, offset, maxLength);
92      return maxLength;
93    }
94  
95    abstract void writeBytesToImpl(byte[] dest, int offset, int maxLength);
96  
97    /**
98     * Returns a mutable view of the underlying bytes for the given {@code HashCode} if it is a
99     * byte-based hashcode. Otherwise it returns {@link HashCode#asBytes}. Do <i>not</i> mutate this
100    * array or else you will break the immutability contract of {@code HashCode}.
101    */
102   byte[] getBytesInternal() {
103     return asBytes();
104   }
105 
106   /**
107    * Returns whether this {@code HashCode} and that {@code HashCode} have the same value, given that
108    * they have the same number of bits.
109    */
110   abstract boolean equalsSameBits(HashCode that);
111 
112   /**
113    * Creates a 32-bit {@code HashCode} representation of the given int value. The underlying bytes
114    * are interpreted in little endian order.
115    *
116    * @since 15.0 (since 12.0 in HashCodes)
117    */
118   public static HashCode fromInt(int hash) {
119     return new IntHashCode(hash);
120   }
121 
122   private static final class IntHashCode extends HashCode implements Serializable {
123     final int hash;
124 
125     IntHashCode(int hash) {
126       this.hash = hash;
127     }
128 
129     @Override
130     public int bits() {
131       return 32;
132     }
133 
134     @Override
135     public byte[] asBytes() {
136       return new byte[] {
137         (byte) hash,
138         (byte) (hash >> 8),
139         (byte) (hash >> 16),
140         (byte) (hash >> 24)
141       };
142     }
143 
144     @Override
145     public int asInt() {
146       return hash;
147     }
148 
149     @Override
150     public long asLong() {
151       throw new IllegalStateException("this HashCode only has 32 bits; cannot create a long");
152     }
153 
154     @Override
155     public long padToLong() {
156       return UnsignedInts.toLong(hash);
157     }
158 
159     @Override
160     void writeBytesToImpl(byte[] dest, int offset, int maxLength) {
161       for (int i = 0; i < maxLength; i++) {
162         dest[offset + i] = (byte) (hash >> (i * 8));
163       }
164     }
165 
166     @Override
167     boolean equalsSameBits(HashCode that) {
168       return hash == that.asInt();
169     }
170 
171     private static final long serialVersionUID = 0;
172   }
173 
174   /**
175    * Creates a 64-bit {@code HashCode} representation of the given long value. The underlying bytes
176    * are interpreted in little endian order.
177    *
178    * @since 15.0 (since 12.0 in HashCodes)
179    */
180   public static HashCode fromLong(long hash) {
181     return new LongHashCode(hash);
182   }
183 
184   private static final class LongHashCode extends HashCode implements Serializable {
185     final long hash;
186 
187     LongHashCode(long hash) {
188       this.hash = hash;
189     }
190 
191     @Override
192     public int bits() {
193       return 64;
194     }
195 
196     @Override
197     public byte[] asBytes() {
198       return new byte[] {
199         (byte) hash,
200         (byte) (hash >> 8),
201         (byte) (hash >> 16),
202         (byte) (hash >> 24),
203         (byte) (hash >> 32),
204         (byte) (hash >> 40),
205         (byte) (hash >> 48),
206         (byte) (hash >> 56)
207       };
208     }
209 
210     @Override
211     public int asInt() {
212       return (int) hash;
213     }
214 
215     @Override
216     public long asLong() {
217       return hash;
218     }
219 
220     @Override
221     public long padToLong() {
222       return hash;
223     }
224 
225     @Override
226     void writeBytesToImpl(byte[] dest, int offset, int maxLength) {
227       for (int i = 0; i < maxLength; i++) {
228         dest[offset + i] = (byte) (hash >> (i * 8));
229       }
230     }
231 
232     @Override
233     boolean equalsSameBits(HashCode that) {
234       return hash == that.asLong();
235     }
236 
237     private static final long serialVersionUID = 0;
238   }
239 
240   /**
241    * Creates a {@code HashCode} from a byte array. The array is defensively copied to preserve the
242    * immutability contract of {@code HashCode}. The array cannot be empty.
243    *
244    * @since 15.0 (since 12.0 in HashCodes)
245    */
246   public static HashCode fromBytes(byte[] bytes) {
247     checkArgument(bytes.length >= 1, "A HashCode must contain at least 1 byte.");
248     return fromBytesNoCopy(bytes.clone());
249   }
250 
251   /**
252    * Creates a {@code HashCode} from a byte array. The array is <i>not</i> copied defensively, so it
253    * must be handed-off so as to preserve the immutability contract of {@code HashCode}.
254    */
255   static HashCode fromBytesNoCopy(byte[] bytes) {
256     return new BytesHashCode(bytes);
257   }
258 
259   private static final class BytesHashCode extends HashCode implements Serializable {
260     final byte[] bytes;
261 
262     BytesHashCode(byte[] bytes) {
263       this.bytes = checkNotNull(bytes);
264     }
265 
266     @Override
267     public int bits() {
268       return bytes.length * 8;
269     }
270 
271     @Override
272     public byte[] asBytes() {
273       return bytes.clone();
274     }
275 
276     @Override
277     public int asInt() {
278       checkState(
279           bytes.length >= 4,
280           "HashCode#asInt() requires >= 4 bytes (it only has %s bytes).",
281           bytes.length);
282       return (bytes[0] & 0xFF)
283           | ((bytes[1] & 0xFF) << 8)
284           | ((bytes[2] & 0xFF) << 16)
285           | ((bytes[3] & 0xFF) << 24);
286     }
287 
288     @Override
289     public long asLong() {
290       checkState(
291           bytes.length >= 8,
292           "HashCode#asLong() requires >= 8 bytes (it only has %s bytes).",
293           bytes.length);
294       return padToLong();
295     }
296 
297     @Override
298     public long padToLong() {
299       long retVal = (bytes[0] & 0xFF);
300       for (int i = 1; i < Math.min(bytes.length, 8); i++) {
301         retVal |= (bytes[i] & 0xFFL) << (i * 8);
302       }
303       return retVal;
304     }
305 
306     @Override
307     void writeBytesToImpl(byte[] dest, int offset, int maxLength) {
308       System.arraycopy(bytes, 0, dest, offset, maxLength);
309     }
310 
311     @Override
312     byte[] getBytesInternal() {
313       return bytes;
314     }
315 
316     @Override
317     boolean equalsSameBits(HashCode that) {
318       // We don't use MessageDigest.isEqual() here because its contract does not guarantee
319       // constant-time evaluation (no short-circuiting).
320       if (this.bytes.length != that.getBytesInternal().length) {
321         return false;
322       }
323 
324       boolean areEqual = true;
325       for (int i = 0; i < this.bytes.length; i++) {
326         areEqual &= (this.bytes[i] == that.getBytesInternal()[i]);
327       }
328       return areEqual;
329     }
330 
331     private static final long serialVersionUID = 0;
332   }
333 
334   /**
335    * Creates a {@code HashCode} from a hexadecimal ({@code base 16}) encoded string. The string must
336    * be at least 2 characters long, and contain only valid, lower-cased hexadecimal characters.
337    *
338    * <p>This method accepts the exact format generated by {@link #toString}. If you require more
339    * lenient {@code base 16} decoding, please use {@link com.google.common.io.BaseEncoding#decode}
340    * (and pass the result to {@link #fromBytes}).
341    *
342    * @since 15.0
343    */
344   public static HashCode fromString(String string) {
345     checkArgument(
346         string.length() >= 2, "input string (%s) must have at least 2 characters", string);
347     checkArgument(
348         string.length() % 2 == 0,
349         "input string (%s) must have an even number of characters",
350         string);
351 
352     byte[] bytes = new byte[string.length() / 2];
353     for (int i = 0; i < string.length(); i += 2) {
354       int ch1 = decode(string.charAt(i)) << 4;
355       int ch2 = decode(string.charAt(i + 1));
356       bytes[i / 2] = (byte) (ch1 + ch2);
357     }
358     return fromBytesNoCopy(bytes);
359   }
360 
361   private static int decode(char ch) {
362     if (ch >= '0' && ch <= '9') {
363       return ch - '0';
364     }
365     if (ch >= 'a' && ch <= 'f') {
366       return ch - 'a' + 10;
367     }
368     throw new IllegalArgumentException("Illegal hexadecimal character: " + ch);
369   }
370 
371   /**
372    * Returns {@code true} if {@code object} is a {@link HashCode} instance with the identical byte
373    * representation to this hash code.
374    *
375    * <p><b>Security note:</b> this method uses a constant-time (not short-circuiting) implementation
376    * to protect against <a href="http://en.wikipedia.org/wiki/Timing_attack">timing attacks</a>.
377    */
378   @Override
379   public final boolean equals(@Nullable Object object) {
380     if (object instanceof HashCode) {
381       HashCode that = (HashCode) object;
382       return bits() == that.bits() && equalsSameBits(that);
383     }
384     return false;
385   }
386 
387   /**
388    * Returns a "Java hash code" for this {@code HashCode} instance; this is well-defined (so, for
389    * example, you can safely put {@code HashCode} instances into a {@code
390    * HashSet}) but is otherwise probably not what you want to use.
391    */
392   @Override
393   public final int hashCode() {
394     // If we have at least 4 bytes (32 bits), just take the first 4 bytes. Since this is
395     // already a (presumably) high-quality hash code, any four bytes of it will do.
396     if (bits() >= 32) {
397       return asInt();
398     }
399     // If we have less than 4 bytes, use them all.
400     byte[] bytes = getBytesInternal();
401     int val = (bytes[0] & 0xFF);
402     for (int i = 1; i < bytes.length; i++) {
403       val |= ((bytes[i] & 0xFF) << (i * 8));
404     }
405     return val;
406   }
407 
408   /**
409    * Returns a string containing each byte of {@link #asBytes}, in order, as a two-digit unsigned
410    * hexadecimal number in lower case.
411    *
412    * <p>Note that if the output is considered to be a single hexadecimal number, this hash code's
413    * bytes are the <i>big-endian</i> representation of that number. This may be surprising since
414    * everything else in the hashing API uniformly treats multibyte values as little-endian. But this
415    * format conveniently matches that of utilities such as the UNIX {@code md5sum} command.
416    *
417    * <p>To create a {@code HashCode} from its string representation, see {@link #fromString}.
418    */
419   @Override
420   public final String toString() {
421     byte[] bytes = getBytesInternal();
422     StringBuilder sb = new StringBuilder(2 * bytes.length);
423     for (byte b : bytes) {
424       sb.append(hexDigits[(b >> 4) & 0xf]).append(hexDigits[b & 0xf]);
425     }
426     return sb.toString();
427   }
428 
429   private static final char[] hexDigits = "0123456789abcdef".toCharArray();
430 }