Coverage Summary for Class: SipHashFunction (com.google.common.hash)

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