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
15package com.google.common.hash;
16
17import static com.google.common.base.Charsets.UTF_8;
18
19import com.google.common.collect.ImmutableSet;
20
21import junit.framework.TestCase;
22
23/**
24 * Unit tests for {@link SipHashFunction}.
25 *
26 * @author Kurt Alfred Kluever
27 */
28public class SipHashFunctionTest extends TestCase {
29
30  // From https://131002.net/siphash/siphash24.c
31  // k = 00 01 02 ...
32  private static final long K0 = 0x0706050403020100L;
33  private static final long K1 = 0x0f0e0d0c0b0a0908L;
34  private static final HashFunction SIP_WITH_KEY = Hashing.sipHash24(K0, K1);
35  private static final HashFunction SIP_WITHOUT_KEY = Hashing.sipHash24();
36
37  // These constants were originally ported from https://www.131002.net/siphash/siphash24.c. See:
38  // https://github.com/nahi/siphash-java-inline/blob/master/src/test/java/SipHashInlineTest.java
39  private static final long[] EXPECTED = new long[] {
40        0x726fdb47dd0e0e31L,
41        0x74f839c593dc67fdL,
42        0x0d6c8009d9a94f5aL,
43        0x85676696d7fb7e2dL,
44        0xcf2794e0277187b7L,
45        0x18765564cd99a68dL,
46        0xcbc9466e58fee3ceL,
47        0xab0200f58b01d137L,
48        0x93f5f5799a932462L,
49        0x9e0082df0ba9e4b0L,
50        0x7a5dbbc594ddb9f3L,
51        0xf4b32f46226bada7L,
52        0x751e8fbc860ee5fbL,
53        0x14ea5627c0843d90L,
54        0xf723ca908e7af2eeL,
55        0xa129ca6149be45e5L,
56        0x3f2acc7f57c29bdbL,
57        0x699ae9f52cbe4794L,
58        0x4bc1b3f0968dd39cL,
59        0xbb6dc91da77961bdL,
60        0xbed65cf21aa2ee98L,
61        0xd0f2cbb02e3b67c7L,
62        0x93536795e3a33e88L,
63        0xa80c038ccd5ccec8L,
64        0xb8ad50c6f649af94L,
65        0xbce192de8a85b8eaL,
66        0x17d835b85bbb15f3L,
67        0x2f2e6163076bcfadL,
68        0xde4daaaca71dc9a5L,
69        0xa6a2506687956571L,
70        0xad87a3535c49ef28L,
71        0x32d892fad841c342L,
72        0x7127512f72f27cceL,
73        0xa7f32346f95978e3L,
74        0x12e0b01abb051238L,
75        0x15e034d40fa197aeL,
76        0x314dffbe0815a3b4L,
77        0x027990f029623981L,
78        0xcadcd4e59ef40c4dL,
79        0x9abfd8766a33735cL,
80        0x0e3ea96b5304a7d0L,
81        0xad0c42d6fc585992L,
82        0x187306c89bc215a9L,
83        0xd4a60abcf3792b95L,
84        0xf935451de4f21df2L,
85        0xa9538f0419755787L,
86        0xdb9acddff56ca510L,
87        0xd06c98cd5c0975ebL,
88        0xe612a3cb9ecba951L,
89        0xc766e62cfcadaf96L,
90        0xee64435a9752fe72L,
91        0xa192d576b245165aL,
92        0x0a8787bf8ecb74b2L,
93        0x81b3e73d20b49b6fL,
94        0x7fa8220ba3b2eceaL,
95        0x245731c13ca42499L,
96        0xb78dbfaf3a8d83bdL,
97        0xea1ad565322a1a0bL,
98        0x60e61c23a3795013L,
99        0x6606d7e446282b93L,
100        0x6ca4ecb15c5f91e1L,
101        0x9f626da15c9625f3L,
102        0xe51b38608ef25f57L,
103        0x958a324ceb064572L
104  };
105
106  public void testVectors() {
107    for (int i = 0; i < EXPECTED.length; ++i) {
108      byte[] msg = new byte[i];
109      for (int j = 0; j < i; ++j) {
110        msg[j] = (byte) j;
111      }
112      assertSip(msg, EXPECTED[i]);
113    }
114  }
115
116  // This test data comes from "SipHash: a fast short-input PRF", "Appendix A: Test values".
117  // It can be downloaded here: https://131002.net/siphash/siphash.pdf
118  public void test15ByteStringFromSipHashPaper() {
119    byte[] message = new byte[] {
120        0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e };
121    long k0 = 0x0706050403020100L;
122    long k1 = 0x0f0e0d0c0b0a0908L;
123
124    assertEquals(0xa129ca6149be45e5L, Hashing.sipHash24(k0, k1).hashBytes(message).asLong());
125  }
126
127  // From https://github.com/BrandonHaynes/siphash-csharp/blob/master/tests/Tests.cs
128  public void testKnownValues() {
129    assertSip(new byte[] { }, 0x726fdb47dd0e0e31L);
130    assertSip(new byte[] { 0x61 }, 0x2ba3e8e9a71148caL);
131    assertSip(new byte[1000000], 0x28205108397aa742L);
132    assertSip("12345678", 0x02130609caea37ebL);
133    assertSip("abcdef", 0x2a6e77e733c7c05dL);
134    assertSip("SipHash", 0x8325093242a96f60L);
135  }
136
137  // Test for common pitfall regarding sign extension.
138  // For example: (long) data[i++] | (long) data[i++] << 8 | ...
139  // If data[i] == (byte) 0x80, the first cast will sign-extend it to 0xffffffffffffff80,
140  // masking the remaining seven bytes.
141  // To test this, we give an input where bit 7 is not cleared. For example:
142  // (1) 00 01 02 03 04 05 06 07 80
143  // (2) 00 01 02 03 04 05 06 07 81
144  // (3) 00 01 02 03 04 05 06 07 ff (or anything in between)
145  // A fault implementation will generate collisions for these inputs.
146  public void testCollisionsDueToIncorrectSignExtension() {
147    byte[] col1 = new byte[] { 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, (byte) 0x80 };
148    byte[] col2 = new byte[] { 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, (byte) 0x81 };
149    byte[] col3 = new byte[] { 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, (byte) 0xff };
150
151    ImmutableSet<HashCode> hashCodes = ImmutableSet.of(
152        SIP_WITH_KEY.hashBytes(col1),
153        SIP_WITH_KEY.hashBytes(col2),
154        SIP_WITH_KEY.hashBytes(col3));
155    assertEquals(3, hashCodes.size());
156  }
157
158  public void testToString() {
159    assertEquals("Hashing.sipHash24(" + K0 + ", " + K1 + ")", SIP_WITH_KEY.toString());
160    assertEquals("Hashing.sipHash24(" + K0 + ", " + K1 + ")", SIP_WITHOUT_KEY.toString());
161    assertEquals("Hashing.sipHash24(20, 13)", Hashing.sipHash24(20, 13).toString());
162  }
163
164  private static void assertSip(String input, long expected) {
165    assertEquals(expected, SIP_WITH_KEY.hashString(input, UTF_8).asLong());
166    assertEquals(expected, SIP_WITH_KEY.newHasher().putString(input, UTF_8).hash().asLong());
167    assertEquals(expected, SIP_WITHOUT_KEY.hashString(input, UTF_8).asLong());
168    assertEquals(expected, SIP_WITHOUT_KEY.newHasher().putString(input, UTF_8).hash().asLong());
169  }
170
171  private static void assertSip(byte[] input, long expected) {
172    assertEquals(expected, SIP_WITH_KEY.hashBytes(input).asLong());
173    assertEquals(expected, SIP_WITH_KEY.newHasher().putBytes(input).hash().asLong());
174    assertEquals(expected, SIP_WITHOUT_KEY.hashBytes(input).asLong());
175    assertEquals(expected, SIP_WITHOUT_KEY.newHasher().putBytes(input).hash().asLong());
176  }
177}
178