001/*
002 * Copyright (C) 2011 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
005 * in compliance with the License. You may obtain a copy of the License at
006 *
007 * http://www.apache.org/licenses/LICENSE-2.0
008 *
009 * Unless required by applicable law or agreed to in writing, software distributed under the License
010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
011 * or implied. See the License for the specific language governing permissions and limitations under
012 * the License.
013 */
014
015package com.google.common.hash;
016
017import static com.google.common.base.Preconditions.checkArgument;
018import static com.google.common.base.Preconditions.checkNotNull;
019import static com.google.common.base.Preconditions.checkState;
020
021import com.google.common.annotations.Beta;
022import com.google.common.base.Preconditions;
023import com.google.common.primitives.Ints;
024import com.google.common.primitives.UnsignedInts;
025
026import java.io.Serializable;
027
028import javax.annotation.CheckReturnValue;
029import javax.annotation.Nullable;
030
031/**
032 * An immutable hash code of arbitrary bit length.
033 *
034 * @author Dimitris Andreou
035 * @author Kurt Alfred Kluever
036 * @since 11.0
037 */
038@Beta
039public abstract class HashCode {
040  HashCode() {}
041
042  /**
043   * Returns the number of bits in this hash code; a positive multiple of 8.
044   */
045  @CheckReturnValue
046  public abstract int bits();
047
048  /**
049   * Returns the first four bytes of {@linkplain #asBytes() this hashcode's bytes}, converted to
050   * an {@code int} value in little-endian order.
051   *
052   * @throws IllegalStateException if {@code bits() < 32}
053   */
054  @CheckReturnValue
055  public abstract int asInt();
056
057  /**
058   * Returns the first eight bytes of {@linkplain #asBytes() this hashcode's bytes}, converted to
059   * a {@code long} value in little-endian order.
060   *
061   * @throws IllegalStateException if {@code bits() < 64}
062   */
063  @CheckReturnValue
064  public abstract long asLong();
065
066  /**
067   * If this hashcode has enough bits, returns {@code asLong()}, otherwise returns a {@code long}
068   * value with {@code asBytes()} as the least-significant bytes and {@code 0x00} as the remaining
069   * most-significant bytes.
070   *
071   * @since 14.0 (since 11.0 as {@code Hashing.padToLong(HashCode)})
072   */
073  @CheckReturnValue
074  public abstract long padToLong();
075
076  /**
077   * Returns the value of this hash code as a byte array. The caller may modify the byte array;
078   * changes to it will <i>not</i> be reflected in this {@code HashCode} object or any other arrays
079   * returned by this method.
080   */
081  // TODO(user): consider ByteString here, when that is available
082  @CheckReturnValue
083  public abstract byte[] asBytes();
084
085  /**
086   * Copies bytes from this hash code into {@code dest}.
087   *
088   * @param dest the byte array into which the hash code will be written
089   * @param offset the start offset in the data
090   * @param maxLength the maximum number of bytes to write
091   * @return the number of bytes written to {@code dest}
092   * @throws IndexOutOfBoundsException if there is not enough room in {@code dest}
093   */
094  public int writeBytesTo(byte[] dest, int offset, int maxLength) {
095    maxLength = Ints.min(maxLength, bits() / 8);
096    Preconditions.checkPositionIndexes(offset, offset + maxLength, dest.length);
097    writeBytesToImpl(dest, offset, maxLength);
098    return maxLength;
099  }
100
101  abstract void writeBytesToImpl(byte[] dest, int offset, int maxLength);
102
103  /**
104   * Returns a mutable view of the underlying bytes for the given {@code HashCode} if it is a
105   * byte-based hashcode. Otherwise it returns {@link HashCode#asBytes}. Do <i>not</i> mutate this
106   * array or else you will break the immutability contract of {@code HashCode}.
107   */
108  byte[] getBytesInternal() {
109    return asBytes();
110  }
111
112  /**
113   * Returns whether this {@code HashCode} and that {@code HashCode} have the same value, given that
114   * they have the same number of bits.
115   */
116  abstract boolean equalsSameBits(HashCode that);
117
118  /**
119   * Creates a 32-bit {@code HashCode} representation of the given int value. The underlying bytes
120   * are interpreted in little endian order.
121   *
122   * @since 15.0 (since 12.0 in HashCodes)
123   */
124  @CheckReturnValue
125  public static HashCode fromInt(int hash) {
126    return new IntHashCode(hash);
127  }
128
129  private static final class IntHashCode extends HashCode implements Serializable {
130    final int hash;
131
132    IntHashCode(int hash) {
133      this.hash = hash;
134    }
135
136    @Override
137    public int bits() {
138      return 32;
139    }
140
141    @Override
142    public byte[] asBytes() {
143      return new byte[] {
144        (byte) hash,
145        (byte) (hash >> 8),
146        (byte) (hash >> 16),
147        (byte) (hash >> 24)
148      };
149    }
150
151    @Override
152    public int asInt() {
153      return hash;
154    }
155
156    @Override
157    public long asLong() {
158      throw new IllegalStateException("this HashCode only has 32 bits; cannot create a long");
159    }
160
161    @Override
162    public long padToLong() {
163      return UnsignedInts.toLong(hash);
164    }
165
166    @Override
167    void writeBytesToImpl(byte[] dest, int offset, int maxLength) {
168      for (int i = 0; i < maxLength; i++) {
169        dest[offset + i] = (byte) (hash >> (i * 8));
170      }
171    }
172
173    @Override
174    boolean equalsSameBits(HashCode that) {
175      return hash == that.asInt();
176    }
177
178    private static final long serialVersionUID = 0;
179  }
180
181  /**
182   * Creates a 64-bit {@code HashCode} representation of the given long value. The underlying bytes
183   * are interpreted in little endian order.
184   *
185   * @since 15.0 (since 12.0 in HashCodes)
186   */
187  @CheckReturnValue
188  public static HashCode fromLong(long hash) {
189    return new LongHashCode(hash);
190  }
191
192  private static final class LongHashCode extends HashCode implements Serializable {
193    final long hash;
194
195    LongHashCode(long hash) {
196      this.hash = hash;
197    }
198
199    @Override
200    public int bits() {
201      return 64;
202    }
203
204    @Override
205    public byte[] asBytes() {
206      return new byte[] {
207        (byte) hash,
208        (byte) (hash >> 8),
209        (byte) (hash >> 16),
210        (byte) (hash >> 24),
211        (byte) (hash >> 32),
212        (byte) (hash >> 40),
213        (byte) (hash >> 48),
214        (byte) (hash >> 56)
215      };
216    }
217
218    @Override
219    public int asInt() {
220      return (int) hash;
221    }
222
223    @Override
224    public long asLong() {
225      return hash;
226    }
227
228    @Override
229    public long padToLong() {
230      return hash;
231    }
232
233    @Override
234    void writeBytesToImpl(byte[] dest, int offset, int maxLength) {
235      for (int i = 0; i < maxLength; i++) {
236        dest[offset + i] = (byte) (hash >> (i * 8));
237      }
238    }
239
240    @Override
241    boolean equalsSameBits(HashCode that) {
242      return hash == that.asLong();
243    }
244
245    private static final long serialVersionUID = 0;
246  }
247
248  /**
249   * Creates a {@code HashCode} from a byte array. The array is defensively copied to preserve
250   * the immutability contract of {@code HashCode}. The array cannot be empty.
251   *
252   * @since 15.0 (since 12.0 in HashCodes)
253   */
254  @CheckReturnValue
255  public static HashCode fromBytes(byte[] bytes) {
256    checkArgument(bytes.length >= 1, "A HashCode must contain at least 1 byte.");
257    return fromBytesNoCopy(bytes.clone());
258  }
259
260  /**
261   * Creates a {@code HashCode} from a byte array. The array is <i>not</i> copied defensively,
262   * so it must be handed-off so as to preserve the immutability contract of {@code HashCode}.
263   */
264  static HashCode fromBytesNoCopy(byte[] bytes) {
265    return new BytesHashCode(bytes);
266  }
267
268  private static final class BytesHashCode extends HashCode implements Serializable {
269    final byte[] bytes;
270
271    BytesHashCode(byte[] bytes) {
272      this.bytes = checkNotNull(bytes);
273    }
274
275    @Override
276    public int bits() {
277      return bytes.length * 8;
278    }
279
280    @Override
281    public byte[] asBytes() {
282      return bytes.clone();
283    }
284
285    @Override
286    public int asInt() {
287      checkState(
288          bytes.length >= 4,
289          "HashCode#asInt() requires >= 4 bytes (it only has %s bytes).",
290          bytes.length);
291      return (bytes[0] & 0xFF)
292          | ((bytes[1] & 0xFF) << 8)
293          | ((bytes[2] & 0xFF) << 16)
294          | ((bytes[3] & 0xFF) << 24);
295    }
296
297    @Override
298    public long asLong() {
299      checkState(
300          bytes.length >= 8,
301          "HashCode#asLong() requires >= 8 bytes (it only has %s bytes).",
302          bytes.length);
303      return padToLong();
304    }
305
306    @Override
307    public long padToLong() {
308      long retVal = (bytes[0] & 0xFF);
309      for (int i = 1; i < Math.min(bytes.length, 8); i++) {
310        retVal |= (bytes[i] & 0xFFL) << (i * 8);
311      }
312      return retVal;
313    }
314
315    @Override
316    void writeBytesToImpl(byte[] dest, int offset, int maxLength) {
317      System.arraycopy(bytes, 0, dest, offset, maxLength);
318    }
319
320    @Override
321    byte[] getBytesInternal() {
322      return bytes;
323    }
324
325    @Override
326    boolean equalsSameBits(HashCode that) {
327      // We don't use MessageDigest.isEqual() here because its contract does not guarantee
328      // constant-time evaluation (no short-circuiting).
329      if (this.bytes.length != that.getBytesInternal().length) {
330        return false;
331      }
332
333      boolean areEqual = true;
334      for (int i = 0; i < this.bytes.length; i++) {
335        areEqual &= (this.bytes[i] == that.getBytesInternal()[i]);
336      }
337      return areEqual;
338    }
339
340    private static final long serialVersionUID = 0;
341  }
342
343  /**
344   * Creates a {@code HashCode} from a hexadecimal ({@code base 16}) encoded string. The string must
345   * be at least 2 characters long, and contain only valid, lower-cased hexadecimal characters.
346   *
347   * <p>This method accepts the exact format generated by {@link #toString}. If you require more
348   * lenient {@code base 16} decoding, please use
349   * {@link com.google.common.io.BaseEncoding#decode} (and pass the result to {@link #fromBytes}).
350   *
351   * @since 15.0
352   */
353  @CheckReturnValue
354  public static HashCode fromString(String string) {
355    checkArgument(
356        string.length() >= 2, "input string (%s) must have at least 2 characters", string);
357    checkArgument(
358        string.length() % 2 == 0,
359        "input string (%s) must have an even number of characters",
360        string);
361
362    byte[] bytes = new byte[string.length() / 2];
363    for (int i = 0; i < string.length(); i += 2) {
364      int ch1 = decode(string.charAt(i)) << 4;
365      int ch2 = decode(string.charAt(i + 1));
366      bytes[i / 2] = (byte) (ch1 + ch2);
367    }
368    return fromBytesNoCopy(bytes);
369  }
370
371  private static int decode(char ch) {
372    if (ch >= '0' && ch <= '9') {
373      return ch - '0';
374    }
375    if (ch >= 'a' && ch <= 'f') {
376      return ch - 'a' + 10;
377    }
378    throw new IllegalArgumentException("Illegal hexadecimal character: " + ch);
379  }
380
381  /**
382   * Returns {@code true} if {@code object} is a {@link HashCode} instance with the identical byte
383   * representation to this hash code.
384   *
385   * <p>Security note:</p> this method uses a constant-time (not short-circuiting) implementation
386   * to protect against <a href="http://en.wikipedia.org/wiki/Timing_attack">timing attacks</a>.
387   */
388  @Override
389  public final boolean equals(@Nullable Object object) {
390    if (object instanceof HashCode) {
391      HashCode that = (HashCode) object;
392      return bits() == that.bits() && equalsSameBits(that);
393    }
394    return false;
395  }
396
397  /**
398   * Returns a "Java hash code" for this {@code HashCode} instance; this is well-defined
399   * (so, for example, you can safely put {@code HashCode} instances into a {@code
400   * HashSet}) but is otherwise probably not what you want to use.
401   */
402  @Override
403  public final int hashCode() {
404    // If we have at least 4 bytes (32 bits), just take the first 4 bytes. Since this is
405    // already a (presumably) high-quality hash code, any four bytes of it will do.
406    if (bits() >= 32) {
407      return asInt();
408    }
409    // If we have less than 4 bytes, use them all.
410    byte[] bytes = getBytesInternal();
411    int val = (bytes[0] & 0xFF);
412    for (int i = 1; i < bytes.length; i++) {
413      val |= ((bytes[i] & 0xFF) << (i * 8));
414    }
415    return val;
416  }
417
418  /**
419   * Returns a string containing each byte of {@link #asBytes}, in order, as a two-digit unsigned
420   * hexadecimal number in lower case.
421   *
422   * <p>Note that if the output is considered to be a single hexadecimal number, this hash code's
423   * bytes are the <i>big-endian</i> representation of that number. This may be surprising since
424   * everything else in the hashing API uniformly treats multibyte values as little-endian. But
425   * this format conveniently matches that of utilities such as the UNIX {@code md5sum} command.
426   *
427   * <p>To create a {@code HashCode} from its string representation, see {@link #fromString}.
428   */
429  @Override
430  public final String toString() {
431    byte[] bytes = getBytesInternal();
432    StringBuilder sb = new StringBuilder(2 * bytes.length);
433    for (byte b : bytes) {
434      sb.append(hexDigits[(b >> 4) & 0xf]).append(hexDigits[b & 0xf]);
435    }
436    return sb.toString();
437  }
438
439  private static final char[] hexDigits = "0123456789abcdef".toCharArray();
440}