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 package com.google.common.hash; 16 17 import static com.google.common.base.Charsets.UTF_8; 18 19 import com.google.common.collect.ImmutableSet; 20 21 import junit.framework.TestCase; 22 23 /** 24 * Unit tests for {@link SipHashFunction}. 25 * 26 * @author Kurt Alfred Kluever 27 */ 28 public 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 testVectors()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 test15ByteStringFromSipHashPaper()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 testKnownValues()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. testCollisionsDueToIncorrectSignExtension()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 testToString()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 assertSip(String input, long expected)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 assertSip(byte[] input, long expected)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