1 // Copyright 2013 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.
18 func TestMemHash32Equality(t
*testing
.T
) {
20 t
.Skip("skipping since AES hash implementation is used")
23 r
:= rand
.New(rand
.NewSource(1234))
24 seed
:= uintptr(r
.Uint64())
25 for i
:= 0; i
< 100; i
++ {
27 got
:= MemHash32(unsafe
.Pointer(&b
), seed
)
28 want
:= MemHash(unsafe
.Pointer(&b
), seed
, 4)
30 t
.Errorf("MemHash32(%x, %v) = %v; want %v", b
, seed
, got
, want
)
35 func TestMemHash64Equality(t
*testing
.T
) {
37 t
.Skip("skipping since AES hash implementation is used")
40 r
:= rand
.New(rand
.NewSource(1234))
41 seed
:= uintptr(r
.Uint64())
42 for i
:= 0; i
< 100; i
++ {
44 got
:= MemHash64(unsafe
.Pointer(&b
), seed
)
45 want
:= MemHash(unsafe
.Pointer(&b
), seed
, 8)
47 t
.Errorf("MemHash64(%x, %v) = %v; want %v", b
, seed
, got
, want
)
52 func TestCompilerVsRuntimeHash(t
*testing
.T
) {
53 // Test to make sure the compiler's hash function and the runtime's hash function agree.
55 for _
, m
:= range []interface{}{
70 map[unsafe
.Pointer
]int{},
76 //map[interface{}]int{},
77 //map[interface{F()}]int{},
80 map[struct{ a
, b
, c
, d
int32 }]int{}, // Note: tests AMEM128
81 map[struct{ a
, b
, _
, d
int32 }]int{},
92 k
:= reflect
.New(reflect
.TypeOf(m
).Key()).Elem().Interface() // the zero key
93 x
, y
:= MapHashCheck(m
, k
)
95 t
.Errorf("hashes did not match (%x vs %x) for map %T", x
, y
, m
)
100 // Smhasher is a torture test for hash functions.
101 // https://code.google.com/p/smhasher/
102 // This code is a port of some of the Smhasher tests to Go.
104 // The current AES hash function passes Smhasher. Our fallback
105 // hash functions don't, so we only enable the difficult tests when
106 // we know the AES implementation is available.
109 // hash should not depend on values outside key.
110 // hash should not depend on alignment.
111 func TestSmhasherSanity(t
*testing
.T
) {
112 r
:= rand
.New(rand
.NewSource(1234))
117 for k
:= 0; k
< REP
; k
++ {
118 for n
:= 0; n
< KEYMAX
; n
++ {
119 for i
:= 0; i
< OFFMAX
; i
++ {
120 var b
[KEYMAX
+ OFFMAX
+ 2*PAD
]byte
121 var c
[KEYMAX
+ OFFMAX
+ 2*PAD
]byte
124 copy(c
[PAD
+i
:PAD
+i
+n
], b
[PAD
:PAD
+n
])
125 if BytesHash(b
[PAD
:PAD
+n
], 0) != BytesHash(c
[PAD
+i
:PAD
+i
+n
], 0) {
126 t
.Errorf("hash depends on bytes outside key")
133 type HashSet
struct {
134 m
map[uintptr]struct{} // set of hashes added
135 n
int // number of hashes added
138 func newHashSet() *HashSet
{
139 return &HashSet
{make(map[uintptr]struct{}), 0}
141 func (s
*HashSet
) add(h
uintptr) {
145 func (s
*HashSet
) addS(x
string) {
146 s
.add(StringHash(x
, 0))
148 func (s
*HashSet
) addB(x
[]byte) {
149 s
.add(BytesHash(x
, 0))
151 func (s
*HashSet
) addS_seed(x
string, seed
uintptr) {
152 s
.add(StringHash(x
, seed
))
154 func (s
*HashSet
) check(t
*testing
.T
) {
156 collisions
:= s
.n
- len(s
.m
)
157 //fmt.Printf("%d/%d\n", len(s.m), s.n)
158 pairs
:= int64(s
.n
) * int64(s
.n
-1) / 2
159 expected
:= float64(pairs
) / math
.Pow(2.0, float64(hashSize
))
160 stddev
:= math
.Sqrt(expected
)
161 if float64(collisions
) > expected
+SLOP
*(3*stddev
+1) {
162 t
.Errorf("unexpected number of collisions: got=%d mean=%f stddev=%f", collisions
, expected
, stddev
)
166 // a string plus adding zeros must make distinct hashes
167 func TestSmhasherAppendedZeros(t
*testing
.T
) {
168 s
:= "hello" + strings
.Repeat("\x00", 256)
170 for i
:= 0; i
<= len(s
); i
++ {
176 // All 0-3 byte strings have distinct hashes.
177 func TestSmhasherSmallKeys(t
*testing
.T
) {
180 for i
:= 0; i
< 256; i
++ {
183 for j
:= 0; j
< 256; j
++ {
186 if !testing
.Short() {
187 for k
:= 0; k
< 256; k
++ {
197 // Different length strings of all zeros have distinct hashes.
198 func TestSmhasherZeros(t
*testing
.T
) {
205 for i
:= 0; i
<= N
; i
++ {
211 // Strings with up to two nonzero bytes all have distinct hashes.
212 func TestSmhasherTwoNonzero(t
*testing
.T
) {
213 if GOARCH
== "wasm" {
214 t
.Skip("Too slow on wasm")
217 t
.Skip("Skipping in short mode")
220 for n
:= 2; n
<= 16; n
++ {
225 func twoNonZero(h
*HashSet
, n
int) {
232 for i
:= 0; i
< n
; i
++ {
233 for x
:= 1; x
< 256; x
++ {
240 // two non-zero bytes
241 for i
:= 0; i
< n
; i
++ {
242 for x
:= 1; x
< 256; x
++ {
244 for j
:= i
+ 1; j
< n
; j
++ {
245 for y
:= 1; y
< 256; y
++ {
256 // Test strings with repeats, like "abcdabcdabcdabcd..."
257 func TestSmhasherCyclic(t
*testing
.T
) {
259 t
.Skip("Skipping in short mode")
261 r
:= rand
.New(rand
.NewSource(1234))
264 for n
:= 4; n
<= 12; n
++ {
266 b
:= make([]byte, REPEAT
*n
)
267 for i
:= 0; i
< N
; i
++ {
268 b
[0] = byte(i
* 79 % 97)
269 b
[1] = byte(i
* 43 % 137)
270 b
[2] = byte(i
* 151 % 197)
271 b
[3] = byte(i
* 199 % 251)
273 for j
:= n
; j
< n
*REPEAT
; j
++ {
282 // Test strings with only a few bits set
283 func TestSmhasherSparse(t
*testing
.T
) {
284 if GOARCH
== "wasm" {
285 t
.Skip("Too slow on wasm")
288 t
.Skip("Skipping in short mode")
299 func sparse(t
*testing
.T
, n
int, k
int) {
300 b
:= make([]byte, n
/8)
306 // set up to k bits at index i and greater
307 func setbits(h
*HashSet
, b
[]byte, i
int, k
int) {
312 for j
:= i
; j
< len(b
)*8; j
++ {
313 b
[j
/8] |
= byte(1 << uint(j
&7))
314 setbits(h
, b
, j
+1, k
-1)
315 b
[j
/8] &= byte(^(1 << uint(j
&7)))
319 // Test all possible combinations of n blocks from the set s.
320 // "permutation" is a bad name here, but it is what Smhasher uses.
321 func TestSmhasherPermutation(t
*testing
.T
) {
322 if GOARCH
== "wasm" {
323 t
.Skip("Too slow on wasm")
326 t
.Skip("Skipping in short mode")
328 permutation(t
, []uint32{0, 1, 2, 3, 4, 5, 6, 7}, 8)
329 permutation(t
, []uint32{0, 1 << 29, 2 << 29, 3 << 29, 4 << 29, 5 << 29, 6 << 29, 7 << 29}, 8)
330 permutation(t
, []uint32{0, 1}, 20)
331 permutation(t
, []uint32{0, 1 << 31}, 20)
332 permutation(t
, []uint32{0, 1, 2, 3, 4, 5, 6, 7, 1 << 29, 2 << 29, 3 << 29, 4 << 29, 5 << 29, 6 << 29, 7 << 29}, 6)
334 func permutation(t
*testing
.T
, s
[]uint32, n
int) {
335 b
:= make([]byte, n
*4)
340 func genPerm(h
*HashSet
, b
[]byte, s
[]uint32, n
int) {
345 for _
, v
:= range s
{
347 b
[n
+1] = byte(v
>> 8)
348 b
[n
+2] = byte(v
>> 16)
349 b
[n
+3] = byte(v
>> 24)
350 genPerm(h
, b
, s
, n
+4)
355 clear() // set bits all to 0
356 random(r
*rand
.Rand
) // set key to something random
357 bits() int // how many bits key has
358 flipBit(i
int) // flip bit i of the key
359 hash() uintptr // hash the key
360 name() string // for error reporting
363 type BytesKey
struct {
367 func (k
*BytesKey
) clear() {
372 func (k
*BytesKey
) random(r
*rand
.Rand
) {
375 func (k
*BytesKey
) bits() int {
378 func (k
*BytesKey
) flipBit(i
int) {
379 k
.b
[i
>>3] ^= byte(1 << uint(i
&7))
381 func (k
*BytesKey
) hash() uintptr {
382 return BytesHash(k
.b
, 0)
384 func (k
*BytesKey
) name() string {
385 return fmt
.Sprintf("bytes%d", len(k
.b
))
388 type Int32Key
struct {
392 func (k
*Int32Key
) clear() {
395 func (k
*Int32Key
) random(r
*rand
.Rand
) {
398 func (k
*Int32Key
) bits() int {
401 func (k
*Int32Key
) flipBit(i
int) {
404 func (k
*Int32Key
) hash() uintptr {
405 return Int32Hash(k
.i
, 0)
407 func (k
*Int32Key
) name() string {
411 type Int64Key
struct {
415 func (k
*Int64Key
) clear() {
418 func (k
*Int64Key
) random(r
*rand
.Rand
) {
419 k
.i
= uint64(r
.Uint32()) + uint64(r
.Uint32())<<32
421 func (k
*Int64Key
) bits() int {
424 func (k
*Int64Key
) flipBit(i
int) {
427 func (k
*Int64Key
) hash() uintptr {
428 return Int64Hash(k
.i
, 0)
430 func (k
*Int64Key
) name() string {
434 type EfaceKey
struct {
438 func (k
*EfaceKey
) clear() {
441 func (k
*EfaceKey
) random(r
*rand
.Rand
) {
442 k
.i
= uint64(r
.Int63())
444 func (k
*EfaceKey
) bits() int {
445 // use 64 bits. This tests inlined interfaces
446 // on 64-bit targets and indirect interfaces on
450 func (k
*EfaceKey
) flipBit(i
int) {
451 k
.i
= k
.i
.(uint64) ^ uint64(1)<<uint(i
)
453 func (k
*EfaceKey
) hash() uintptr {
454 return EfaceHash(k
.i
, 0)
456 func (k
*EfaceKey
) name() string {
460 type IfaceKey
struct {
467 func (x fInter
) F() {
470 func (k
*IfaceKey
) clear() {
473 func (k
*IfaceKey
) random(r
*rand
.Rand
) {
474 k
.i
= fInter(r
.Int63())
476 func (k
*IfaceKey
) bits() int {
477 // use 64 bits. This tests inlined interfaces
478 // on 64-bit targets and indirect interfaces on
482 func (k
*IfaceKey
) flipBit(i
int) {
483 k
.i
= k
.i
.(fInter
) ^ fInter(1)<<uint(i
)
485 func (k
*IfaceKey
) hash() uintptr {
486 return IfaceHash(k
.i
, 0)
488 func (k
*IfaceKey
) name() string {
492 // Flipping a single bit of a key should flip each output bit with 50% probability.
493 func TestSmhasherAvalanche(t
*testing
.T
) {
494 if GOARCH
== "wasm" {
495 t
.Skip("Too slow on wasm")
498 t
.Skip("Skipping in short mode")
500 avalancheTest1(t
, &BytesKey
{make([]byte, 2)})
501 avalancheTest1(t
, &BytesKey
{make([]byte, 4)})
502 avalancheTest1(t
, &BytesKey
{make([]byte, 8)})
503 avalancheTest1(t
, &BytesKey
{make([]byte, 16)})
504 avalancheTest1(t
, &BytesKey
{make([]byte, 32)})
505 avalancheTest1(t
, &BytesKey
{make([]byte, 200)})
506 avalancheTest1(t
, &Int32Key
{})
507 avalancheTest1(t
, &Int64Key
{})
508 avalancheTest1(t
, &EfaceKey
{})
509 avalancheTest1(t
, &IfaceKey
{})
511 func avalancheTest1(t
*testing
.T
, k Key
) {
513 r
:= rand
.New(rand
.NewSource(1234))
516 // grid[i][j] is a count of whether flipping
517 // input bit i affects output bit j.
518 grid
:= make([][hashSize
]int, n
)
520 for z
:= 0; z
< REP
; z
++ {
521 // pick a random key, hash it
525 // flip each bit, hash & compare the results
526 for i
:= 0; i
< n
; i
++ {
531 // record the effects of that bit flip
533 for j
:= 0; j
< hashSize
; j
++ {
540 // Each entry in the grid should be about REP/2.
541 // More precisely, we did N = k.bits() * hashSize experiments where
542 // each is the sum of REP coin flips. We want to find bounds on the
543 // sum of coin flips such that a truly random experiment would have
544 // all sums inside those bounds with 99% probability.
547 // find c such that Prob(mean-c*stddev < x < mean+c*stddev)^N > .9999
548 for c
= 0.0; math
.Pow(math
.Erf(c
/math
.Sqrt(2)), float64(N
)) < .9999; c
+= .1 {
550 c
*= 4.0 // allowed slack - we don't need to be perfectly random
552 stddev
:= .5 * math
.Sqrt(REP
)
553 low
:= int(mean
- c
*stddev
)
554 high
:= int(mean
+ c
*stddev
)
555 for i
:= 0; i
< n
; i
++ {
556 for j
:= 0; j
< hashSize
; j
++ {
558 if x
< low || x
> high
{
559 t
.Errorf("bad bias for %s bit %d -> bit %d: %d/%d\n", k
.name(), i
, j
, x
, REP
)
565 // All bit rotations of a set of distinct keys
566 func TestSmhasherWindowed(t
*testing
.T
) {
567 windowed(t
, &Int32Key
{})
568 windowed(t
, &Int64Key
{})
569 windowed(t
, &BytesKey
{make([]byte, 128)})
571 func windowed(t
*testing
.T
, k Key
) {
572 if GOARCH
== "wasm" {
573 t
.Skip("Too slow on wasm")
576 t
.Skip("Skipping in short mode")
580 for r
:= 0; r
< k
.bits(); r
++ {
582 for i
:= 0; i
< 1<<BITS
; i
++ {
584 for j
:= 0; j
< BITS
; j
++ {
585 if i
>>uint(j
)&1 != 0 {
586 k
.flipBit((j
+ r
) % k
.bits())
595 // All keys of the form prefix + [A-Za-z0-9]*N + suffix.
596 func TestSmhasherText(t
*testing
.T
) {
598 t
.Skip("Skipping in short mode")
600 text(t
, "Foo", "Bar")
601 text(t
, "FooBar", "")
602 text(t
, "", "FooBar")
604 func text(t
*testing
.T
, prefix
, suffix
string) {
606 const S
= "ABCDEFGHIJKLMNOPQRSTabcdefghijklmnopqrst0123456789"
608 b
:= make([]byte, len(prefix
)+N
+len(suffix
))
610 copy(b
[len(prefix
)+N
:], suffix
)
613 for i
:= 0; i
< L
; i
++ {
615 for j
:= 0; j
< L
; j
++ {
617 for k
:= 0; k
< L
; k
++ {
619 for x
:= 0; x
< L
; x
++ {
629 // Make sure different seed values generate different hashes.
630 func TestSmhasherSeed(t
*testing
.T
) {
634 for i
:= 0; i
< N
; i
++ {
635 h
.addS_seed(s
, uintptr(i
))
640 // size of the hash output (32 or 64 bits)
641 const hashSize
= 32 + int(^uintptr(0)>>63<<5)
643 func randBytes(r
*rand
.Rand
, b
[]byte) {
645 b
[i
] = byte(r
.Uint32())
649 func benchmarkHash(b
*testing
.B
, n
int) {
650 s
:= strings
.Repeat("A", n
)
652 for i
:= 0; i
< b
.N
; i
++ {
658 func BenchmarkHash5(b
*testing
.B
) { benchmarkHash(b
, 5) }
659 func BenchmarkHash16(b
*testing
.B
) { benchmarkHash(b
, 16) }
660 func BenchmarkHash64(b
*testing
.B
) { benchmarkHash(b
, 64) }
661 func BenchmarkHash1024(b
*testing
.B
) { benchmarkHash(b
, 1024) }
662 func BenchmarkHash65536(b
*testing
.B
) { benchmarkHash(b
, 65536) }
664 func TestArrayHash(t
*testing
.T
) {
665 if Compiler
== "gccgo" {
666 t
.Skip("does not work on gccgo without better escape analysis")
669 // Make sure that "" in arrays hash correctly. The hash
670 // should at least scramble the input seed so that, e.g.,
671 // {"","foo"} and {"foo",""} have different hashes.
673 // If the hash is bad, then all (8 choose 4) = 70 keys
674 // have the same hash. If so, we allocate 70/8 = 8
675 // overflow buckets. If the hash is good we don't
676 // normally allocate any overflow buckets, and the
677 // probability of even one or two overflows goes down rapidly.
678 // (There is always 1 allocation of the bucket array. The map
679 // header is allocated on the stack.)
681 // Make the key type at most 128 bytes. Otherwise,
682 // we get an allocation per key.
684 m
:= make(map[key
]bool, 70)
686 // fill m with keys that have 4 "foo"s and 4 ""s.
687 for i
:= 0; i
< 256; i
++ {
690 for j
:= uint(0); j
< 8; j
++ {
701 t
.Errorf("bad test: (8 choose 4) should be 70, not %d", len(m
))
704 if n
:= testing
.AllocsPerRun(10, f
); n
> 6 {
705 t
.Errorf("too many allocs %f - hash not balanced", n
)
708 func TestStructHash(t
*testing
.T
) {
709 // See the comment in TestArrayHash.
712 a
, b
, c
, d
, e
, f
, g
, h
string
714 m
:= make(map[key
]bool, 70)
716 // fill m with keys that have 4 "foo"s and 4 ""s.
717 for i
:= 0; i
< 256; i
++ {
757 t
.Errorf("bad test: (8 choose 4) should be 70, not %d", len(m
))
760 if n
:= testing
.AllocsPerRun(10, f
); n
> 6 {
761 t
.Errorf("too many allocs %f - hash not balanced", n
)
767 func BenchmarkAlignedLoad(b
*testing
.B
) {
769 p
:= unsafe
.Pointer(&buf
[0])
771 for i
:= 0; i
< b
.N
; i
++ {
772 s
+= ReadUnaligned64(p
)
777 func BenchmarkUnalignedLoad(b
*testing
.B
) {
779 p
:= unsafe
.Pointer(&buf
[1])
781 for i
:= 0; i
< b
.N
; i
++ {
782 s
+= ReadUnaligned64(p
)
787 func TestCollisions(t
*testing
.T
) {
789 t
.Skip("Skipping in short mode")
791 for i
:= 0; i
< 16; i
++ {
792 for j
:= 0; j
< 16; j
++ {
797 m
:= make(map[uint16]struct{}, 1<<16)
798 for n
:= 0; n
< 1<<16; n
++ {
801 m
[uint16(BytesHash(a
[:], 0))] = struct{}{}
804 t
.Errorf("too many collisions i=%d j=%d outputs=%d out of 65536\n", i
, j
, len(m
))