1// Copyright 2019 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package maphash
6
7import (
8	"bytes"
9	"fmt"
10	"hash"
11	"testing"
12)
13
14func TestUnseededHash(t *testing.T) {
15	m := map[uint64]struct{}{}
16	for i := 0; i < 1000; i++ {
17		h := new(Hash)
18		m[h.Sum64()] = struct{}{}
19	}
20	if len(m) < 900 {
21		t.Errorf("empty hash not sufficiently random: got %d, want 1000", len(m))
22	}
23}
24
25func TestSeededHash(t *testing.T) {
26	s := MakeSeed()
27	m := map[uint64]struct{}{}
28	for i := 0; i < 1000; i++ {
29		h := new(Hash)
30		h.SetSeed(s)
31		m[h.Sum64()] = struct{}{}
32	}
33	if len(m) != 1 {
34		t.Errorf("seeded hash is random: got %d, want 1", len(m))
35	}
36}
37
38func TestHashGrouping(t *testing.T) {
39	b := bytes.Repeat([]byte("foo"), 100)
40	hh := make([]*Hash, 7)
41	for i := range hh {
42		hh[i] = new(Hash)
43	}
44	for _, h := range hh[1:] {
45		h.SetSeed(hh[0].Seed())
46	}
47	hh[0].Write(b)
48	hh[1].WriteString(string(b))
49
50	writeByte := func(h *Hash, b byte) {
51		err := h.WriteByte(b)
52		if err != nil {
53			t.Fatalf("WriteByte: %v", err)
54		}
55	}
56	writeSingleByte := func(h *Hash, b byte) {
57		_, err := h.Write([]byte{b})
58		if err != nil {
59			t.Fatalf("Write single byte: %v", err)
60		}
61	}
62	writeStringSingleByte := func(h *Hash, b byte) {
63		_, err := h.WriteString(string([]byte{b}))
64		if err != nil {
65			t.Fatalf("WriteString single byte: %v", err)
66		}
67	}
68
69	for i, x := range b {
70		writeByte(hh[2], x)
71		writeSingleByte(hh[3], x)
72		if i == 0 {
73			writeByte(hh[4], x)
74		} else {
75			writeSingleByte(hh[4], x)
76		}
77		writeStringSingleByte(hh[5], x)
78		if i == 0 {
79			writeByte(hh[6], x)
80		} else {
81			writeStringSingleByte(hh[6], x)
82		}
83	}
84
85	sum := hh[0].Sum64()
86	for i, h := range hh {
87		if sum != h.Sum64() {
88			t.Errorf("hash %d not identical to a single Write", i)
89		}
90	}
91
92	if sum1 := Bytes(hh[0].Seed(), b); sum1 != hh[0].Sum64() {
93		t.Errorf("hash using Bytes not identical to a single Write")
94	}
95
96	if sum1 := String(hh[0].Seed(), string(b)); sum1 != hh[0].Sum64() {
97		t.Errorf("hash using String not identical to a single Write")
98	}
99}
100
101func TestHashBytesVsString(t *testing.T) {
102	s := "foo"
103	b := []byte(s)
104	h1 := new(Hash)
105	h2 := new(Hash)
106	h2.SetSeed(h1.Seed())
107	n1, err1 := h1.WriteString(s)
108	if n1 != len(s) || err1 != nil {
109		t.Fatalf("WriteString(s) = %d, %v, want %d, nil", n1, err1, len(s))
110	}
111	n2, err2 := h2.Write(b)
112	if n2 != len(b) || err2 != nil {
113		t.Fatalf("Write(b) = %d, %v, want %d, nil", n2, err2, len(b))
114	}
115	if h1.Sum64() != h2.Sum64() {
116		t.Errorf("hash of string and bytes not identical")
117	}
118}
119
120func TestHashHighBytes(t *testing.T) {
121	// See issue 34925.
122	const N = 10
123	m := map[uint64]struct{}{}
124	for i := 0; i < N; i++ {
125		h := new(Hash)
126		h.WriteString("foo")
127		m[h.Sum64()>>32] = struct{}{}
128	}
129	if len(m) < N/2 {
130		t.Errorf("from %d seeds, wanted at least %d different hashes; got %d", N, N/2, len(m))
131	}
132}
133
134func TestRepeat(t *testing.T) {
135	h1 := new(Hash)
136	h1.WriteString("testing")
137	sum1 := h1.Sum64()
138
139	h1.Reset()
140	h1.WriteString("testing")
141	sum2 := h1.Sum64()
142
143	if sum1 != sum2 {
144		t.Errorf("different sum after resetting: %#x != %#x", sum1, sum2)
145	}
146
147	h2 := new(Hash)
148	h2.SetSeed(h1.Seed())
149	h2.WriteString("testing")
150	sum3 := h2.Sum64()
151
152	if sum1 != sum3 {
153		t.Errorf("different sum on the same seed: %#x != %#x", sum1, sum3)
154	}
155}
156
157func TestSeedFromSum64(t *testing.T) {
158	h1 := new(Hash)
159	h1.WriteString("foo")
160	x := h1.Sum64() // seed generated here
161	h2 := new(Hash)
162	h2.SetSeed(h1.Seed())
163	h2.WriteString("foo")
164	y := h2.Sum64()
165	if x != y {
166		t.Errorf("hashes don't match: want %x, got %x", x, y)
167	}
168}
169
170func TestSeedFromSeed(t *testing.T) {
171	h1 := new(Hash)
172	h1.WriteString("foo")
173	_ = h1.Seed() // seed generated here
174	x := h1.Sum64()
175	h2 := new(Hash)
176	h2.SetSeed(h1.Seed())
177	h2.WriteString("foo")
178	y := h2.Sum64()
179	if x != y {
180		t.Errorf("hashes don't match: want %x, got %x", x, y)
181	}
182}
183
184func TestSeedFromFlush(t *testing.T) {
185	b := make([]byte, 65)
186	h1 := new(Hash)
187	h1.Write(b) // seed generated here
188	x := h1.Sum64()
189	h2 := new(Hash)
190	h2.SetSeed(h1.Seed())
191	h2.Write(b)
192	y := h2.Sum64()
193	if x != y {
194		t.Errorf("hashes don't match: want %x, got %x", x, y)
195	}
196}
197
198func TestSeedFromReset(t *testing.T) {
199	h1 := new(Hash)
200	h1.WriteString("foo")
201	h1.Reset() // seed generated here
202	h1.WriteString("foo")
203	x := h1.Sum64()
204	h2 := new(Hash)
205	h2.SetSeed(h1.Seed())
206	h2.WriteString("foo")
207	y := h2.Sum64()
208	if x != y {
209		t.Errorf("hashes don't match: want %x, got %x", x, y)
210	}
211}
212
213// Make sure a Hash implements the hash.Hash and hash.Hash64 interfaces.
214var _ hash.Hash = &Hash{}
215var _ hash.Hash64 = &Hash{}
216
217func benchmarkSize(b *testing.B, size int) {
218	h := &Hash{}
219	buf := make([]byte, size)
220	s := string(buf)
221
222	b.Run("Write", func(b *testing.B) {
223		b.SetBytes(int64(size))
224		for i := 0; i < b.N; i++ {
225			h.Reset()
226			h.Write(buf)
227			h.Sum64()
228		}
229	})
230
231	b.Run("Bytes", func(b *testing.B) {
232		b.SetBytes(int64(size))
233		seed := h.Seed()
234		for i := 0; i < b.N; i++ {
235			Bytes(seed, buf)
236		}
237	})
238
239	b.Run("String", func(b *testing.B) {
240		b.SetBytes(int64(size))
241		seed := h.Seed()
242		for i := 0; i < b.N; i++ {
243			String(seed, s)
244		}
245	})
246}
247
248func BenchmarkHash(b *testing.B) {
249	sizes := []int{4, 8, 16, 32, 64, 256, 320, 1024, 4096, 16384}
250	for _, size := range sizes {
251		b.Run(fmt.Sprint("n=", size), func(b *testing.B) {
252			benchmarkSize(b, size)
253		})
254	}
255}
256