1 /* 2 * Copyright (C) 2012 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 /* 16 * SipHash-c-d was designed by Jean-Philippe Aumasson and Daniel J. Bernstein and is described in 17 * "SipHash: a fast short-input PRF" (available at https://131002.net/siphash/siphash.pdf). 18 */ 19 20 package com.google.common.hash; 21 22 import static com.google.common.base.Preconditions.checkArgument; 23 24 import java.io.Serializable; 25 import java.nio.ByteBuffer; 26 27 import javax.annotation.Nullable; 28 29 /** 30 * {@link HashFunction} implementation of SipHash-c-d. 31 * 32 * @author Kurt Alfred Kluever 33 * @author Jean-Philippe Aumasson 34 * @author Daniel J. Bernstein 35 */ 36 final class SipHashFunction extends AbstractStreamingHashFunction implements Serializable { 37 38 // The number of compression rounds. 39 private final int c; 40 // The number of finalization rounds. 41 private final int d; 42 // Two 64-bit keys (represent a single 128-bit key). 43 private final long k0; 44 private final long k1; 45 46 /** 47 * @param c the number of compression rounds (must be positive) 48 * @param d the number of finalization rounds (must be positive) 49 * @param k0 the first half of the key 50 * @param k1 the second half of the key 51 */ 52 SipHashFunction(int c, int d, long k0, long k1) { 53 checkArgument(c > 0, 54 "The number of SipRound iterations (c=%s) during Compression must be positive.", c); 55 checkArgument(d > 0, 56 "The number of SipRound iterations (d=%s) during Finalization must be positive.", d); 57 this.c = c; 58 this.d = d; 59 this.k0 = k0; 60 this.k1 = k1; 61 } 62 63 @Override public int bits() { 64 return 64; 65 } 66 67 @Override public Hasher newHasher() { 68 return new SipHasher(c, d, k0, k1); 69 } 70 71 // TODO(user): Implement and benchmark the hashFoo() shortcuts. 72 73 @Override public String toString() { 74 return "Hashing.sipHash" + c + "" + d + "(" + k0 + ", " + k1 + ")"; 75 } 76 77 @Override 78 public boolean equals(@Nullable Object object) { 79 if (object instanceof SipHashFunction) { 80 SipHashFunction other = (SipHashFunction) object; 81 return (c == other.c) 82 && (d == other.d) 83 && (k0 == other.k0) 84 && (k1 == other.k1); 85 } 86 return false; 87 } 88 89 @Override 90 public int hashCode() { 91 return (int) (getClass().hashCode() ^ c ^ d ^ k0 ^ k1); 92 } 93 94 private static final class SipHasher extends AbstractStreamingHasher { 95 private static final int CHUNK_SIZE = 8; 96 97 // The number of compression rounds. 98 private final int c; 99 // The number of finalization rounds. 100 private final int d; 101 102 // Four 64-bit words of internal state. 103 // The initial state corresponds to the ASCII string "somepseudorandomlygeneratedbytes", 104 // big-endian encoded. There is nothing special about this value; the only requirement 105 // was some asymmetry so that the initial v0 and v1 differ from v2 and v3. 106 private long v0 = 0x736f6d6570736575L; 107 private long v1 = 0x646f72616e646f6dL; 108 private long v2 = 0x6c7967656e657261L; 109 private long v3 = 0x7465646279746573L; 110 111 // The number of bytes in the input. 112 private long b = 0; 113 114 // The final 64-bit chunk includes the last 0 through 7 bytes of m followed by null bytes 115 // and ending with a byte encoding the positive integer b mod 256. 116 private long finalM = 0; 117 118 SipHasher(int c, int d, long k0, long k1) { 119 super(CHUNK_SIZE); 120 this.c = c; 121 this.d = d; 122 this.v0 ^= k0; 123 this.v1 ^= k1; 124 this.v2 ^= k0; 125 this.v3 ^= k1; 126 } 127 128 @Override protected void process(ByteBuffer buffer) { 129 b += CHUNK_SIZE; 130 processM(buffer.getLong()); 131 } 132 133 @Override protected void processRemaining(ByteBuffer buffer) { 134 b += buffer.remaining(); 135 for (int i = 0; buffer.hasRemaining(); i += 8) { 136 finalM ^= (buffer.get() & 0xFFL) << i; 137 } 138 } 139 140 @Override public HashCode makeHash() { 141 // End with a byte encoding the positive integer b mod 256. 142 finalM ^= b << 56; 143 processM(finalM); 144 145 // Finalization 146 v2 ^= 0xFFL; 147 sipRound(d); 148 return HashCode.fromLong(v0 ^ v1 ^ v2 ^ v3); 149 } 150 151 private void processM(long m) { 152 v3 ^= m; 153 sipRound(c); 154 v0 ^= m; 155 } 156 157 private void sipRound(int iterations) { 158 for (int i = 0; i < iterations; i++) { 159 v0 += v1; 160 v2 += v3; 161 v1 = Long.rotateLeft(v1, 13); 162 v3 = Long.rotateLeft(v3, 16); 163 v1 ^= v0; 164 v3 ^= v2; 165 v0 = Long.rotateLeft(v0, 32); 166 v2 += v1; 167 v0 += v3; 168 v1 = Long.rotateLeft(v1, 17); 169 v3 = Long.rotateLeft(v3, 21); 170 v1 ^= v2; 171 v3 ^= v0; 172 v2 = Long.rotateLeft(v2, 32); 173 } 174 } 175 } 176 177 private static final long serialVersionUID = 0L; 178 } 179
