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;
025import com.google.errorprone.annotations.CanIgnoreReturnValue;
026import java.io.Serializable;
027import javax.annotation.Nullable;
028
029/**
030 * An immutable hash code of arbitrary bit length.
031 *
032 * @author Dimitris Andreou
033 * @author Kurt Alfred Kluever
034 * @since 11.0
035 */
036@Beta
037public abstract class HashCode {
038  HashCode() {}
039
040  /**
041   * Returns the number of bits in this hash code; a positive multiple of 8.
042   */
043  public abstract int bits();
044
045  /**
046   * Returns the first four bytes of {@linkplain #asBytes() this hashcode's bytes}, converted to an
047   * {@code int} value in little-endian order.
048   *
049   * @throws IllegalStateException if {@code bits() < 32}
050   */
051  public abstract int asInt();
052
053  /**
054   * Returns the first eight bytes of {@linkplain #asBytes() this hashcode's bytes}, converted to a
055   * {@code long} value in little-endian order.
056   *
057   * @throws IllegalStateException if {@code bits() < 64}
058   */
059  public abstract long asLong();
060
061  /**
062   * If this hashcode has enough bits, returns {@code asLong()}, otherwise returns a {@code long}
063   * value with {@code asBytes()} as the least-significant bytes and {@code 0x00} as the remaining
064   * most-significant bytes.
065   *
066   * @since 14.0 (since 11.0 as {@code Hashing.padToLong(HashCode)})
067   */
068  public abstract long padToLong();
069
070  /**
071   * Returns the value of this hash code as a byte array. The caller may modify the byte array;
072   * changes to it will <i>not</i> be reflected in this {@code HashCode} object or any other arrays
073   * returned by this method.
074   */
075  // TODO(user): consider ByteString here, when that is available
076  public abstract byte[] asBytes();
077
078  /**
079   * Copies bytes from this hash code into {@code dest}.
080   *
081   * @param dest the byte array into which the hash code will be written
082   * @param offset the start offset in the data
083   * @param maxLength the maximum number of bytes to write
084   * @return the number of bytes written to {@code dest}
085   * @throws IndexOutOfBoundsException if there is not enough room in {@code dest}
086   */
087  @CanIgnoreReturnValue
088  public int writeBytesTo(byte[] dest, int offset, int maxLength) {
089    maxLength = Ints.min(maxLength, bits() / 8);
090    Preconditions.checkPositionIndexes(offset, offset + maxLength, dest.length);
091    writeBytesToImpl(dest, offset, maxLength);
092    return maxLength;
093  }
094
095  abstract void writeBytesToImpl(byte[] dest, int offset, int maxLength);
096
097  /**
098   * Returns a mutable view of the underlying bytes for the given {@code HashCode} if it is a
099   * 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}