1/*
2 * Copyright (C) 2011 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.google.common.hash;
18
19import static com.google.common.base.Charsets.UTF_16LE;
20
21import com.google.common.collect.Iterables;
22import com.google.common.collect.Lists;
23import com.google.common.hash.AbstractStreamingHashFunction.AbstractStreamingHasher;
24import com.google.common.hash.HashTestUtils.RandomHasherAction;
25import com.google.common.jdk5backport.Arrays;
26
27import junit.framework.TestCase;
28
29import java.io.ByteArrayOutputStream;
30import java.io.UnsupportedEncodingException;
31import java.nio.ByteBuffer;
32import java.nio.ByteOrder;
33import java.nio.charset.Charset;
34import java.util.Collections;
35import java.util.List;
36import java.util.Random;
37
38/**
39 * Tests for AbstractStreamingHasher.
40 *
41 * @author Dimitris Andreou
42 */
43public class AbstractStreamingHasherTest extends TestCase {
44  public void testBytes() {
45    Sink sink = new Sink(4); // byte order insignificant here
46    byte[] expected = { 1, 2, 3, 4, 5, 6, 7, 8 };
47    sink.putByte((byte) 1);
48    sink.putBytes(new byte[] { 2, 3, 4, 5, 6 });
49    sink.putByte((byte) 7);
50    sink.putBytes(new byte[] {});
51    sink.putBytes(new byte[] { 8 });
52    sink.hash();
53    sink.assertInvariants(8);
54    sink.assertBytes(expected);
55  }
56
57  public void testShort() {
58    Sink sink = new Sink(4);
59    sink.putShort((short) 0x0201);
60    sink.hash();
61    sink.assertInvariants(2);
62    sink.assertBytes(new byte[] { 1, 2, 0, 0 }); // padded with zeros
63  }
64
65  public void testInt() {
66    Sink sink = new Sink(4);
67    sink.putInt(0x04030201);
68    sink.hash();
69    sink.assertInvariants(4);
70    sink.assertBytes(new byte[] { 1, 2, 3, 4 });
71  }
72
73  public void testLong() {
74    Sink sink = new Sink(8);
75    sink.putLong(0x0807060504030201L);
76    sink.hash();
77    sink.assertInvariants(8);
78    sink.assertBytes(new byte[] { 1, 2, 3, 4, 5, 6, 7, 8 });
79  }
80
81  public void testChar() {
82    Sink sink = new Sink(4);
83    sink.putChar((char) 0x0201);
84    sink.hash();
85    sink.assertInvariants(2);
86    sink.assertBytes(new byte[] { 1, 2, 0, 0  }); // padded with zeros
87  }
88
89  public void testString() throws UnsupportedEncodingException {
90    Random random = new Random();
91    for (int i = 0; i < 100; i++) {
92      byte[] bytes = new byte[64];
93      random.nextBytes(bytes);
94      String s = new String(bytes, UTF_16LE.name()); // so all random strings are valid
95      assertEquals(
96          new Sink(4).putString(s).hash(),
97          new Sink(4).putBytes(s.getBytes(UTF_16LE.name())).hash());
98      assertEquals(
99          new Sink(4).putString(s).hash(),
100          new Sink(4).putString(s, UTF_16LE).hash());
101    }
102  }
103
104  public void testFloat() {
105    Sink sink = new Sink(4);
106    sink.putFloat(Float.intBitsToFloat(0x04030201));
107    sink.hash();
108    sink.assertInvariants(4);
109    sink.assertBytes(new byte[] { 1, 2, 3, 4 });
110  }
111
112  public void testDouble() {
113    Sink sink = new Sink(8);
114    sink.putDouble(Double.longBitsToDouble(0x0807060504030201L));
115    sink.hash();
116    sink.assertInvariants(8);
117    sink.assertBytes(new byte[] { 1, 2, 3, 4, 5, 6, 7, 8 });
118  }
119
120  public void testCorrectExceptions() {
121    Sink sink = new Sink(4);
122    try {
123      sink.putBytes(new byte[8], -1, 4);
124      fail();
125    } catch (IndexOutOfBoundsException ok) {}
126    try {
127      sink.putBytes(new byte[8], 0, 16);
128      fail();
129    } catch (IndexOutOfBoundsException ok) {}
130    try {
131      sink.putBytes(new byte[8], 0, -1);
132      fail();
133    } catch (IndexOutOfBoundsException ok) {}
134  }
135
136  /**
137   * This test creates a long random sequence of inputs, then a lot of differently configured
138   * sinks process it; all should produce the same answer, the only difference should be the
139   * number of process()/processRemaining() invocations, due to alignment.
140   */
141  public void testExhaustive() throws Exception {
142    Random random = new Random(0); // will iteratively make more debuggable, each time it breaks
143    for (int totalInsertions = 0; totalInsertions < 200; totalInsertions++) {
144
145      List<Sink> sinks = Lists.newArrayList();
146      for (int chunkSize = 4; chunkSize <= 32; chunkSize++) {
147        for (int bufferSize = chunkSize; bufferSize <= chunkSize * 4; bufferSize += chunkSize) {
148          // yes, that's a lot of sinks!
149          sinks.add(new Sink(chunkSize, bufferSize));
150          // For convenience, testing only with big endianness, to match DataOutputStream.
151          // I regard highly unlikely that both the little endianness tests above and this one
152          // passes, and there is still a little endianness bug lurking around.
153        }
154      }
155
156      Control control = new Control();
157      Hasher controlSink = control.newHasher(1024);
158
159      Iterable<Hasher> sinksAndControl =
160          Iterables.concat(sinks, Collections.singleton(controlSink));
161      for (int insertion = 0; insertion < totalInsertions; insertion++) {
162        RandomHasherAction.pickAtRandom(random).performAction(random, sinksAndControl);
163      }
164      // We need to ensure that at least 4 bytes have been put into the hasher or else
165      // Hasher#hash will throw an ISE.
166      int intToPut = random.nextInt();
167      for (Hasher hasher : sinksAndControl) {
168        hasher.putInt(intToPut);
169      }
170      for (Sink sink : sinks) {
171        sink.hash();
172      }
173
174      byte[] expected = controlSink.hash().asBytes();
175      for (Sink sink : sinks) {
176        sink.assertInvariants(expected.length);
177        sink.assertBytes(expected);
178      }
179    }
180  }
181
182  private static class Sink extends AbstractStreamingHasher {
183    final int chunkSize;
184    final int bufferSize;
185    final ByteArrayOutputStream out = new ByteArrayOutputStream();
186
187    int processCalled = 0;
188    boolean remainingCalled = false;
189
190    Sink(int chunkSize, int bufferSize) {
191      super(chunkSize, bufferSize);
192      this.chunkSize = chunkSize;
193      this.bufferSize = bufferSize;
194    }
195
196    Sink(int chunkSize) {
197      super(chunkSize);
198      this.chunkSize = chunkSize;
199      this.bufferSize = chunkSize;
200    }
201
202    @Override HashCode makeHash() {
203      return HashCode.fromBytes(out.toByteArray());
204    }
205
206    @Override protected void process(ByteBuffer bb) {
207      processCalled++;
208      assertEquals(ByteOrder.LITTLE_ENDIAN, bb.order());
209      assertTrue(bb.remaining() >= chunkSize);
210      for (int i = 0; i < chunkSize; i++) {
211        out.write(bb.get());
212      }
213    }
214
215    @Override protected void processRemaining(ByteBuffer bb) {
216      assertFalse(remainingCalled);
217      remainingCalled = true;
218      assertEquals(ByteOrder.LITTLE_ENDIAN, bb.order());
219      assertTrue(bb.remaining() > 0);
220      assertTrue(bb.remaining() < bufferSize);
221      int before = processCalled;
222      super.processRemaining(bb);
223      int after = processCalled;
224      assertEquals(before + 1, after); // default implementation pads and calls process()
225      processCalled--; // don't count the tail invocation (makes tests a bit more understandable)
226    }
227
228    // ensures that the number of invocations looks sane
229    void assertInvariants(int expectedBytes) {
230      // we should have seen as many bytes as the next multiple of chunk after expectedBytes - 1
231      assertEquals(out.toByteArray().length, ceilToMultiple(expectedBytes, chunkSize));
232      assertEquals(expectedBytes / chunkSize, processCalled);
233      assertEquals(expectedBytes % chunkSize != 0, remainingCalled);
234    }
235
236    // returns the minimum x such as x >= a && (x % b) == 0
237    private static int ceilToMultiple(int a, int b) {
238      int remainder = a % b;
239      return remainder == 0 ? a : a + b - remainder;
240    }
241
242    void assertBytes(byte[] expected) {
243      byte[] got = out.toByteArray();
244      for (int i = 0; i < expected.length; i++) {
245        assertEquals(expected[i], got[i]);
246      }
247    }
248  }
249
250  // Assumes that AbstractNonStreamingHashFunction works properly (must be tested elsewhere!)
251  private static class Control extends AbstractNonStreamingHashFunction {
252    @Override
253    public HashCode hashBytes(byte[] input) {
254      return HashCode.fromBytes(input);
255    }
256
257    @Override
258    public HashCode hashBytes(byte[] input, int off, int len) {
259      return hashBytes(Arrays.copyOfRange(input, off, off + len));
260    }
261
262    @Override
263    public int bits() {
264      throw new UnsupportedOperationException();
265    }
266
267    @Override
268    public HashCode hashString(CharSequence input) {
269      throw new UnsupportedOperationException();
270    }
271
272    @Override
273    public HashCode hashString(CharSequence input, Charset charset) {
274      throw new UnsupportedOperationException();
275    }
276
277    @Override
278    public HashCode hashLong(long input) {
279      throw new UnsupportedOperationException();
280    }
281
282    @Override
283    public HashCode hashInt(int input) {
284      throw new UnsupportedOperationException();
285    }
286  }
287}
288