runtime: aeshash, xor seed in earlier

Instead of doing:

x = input
one round of aes on x
x ^= seed
two rounds of aes on x

Do:

x = input
x ^= seed
three rounds of aes on x

This change provides some additional seed-dependent scrambling
which should help prevent collisions.

Change-Id: I02c774d09c2eb6917cf861513816a1024a9b65d7
Reviewed-on: https://go-review.googlesource.com/23577
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

1 files changed, 20 insertions, 0 deletions

diff --git a/src/runtime/hash_test.go b/src/runtime/hash_test.go
index 96ed68247e..3108b3bf59 100644
--- a/src/runtime/hash_test.go
+++ b/src/runtime/hash_test.go
@@ -681,3 +681,23 @@ func BenchmarkUnalignedLoad(b *testing.B) {
 	}
 	sink = s
 }
+
+func TestCollisions(t *testing.T) {
+	for i := 0; i < 16; i++ {
+		for j := 0; j < 16; j++ {
+			if j == i {
+				continue
+			}
+			var a [16]byte
+			m := make(map[uint16]struct{}, 1<<16)
+			for n := 0; n < 1<<16; n++ {
+				a[i] = byte(n)
+				a[j] = byte(n >> 8)
+				m[uint16(BytesHash(a[:], 0))] = struct{}{}
+			}
+			if len(m) <= 1<<15 {
+				t.Errorf("too many collisions i=%d j=%d outputs=%d out of 65536\n", i, j, len(m))
+			}
+		}
+	}
+}