diff options
Diffstat (limited to 'guava-tests/test/com/google/common/hash')
14 files changed, 308 insertions, 1575 deletions
diff --git a/guava-tests/test/com/google/common/hash/AbstractByteHasherTest.java b/guava-tests/test/com/google/common/hash/AbstractByteHasherTest.java deleted file mode 100644 index 53a55a5..0000000 --- a/guava-tests/test/com/google/common/hash/AbstractByteHasherTest.java +++ /dev/null @@ -1,140 +0,0 @@ -/* - * Copyright (C) 2012 The Guava Authors - * - * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except - * in compliance with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software distributed under the License - * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express - * or implied. See the License for the specific language governing permissions and limitations under - * the License. - */ - -package com.google.common.hash; - -import static com.google.common.base.Charsets.UTF_16LE; -import static org.junit.Assert.assertArrayEquals; - -import junit.framework.TestCase; - -import java.io.ByteArrayOutputStream; -import java.util.Random; - -/** - * Tests for AbstractByteHasher. - * - * @author Colin Decker - */ -public class AbstractByteHasherTest extends TestCase { - - public void testBytes() { - TestHasher hasher = new TestHasher(); // byte order insignificant here - byte[] expected = {1, 2, 3, 4, 5, 6, 7, 8}; - hasher.putByte((byte) 1); - hasher.putBytes(new byte[]{2, 3, 4, 5, 6}); - hasher.putByte((byte) 7); - hasher.putBytes(new byte[]{}); - hasher.putBytes(new byte[]{8}); - hasher.assertBytes(expected); - } - - public void testShort() { - TestHasher hasher = new TestHasher(); - hasher.putShort((short) 0x0201); - hasher.assertBytes(new byte[]{1, 2}); - } - - public void testInt() { - TestHasher hasher = new TestHasher(); - hasher.putInt(0x04030201); - hasher.assertBytes(new byte[]{1, 2, 3, 4}); - } - - public void testLong() { - TestHasher hasher = new TestHasher(); - hasher.putLong(0x0807060504030201L); - hasher.assertBytes(new byte[]{1, 2, 3, 4, 5, 6, 7, 8}); - } - - public void testChar() { - TestHasher hasher = new TestHasher(); - hasher.putChar((char) 0x0201); - hasher.assertBytes(new byte[]{1, 2}); - } - - public void testString() { - Random random = new Random(); - for (int i = 0; i < 100; i++) { - byte[] bytes = new byte[64]; - random.nextBytes(bytes); - String s = new String(bytes, UTF_16LE); // so all random strings are valid - assertEquals( - new TestHasher().putString(s).hash(), - new TestHasher().putBytes(s.getBytes(UTF_16LE)).hash()); - assertEquals( - new TestHasher().putString(s).hash(), - new TestHasher().putString(s, UTF_16LE).hash()); - } - } - - public void testFloat() { - TestHasher hasher = new TestHasher(); - hasher.putFloat(Float.intBitsToFloat(0x04030201)); - hasher.assertBytes(new byte[]{1, 2, 3, 4}); - } - - public void testDouble() { - TestHasher hasher = new TestHasher(); - hasher.putDouble(Double.longBitsToDouble(0x0807060504030201L)); - hasher.assertBytes(new byte[]{1, 2, 3, 4, 5, 6, 7, 8}); - } - - public void testCorrectExceptions() { - TestHasher hasher = new TestHasher(); - try { - hasher.putBytes(new byte[8], -1, 4); - fail(); - } catch (IndexOutOfBoundsException expected) { - } - try { - hasher.putBytes(new byte[8], 0, 16); - fail(); - } catch (IndexOutOfBoundsException expected) { - } - try { - hasher.putBytes(new byte[8], 0, -1); - fail(); - } catch (IndexOutOfBoundsException expected) { - } - } - - private class TestHasher extends AbstractByteHasher { - - private final ByteArrayOutputStream out = new ByteArrayOutputStream(); - - @Override - protected void update(byte b) { - out.write(b); - } - - @Override - protected void update(byte[] b, int off, int len) { - out.write(b, off, len); - } - - byte[] bytes() { - return out.toByteArray(); - } - - void assertBytes(byte[] expected) { - assertArrayEquals(expected, bytes()); - } - - @Override - public HashCode hash() { - return HashCodes.fromBytesNoCopy(bytes()); - } - } -} diff --git a/guava-tests/test/com/google/common/hash/AbstractNonStreamingHashFunctionTest.java b/guava-tests/test/com/google/common/hash/AbstractNonStreamingHashFunctionTest.java index 2cec063..b4edf42 100644 --- a/guava-tests/test/com/google/common/hash/AbstractNonStreamingHashFunctionTest.java +++ b/guava-tests/test/com/google/common/hash/AbstractNonStreamingHashFunctionTest.java @@ -1,18 +1,4 @@ -/* - * Copyright (C) 2011 The Guava Authors - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ +// Copyright 2011 Google Inc. All Rights Reserved. package com.google.common.hash; @@ -36,8 +22,8 @@ public class AbstractNonStreamingHashFunctionTest extends TestCase { * Constructs two trivial HashFunctions (output := input), one streaming and one non-streaming, * and checks that their results are identical, no matter which newHasher version we used. */ - public void testExhaustive() { - List<Hasher> hashers = ImmutableList.of( + public void test() { + List<Hasher> hashers = ImmutableList.of( new StreamingVersion().newHasher(), new StreamingVersion().newHasher(52), new NonStreamingVersion().newHasher(), @@ -54,43 +40,7 @@ public class AbstractNonStreamingHashFunctionTest extends TestCase { assertEquals(codes[i - 1], codes[i]); } } - - public void testPutStringWithLowSurrogate() { - // we pad because the dummy hash function we use to test this, merely copies the input into - // the output, so the input must be at least 32 bits, since the output has to be that long - assertPutString(new char[] { 'p', HashTestUtils.randomLowSurrogate(new Random()) }); - } - - public void testPutStringWithHighSurrogate() { - // we pad because the dummy hash function we use to test this, merely copies the input into - // the output, so the input must be at least 32 bits, since the output has to be that long - assertPutString(new char[] { 'p', HashTestUtils.randomHighSurrogate(new Random()) }); - } - - public void testPutStringWithLowHighSurrogate() { - assertPutString(new char[] { - HashTestUtils.randomLowSurrogate(new Random()), - HashTestUtils.randomHighSurrogate(new Random()) }); - } - - public void testPutStringWithHighLowSurrogate() { - assertPutString(new char[] { - HashTestUtils.randomHighSurrogate(new Random()), - HashTestUtils.randomLowSurrogate(new Random()) }); - } - - private static void assertPutString(char[] chars) { - Hasher h1 = new NonStreamingVersion().newHasher(); - Hasher h2 = new NonStreamingVersion().newHasher(); - String s = new String(chars); - // this is the correct implementation of the spec - for (int i = 0; i < s.length(); i++) { - h1.putChar(s.charAt(i)); - } - h2.putString(s); - assertEquals(h1.hash(), h2.hash()); - } - + static class StreamingVersion extends AbstractStreamingHashFunction { @Override public int bits() { @@ -122,7 +72,7 @@ public class AbstractNonStreamingHashFunctionTest extends TestCase { }; } } - + static class NonStreamingVersion extends AbstractNonStreamingHashFunction { @Override public int bits() { @@ -138,12 +88,12 @@ public class AbstractNonStreamingHashFunctionTest extends TestCase { public HashCode hashBytes(byte[] input, int off, int len) { return HashCodes.fromBytes(Arrays.copyOfRange(input, off, off + len)); } - + @Override public HashCode hashString(CharSequence input) { throw new UnsupportedOperationException(); } - + @Override public HashCode hashString(CharSequence input, Charset charset) { throw new UnsupportedOperationException(); @@ -153,10 +103,5 @@ public class AbstractNonStreamingHashFunctionTest extends TestCase { public HashCode hashLong(long input) { throw new UnsupportedOperationException(); } - - @Override - public HashCode hashInt(int input) { - throw new UnsupportedOperationException(); - } } } diff --git a/guava-tests/test/com/google/common/hash/AbstractStreamingHasherTest.java b/guava-tests/test/com/google/common/hash/AbstractStreamingHasherTest.java index 7324e6f..8f1cbb4 100644 --- a/guava-tests/test/com/google/common/hash/AbstractStreamingHasherTest.java +++ b/guava-tests/test/com/google/common/hash/AbstractStreamingHasherTest.java @@ -1,23 +1,7 @@ -/* - * Copyright (C) 2011 The Guava Authors - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ +// Copyright 2011 Google Inc. All Rights Reserved. package com.google.common.hash; -import static com.google.common.base.Charsets.UTF_16LE; - import com.google.common.collect.Iterables; import com.google.common.collect.Lists; import com.google.common.hash.AbstractStreamingHashFunction.AbstractStreamingHasher; @@ -35,24 +19,30 @@ import java.util.List; import java.util.Random; /** - * Tests for AbstractStreamingHasher. - * - * @author Dimitris Andreou + * Tests for AbstractHashSink. + * + * @author andreou@google.com (Dimitris Andreou) */ public class AbstractStreamingHasherTest extends TestCase { + /** Test we get the HashCode that is created by the sink. Later we ignore the result */ + public void testSanity() { + Sink sink = new Sink(4); + assertEquals(0xDeadBeef, sink.makeHash().asInt()); + } + public void testBytes() { Sink sink = new Sink(4); // byte order insignificant here byte[] expected = { 1, 2, 3, 4, 5, 6, 7, 8 }; sink.putByte((byte) 1); sink.putBytes(new byte[] { 2, 3, 4, 5, 6 }); sink.putByte((byte) 7); - sink.putBytes(new byte[] {}); + sink.putBytes(new byte[] { }); sink.putBytes(new byte[] { 8 }); sink.hash(); sink.assertInvariants(8); sink.assertBytes(expected); } - + public void testShort() { Sink sink = new Sink(4); sink.putShort((short) 0x0201); @@ -60,7 +50,7 @@ public class AbstractStreamingHasherTest extends TestCase { sink.assertInvariants(2); sink.assertBytes(new byte[] { 1, 2, 0, 0 }); // padded with zeros } - + public void testInt() { Sink sink = new Sink(4); sink.putInt(0x04030201); @@ -68,7 +58,7 @@ public class AbstractStreamingHasherTest extends TestCase { sink.assertInvariants(4); sink.assertBytes(new byte[] { 1, 2, 3, 4 }); } - + public void testLong() { Sink sink = new Sink(8); sink.putLong(0x0807060504030201L); @@ -76,7 +66,7 @@ public class AbstractStreamingHasherTest extends TestCase { sink.assertInvariants(8); sink.assertBytes(new byte[] { 1, 2, 3, 4, 5, 6, 7, 8 }); } - + public void testChar() { Sink sink = new Sink(4); sink.putChar((char) 0x0201); @@ -84,22 +74,7 @@ public class AbstractStreamingHasherTest extends TestCase { sink.assertInvariants(2); sink.assertBytes(new byte[] { 1, 2, 0, 0 }); // padded with zeros } - - public void testString() { - Random random = new Random(); - for (int i = 0; i < 100; i++) { - byte[] bytes = new byte[64]; - random.nextBytes(bytes); - String s = new String(bytes, UTF_16LE); // so all random strings are valid - assertEquals( - new Sink(4).putString(s).hash(), - new Sink(4).putBytes(s.getBytes(UTF_16LE)).hash()); - assertEquals( - new Sink(4).putString(s).hash(), - new Sink(4).putString(s, UTF_16LE).hash()); - } - } - + public void testFloat() { Sink sink = new Sink(4); sink.putFloat(Float.intBitsToFloat(0x04030201)); @@ -107,7 +82,7 @@ public class AbstractStreamingHasherTest extends TestCase { sink.assertInvariants(4); sink.assertBytes(new byte[] { 1, 2, 3, 4 }); } - + public void testDouble() { Sink sink = new Sink(8); sink.putDouble(Double.longBitsToDouble(0x0807060504030201L)); @@ -115,7 +90,7 @@ public class AbstractStreamingHasherTest extends TestCase { sink.assertInvariants(8); sink.assertBytes(new byte[] { 1, 2, 3, 4, 5, 6, 7, 8 }); } - + public void testCorrectExceptions() { Sink sink = new Sink(4); try { @@ -131,16 +106,16 @@ public class AbstractStreamingHasherTest extends TestCase { fail(); } catch (IndexOutOfBoundsException ok) {} } - + /** * This test creates a long random sequence of inputs, then a lot of differently configured * sinks process it; all should produce the same answer, the only difference should be the - * number of process()/processRemaining() invocations, due to alignment. + * number of process()/processRemaining() invocations, due to alignment. */ public void testExhaustive() throws Exception { Random random = new Random(0); // will iteratively make more debuggable, each time it breaks for (int totalInsertions = 0; totalInsertions < 200; totalInsertions++) { - + List<Sink> sinks = Lists.newArrayList(); for (int chunkSize = 4; chunkSize <= 32; chunkSize++) { for (int bufferSize = chunkSize; bufferSize <= chunkSize * 4; bufferSize += chunkSize) { @@ -148,28 +123,22 @@ public class AbstractStreamingHasherTest extends TestCase { sinks.add(new Sink(chunkSize, bufferSize)); // For convenience, testing only with big endianness, to match DataOutputStream. // I regard highly unlikely that both the little endianness tests above and this one - // passes, and there is still a little endianness bug lurking around. + // passes, and there is still a little endianness bug lurking around. } } - + Control control = new Control(); Hasher controlSink = control.newHasher(1024); - - Iterable<Hasher> sinksAndControl = - Iterables.concat(sinks, Collections.singleton(controlSink)); + + Iterable<Hasher> sinksAndControl = Iterables.concat( + sinks, Collections.singleton(controlSink)); for (int insertion = 0; insertion < totalInsertions; insertion++) { - RandomHasherAction.pickAtRandom(random).performAction(random, sinksAndControl); - } - // We need to ensure that at least 4 bytes have been put into the hasher or else - // Hasher#hash will throw an ISE. - int intToPut = random.nextInt(); - for (Hasher hasher : sinksAndControl) { - hasher.putInt(intToPut); + RandomHasherAction.pickAtRandom(random).performAction(random, sinksAndControl); } for (Sink sink : sinks) { sink.hash(); } - + byte[] expected = controlSink.hash().asBytes(); for (Sink sink : sinks) { sink.assertInvariants(expected.length); @@ -177,15 +146,15 @@ public class AbstractStreamingHasherTest extends TestCase { } } } - + private static class Sink extends AbstractStreamingHasher { final int chunkSize; final int bufferSize; final ByteArrayOutputStream out = new ByteArrayOutputStream(); - + int processCalled = 0; boolean remainingCalled = false; - + Sink(int chunkSize, int bufferSize) { super(chunkSize, bufferSize); this.chunkSize = chunkSize; @@ -199,7 +168,7 @@ public class AbstractStreamingHasherTest extends TestCase { } @Override HashCode makeHash() { - return HashCodes.fromBytes(out.toByteArray()); + return HashCodes.fromInt(0xDeadBeef); } @Override protected void process(ByteBuffer bb) { @@ -210,7 +179,7 @@ public class AbstractStreamingHasherTest extends TestCase { out.write(bb.get()); } } - + @Override protected void processRemaining(ByteBuffer bb) { assertFalse(remainingCalled); remainingCalled = true; @@ -223,21 +192,21 @@ public class AbstractStreamingHasherTest extends TestCase { assertEquals(before + 1, after); // default implementation pads and calls process() processCalled--; // don't count the tail invocation (makes tests a bit more understandable) } - + // ensures that the number of invocations looks sane void assertInvariants(int expectedBytes) { - // we should have seen as many bytes as the next multiple of chunk after expectedBytes - 1 + // we should have seen as many bytes as the next multiple of chunk after expectedBytes - 1 assertEquals(out.toByteArray().length, ceilToMultiple(expectedBytes, chunkSize)); assertEquals(expectedBytes / chunkSize, processCalled); assertEquals(expectedBytes % chunkSize != 0, remainingCalled); } - + // returns the minimum x such as x >= a && (x % b) == 0 private static int ceilToMultiple(int a, int b) { int remainder = a % b; return remainder == 0 ? a : a + b - remainder; } - + void assertBytes(byte[] expected) { byte[] got = out.toByteArray(); for (int i = 0; i < expected.length; i++) { @@ -245,14 +214,13 @@ public class AbstractStreamingHasherTest extends TestCase { } } } - - // Assumes that AbstractNonStreamingHashFunction works properly (must be tested elsewhere!) + private static class Control extends AbstractNonStreamingHashFunction { @Override public HashCode hashBytes(byte[] input) { return HashCodes.fromBytes(input); } - + @Override public HashCode hashBytes(byte[] input, int off, int len) { return hashBytes(Arrays.copyOfRange(input, off, off + len)); @@ -277,10 +245,5 @@ public class AbstractStreamingHasherTest extends TestCase { public HashCode hashLong(long input) { throw new UnsupportedOperationException(); } - - @Override - public HashCode hashInt(int input) { - throw new UnsupportedOperationException(); - } } } diff --git a/guava-tests/test/com/google/common/hash/BloomFilterTest.java b/guava-tests/test/com/google/common/hash/BloomFilterTest.java index d9056f6..26b7641 100644 --- a/guava-tests/test/com/google/common/hash/BloomFilterTest.java +++ b/guava-tests/test/com/google/common/hash/BloomFilterTest.java @@ -1,79 +1,20 @@ -/* - * Copyright (C) 2011 The Guava Authors - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ +// Copyright 2011 Google Inc. All Rights Reserved. package com.google.common.hash; -import com.google.common.collect.ImmutableSet; import com.google.common.primitives.Ints; -import com.google.common.testing.EqualsTester; -import com.google.common.testing.NullPointerTester; import com.google.common.testing.SerializableTester; import junit.framework.TestCase; import java.util.Random; -import javax.annotation.Nullable; - /** * Tests for SimpleGenericBloomFilter and derived BloomFilter views. - * - * @author Dimitris Andreou + * + * @author andreou@google.com (Dimitris Andreou) */ public class BloomFilterTest extends TestCase { - - public void testCreateAndCheckBloomFilterWithKnownFalsePositives() { - int numInsertions = 1000000; - BloomFilter<CharSequence> bf = BloomFilter.create(Funnels.stringFunnel(), numInsertions); - - // Insert "numInsertions" even numbers into the BF. - for (int i = 0; i < numInsertions * 2; i += 2) { - bf.put(Integer.toString(i)); - } - - // Assert that the BF "might" have all of the even numbers. - for (int i = 0; i < numInsertions * 2; i += 2) { - assertTrue(bf.mightContain(Integer.toString(i))); - } - - // Now we check for known false positives using a set of known false positives. - // (These are all of the false positives under 900.) - ImmutableSet<Integer> falsePositives = ImmutableSet.of( - 49, 51, 59, 163, 199, 321, 325, 363, 367, 469, 545, 561, 727, 769, 773, 781); - for (int i = 1; i < 900; i += 2) { - if (!falsePositives.contains(i)) { - assertFalse("BF should not contain " + i, bf.mightContain(Integer.toString(i))); - } - } - - // Check that there are exactly 29824 false positives for this BF. - int knownNumberOfFalsePositives = 29824; - int numFpp = 0; - for (int i = 1; i < numInsertions * 2; i += 2) { - if (bf.mightContain(Integer.toString(i))) { - numFpp++; - } - } - assertEquals(knownNumberOfFalsePositives, numFpp); - double actualFpp = (double) knownNumberOfFalsePositives / numInsertions; - double expectedFpp = bf.expectedFpp(); - // The normal order of (expected, actual) is reversed here on purpose. - assertEquals(actualFpp, expectedFpp, 0.00015); - } - /** * Sanity checking with many combinations of false positive rates and expected insertions */ @@ -84,43 +25,9 @@ public class BloomFilterTest extends TestCase { } } } - - public void testPreconditions() { - try { - BloomFilter.create(Funnels.stringFunnel(), -1); - fail(); - } catch (IllegalArgumentException expected) {} - try { - BloomFilter.create(Funnels.stringFunnel(), -1, 0.03); - fail(); - } catch (IllegalArgumentException expected) {} - try { - BloomFilter.create(Funnels.stringFunnel(), 1, 0.0); - fail(); - } catch (IllegalArgumentException expected) {} - try { - BloomFilter.create(Funnels.stringFunnel(), 1, 1.0); - fail(); - } catch (IllegalArgumentException expected) {} - } - - public void testFailureWhenMoreThan255HashFunctionsAreNeeded() { - try { - int n = 1000; - double p = 0.00000000000000000000000000000000000000000000000000000000000000000000000000000001; - BloomFilter.create(Funnels.stringFunnel(), n, p); - fail(); - } catch (IllegalArgumentException expected) {} - } - - public void testNullPointers() { - NullPointerTester tester = new NullPointerTester(); - tester.testAllPublicInstanceMethods(BloomFilter.create(Funnels.stringFunnel(), 100)); - tester.testAllPublicStaticMethods(BloomFilter.class); - } - + /** - * Tests that we never get an optimal hashes number of zero. + * Tests that we never get an optimal hashes number of zero. */ public void testOptimalHashes() { for (int n = 1; n < 1000; n++) { @@ -129,9 +36,9 @@ public class BloomFilterTest extends TestCase { } } } - + /** - * Tests that we always get a non-negative optimal size. + * Tests that we always get a non-negative optimal size. */ public void testOptimalSize() { for (int n = 1; n < 1000; n++) { @@ -139,148 +46,36 @@ public class BloomFilterTest extends TestCase { assertTrue(BloomFilter.optimalNumOfBits(n, fpp) >= 0); } } - + // some random values - Random random = new Random(0); + Random random = new Random(0); for (int repeats = 0; repeats < 10000; repeats++) { assertTrue(BloomFilter.optimalNumOfBits(random.nextInt(1 << 16), random.nextDouble()) >= 0); } - - // and some crazy values (this used to be capped to Integer.MAX_VALUE, now it can go bigger - assertEquals(3327428144502L, BloomFilter.optimalNumOfBits( + + // and some crazy values + assertEquals(Integer.MAX_VALUE, BloomFilter.optimalNumOfBits( Integer.MAX_VALUE, Double.MIN_VALUE)); - try { - BloomFilter.create(HashTestUtils.BAD_FUNNEL, Integer.MAX_VALUE, Double.MIN_VALUE); - fail("we can't represent such a large BF!"); - } catch (IllegalArgumentException expected) { - assertEquals("Could not create BloomFilter of 3327428144502 bits", expected.getMessage()); - } } - + private void checkSanity(BloomFilter<Object> bf) { assertFalse(bf.mightContain(new Object())); - assertFalse(bf.apply(new Object())); for (int i = 0; i < 100; i++) { Object o = new Object(); bf.put(o); assertTrue(bf.mightContain(o)); - assertTrue(bf.apply(o)); } } - - public void testCopy() { - BloomFilter<CharSequence> original = BloomFilter.create(Funnels.stringFunnel(), 100); - BloomFilter<CharSequence> copy = original.copy(); - assertNotSame(original, copy); - assertEquals(original, copy); - } - - public void testExpectedFpp() { - BloomFilter<Object> bf = BloomFilter.create(HashTestUtils.BAD_FUNNEL, 10, 0.03); - double fpp = bf.expectedFpp(); - assertEquals(0.0, fpp); - // usually completed in less than 200 iterations - while (fpp != 1.0) { - boolean changed = bf.put(new Object()); - double newFpp = bf.expectedFpp(); - // if changed, the new fpp is strictly higher, otherwise it is the same - assertTrue(changed ? newFpp > fpp : newFpp == fpp); - fpp = newFpp; - } - } - - public void testEquals_empty() { - new EqualsTester() - .addEqualityGroup(BloomFilter.create(Funnels.byteArrayFunnel(), 100, 0.01)) - .addEqualityGroup(BloomFilter.create(Funnels.byteArrayFunnel(), 100, 0.02)) - .addEqualityGroup(BloomFilter.create(Funnels.byteArrayFunnel(), 200, 0.01)) - .addEqualityGroup(BloomFilter.create(Funnels.byteArrayFunnel(), 200, 0.02)) - .addEqualityGroup(BloomFilter.create(Funnels.stringFunnel(), 100, 0.01)) - .addEqualityGroup(BloomFilter.create(Funnels.stringFunnel(), 100, 0.02)) - .addEqualityGroup(BloomFilter.create(Funnels.stringFunnel(), 200, 0.01)) - .addEqualityGroup(BloomFilter.create(Funnels.stringFunnel(), 200, 0.02)) - .testEquals(); - } - - public void testEquals() { - BloomFilter<CharSequence> bf1 = BloomFilter.create(Funnels.stringFunnel(), 100); - bf1.put("1"); - bf1.put("2"); - - BloomFilter<CharSequence> bf2 = BloomFilter.create(Funnels.stringFunnel(), 100); - bf2.put("1"); - bf2.put("2"); - - new EqualsTester() - .addEqualityGroup(bf1, bf2) - .testEquals(); - - bf2.put("3"); - - new EqualsTester() - .addEqualityGroup(bf1) - .addEqualityGroup(bf2) - .testEquals(); - } - - public void testEqualsWithCustomFunnel() { - BloomFilter<Long> bf1 = BloomFilter.create(new CustomFunnel(), 100); - BloomFilter<Long> bf2 = BloomFilter.create(new CustomFunnel(), 100); - assertEquals(bf1, bf2); - } - - public void testSerializationWithCustomFunnel() { - SerializableTester.reserializeAndAssert(BloomFilter.create(new CustomFunnel(), 100)); - } - - private static final class CustomFunnel implements Funnel<Long> { - @Override - public void funnel(Long value, PrimitiveSink into) { - into.putLong(value); - } - @Override - public boolean equals(@Nullable Object object) { - return (object instanceof CustomFunnel); - } - @Override - public int hashCode() { - return 42; - } - } - - public void testPutReturnValue() { - for (int i = 0; i < 10; i++) { - BloomFilter<CharSequence> bf = BloomFilter.create(Funnels.stringFunnel(), 100); - for (int j = 0; j < 10; j++) { - String value = new Object().toString(); - boolean mightContain = bf.mightContain(value); - boolean put = bf.put(value); - assertTrue(mightContain != put); - } - } - } - - public void testJavaSerialization() { + + public void testSerialization() { BloomFilter<byte[]> bf = BloomFilter.create(Funnels.byteArrayFunnel(), 100); for (int i = 0; i < 10; i++) { bf.put(Ints.toByteArray(i)); } - - BloomFilter<byte[]> copy = SerializableTester.reserialize(bf); + + bf = SerializableTester.reserialize(bf); for (int i = 0; i < 10; i++) { - assertTrue(copy.mightContain(Ints.toByteArray(i))); + assertTrue(bf.mightContain(Ints.toByteArray(i))); } - assertEquals(bf.expectedFpp(), copy.expectedFpp()); - - SerializableTester.reserializeAndAssert(bf); - } - - /** - * This test will fail whenever someone updates/reorders the BloomFilterStrategies constants. - * Only appending a new constant is allowed. - */ - public void testBloomFilterStrategies() { - assertEquals(1, BloomFilterStrategies.values().length); - assertEquals(BloomFilterStrategies.MURMUR128_MITZ_32, BloomFilterStrategies.values()[0]); } } diff --git a/guava-tests/test/com/google/common/hash/ChecksumHashFunctionTest.java b/guava-tests/test/com/google/common/hash/ChecksumHashFunctionTest.java deleted file mode 100644 index 5b29c46..0000000 --- a/guava-tests/test/com/google/common/hash/ChecksumHashFunctionTest.java +++ /dev/null @@ -1,87 +0,0 @@ -/* - * Copyright (C) 2012 The Guava Authors - * - * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except - * in compliance with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software distributed under the License - * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express - * or implied. See the License for the specific language governing permissions and limitations under - * the License. - */ - -package com.google.common.hash; - -import static com.google.common.hash.Hashing.ChecksumType.ADLER_32; -import static com.google.common.hash.Hashing.ChecksumType.CRC_32; - -import com.google.common.base.Supplier; - -import junit.framework.TestCase; - -import java.util.zip.Checksum; - -/** - * Tests for ChecksumHashFunction. - * - * @author Colin Decker - */ -public class ChecksumHashFunctionTest extends TestCase { - - public void testCrc32_equalsChecksumValue() throws Exception { - assertChecksum(CRC_32, ""); - assertChecksum(CRC_32, "Z"); - assertChecksum(CRC_32, "foobar"); - } - - public void testAdler32_equalsChecksumValue() throws Exception { - assertChecksum(ADLER_32, ""); - assertChecksum(ADLER_32, "Z"); - assertChecksum(ADLER_32, "foobar"); - } - - public void testCrc32_knownValues() throws Exception { - assertHash32(0x1C8600E3, CRC_32, "hell"); - assertHash32(0x3610A686, CRC_32, "hello"); - assertHash32(0xED81F9F6, CRC_32, "hello "); - assertHash32(0x4850DDC2, CRC_32, "hello w"); - assertHash32(0x7A2D6005, CRC_32, "hello wo"); - assertHash32(0x1C192672, CRC_32, "hello wor"); - assertHash32(0x414FA339, CRC_32, "The quick brown fox jumps over the lazy dog"); - assertHash32(0x4400B5BC, CRC_32, "The quick brown fox jumps over the lazy cog"); - } - - public void testAdler32_knownValues() throws Exception { - assertHash32(0x041701A6, ADLER_32, "hell"); - assertHash32(0x062C0215, ADLER_32, "hello"); - assertHash32(0x08610235, ADLER_32, "hello "); - assertHash32(0x0B0D02AC, ADLER_32, "hello w"); - assertHash32(0x0E28031B, ADLER_32, "hello wo"); - assertHash32(0x11B5038D, ADLER_32, "hello wor"); - assertHash32(0x5BDC0FDA, ADLER_32, "The quick brown fox jumps over the lazy dog"); - assertHash32(0x5BD90FD9, ADLER_32, "The quick brown fox jumps over the lazy cog"); - } - - private static void assertChecksum(Supplier<Checksum> supplier, String input) { - byte[] bytes = HashTestUtils.ascii(input); - - Checksum checksum = supplier.get(); - checksum.update(bytes, 0, bytes.length); - long value = checksum.getValue(); - - String toString = "name"; - HashFunction func = new ChecksumHashFunction(supplier, 32, toString); - assertEquals(toString, func.toString()); - assertEquals(value, func.hashBytes(bytes).padToLong()); - } - - private static void assertHash32(int expected, Supplier<Checksum> supplier, String input) { - byte[] bytes = HashTestUtils.ascii(input); - String toString = "name"; - HashFunction func = new ChecksumHashFunction(supplier, 32, toString); - assertEquals(expected, func.hashBytes(bytes).asInt()); - assertEquals(toString, func.toString()); - } -} diff --git a/guava-tests/test/com/google/common/hash/FunnelsTest.java b/guava-tests/test/com/google/common/hash/FunnelsTest.java index 368f7b5..698549a 100644 --- a/guava-tests/test/com/google/common/hash/FunnelsTest.java +++ b/guava-tests/test/com/google/common/hash/FunnelsTest.java @@ -1,41 +1,31 @@ -/* - * Copyright (C) 2011 The Guava Authors - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ +// Copyright 2011 Google Inc. All Rights Reserved. package com.google.common.hash; -import static org.mockito.Mockito.mock; -import static org.mockito.Mockito.verify; - import com.google.common.hash.AbstractStreamingHashFunction.AbstractStreamingHasher; import junit.framework.TestCase; -import java.io.OutputStream; +import org.easymock.EasyMock; + import java.nio.ByteBuffer; /** * Tests for HashExtractors. - * - * @author Dimitris Andreou + * + * @author andreou@google.com (Dimitris Andreou) */ public class FunnelsTest extends TestCase { public void testForBytes() { - PrimitiveSink bytePrimitiveSink = mock(PrimitiveSink.class); - Funnels.byteArrayFunnel().funnel(new byte[] { 4, 3, 2, 1 }, bytePrimitiveSink); - verify(bytePrimitiveSink).putBytes(new byte[] { 4, 3, 2, 1 }); + Sink byteSink = EasyMock.createMock(Sink.class); + + EasyMock.expect(byteSink.putBytes(EasyMock.aryEq(new byte[] { 4, 3, 2, 1}))) + .andReturn(byteSink).once(); + EasyMock.replay(byteSink); + + Funnels.byteArrayFunnel().funnel(new byte[]{4, 3, 2, 1}, byteSink); + + EasyMock.verify(byteSink); } public void testForBytes_null() { @@ -43,39 +33,23 @@ public class FunnelsTest extends TestCase { } public void testForStrings() { - PrimitiveSink bytePrimitiveSink = mock(PrimitiveSink.class); - Funnels.stringFunnel().funnel("test", bytePrimitiveSink); - verify(bytePrimitiveSink).putString("test"); - } + Sink byteSink = EasyMock.createMock(Sink.class); + + EasyMock.expect(byteSink.putString("test")).andReturn(byteSink).once(); + EasyMock.replay(byteSink); + + Funnels.stringFunnel().funnel("test", byteSink); + + EasyMock.verify(byteSink); + } + public void testForStrings_null() { assertNullsThrowException(Funnels.stringFunnel()); } - - public void testForInts() { - Integer value = 1234; - PrimitiveSink bytePrimitiveSink = mock(PrimitiveSink.class); - Funnels.integerFunnel().funnel(value, bytePrimitiveSink); - verify(bytePrimitiveSink).putInt(1234); - } - - public void testForInts_null() { - assertNullsThrowException(Funnels.integerFunnel()); - } - - public void testForLongs() { - Long value = 1234L; - PrimitiveSink bytePrimitiveSink = mock(PrimitiveSink.class); - Funnels.longFunnel().funnel(value, bytePrimitiveSink); - verify(bytePrimitiveSink).putLong(1234); - } - - public void testForLongs_null() { - assertNullsThrowException(Funnels.longFunnel()); - } - + private static void assertNullsThrowException(Funnel<?> funnel) { - PrimitiveSink bytePrimitiveSink = new AbstractStreamingHasher(4, 4) { + Sink byteSink = new AbstractStreamingHasher(4, 4) { @Override HashCode makeHash() { throw new UnsupportedOperationException(); } @Override protected void process(ByteBuffer bb) { @@ -85,20 +59,8 @@ public class FunnelsTest extends TestCase { } }; try { - funnel.funnel(null, bytePrimitiveSink); + funnel.funnel(null, byteSink); fail(); } catch (NullPointerException ok) {} } - - public void testAsOutputStream() throws Exception { - PrimitiveSink sink = mock(PrimitiveSink.class); - OutputStream out = Funnels.asOutputStream(sink); - byte[] bytes = { 1, 2, 3, 4 }; - out.write(255); - out.write(bytes); - out.write(bytes, 1, 2); - verify(sink).putByte((byte) 255); - verify(sink).putBytes(bytes); - verify(sink).putBytes(bytes, 1, 2); - } } diff --git a/guava-tests/test/com/google/common/hash/HashCodesTest.java b/guava-tests/test/com/google/common/hash/HashCodesTest.java index 70fb7ec..2b483ac 100644 --- a/guava-tests/test/com/google/common/hash/HashCodesTest.java +++ b/guava-tests/test/com/google/common/hash/HashCodesTest.java @@ -1,23 +1,8 @@ -/* - * Copyright (C) 2011 The Guava Authors - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ +// Copyright 2011 Google Inc. All Rights Reserved. package com.google.common.hash; import com.google.common.collect.ImmutableList; -import com.google.common.testing.ClassSanityTester; import junit.framework.TestCase; @@ -25,124 +10,67 @@ import java.util.Arrays; /** * Tests for HashCodes, especially making sure that their endianness promises (big-endian) - * are upheld. - * - * @author Dimitris Andreou + * are upheld. + * + * @author andreou@google.com (Dimitris Andreou) */ public class HashCodesTest extends TestCase { // note: asInt(), asLong() are in little endian private static final ImmutableList<ExpectedHashCode> expectedHashCodes = ImmutableList.of( - new ExpectedHashCode(new byte[] { + new ExpectedHashCode(new byte[] { (byte) 0xef, (byte) 0xcd, (byte) 0xab, (byte) 0x89, (byte) 0x67, (byte) 0x45, (byte) 0x23, (byte) 0x01}, 0x89abcdef, 0x0123456789abcdefL, "efcdab8967452301"), - - new ExpectedHashCode(new byte[] { + + new ExpectedHashCode(new byte[] { (byte) 0xef, (byte) 0xcd, (byte) 0xab, (byte) 0x89, (byte) 0x67, (byte) 0x45, (byte) 0x23, (byte) 0x01, // up to here, same bytes as above (byte) 0x01, (byte) 0x02, (byte) 0x03, (byte) 0x04, (byte) 0x05, (byte) 0x06, (byte) 0x07, (byte) 0x08}, 0x89abcdef, 0x0123456789abcdefL, // asInt/asLong as above, due to equal eight first bytes - "efcdab89674523010102030405060708"), - + "efcdab89674523010102030405060708"), + new ExpectedHashCode(new byte[] { (byte) 0xdf, (byte) 0x9b, (byte) 0x57, (byte) 0x13 }, 0x13579bdf, null, "df9b5713"), - - new ExpectedHashCode(new byte[] { + + new ExpectedHashCode(new byte[] { (byte) 0xcd, (byte) 0xab, (byte) 0x00, (byte) 0x00}, 0x0000abcd, null, "cdab0000"), - - new ExpectedHashCode(new byte[] { + + new ExpectedHashCode(new byte[] { (byte) 0xef, (byte) 0xcd, (byte) 0xab, (byte) 0x00, (byte) 0x00, (byte) 0x00, (byte) 0x00, (byte) 0x00}, 0x00abcdef, 0x0000000000abcdefL, "efcdab0000000000") ); - + // expectedHashCodes must contain at least one hash code with 4 bytes public void testFromInt() { for (ExpectedHashCode expected : expectedHashCodes) { - if (expected.bytes.length == 4) { + if (expected.bytes.length == 4) { HashCode fromInt = HashCodes.fromInt(expected.asInt); assertExpectedHashCode(expected, fromInt); } } } - + // expectedHashCodes must contain at least one hash code with 8 bytes public void testFromLong() { for (ExpectedHashCode expected : expectedHashCodes) { - if (expected.bytes.length == 8) { + if (expected.bytes.length == 8) { HashCode fromLong = HashCodes.fromLong(expected.asLong); assertExpectedHashCode(expected, fromLong); } } } - + public void testFromBytes() { for (ExpectedHashCode expected : expectedHashCodes) { HashCode fromBytes = HashCodes.fromBytes(expected.bytes); assertExpectedHashCode(expected, fromBytes); } } - - public void testFromBytes_copyOccurs() { - byte[] bytes = new byte[] { (byte) 0xcd, (byte) 0xab, (byte) 0x00, (byte) 0x00 }; - HashCode hashCode = HashCodes.fromBytes(bytes); - int expectedInt = 0x0000abcd; - String expectedToString = "cdab0000"; - - assertEquals(expectedInt, hashCode.asInt()); - assertEquals(expectedToString, hashCode.toString()); - - bytes[0] = (byte) 0x00; - - assertEquals(expectedInt, hashCode.asInt()); - assertEquals(expectedToString, hashCode.toString()); - } - - public void testFromBytesNoCopy_noCopyOccurs() { - byte[] bytes = new byte[] { (byte) 0xcd, (byte) 0xab, (byte) 0x00, (byte) 0x00 }; - HashCode hashCode = HashCodes.fromBytesNoCopy(bytes); - - assertEquals(0x0000abcd, hashCode.asInt()); - assertEquals("cdab0000", hashCode.toString()); - - bytes[0] = (byte) 0x00; - - assertEquals(0x0000ab00, hashCode.asInt()); - assertEquals("00ab0000", hashCode.toString()); - } - - public void testPadToLong() { - assertEquals(0x1111111111111111L, HashCodes.fromLong(0x1111111111111111L).padToLong()); - assertEquals(0x9999999999999999L, HashCodes.fromLong(0x9999999999999999L).padToLong()); - assertEquals(0x0000000011111111L, HashCodes.fromInt(0x11111111).padToLong()); - assertEquals(0x0000000099999999L, HashCodes.fromInt(0x99999999).padToLong()); - - byte[] longBytes = {(byte) 0x99, (byte) 0x99, (byte) 0x99, (byte) 0x99, - (byte) 0x99, (byte) 0x99, (byte) 0x99, (byte) 0x99}; - byte[] intBytes = {(byte) 0x99, (byte) 0x99, (byte) 0x99, (byte) 0x99}; - assertEquals(0x9999999999999999L, HashCodes.fromBytesNoCopy(longBytes).padToLong()); - assertEquals(0x0000000099999999L, HashCodes.fromBytesNoCopy(intBytes).padToLong()); - } - - public void testHashCodes_nulls() throws Exception { - sanityTester().testNulls(); - } - - public void testHashCodes_equalsAndSerializable() throws Exception { - sanityTester().testEqualsAndSerializable(); - } - - private static ClassSanityTester.FactoryMethodReturnValueTester sanityTester() { - return new ClassSanityTester() - .setDefault(byte[].class, new byte[] {1, 2, 3, 4}) - .setSampleInstances(byte[].class, - ImmutableList.of(new byte[] {1, 2, 3, 4}, new byte[] {5, 6, 7, 8})) - .forAllPublicStaticMethods(HashCodes.class); - } - - private static void assertExpectedHashCode(ExpectedHashCode expected, HashCode hash) { + + private void assertExpectedHashCode(ExpectedHashCode expected, HashCode hash) { assertTrue(Arrays.equals(expected.bytes, hash.asBytes())); byte[] bb = new byte[hash.bits() / 8]; hash.writeBytesTo(bb, 0, bb.length); @@ -160,27 +88,27 @@ public class HashCodesTest extends TestCase { assertSideEffectFree(hash); assertReadableBytes(hash); } - - private static void assertSideEffectFree(HashCode hash) { + + private void assertSideEffectFree(HashCode hash) { byte[] original = hash.asBytes(); byte[] mutated = hash.asBytes(); mutated[0]++; assertTrue(Arrays.equals(original, hash.asBytes())); } - - private static void assertReadableBytes(HashCode hashCode) { + + private void assertReadableBytes(HashCode hashCode) { assertTrue(hashCode.bits() >= 32); // sanity byte[] hashBytes = hashCode.asBytes(); int totalBytes = hashCode.bits() / 8; - + for (int bytes = 0; bytes < totalBytes; bytes++) { byte[] bb = new byte[bytes]; hashCode.writeBytesTo(bb, 0, bb.length); - + assertTrue(Arrays.equals(Arrays.copyOf(hashBytes, bytes), bb)); } } - + private static class ExpectedHashCode { final byte[] bytes; final int asInt; diff --git a/guava-tests/test/com/google/common/hash/HashFunctionsTest.java b/guava-tests/test/com/google/common/hash/HashFunctionsTest.java new file mode 100644 index 0000000..f9fd6c4 --- /dev/null +++ b/guava-tests/test/com/google/common/hash/HashFunctionsTest.java @@ -0,0 +1,74 @@ +// Copyright 2011 Google Inc. All Rights Reserved. + +package com.google.common.hash; + +import com.google.common.collect.Sets; + +import junit.framework.TestCase; + +import java.util.Set; + +/** + * Tests for HashFunctions. + * + * @author andreou@google.com (Dimitris Andreou) + */ +public class HashFunctionsTest extends TestCase { + public void testMd5() { + assertInvariants(Hashing.md5()); + } + + public void testMurmur3_138() { + assertInvariants(Hashing.murmur3_128()); + } + + public void testMurmur3_32() { + assertInvariants(Hashing.murmur3_32()); + } + + public void testGoodFastHash() { + for (int i = 1; i < 500; i++) { + HashFunction hasher = Hashing.goodFastHash(i); + assertTrue(hasher.bits() >= i); + assertInvariants(hasher); + } + } + + /** + * Checks that a Hasher returns the same HashCode when given the same input, and also + * that the collision rate looks sane. + */ + private static void assertInvariants(HashFunction hashFunction) { + int objects = 100; + Set<HashCode> hashcodes = Sets.newHashSetWithExpectedSize(objects); + for (int i = 0; i < objects; i++) { + Object o = new Object(); + HashCode hashcode1 = hashFunction.newHasher().putObject(o, HashTestUtils.BAD_FUNNEL).hash(); + HashCode hashcode2 = hashFunction.newHasher().putObject(o, HashTestUtils.BAD_FUNNEL).hash(); + assertEquals(hashcode1, hashcode2); // idempotent + assertEquals(hashFunction.bits(), hashcode1.bits()); + assertEquals(hashFunction.bits(), hashcode1.asBytes().length * 8); + hashcodes.add(hashcode1); + } + assertTrue(hashcodes.size() > objects * 0.95); // quite relaxed test + + assertHashBytesThrowsCorrectExceptions(hashFunction); + } + + private static void assertHashBytesThrowsCorrectExceptions(HashFunction hashFunction) { + hashFunction.hashBytes(new byte[64], 0, 0); + + try { + hashFunction.hashBytes(new byte[128], -1, 128); + fail(); + } catch (IndexOutOfBoundsException ok) {} + try { + hashFunction.hashBytes(new byte[128], 64, 256 /* too long len */); + fail(); + } catch (IndexOutOfBoundsException ok) {} + try { + hashFunction.hashBytes(new byte[64], 0, -1); + fail(); + } catch (IndexOutOfBoundsException ok) {} + } +} diff --git a/guava-tests/test/com/google/common/hash/HashTestUtils.java b/guava-tests/test/com/google/common/hash/HashTestUtils.java index 8a894f7..a857a79 100644 --- a/guava-tests/test/com/google/common/hash/HashTestUtils.java +++ b/guava-tests/test/com/google/common/hash/HashTestUtils.java @@ -1,44 +1,20 @@ -/* - * Copyright (C) 2011 The Guava Authors - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ +// Copyright 2011 Google Inc. All Rights Reserved. package com.google.common.hash; -import static org.junit.Assert.assertEquals; - -import com.google.common.base.Charsets; -import com.google.common.collect.ImmutableList; -import com.google.common.collect.ImmutableSet; -import com.google.common.collect.Sets; import com.google.common.primitives.Ints; -import com.google.common.testing.EqualsTester; import org.junit.Assert; -import java.nio.charset.Charset; +import java.nio.ByteBuffer; +import java.nio.ByteOrder; import java.util.Arrays; import java.util.Random; -import java.util.Set; /** - * Various utilities for testing {@link HashFunction}s. - * - * @author Dimitris Andreou - * @author Kurt Alfred Kluever + * @author andreou@google.com (Dimitris Andreou) */ -final class HashTestUtils { +class HashTestUtils { private HashTestUtils() {} /** @@ -52,6 +28,17 @@ final class HashTestUtils { return bytes; } + /** + * Returns a byte array representation for a sequence of longs, in big-endian order. + */ + static byte[] toBytes(ByteOrder bo, long... longs) { + ByteBuffer bb = ByteBuffer.wrap(new byte[longs.length * 8]).order(bo); + for (long x : longs) { + bb.putLong(x); + } + return bb.array(); + } + interface HashFn { byte[] hash(byte[] input, int seed); } @@ -69,510 +56,123 @@ final class HashTestUtils { byte[] hash = hashFunction.hash(Arrays.copyOf(key, i), seed); System.arraycopy(hash, 0, hashes, i * hashBytes, hash.length); } - + // Then hash the result array byte[] result = hashFunction.hash(hashes, 0); - + // interpreted in little-endian order. - int verification = Integer.reverseBytes(Ints.fromByteArray(result)); + int verification = Integer.reverseBytes(Ints.fromByteArray(result)); if (expected != verification) { throw new AssertionError("Expected: " + Integer.toHexString(expected) + " got: " + Integer.toHexString(verification)); } } - + + static void assertEqualHashes(byte[] expectedHash, byte[] actualHash) { + if (!Arrays.equals(expectedHash, actualHash)) { + Assert.fail(String.format("Should be: %x, was %x", expectedHash, actualHash)); + } + } + static final Funnel<Object> BAD_FUNNEL = new Funnel<Object>() { - @Override public void funnel(Object object, PrimitiveSink bytePrimitiveSink) { - bytePrimitiveSink.putInt(object.hashCode()); + @Override public void funnel(Object object, Sink byteSink) { + byteSink.putInt(object.hashCode()); } }; - + static enum RandomHasherAction { PUT_BOOLEAN() { - @Override void performAction(Random random, Iterable<? extends PrimitiveSink> sinks) { + @Override void performAction(Random random, Iterable<? extends Sink> sinks) { boolean value = random.nextBoolean(); - for (PrimitiveSink sink : sinks) { + for (Sink sink : sinks) { sink.putBoolean(value); } } }, PUT_BYTE() { - @Override void performAction(Random random, Iterable<? extends PrimitiveSink> sinks) { + @Override void performAction(Random random, Iterable<? extends Sink> sinks) { int value = random.nextInt(); - for (PrimitiveSink sink : sinks) { + for (Sink sink : sinks) { sink.putByte((byte) value); } } }, PUT_SHORT() { - @Override void performAction(Random random, Iterable<? extends PrimitiveSink> sinks) { + @Override void performAction(Random random, Iterable<? extends Sink> sinks) { short value = (short) random.nextInt(); - for (PrimitiveSink sink : sinks) { + for (Sink sink : sinks) { sink.putShort(value); } } }, PUT_CHAR() { - @Override void performAction(Random random, Iterable<? extends PrimitiveSink> sinks) { + @Override void performAction(Random random, Iterable<? extends Sink> sinks) { char value = (char) random.nextInt(); - for (PrimitiveSink sink : sinks) { + for (Sink sink : sinks) { sink.putChar(value); } } }, PUT_INT() { - @Override void performAction(Random random, Iterable<? extends PrimitiveSink> sinks) { + @Override void performAction(Random random, Iterable<? extends Sink> sinks) { int value = random.nextInt(); - for (PrimitiveSink sink : sinks) { + for (Sink sink : sinks) { sink.putInt(value); } } }, PUT_LONG() { - @Override void performAction(Random random, Iterable<? extends PrimitiveSink> sinks) { + @Override void performAction(Random random, Iterable<? extends Sink> sinks) { long value = random.nextLong(); - for (PrimitiveSink sink : sinks) { + for (Sink sink : sinks) { sink.putLong(value); } } }, PUT_FLOAT() { - @Override void performAction(Random random, Iterable<? extends PrimitiveSink> sinks) { + @Override void performAction(Random random, Iterable<? extends Sink> sinks) { float value = random.nextFloat(); - for (PrimitiveSink sink : sinks) { + for (Sink sink : sinks) { sink.putFloat(value); } } }, PUT_DOUBLE() { - @Override void performAction(Random random, Iterable<? extends PrimitiveSink> sinks) { + @Override void performAction(Random random, Iterable<? extends Sink> sinks) { double value = random.nextDouble(); - for (PrimitiveSink sink : sinks) { + for (Sink sink : sinks) { sink.putDouble(value); } } }, PUT_BYTES() { - @Override void performAction(Random random, Iterable<? extends PrimitiveSink> sinks) { + @Override void performAction(Random random, Iterable<? extends Sink> sinks) { byte[] value = new byte[random.nextInt(128)]; random.nextBytes(value); - for (PrimitiveSink sink : sinks) { + for (Sink sink : sinks) { sink.putBytes(value); } } }, PUT_BYTES_INT_INT() { - @Override void performAction(Random random, Iterable<? extends PrimitiveSink> sinks) { + @Override void performAction(Random random, Iterable<? extends Sink> sinks) { byte[] value = new byte[random.nextInt(128)]; random.nextBytes(value); int off = random.nextInt(value.length + 1); int len = random.nextInt(value.length - off + 1); - for (PrimitiveSink sink : sinks) { + for (Sink sink : sinks) { sink.putBytes(value); } } - }, - PUT_STRING() { - @Override void performAction(Random random, Iterable<? extends PrimitiveSink> sinks) { - char[] value = new char[random.nextInt(128)]; - for (int i = 0; i < value.length; i++) { - value[i] = (char) random.nextInt(); - } - String s = new String(value); - for (PrimitiveSink sink : sinks) { - sink.putString(s); - } - } - }, - PUT_STRING_LOW_SURROGATE() { - @Override void performAction(Random random, Iterable<? extends PrimitiveSink> sinks) { - String s = new String(new char[] { randomLowSurrogate(random) }); - for (PrimitiveSink sink : sinks) { - sink.putString(s); - } - } - }, - PUT_STRING_HIGH_SURROGATE() { - @Override void performAction(Random random, Iterable<? extends PrimitiveSink> sinks) { - String s = new String(new char[] { randomHighSurrogate(random) }); - for (PrimitiveSink sink : sinks) { - sink.putString(s); - } - } - }, - PUT_STRING_LOW_HIGH_SURROGATE() { - @Override void performAction(Random random, Iterable<? extends PrimitiveSink> sinks) { - String s = new String(new char[] { - randomLowSurrogate(random), randomHighSurrogate(random)}); - for (PrimitiveSink sink : sinks) { - sink.putString(s); - } - } - }, - PUT_STRING_HIGH_LOW_SURROGATE() { - @Override void performAction(Random random, Iterable<? extends PrimitiveSink> sinks) { - String s = new String(new char[] { - randomHighSurrogate(random), randomLowSurrogate(random)}); - for (PrimitiveSink sink : sinks) { - sink.putString(s); - } - } }; - - abstract void performAction(Random random, Iterable<? extends PrimitiveSink> sinks); - + + abstract void performAction(Random random, Iterable<? extends Sink> sinks); + private static final RandomHasherAction[] actions = values(); - + static RandomHasherAction pickAtRandom(Random random) { return actions[random.nextInt(actions.length)]; } } - - /** - * Test that the hash function contains no funnels. A funnel is a situation where a set of input - * (key) bits 'affects' a strictly smaller set of output bits. Funneling is bad because it can - * result in more-than-ideal collisions for a non-uniformly distributed key space. In practice, - * most key spaces are ANYTHING BUT uniformly distributed. A bit(i) in the input is said to - * 'affect' a bit(j) in the output if two inputs, identical but for bit(i), will differ at output - * bit(j) about half the time - * - * <p>Funneling is pretty simple to detect. The key idea is to find example keys which - * unequivocably demonstrate that funneling cannot be occuring. This is done bit-by-bit. For - * each input bit(i) and output bit(j), two pairs of keys must be found with all bits identical - * except bit(i). One pair must differ in output bit(j), and one pair must not. This proves that - * input bit(i) can alter output bit(j). - */ - static void checkNoFunnels(HashFunction function) { - Random rand = new Random(0); - int keyBits = 32; - int hashBits = function.bits(); - - // output loop tests input bit - for (int i = 0; i < keyBits; i++) { - int same = 0x0; // bitset for output bits with same values - int diff = 0x0; // bitset for output bits with different values - int count = 0; - // originally was 2 * Math.log(...), making it try more times to avoid flakiness issues - int maxCount = (int) (4 * Math.log(2 * keyBits * hashBits) + 1); - while (same != 0xffffffff || diff != 0xffffffff) { - int key1 = rand.nextInt(); - // flip input bit for key2 - int key2 = key1 ^ (1 << i); - // get hashes - int hash1 = function.newHasher().putInt(key1).hash().asInt(); - int hash2 = function.newHasher().putInt(key2).hash().asInt(); - // test whether the hash values have same output bits - same |= ~(hash1 ^ hash2); - // test whether the hash values have different output bits - diff |= (hash1 ^ hash2); - - count++; - // check whether we've exceeded the probabilistically - // likely number of trials to have proven no funneling - if (count > maxCount) { - Assert.fail("input bit(" + i + ") was found not to affect all " + - hashBits + " output bits; The unaffected bits are " + - "as follows: " + ~(same & diff) + ". This was " + - "determined after " + count + " trials."); - } - } - } - } - - /** - * Test for avalanche. Avalanche means that output bits differ with roughly 1/2 probability on - * different input keys. This test verifies that each possible 1-bit key delta achieves avalanche. - * - * <p>For more information: http://burtleburtle.net/bob/hash/avalanche.html - */ - static void checkAvalanche(HashFunction function, int trials, double epsilon) { - Random rand = new Random(0); - int keyBits = 32; - int hashBits = function.bits(); - for (int i = 0; i < keyBits; i++) { - int[] same = new int[hashBits]; - int[] diff = new int[hashBits]; - // go through trials to compute probability - for (int j = 0; j < trials; j++) { - int key1 = rand.nextInt(); - // flip input bit for key2 - int key2 = key1 ^ (1 << i); - // compute hash values - int hash1 = function.newHasher().putInt(key1).hash().asInt(); - int hash2 = function.newHasher().putInt(key2).hash().asInt(); - for (int k = 0; k < hashBits; k++) { - if ((hash1 & (1 << k)) == (hash2 & (1 << k))) { - same[k] += 1; - } else { - diff[k] += 1; - } - } - } - // measure probability and assert it's within margin of error - for (int j = 0; j < hashBits; j++) { - double prob = (double) diff[j] / (double) (diff[j] + same[j]); - Assert.assertEquals(0.50d, prob, epsilon); - } - } - } - - /** - * Test for 2-bit characteristics. A characteristic is a delta in the input which is repeated in - * the output. For example, if f() is a block cipher and c is a characteristic, then - * f(x^c) = f(x)^c with greater than expected probability. The test for funneling is merely a test - * for 1-bit characteristics. - * - * <p>There is more general code provided by Bob Jenkins to test arbitrarily sized characteristics - * using the magic of gaussian elimination: http://burtleburtle.net/bob/crypto/findingc.html. - */ - static void checkNo2BitCharacteristics(HashFunction function) { - Random rand = new Random(0); - int keyBits = 32; - - // get every one of (keyBits choose 2) deltas: - for (int i = 0; i < keyBits; i++) { - for (int j = 0; j < keyBits; j++) { - if (j <= i) continue; - int count = 0; - int maxCount = 20; // the probability of error here is miniscule - boolean diff = false; - - while (diff == false) { - int delta = (1 << i) | (1 << j); - int key1 = rand.nextInt(); - // apply delta - int key2 = key1 ^ delta; - - // get hashes - int hash1 = function.newHasher().putInt(key1).hash().asInt(); - int hash2 = function.newHasher().putInt(key2).hash().asInt(); - - // this 2-bit candidate delta is not a characteristic - // if deltas are different - if ((hash1 ^ hash2) != delta) { - diff = true; - continue; - } - - // check if we've exceeded the probabilistically - // likely number of trials to have proven 2-bit candidate - // is not a characteristic - count++; - if (count > maxCount) { - Assert.fail("2-bit delta (" + i + ", " + j + ") is likely a " + - "characteristic for this hash. This was " + - "determined after " + count + " trials"); - } - } - } - } - } - - /** - * Test for avalanche with 2-bit deltas. Most probabilities of output bit(j) differing are well - * within 50%. - */ - static void check2BitAvalanche(HashFunction function, int trials, double epsilon) { - Random rand = new Random(0); - int keyBits = 32; - int hashBits = function.bits(); - for (int bit1 = 0; bit1 < keyBits; bit1++) { - for (int bit2 = 0; bit2 < keyBits; bit2++) { - if (bit2 <= bit1) continue; - int delta = (1 << bit1) | (1 << bit2); - int[] same = new int[hashBits]; - int[] diff = new int[hashBits]; - // go through trials to compute probability - for (int j = 0; j < trials; j++) { - int key1 = rand.nextInt(); - // flip input bit for key2 - int key2 = key1 ^ delta; - // compute hash values - int hash1 = function.newHasher().putInt(key1).hash().asInt(); - int hash2 = function.newHasher().putInt(key2).hash().asInt(); - for (int k = 0; k < hashBits; k++) { - if ((hash1 & (1 << k)) == (hash2 & (1 << k))) { - same[k] += 1; - } else { - diff[k] += 1; - } - } - } - // measure probability and assert it's within margin of error - for (int j = 0; j < hashBits; j++) { - double prob = (double) diff[j] / (double) (diff[j] + same[j]); - Assert.assertEquals(0.50d, prob, epsilon); - } - } - } - } - - /** - * Checks that a Hasher returns the same HashCode when given the same input, and also - * that the collision rate looks sane. - */ - static void assertInvariants(HashFunction hashFunction) { - int objects = 100; - Set<HashCode> hashcodes = Sets.newHashSetWithExpectedSize(objects); - for (int i = 0; i < objects; i++) { - Object o = new Object(); - HashCode hashcode1 = hashFunction.hashObject(o, HashTestUtils.BAD_FUNNEL); - HashCode hashcode2 = hashFunction.hashObject(o, HashTestUtils.BAD_FUNNEL); - Assert.assertEquals(hashcode1, hashcode2); // idempotent - Assert.assertEquals(hashFunction.bits(), hashcode1.bits()); - Assert.assertEquals(hashFunction.bits(), hashcode1.asBytes().length * 8); - hashcodes.add(hashcode1); - } - Assert.assertTrue(hashcodes.size() > objects * 0.95); // quite relaxed test - - assertHashBytesThrowsCorrectExceptions(hashFunction); - assertIndependentHashers(hashFunction); - assertShortcutsAreEquivalent(hashFunction, 512); - } - - static void assertHashBytesThrowsCorrectExceptions(HashFunction hashFunction) { - hashFunction.hashBytes(new byte[64], 0, 0); - - try { - hashFunction.hashBytes(new byte[128], -1, 128); - Assert.fail(); - } catch (IndexOutOfBoundsException expected) {} - try { - hashFunction.hashBytes(new byte[128], 64, 256 /* too long len */); - Assert.fail(); - } catch (IndexOutOfBoundsException expected) {} - try { - hashFunction.hashBytes(new byte[64], 0, -1); - Assert.fail(); - } catch (IndexOutOfBoundsException expected) {} - } - - static void assertIndependentHashers(HashFunction hashFunction) { - int numActions = 100; - // hashcodes from non-overlapping hash computations - HashCode expected1 = randomHash(hashFunction, new Random(1L), numActions); - HashCode expected2 = randomHash(hashFunction, new Random(2L), numActions); - - // equivalent, but overlapping, computations (should produce the same results as above) - Random random1 = new Random(1L); - Random random2 = new Random(2L); - Hasher hasher1 = hashFunction.newHasher(); - Hasher hasher2 = hashFunction.newHasher(); - for (int i = 0; i < numActions; i++) { - RandomHasherAction.pickAtRandom(random1).performAction(random1, ImmutableSet.of(hasher1)); - RandomHasherAction.pickAtRandom(random2).performAction(random2, ImmutableSet.of(hasher2)); - } - - Assert.assertEquals(expected1, hasher1.hash()); - Assert.assertEquals(expected2, hasher2.hash()); - } - - static HashCode randomHash(HashFunction hashFunction, Random random, int numActions) { - Hasher hasher = hashFunction.newHasher(); - for (int i = 0; i < numActions; i++) { - RandomHasherAction.pickAtRandom(random).performAction(random, ImmutableSet.of(hasher)); - } - return hasher.hash(); - } - - private static void assertShortcutsAreEquivalent(HashFunction hashFunction, int trials) { - Random random = new Random(42085L); - for (int i = 0; i < trials; i++) { - assertHashBytesEquivalence(hashFunction, random); - assertHashIntEquivalence(hashFunction, random); - assertHashLongEquivalence(hashFunction, random); - assertHashStringEquivalence(hashFunction, random); - assertHashStringWithSurrogatesEquivalence(hashFunction, random); - } - } - - private static void assertHashBytesEquivalence(HashFunction hashFunction, Random random) { - int size = random.nextInt(2048); - byte[] bytes = new byte[size]; - random.nextBytes(bytes); - assertEquals(hashFunction.hashBytes(bytes), - hashFunction.newHasher(size).putBytes(bytes).hash()); - int off = random.nextInt(size); - int len = random.nextInt(size - off); - assertEquals(hashFunction.hashBytes(bytes, off, len), - hashFunction.newHasher(size).putBytes(bytes, off, len).hash()); - } - - private static void assertHashIntEquivalence(HashFunction hashFunction, Random random) { - int i = random.nextInt(); - assertEquals(hashFunction.hashInt(i), - hashFunction.newHasher().putInt(i).hash()); - } - - private static void assertHashLongEquivalence(HashFunction hashFunction, Random random) { - long l = random.nextLong(); - assertEquals(hashFunction.hashLong(l), - hashFunction.newHasher().putLong(l).hash()); - } - - private static final ImmutableList<Charset> CHARSETS = ImmutableList.of( - Charsets.ISO_8859_1, - Charsets.US_ASCII, - Charsets.UTF_16, - Charsets.UTF_16BE, - Charsets.UTF_16LE, - Charsets.UTF_8); - - private static void assertHashStringEquivalence(HashFunction hashFunction, Random random) { - // Test that only data and data-order is important, not the individual operations. - new EqualsTester() - .addEqualityGroup( - hashFunction.newHasher().putString("abc").hash(), - hashFunction.newHasher().putString("ab").putString("c").hash(), - hashFunction.newHasher().putString("a").putString("bc").hash(), - hashFunction.newHasher().putString("a").putString("b").putString("c").hash(), - hashFunction.newHasher().putChar('a').putString("bc").hash(), - hashFunction.newHasher().putString("ab").putChar('c').hash(), - hashFunction.newHasher().putChar('a').putChar('b').putChar('c').hash()) - .testEquals(); - - int size = random.nextInt(2048); - byte[] bytes = new byte[size]; - random.nextBytes(bytes); - String string = new String(bytes); - assertEquals(hashFunction.hashString(string), - hashFunction.newHasher().putString(string).hash()); - // These assertions causes failures when testing with mvn. See b/6657789 - // assertEquals(hashFunction.hashString(string), - // hashFunction.hashString(string, Charsets.UTF_16LE)); - // assertEquals(hashFunction.hashString(string), - // hashFunction.newHasher().putString(string, Charsets.UTF_16LE).hash()); - for (Charset charset : CHARSETS) { - assertEquals(hashFunction.hashString(string, charset), - hashFunction.newHasher().putString(string, charset).hash()); - } - } - - /** - * This verifies that putString(String) and hashString(String) are equivalent, even for - * funny strings composed by (possibly unmatched, and mostly illegal) surrogate characters. - * (But doesn't test that they do the right thing - just their consistency). - */ - private static void assertHashStringWithSurrogatesEquivalence( - HashFunction hashFunction, Random random) { - int size = random.nextInt(8) + 1; - char[] chars = new char[size]; - for (int i = 0; i < chars.length; i++) { - chars[i] = random.nextBoolean() ? randomLowSurrogate(random) : randomHighSurrogate(random); - } - String string = new String(chars); - assertEquals(hashFunction.hashString(string), - hashFunction.newHasher().putString(string).hash()); - } - - static char randomLowSurrogate(Random random) { - return (char) (Character.MIN_LOW_SURROGATE - + random.nextInt(Character.MAX_LOW_SURROGATE - Character.MIN_LOW_SURROGATE + 1)); - } - - static char randomHighSurrogate(Random random) { - return (char) (Character.MIN_HIGH_SURROGATE - + random.nextInt(Character.MAX_HIGH_SURROGATE - Character.MIN_HIGH_SURROGATE + 1)); - } } diff --git a/guava-tests/test/com/google/common/hash/HashingTest.java b/guava-tests/test/com/google/common/hash/HashingTest.java index f5488a1..547d5a3 100644 --- a/guava-tests/test/com/google/common/hash/HashingTest.java +++ b/guava-tests/test/com/google/common/hash/HashingTest.java @@ -16,125 +16,20 @@ package com.google.common.hash; -import static com.google.common.hash.Hashing.ConcatenatedHashFunction; - -import com.google.common.base.Charsets; import com.google.common.collect.ImmutableList; -import com.google.common.collect.ImmutableTable; import com.google.common.collect.Lists; -import com.google.common.collect.Table.Cell; -import com.google.common.testing.NullPointerTester; import com.google.common.util.concurrent.AtomicLongMap; import junit.framework.TestCase; -import java.nio.ByteBuffer; import java.util.Collections; import java.util.List; import java.util.Random; /** - * Unit tests for {@link Hashing}. - * - * @author Dimitris Andreou - * @author Kurt Alfred Kluever + * Unit tests for functions of {@code Hashing} that don't have their own tests. */ public class HashingTest extends TestCase { - public void testMd5() { - HashTestUtils.checkAvalanche(Hashing.md5(), 100, 0.4); - HashTestUtils.checkNo2BitCharacteristics(Hashing.md5()); - HashTestUtils.checkNoFunnels(Hashing.md5()); - HashTestUtils.assertInvariants(Hashing.md5()); - assertEquals("Hashing.md5()", Hashing.md5().toString()); - } - - public void testSha1() { - HashTestUtils.checkAvalanche(Hashing.sha1(), 100, 0.4); - HashTestUtils.checkNo2BitCharacteristics(Hashing.sha1()); - HashTestUtils.checkNoFunnels(Hashing.sha1()); - HashTestUtils.assertInvariants(Hashing.sha1()); - assertEquals("Hashing.sha1()", Hashing.sha1().toString()); - } - - public void testSha256() { - HashTestUtils.checkAvalanche(Hashing.sha256(), 100, 0.4); - HashTestUtils.checkNo2BitCharacteristics(Hashing.sha256()); - HashTestUtils.checkNoFunnels(Hashing.sha256()); - HashTestUtils.assertInvariants(Hashing.sha256()); - assertEquals("Hashing.sha256()", Hashing.sha256().toString()); - } - - public void testSha512() { - HashTestUtils.checkAvalanche(Hashing.sha512(), 100, 0.4); - HashTestUtils.checkNo2BitCharacteristics(Hashing.sha512()); - HashTestUtils.checkNoFunnels(Hashing.sha512()); - HashTestUtils.assertInvariants(Hashing.sha512()); - assertEquals("Hashing.sha512()", Hashing.sha512().toString()); - } - - public void testCrc32() { - HashTestUtils.assertInvariants(Hashing.crc32()); - assertEquals("Hashing.crc32()", Hashing.crc32().toString()); - } - - public void testAdler32() { - HashTestUtils.assertInvariants(Hashing.adler32()); - assertEquals("Hashing.adler32()", Hashing.adler32().toString()); - } - - public void testMurmur3_128() { - HashTestUtils.check2BitAvalanche(Hashing.murmur3_128(), 250, 0.20); - HashTestUtils.checkAvalanche(Hashing.murmur3_128(), 250, 0.17); - HashTestUtils.checkNo2BitCharacteristics(Hashing.murmur3_128()); - HashTestUtils.checkNoFunnels(Hashing.murmur3_128()); - HashTestUtils.assertInvariants(Hashing.murmur3_128()); - assertEquals("Hashing.murmur3_128(0)", Hashing.murmur3_128().toString()); - } - - public void testMurmur3_32() { - HashTestUtils.check2BitAvalanche(Hashing.murmur3_32(), 250, 0.20); - HashTestUtils.checkAvalanche(Hashing.murmur3_32(), 250, 0.17); - HashTestUtils.checkNo2BitCharacteristics(Hashing.murmur3_32()); - HashTestUtils.checkNoFunnels(Hashing.murmur3_32()); - HashTestUtils.assertInvariants(Hashing.murmur3_32()); - assertEquals("Hashing.murmur3_32(0)", Hashing.murmur3_32().toString()); - } - - public void testGoodFastHash() { - for (int i = 1; i < 200; i += 17) { - HashFunction hasher = Hashing.goodFastHash(i); - assertTrue(hasher.bits() >= i); - HashTestUtils.assertInvariants(hasher); - } - } - - // goodFastHash(32) uses Murmur3_32. Use the same epsilon bounds. - public void testGoodFastHash32() { - HashTestUtils.check2BitAvalanche(Hashing.goodFastHash(32), 250, 0.20); - HashTestUtils.checkAvalanche(Hashing.goodFastHash(32), 250, 0.17); - HashTestUtils.checkNo2BitCharacteristics(Hashing.goodFastHash(32)); - HashTestUtils.checkNoFunnels(Hashing.goodFastHash(32)); - HashTestUtils.assertInvariants(Hashing.goodFastHash(32)); - } - - // goodFastHash(128) uses Murmur3_128. Use the same epsilon bounds. - public void testGoodFastHash128() { - HashTestUtils.check2BitAvalanche(Hashing.goodFastHash(128), 250, 0.20); - HashTestUtils.checkAvalanche(Hashing.goodFastHash(128), 250, 0.17); - HashTestUtils.checkNo2BitCharacteristics(Hashing.goodFastHash(128)); - HashTestUtils.checkNoFunnels(Hashing.goodFastHash(128)); - HashTestUtils.assertInvariants(Hashing.goodFastHash(128)); - } - - // goodFastHash(256) uses Murmur3_128. Use the same epsilon bounds. - public void testGoodFastHash256() { - HashTestUtils.check2BitAvalanche(Hashing.goodFastHash(256), 250, 0.20); - HashTestUtils.checkAvalanche(Hashing.goodFastHash(256), 250, 0.17); - HashTestUtils.checkNo2BitCharacteristics(Hashing.goodFastHash(256)); - HashTestUtils.checkNoFunnels(Hashing.goodFastHash(256)); - HashTestUtils.assertInvariants(Hashing.goodFastHash(256)); - } - public void testPadToLong() { assertEquals(0x1111111111111111L, Hashing.padToLong(HashCodes.fromLong(0x1111111111111111L))); assertEquals(0x9999999999999999L, Hashing.padToLong(HashCodes.fromLong(0x9999999999999999L))); @@ -208,24 +103,14 @@ public class HashingTest extends TestCase { assertEquals(Hashing.consistentHash(equivLong, 5555), Hashing.consistentHash(hashCode, 5555)); } - /** - * Tests that the linear congruential generator is actually compatible with the c++ - * implementation. - * - * This test was added to help refactoring, it is not a strict requirement, it can be removed if - * functionality changes in the future. - */ - public void testConsistentHash_linearCongruentialGeneratorCompatibility() { - assertEquals(55, Hashing.consistentHash(1, 100)); - assertEquals(62, Hashing.consistentHash(2, 100)); - assertEquals(8, Hashing.consistentHash(3, 100)); - assertEquals(45, Hashing.consistentHash(4, 100)); - assertEquals(59, Hashing.consistentHash(5, 100)); + public void testCombineOrdered_null() { + try { + Hashing.combineOrdered(null); + fail(); + } catch (NullPointerException expected) { + } } - private static final double MAX_PERCENT_SPREAD = 0.5; - private static final long RANDOM_SEED = 177L; - public void testCombineOrdered_empty() { try { Hashing.combineOrdered(Collections.<HashCode>emptySet()); @@ -268,6 +153,14 @@ public class HashingTest extends TestCase { assertFalse(hashCode1.equals(hashCode2)); } + public void testCombineUnordered_null() { + try { + Hashing.combineUnordered(null); + fail(); + } catch (NullPointerException expected) { + } + } + public void testCombineUnordered_empty() { try { Hashing.combineUnordered(Collections.<HashCode>emptySet()); @@ -308,82 +201,4 @@ public class HashingTest extends TestCase { assertEquals(hashCode1, hashCode2); } - - public void testConcatenatedHashFunction_bits() { - assertEquals(Hashing.md5().bits(), - new ConcatenatedHashFunction(Hashing.md5()).bits()); - assertEquals(Hashing.md5().bits() + Hashing.murmur3_32().bits(), - new ConcatenatedHashFunction(Hashing.md5(), Hashing.murmur3_32()).bits()); - assertEquals(Hashing.md5().bits() + Hashing.murmur3_32().bits() + Hashing.murmur3_128().bits(), - new ConcatenatedHashFunction( - Hashing.md5(), Hashing.murmur3_32(), Hashing.murmur3_128()).bits()); - } - - public void testConcatenatedHashFunction_makeHash() { - byte[] md5Hash = Hashing.md5().hashLong(42L).asBytes(); - byte[] murmur3Hash = Hashing.murmur3_32().hashLong(42L).asBytes(); - byte[] combined = new byte[md5Hash.length + murmur3Hash.length]; - ByteBuffer buffer = ByteBuffer.wrap(combined); - buffer.put(md5Hash); - buffer.put(murmur3Hash); - - assertEquals(HashCodes.fromBytes(combined), - new ConcatenatedHashFunction(Hashing.md5(), Hashing.murmur3_32()).hashLong(42L)); - } - - private static final String EMPTY_STRING = ""; - private static final String TQBFJOTLD = "The quick brown fox jumps over the lazy dog"; - private static final String TQBFJOTLDP = "The quick brown fox jumps over the lazy dog."; - - private static final ImmutableTable<HashFunction, String, String> KNOWN_HASHES = - ImmutableTable.<HashFunction, String, String>builder() - .put(Hashing.adler32(), EMPTY_STRING, "01000000") - .put(Hashing.adler32(), TQBFJOTLD, "da0fdc5b") - .put(Hashing.adler32(), TQBFJOTLDP, "0810e46b") - .put(Hashing.md5(), EMPTY_STRING, "d41d8cd98f00b204e9800998ecf8427e") - .put(Hashing.md5(), TQBFJOTLD, "9e107d9d372bb6826bd81d3542a419d6") - .put(Hashing.md5(), TQBFJOTLDP, "e4d909c290d0fb1ca068ffaddf22cbd0") - .put(Hashing.murmur3_128(), EMPTY_STRING, "00000000000000000000000000000000") - .put(Hashing.murmur3_128(), TQBFJOTLD, "6c1b07bc7bbc4be347939ac4a93c437a") - .put(Hashing.murmur3_128(), TQBFJOTLDP, "c902e99e1f4899cde7b68789a3a15d69") - .put(Hashing.murmur3_32(), EMPTY_STRING, "00000000") - .put(Hashing.murmur3_32(), TQBFJOTLD, "23f74f2e") - .put(Hashing.murmur3_32(), TQBFJOTLDP, "fc8bc4d5") - .put(Hashing.sha1(), EMPTY_STRING, "da39a3ee5e6b4b0d3255bfef95601890afd80709") - .put(Hashing.sha1(), TQBFJOTLD, "2fd4e1c67a2d28fced849ee1bb76e7391b93eb12") - .put(Hashing.sha1(), TQBFJOTLDP, "408d94384216f890ff7a0c3528e8bed1e0b01621") - .put(Hashing.sha256(), EMPTY_STRING, - "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855") - .put(Hashing.sha256(), TQBFJOTLD, - "d7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592") - .put(Hashing.sha256(), TQBFJOTLDP, - "ef537f25c895bfa782526529a9b63d97aa631564d5d789c2b765448c8635fb6c") - .put(Hashing.sha512(), EMPTY_STRING, - "cf83e1357eefb8bdf1542850d66d8007d620e4050b5715dc83f4a921d36ce9ce" + - "47d0d13c5d85f2b0ff8318d2877eec2f63b931bd47417a81a538327af927da3e") - .put(Hashing.sha512(), TQBFJOTLD, - "07e547d9586f6a73f73fbac0435ed76951218fb7d0c8d788a309d785436bbb64" + - "2e93a252a954f23912547d1e8a3b5ed6e1bfd7097821233fa0538f3db854fee6") - .put(Hashing.sha512(), TQBFJOTLDP, - "91ea1245f20d46ae9a037a989f54f1f790f0a47607eeb8a14d12890cea77a1bb" + - "c6c7ed9cf205e67b7f2b8fd4c7dfd3a7a8617e45f3c463d481c7e586c39ac1ed") - .build(); - - public void testKnownUtf8Hashing() { - for (Cell<HashFunction, String, String> cell : KNOWN_HASHES.cellSet()) { - HashFunction func = cell.getRowKey(); - String input = cell.getColumnKey(); - String expected = cell.getValue(); - assertEquals( - String.format("Known hash for hash(%s, UTF_8) failed", input), - expected, - func.hashString(input, Charsets.UTF_8).toString()); - } - } - - public void testNullPointers() { - NullPointerTester tester = new NullPointerTester() - .setDefault(HashCode.class, HashCodes.fromInt(0)); - tester.testAllPublicStaticMethods(Hashing.class); - } } diff --git a/guava-tests/test/com/google/common/hash/MessageDigestHashFunctionTest.java b/guava-tests/test/com/google/common/hash/MessageDigestHashFunctionTest.java index 2a9547b..a70466e 100644 --- a/guava-tests/test/com/google/common/hash/MessageDigestHashFunctionTest.java +++ b/guava-tests/test/com/google/common/hash/MessageDigestHashFunctionTest.java @@ -1,73 +1,34 @@ -/* - * Copyright (C) 2011 The Guava Authors - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ +// Copyright 2011 Google Inc. All Rights Reserved. package com.google.common.hash; -import com.google.common.collect.ImmutableSet; - -import junit.framework.TestCase; - import java.security.MessageDigest; import java.security.NoSuchAlgorithmException; -import java.util.Arrays; + +import junit.framework.TestCase; /** * Tests for the MessageDigestHashFunction. * - * @author Kurt Alfred Kluever + * @author kak@google.com (Kurt Alfred Kluever) */ public class MessageDigestHashFunctionTest extends TestCase { - private static final ImmutableSet<String> INPUTS = ImmutableSet.of("", "Z", "foobar"); - private static final ImmutableSet<String> ALGORITHMS = ImmutableSet.of( - "MD5", "SHA1", "SHA-1", "SHA-256", "SHA-512"); - - public void testHashing() { - for (String stringToTest : INPUTS) { - for (String algorithmToTest : ALGORITHMS) { - assertMessageDigestHashing(HashTestUtils.ascii(stringToTest), algorithmToTest); - } - } + public void testMd5Hashing() throws Exception { + assertMessageDigestHashing(HashTestUtils.ascii(""), "MD5"); + assertMessageDigestHashing(HashTestUtils.ascii("Z"), "MD5"); + assertMessageDigestHashing(HashTestUtils.ascii("foobar"), "MD5"); } - public void testToString() { - assertEquals("Hashing.md5()", Hashing.md5().toString()); - assertEquals("Hashing.sha1()", Hashing.sha1().toString()); - assertEquals("Hashing.sha256()", Hashing.sha256().toString()); - assertEquals("Hashing.sha512()", Hashing.sha512().toString()); + public void testSha1Hashing() throws Exception { + assertMessageDigestHashing(HashTestUtils.ascii(""), "SHA1"); + assertMessageDigestHashing(HashTestUtils.ascii("Z"), "SHA1"); + assertMessageDigestHashing(HashTestUtils.ascii("foobar"), "SHA1"); } - private static void assertMessageDigestHashing(byte[] input, String algorithmName) { - try { - MessageDigest digest = MessageDigest.getInstance(algorithmName); - assertEquals( - HashCodes.fromBytes(digest.digest(input)), - new MessageDigestHashFunction(algorithmName, algorithmName).hashBytes(input)); - for (int bytes = 4; bytes <= digest.getDigestLength(); bytes++) { - assertEquals( - HashCodes.fromBytes(Arrays.copyOf(digest.digest(input), bytes)), - new MessageDigestHashFunction(algorithmName, bytes, algorithmName).hashBytes(input)); - } - try { - int maxSize = digest.getDigestLength(); - new MessageDigestHashFunction(algorithmName, maxSize + 1, algorithmName); - fail(); - } catch (IllegalArgumentException expected) { - } - } catch (NoSuchAlgorithmException nsae) { - throw new AssertionError(nsae); - } + private static void assertMessageDigestHashing(byte[] input, String algorithmName) + throws NoSuchAlgorithmException { + HashTestUtils.assertEqualHashes( + MessageDigest.getInstance(algorithmName).digest(input), + new MessageDigestHashFunction(algorithmName).hashBytes(input).asBytes()); } } diff --git a/guava-tests/test/com/google/common/hash/Murmur3Hash128Test.java b/guava-tests/test/com/google/common/hash/Murmur3Hash128Test.java index ab319fb..4a4eea7 100644 --- a/guava-tests/test/com/google/common/hash/Murmur3Hash128Test.java +++ b/guava-tests/test/com/google/common/hash/Murmur3Hash128Test.java @@ -16,55 +16,44 @@ package com.google.common.hash; +import static com.google.common.hash.HashTestUtils.ascii; +import static com.google.common.hash.HashTestUtils.toBytes; import static com.google.common.hash.Hashing.murmur3_128; +import static java.nio.ByteOrder.LITTLE_ENDIAN; -import com.google.common.base.Charsets; import com.google.common.hash.Funnels; import com.google.common.hash.HashTestUtils.HashFn; import junit.framework.TestCase; -import java.nio.ByteBuffer; -import java.nio.ByteOrder; +import java.util.Arrays; /** - * Tests for {@link Murmur3_128HashFunction}. + * Tests for Murmur3Hash128. */ public class Murmur3Hash128Test extends TestCase { - public void testKnownValues() { - assertHash(0, 0x629942693e10f867L, 0x92db0b82baeb5347L, "hell"); - assertHash(1, 0xa78ddff5adae8d10L, 0x128900ef20900135L, "hello"); - assertHash(2, 0x8a486b23f422e826L, 0xf962a2c58947765fL, "hello "); - assertHash(3, 0x2ea59f466f6bed8cL, 0xc610990acc428a17L, "hello w"); - assertHash(4, 0x79f6305a386c572cL, 0x46305aed3483b94eL, "hello wo"); - assertHash(5, 0xc2219d213ec1f1b5L, 0xa1d8e2e0a52785bdL, "hello wor"); - assertHash(0, 0xe34bbc7bbc071b6cL, 0x7a433ca9c49a9347L, - "The quick brown fox jumps over the lazy dog"); - assertHash(0, 0x658ca970ff85269aL, 0x43fee3eaa68e5c3eL, - "The quick brown fox jumps over the lazy cog"); - - // Known output from Python smhasher - HashCode foxHash = - murmur3_128(0).hashString("The quick brown fox jumps over the lazy dog", Charsets.UTF_8); - assertEquals("6c1b07bc7bbc4be347939ac4a93c437a", foxHash.toString()); - } - - private static void assertHash(int seed, long expected1, long expected2, String stringInput) { - HashCode expected = toHashCode(expected1, expected2); - byte[] input = HashTestUtils.ascii(stringInput); - assertEquals(expected, murmur3_128(seed).hashBytes(input)); - assertEquals(expected, murmur3_128(seed).newHasher().putBytes(input).hash()); + public void testCompatibilityWithCPlusPlus() { + assertHash(0, toBytes(LITTLE_ENDIAN, 0x629942693e10f867L, 0x92db0b82baeb5347L), + ascii("hell")); + assertHash(1, toBytes(LITTLE_ENDIAN, 0xa78ddff5adae8d10L, 0x128900ef20900135L), + ascii("hello")); + assertHash(2, toBytes(LITTLE_ENDIAN, 0x8a486b23f422e826L, 0xf962a2c58947765fL), + ascii("hello ")); + assertHash(3, toBytes(LITTLE_ENDIAN, 0x2ea59f466f6bed8cL, 0xc610990acc428a17L), + ascii("hello w")); + assertHash(4, toBytes(LITTLE_ENDIAN, 0x79f6305a386c572cL, 0x46305aed3483b94eL), + ascii("hello wo")); + assertHash(5, toBytes(LITTLE_ENDIAN, 0xc2219d213ec1f1b5L, 0xa1d8e2e0a52785bdL), + ascii("hello wor")); + assertHash(0, toBytes(LITTLE_ENDIAN, 0xe34bbc7bbc071b6cL, 0x7a433ca9c49a9347L), + ascii("The quick brown fox jumps over the lazy dog")); + assertHash(0, toBytes(LITTLE_ENDIAN, 0x658ca970ff85269aL, 0x43fee3eaa68e5c3eL), + ascii("The quick brown fox jumps over the lazy cog")); } - - /** - * Returns a {@link HashCode} for a sequence of longs, in big-endian order. - */ - private static HashCode toHashCode(long... longs) { - ByteBuffer bb = ByteBuffer.wrap(new byte[longs.length * 8]).order(ByteOrder.LITTLE_ENDIAN); - for (long x : longs) { - bb.putLong(x); - } - return HashCodes.fromBytes(bb.array()); + + private static void assertHash(int seed, byte[] expectedHash, byte[] input) { + byte[] hash = murmur3_128(seed).newHasher().putBytes(input).hash().asBytes(); + assertTrue(Arrays.equals(expectedHash, hash)); } public void testParanoid() { @@ -75,12 +64,8 @@ public class Murmur3Hash128Test extends TestCase { return hasher.hash().asBytes(); } }; - // Murmur3F, MurmurHash3 for x64, 128-bit (MurmurHash3_x64_128) - // From http://code.google.com/p/smhasher/source/browse/trunk/main.cpp + // the magic number comes from: + // http://code.google.com/p/smhasher/source/browse/trunk/main.cpp, #74 HashTestUtils.verifyHashFunction(hf, 128, 0x6384BA69); } - - public void testInvariants() { - HashTestUtils.assertInvariants(murmur3_128()); - } } diff --git a/guava-tests/test/com/google/common/hash/Murmur3Hash32Test.java b/guava-tests/test/com/google/common/hash/Murmur3Hash32Test.java index dcd57ae..541b53a 100644 --- a/guava-tests/test/com/google/common/hash/Murmur3Hash32Test.java +++ b/guava-tests/test/com/google/common/hash/Murmur3Hash32Test.java @@ -24,38 +24,9 @@ import com.google.common.hash.HashTestUtils.HashFn; import junit.framework.TestCase; /** - * Tests for {@link Murmur3_32HashFunction}. + * Tests for Murmur3Hash32. */ public class Murmur3Hash32Test extends TestCase { - public void testKnownIntegerInputs() { - assertHash(593689054, murmur3_32().hashInt(0)); - assertHash(-189366624, murmur3_32().hashInt(-42)); - assertHash(-1134849565, murmur3_32().hashInt(42)); - assertHash(-1718298732, murmur3_32().hashInt(Integer.MIN_VALUE)); - assertHash(-1653689534, murmur3_32().hashInt(Integer.MAX_VALUE)); - } - - public void testKnownLongInputs() { - assertHash(1669671676, murmur3_32().hashLong(0L)); - assertHash(-846261623, murmur3_32().hashLong(-42L)); - assertHash(1871679806, murmur3_32().hashLong(42L)); - assertHash(1366273829, murmur3_32().hashLong(Long.MIN_VALUE)); - assertHash(-2106506049, murmur3_32().hashLong(Long.MAX_VALUE)); - } - - public void testKnownStringInputs() { - assertHash(0, murmur3_32().hashString("")); - assertHash(679745764, murmur3_32().hashString("k")); - assertHash(1510782915, murmur3_32().hashString("hell")); - assertHash(-675079799, murmur3_32().hashString("hello")); - assertHash(1935035788, murmur3_32().hashString("http://www.google.com/")); - assertHash(-528633700, murmur3_32().hashString("The quick brown fox jumps over the lazy dog")); - } - - private static void assertHash(int expected, HashCode actual) { - assertEquals(HashCodes.fromInt(expected), actual); - } - public void testParanoid() { HashFn hf = new HashFn() { @Override public byte[] hash(byte[] input, int seed) { @@ -64,12 +35,8 @@ public class Murmur3Hash32Test extends TestCase { return hasher.hash().asBytes(); } }; - // Murmur3A, MurmurHash3 for x86, 32-bit (MurmurHash3_x86_32) - // http://code.google.com/p/smhasher/source/browse/trunk/main.cpp + // the magic number comes from: + // http://code.google.com/p/smhasher/source/browse/trunk/main.cpp, #72 HashTestUtils.verifyHashFunction(hf, 32, 0xB0F57EE3); } - - public void testInvariants() { - HashTestUtils.assertInvariants(murmur3_32()); - } } diff --git a/guava-tests/test/com/google/common/hash/PackageSanityTests.java b/guava-tests/test/com/google/common/hash/PackageSanityTests.java deleted file mode 100644 index a752a33..0000000 --- a/guava-tests/test/com/google/common/hash/PackageSanityTests.java +++ /dev/null @@ -1,35 +0,0 @@ -/* - * Copyright (C) 2012 The Guava Authors - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package com.google.common.hash; - -import com.google.common.hash.BloomFilterStrategies.BitArray; -import com.google.common.testing.AbstractPackageSanityTests; - -/** - * Basic sanity tests for the entire package. - * - * @author Ben Yu - */ - -public class PackageSanityTests extends AbstractPackageSanityTests { - public PackageSanityTests() { - setDefault(BitArray.class, new BitArray(1)); - setDefault(HashCode.class, HashCodes.fromInt(1)); - setDefault(String.class, "MD5"); - setDefault(int.class, 32); - } -} |