Source file src/runtime/hash_test.go

     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.
     4  
     5  package runtime_test
     6  
     7  import (
     8  	"encoding/binary"
     9  	"fmt"
    10  	"internal/byteorder"
    11  	"internal/race"
    12  	"internal/testenv"
    13  	"math"
    14  	"math/rand"
    15  	"os"
    16  	. "runtime"
    17  	"slices"
    18  	"strings"
    19  	"testing"
    20  	"unsafe"
    21  )
    22  
    23  // Test that unalgined access to memhash32 doesn't cause a problem.
    24  func TestMemHash32AlignAccess(t *testing.T) {
    25  	type Key struct {
    26  		_ [1]byte
    27  		k [4]byte
    28  		_ [3]byte
    29  	}
    30  	key := Key{}
    31  	sink = (uint64)(MemHash32(unsafe.Pointer(&key.k), 0))
    32  }
    33  
    34  func TestMemHash32Equality(t *testing.T) {
    35  	if *UseAeshash {
    36  		t.Skip("skipping since AES hash implementation is used")
    37  	}
    38  	var b [4]byte
    39  	r := rand.New(rand.NewSource(1234))
    40  	seed := uintptr(r.Uint64())
    41  	for i := 0; i < 100; i++ {
    42  		randBytes(r, b[:])
    43  		got := MemHash32(unsafe.Pointer(&b), seed)
    44  		want := MemHash(unsafe.Pointer(&b), seed, 4)
    45  		if got != want {
    46  			t.Errorf("MemHash32(%x, %v) = %v; want %v", b, seed, got, want)
    47  		}
    48  	}
    49  }
    50  
    51  // Test that unalgined access to memhash64 doesn't cause a problem.
    52  func TestMemHash64AlignAccess(t *testing.T) {
    53  	type Key struct {
    54  		_ [1]byte
    55  		k [8]byte
    56  		_ [7]byte
    57  	}
    58  	key := Key{}
    59  	sink = (uint64)(MemHash64(unsafe.Pointer(&key.k), 0))
    60  }
    61  
    62  func TestMemHash64Equality(t *testing.T) {
    63  	if *UseAeshash {
    64  		t.Skip("skipping since AES hash implementation is used")
    65  	}
    66  	var b [8]byte
    67  	r := rand.New(rand.NewSource(1234))
    68  	seed := uintptr(r.Uint64())
    69  	for i := 0; i < 100; i++ {
    70  		randBytes(r, b[:])
    71  		got := MemHash64(unsafe.Pointer(&b), seed)
    72  		want := MemHash(unsafe.Pointer(&b), seed, 8)
    73  		if got != want {
    74  			t.Errorf("MemHash64(%x, %v) = %v; want %v", b, seed, got, want)
    75  		}
    76  	}
    77  }
    78  
    79  // Smhasher is a torture test for hash functions.
    80  // https://code.google.com/p/smhasher/
    81  // This code is a port of some of the Smhasher tests to Go.
    82  //
    83  // The current AES hash function passes Smhasher. Our fallback
    84  // hash functions don't, so we only enable the difficult tests when
    85  // we know the AES implementation is available.
    86  
    87  // Sanity checks.
    88  // hash should not depend on values outside key.
    89  // hash should not depend on alignment.
    90  func TestSmhasherSanity(t *testing.T) {
    91  	r := rand.New(rand.NewSource(1234))
    92  	const REP = 10
    93  	const KEYMAX = 128
    94  	const PAD = 16
    95  	const OFFMAX = 16
    96  	for k := 0; k < REP; k++ {
    97  		for n := 0; n < KEYMAX; n++ {
    98  			for i := 0; i < OFFMAX; i++ {
    99  				var b [KEYMAX + OFFMAX + 2*PAD]byte
   100  				var c [KEYMAX + OFFMAX + 2*PAD]byte
   101  				randBytes(r, b[:])
   102  				randBytes(r, c[:])
   103  				copy(c[PAD+i:PAD+i+n], b[PAD:PAD+n])
   104  				if BytesHash(b[PAD:PAD+n], 0) != BytesHash(c[PAD+i:PAD+i+n], 0) {
   105  					t.Errorf("hash depends on bytes outside key")
   106  				}
   107  			}
   108  		}
   109  	}
   110  }
   111  
   112  type HashSet struct {
   113  	list []uintptr // list of hashes added
   114  }
   115  
   116  func newHashSet() *HashSet {
   117  	return &HashSet{list: make([]uintptr, 0, 1024)}
   118  }
   119  func (s *HashSet) add(h uintptr) {
   120  	s.list = append(s.list, h)
   121  }
   122  func (s *HashSet) addS(x string) {
   123  	s.add(StringHash(x, 0))
   124  }
   125  func (s *HashSet) addB(x []byte) {
   126  	s.add(BytesHash(x, 0))
   127  }
   128  func (s *HashSet) addS_seed(x string, seed uintptr) {
   129  	s.add(StringHash(x, seed))
   130  }
   131  func (s *HashSet) check(t *testing.T) {
   132  	list := s.list
   133  	slices.Sort(list)
   134  
   135  	collisions := 0
   136  	for i := 1; i < len(list); i++ {
   137  		if list[i] == list[i-1] {
   138  			collisions++
   139  		}
   140  	}
   141  	n := len(list)
   142  
   143  	const SLOP = 50.0
   144  	pairs := int64(n) * int64(n-1) / 2
   145  	expected := float64(pairs) / math.Pow(2.0, float64(hashSize))
   146  	stddev := math.Sqrt(expected)
   147  	if float64(collisions) > expected+SLOP*(3*stddev+1) {
   148  		t.Errorf("unexpected number of collisions: got=%d mean=%f stddev=%f threshold=%f", collisions, expected, stddev, expected+SLOP*(3*stddev+1))
   149  	}
   150  	// Reset for reuse
   151  	s.list = s.list[:0]
   152  }
   153  
   154  // a string plus adding zeros must make distinct hashes
   155  func TestSmhasherAppendedZeros(t *testing.T) {
   156  	s := "hello" + strings.Repeat("\x00", 256)
   157  	h := newHashSet()
   158  	for i := 0; i <= len(s); i++ {
   159  		h.addS(s[:i])
   160  	}
   161  	h.check(t)
   162  }
   163  
   164  // All 0-3 byte strings have distinct hashes.
   165  func TestSmhasherSmallKeys(t *testing.T) {
   166  	if race.Enabled {
   167  		t.Skip("Too long for race mode")
   168  	}
   169  	testenv.ParallelOn64Bit(t)
   170  	h := newHashSet()
   171  	var b [3]byte
   172  	for i := 0; i < 256; i++ {
   173  		b[0] = byte(i)
   174  		h.addB(b[:1])
   175  		for j := 0; j < 256; j++ {
   176  			b[1] = byte(j)
   177  			h.addB(b[:2])
   178  			if !testing.Short() {
   179  				for k := 0; k < 256; k++ {
   180  					b[2] = byte(k)
   181  					h.addB(b[:3])
   182  				}
   183  			}
   184  		}
   185  	}
   186  	h.check(t)
   187  }
   188  
   189  // Different length strings of all zeros have distinct hashes.
   190  func TestSmhasherZeros(t *testing.T) {
   191  	t.Parallel()
   192  	N := 256 * 1024
   193  	if testing.Short() {
   194  		N = 1024
   195  	}
   196  	h := newHashSet()
   197  	b := make([]byte, N)
   198  	for i := 0; i <= N; i++ {
   199  		h.addB(b[:i])
   200  	}
   201  	h.check(t)
   202  }
   203  
   204  // Strings with up to two nonzero bytes all have distinct hashes.
   205  func TestSmhasherTwoNonzero(t *testing.T) {
   206  	if GOARCH == "wasm" {
   207  		t.Skip("Too slow on wasm")
   208  	}
   209  	if testing.Short() {
   210  		t.Skip("Skipping in short mode")
   211  	}
   212  	if race.Enabled {
   213  		t.Skip("Too long for race mode")
   214  	}
   215  	testenv.ParallelOn64Bit(t)
   216  	h := newHashSet()
   217  	for n := 2; n <= 16; n++ {
   218  		twoNonZero(h, n)
   219  	}
   220  	h.check(t)
   221  }
   222  func twoNonZero(h *HashSet, n int) {
   223  	b := make([]byte, n)
   224  
   225  	// all zero
   226  	h.addB(b)
   227  
   228  	// one non-zero byte
   229  	for i := 0; i < n; i++ {
   230  		for x := 1; x < 256; x++ {
   231  			b[i] = byte(x)
   232  			h.addB(b)
   233  			b[i] = 0
   234  		}
   235  	}
   236  
   237  	// two non-zero bytes
   238  	for i := 0; i < n; i++ {
   239  		for x := 1; x < 256; x++ {
   240  			b[i] = byte(x)
   241  			for j := i + 1; j < n; j++ {
   242  				for y := 1; y < 256; y++ {
   243  					b[j] = byte(y)
   244  					h.addB(b)
   245  					b[j] = 0
   246  				}
   247  			}
   248  			b[i] = 0
   249  		}
   250  	}
   251  }
   252  
   253  // Test strings with repeats, like "abcdabcdabcdabcd..."
   254  func TestSmhasherCyclic(t *testing.T) {
   255  	if testing.Short() {
   256  		t.Skip("Skipping in short mode")
   257  	}
   258  	if race.Enabled {
   259  		t.Skip("Too long for race mode")
   260  	}
   261  	t.Parallel()
   262  	r := rand.New(rand.NewSource(1234))
   263  	const REPEAT = 8
   264  	const N = 1000000
   265  	h := newHashSet()
   266  	for n := 4; n <= 12; n++ {
   267  		b := make([]byte, REPEAT*n)
   268  		for i := 0; i < N; i++ {
   269  			b[0] = byte(i * 79 % 97)
   270  			b[1] = byte(i * 43 % 137)
   271  			b[2] = byte(i * 151 % 197)
   272  			b[3] = byte(i * 199 % 251)
   273  			randBytes(r, b[4:n])
   274  			for j := n; j < n*REPEAT; j++ {
   275  				b[j] = b[j-n]
   276  			}
   277  			h.addB(b)
   278  		}
   279  		h.check(t)
   280  	}
   281  }
   282  
   283  // Test strings with only a few bits set
   284  func TestSmhasherSparse(t *testing.T) {
   285  	if GOARCH == "wasm" {
   286  		t.Skip("Too slow on wasm")
   287  	}
   288  	if testing.Short() {
   289  		t.Skip("Skipping in short mode")
   290  	}
   291  	t.Parallel()
   292  	h := newHashSet()
   293  	sparse(t, h, 32, 6)
   294  	sparse(t, h, 40, 6)
   295  	sparse(t, h, 48, 5)
   296  	sparse(t, h, 56, 5)
   297  	sparse(t, h, 64, 5)
   298  	sparse(t, h, 96, 4)
   299  	sparse(t, h, 256, 3)
   300  	sparse(t, h, 2048, 2)
   301  }
   302  func sparse(t *testing.T, h *HashSet, n int, k int) {
   303  	b := make([]byte, n/8)
   304  	setbits(h, b, 0, k)
   305  	h.check(t)
   306  }
   307  
   308  // set up to k bits at index i and greater
   309  func setbits(h *HashSet, b []byte, i int, k int) {
   310  	h.addB(b)
   311  	if k == 0 {
   312  		return
   313  	}
   314  	for j := i; j < len(b)*8; j++ {
   315  		b[j/8] |= byte(1 << uint(j&7))
   316  		setbits(h, b, j+1, k-1)
   317  		b[j/8] &= byte(^(1 << uint(j&7)))
   318  	}
   319  }
   320  
   321  // Test all possible combinations of n blocks from the set s.
   322  // "permutation" is a bad name here, but it is what Smhasher uses.
   323  func TestSmhasherPermutation(t *testing.T) {
   324  	if GOARCH == "wasm" {
   325  		t.Skip("Too slow on wasm")
   326  	}
   327  	if testing.Short() {
   328  		t.Skip("Skipping in short mode")
   329  	}
   330  	if race.Enabled {
   331  		t.Skip("Too long for race mode")
   332  	}
   333  	testenv.ParallelOn64Bit(t)
   334  	h := newHashSet()
   335  	permutation(t, h, []uint32{0, 1, 2, 3, 4, 5, 6, 7}, 8)
   336  	permutation(t, h, []uint32{0, 1 << 29, 2 << 29, 3 << 29, 4 << 29, 5 << 29, 6 << 29, 7 << 29}, 8)
   337  	permutation(t, h, []uint32{0, 1}, 20)
   338  	permutation(t, h, []uint32{0, 1 << 31}, 20)
   339  	permutation(t, h, []uint32{0, 1, 2, 3, 4, 5, 6, 7, 1 << 29, 2 << 29, 3 << 29, 4 << 29, 5 << 29, 6 << 29, 7 << 29}, 6)
   340  }
   341  func permutation(t *testing.T, h *HashSet, s []uint32, n int) {
   342  	b := make([]byte, n*4)
   343  	genPerm(h, b, s, 0)
   344  	h.check(t)
   345  }
   346  func genPerm(h *HashSet, b []byte, s []uint32, n int) {
   347  	h.addB(b[:n])
   348  	if n == len(b) {
   349  		return
   350  	}
   351  	for _, v := range s {
   352  		byteorder.LEPutUint32(b[n:], v)
   353  		genPerm(h, b, s, n+4)
   354  	}
   355  }
   356  
   357  type Key interface {
   358  	clear()              // set bits all to 0
   359  	random(r *rand.Rand) // set key to something random
   360  	bits() int           // how many bits key has
   361  	flipBit(i int)       // flip bit i of the key
   362  	hash() uintptr       // hash the key
   363  	name() string        // for error reporting
   364  }
   365  
   366  type BytesKey struct {
   367  	b []byte
   368  }
   369  
   370  func (k *BytesKey) clear() {
   371  	clear(k.b)
   372  }
   373  func (k *BytesKey) random(r *rand.Rand) {
   374  	randBytes(r, k.b)
   375  }
   376  func (k *BytesKey) bits() int {
   377  	return len(k.b) * 8
   378  }
   379  func (k *BytesKey) flipBit(i int) {
   380  	k.b[i>>3] ^= byte(1 << uint(i&7))
   381  }
   382  func (k *BytesKey) hash() uintptr {
   383  	return BytesHash(k.b, 0)
   384  }
   385  func (k *BytesKey) name() string {
   386  	return fmt.Sprintf("bytes%d", len(k.b))
   387  }
   388  
   389  type Int32Key struct {
   390  	i uint32
   391  }
   392  
   393  func (k *Int32Key) clear() {
   394  	k.i = 0
   395  }
   396  func (k *Int32Key) random(r *rand.Rand) {
   397  	k.i = r.Uint32()
   398  }
   399  func (k *Int32Key) bits() int {
   400  	return 32
   401  }
   402  func (k *Int32Key) flipBit(i int) {
   403  	k.i ^= 1 << uint(i)
   404  }
   405  func (k *Int32Key) hash() uintptr {
   406  	return Int32Hash(k.i, 0)
   407  }
   408  func (k *Int32Key) name() string {
   409  	return "int32"
   410  }
   411  
   412  type Int64Key struct {
   413  	i uint64
   414  }
   415  
   416  func (k *Int64Key) clear() {
   417  	k.i = 0
   418  }
   419  func (k *Int64Key) random(r *rand.Rand) {
   420  	k.i = uint64(r.Uint32()) + uint64(r.Uint32())<<32
   421  }
   422  func (k *Int64Key) bits() int {
   423  	return 64
   424  }
   425  func (k *Int64Key) flipBit(i int) {
   426  	k.i ^= 1 << uint(i)
   427  }
   428  func (k *Int64Key) hash() uintptr {
   429  	return Int64Hash(k.i, 0)
   430  }
   431  func (k *Int64Key) name() string {
   432  	return "int64"
   433  }
   434  
   435  type EfaceKey struct {
   436  	i any
   437  }
   438  
   439  func (k *EfaceKey) clear() {
   440  	k.i = nil
   441  }
   442  func (k *EfaceKey) random(r *rand.Rand) {
   443  	k.i = uint64(r.Int63())
   444  }
   445  func (k *EfaceKey) bits() int {
   446  	// use 64 bits. This tests inlined interfaces
   447  	// on 64-bit targets and indirect interfaces on
   448  	// 32-bit targets.
   449  	return 64
   450  }
   451  func (k *EfaceKey) flipBit(i int) {
   452  	k.i = k.i.(uint64) ^ uint64(1)<<uint(i)
   453  }
   454  func (k *EfaceKey) hash() uintptr {
   455  	return EfaceHash(k.i, 0)
   456  }
   457  func (k *EfaceKey) name() string {
   458  	return "Eface"
   459  }
   460  
   461  type IfaceKey struct {
   462  	i interface {
   463  		F()
   464  	}
   465  }
   466  type fInter uint64
   467  
   468  func (x fInter) F() {
   469  }
   470  
   471  func (k *IfaceKey) clear() {
   472  	k.i = nil
   473  }
   474  func (k *IfaceKey) random(r *rand.Rand) {
   475  	k.i = fInter(r.Int63())
   476  }
   477  func (k *IfaceKey) bits() int {
   478  	// use 64 bits. This tests inlined interfaces
   479  	// on 64-bit targets and indirect interfaces on
   480  	// 32-bit targets.
   481  	return 64
   482  }
   483  func (k *IfaceKey) flipBit(i int) {
   484  	k.i = k.i.(fInter) ^ fInter(1)<<uint(i)
   485  }
   486  func (k *IfaceKey) hash() uintptr {
   487  	return IfaceHash(k.i, 0)
   488  }
   489  func (k *IfaceKey) name() string {
   490  	return "Iface"
   491  }
   492  
   493  // Flipping a single bit of a key should flip each output bit with 50% probability.
   494  func TestSmhasherAvalanche(t *testing.T) {
   495  	if GOARCH == "wasm" {
   496  		t.Skip("Too slow on wasm")
   497  	}
   498  	if testing.Short() {
   499  		t.Skip("Skipping in short mode")
   500  	}
   501  	if race.Enabled {
   502  		t.Skip("Too long for race mode")
   503  	}
   504  	t.Parallel()
   505  	avalancheTest1(t, &BytesKey{make([]byte, 2)})
   506  	avalancheTest1(t, &BytesKey{make([]byte, 4)})
   507  	avalancheTest1(t, &BytesKey{make([]byte, 8)})
   508  	avalancheTest1(t, &BytesKey{make([]byte, 16)})
   509  	avalancheTest1(t, &BytesKey{make([]byte, 32)})
   510  	avalancheTest1(t, &BytesKey{make([]byte, 200)})
   511  	avalancheTest1(t, &Int32Key{})
   512  	avalancheTest1(t, &Int64Key{})
   513  	avalancheTest1(t, &EfaceKey{})
   514  	avalancheTest1(t, &IfaceKey{})
   515  }
   516  func avalancheTest1(t *testing.T, k Key) {
   517  	const REP = 100000
   518  	r := rand.New(rand.NewSource(1234))
   519  	n := k.bits()
   520  
   521  	// grid[i][j] is a count of whether flipping
   522  	// input bit i affects output bit j.
   523  	grid := make([][hashSize]int, n)
   524  
   525  	for z := 0; z < REP; z++ {
   526  		// pick a random key, hash it
   527  		k.random(r)
   528  		h := k.hash()
   529  
   530  		// flip each bit, hash & compare the results
   531  		for i := 0; i < n; i++ {
   532  			k.flipBit(i)
   533  			d := h ^ k.hash()
   534  			k.flipBit(i)
   535  
   536  			// record the effects of that bit flip
   537  			g := &grid[i]
   538  			for j := 0; j < hashSize; j++ {
   539  				g[j] += int(d & 1)
   540  				d >>= 1
   541  			}
   542  		}
   543  	}
   544  
   545  	// Each entry in the grid should be about REP/2.
   546  	// More precisely, we did N = k.bits() * hashSize experiments where
   547  	// each is the sum of REP coin flips. We want to find bounds on the
   548  	// sum of coin flips such that a truly random experiment would have
   549  	// all sums inside those bounds with 99% probability.
   550  	N := n * hashSize
   551  	var c float64
   552  	// find c such that Prob(mean-c*stddev < x < mean+c*stddev)^N > .9999
   553  	for c = 0.0; math.Pow(math.Erf(c/math.Sqrt(2)), float64(N)) < .9999; c += .1 {
   554  	}
   555  	c *= 11.0 // allowed slack: 40% to 60% - we don't need to be perfectly random
   556  	mean := .5 * REP
   557  	stddev := .5 * math.Sqrt(REP)
   558  	low := int(mean - c*stddev)
   559  	high := int(mean + c*stddev)
   560  	for i := 0; i < n; i++ {
   561  		for j := 0; j < hashSize; j++ {
   562  			x := grid[i][j]
   563  			if x < low || x > high {
   564  				t.Errorf("bad bias for %s bit %d -> bit %d: %d/%d\n", k.name(), i, j, x, REP)
   565  			}
   566  		}
   567  	}
   568  }
   569  
   570  // All bit rotations of a set of distinct keys
   571  func TestSmhasherWindowed(t *testing.T) {
   572  	if race.Enabled {
   573  		t.Skip("Too long for race mode")
   574  	}
   575  	t.Parallel()
   576  	h := newHashSet()
   577  	t.Logf("32 bit keys")
   578  	windowed(t, h, &Int32Key{})
   579  	t.Logf("64 bit keys")
   580  	windowed(t, h, &Int64Key{})
   581  	t.Logf("string keys")
   582  	windowed(t, h, &BytesKey{make([]byte, 128)})
   583  }
   584  func windowed(t *testing.T, h *HashSet, k Key) {
   585  	if GOARCH == "wasm" {
   586  		t.Skip("Too slow on wasm")
   587  	}
   588  	if PtrSize == 4 {
   589  		// This test tends to be flaky on 32-bit systems.
   590  		// There's not enough bits in the hash output, so we
   591  		// expect a nontrivial number of collisions, and it is
   592  		// often quite a bit higher than expected. See issue 43130.
   593  		t.Skip("Flaky on 32-bit systems")
   594  	}
   595  	if testing.Short() {
   596  		t.Skip("Skipping in short mode")
   597  	}
   598  	const BITS = 16
   599  
   600  	for r := 0; r < k.bits(); r++ {
   601  		for i := 0; i < 1<<BITS; i++ {
   602  			k.clear()
   603  			for j := 0; j < BITS; j++ {
   604  				if i>>uint(j)&1 != 0 {
   605  					k.flipBit((j + r) % k.bits())
   606  				}
   607  			}
   608  			h.add(k.hash())
   609  		}
   610  		h.check(t)
   611  	}
   612  }
   613  
   614  // All keys of the form prefix + [A-Za-z0-9]*N + suffix.
   615  func TestSmhasherText(t *testing.T) {
   616  	if testing.Short() {
   617  		t.Skip("Skipping in short mode")
   618  	}
   619  	t.Parallel()
   620  	h := newHashSet()
   621  	text(t, h, "Foo", "Bar")
   622  	text(t, h, "FooBar", "")
   623  	text(t, h, "", "FooBar")
   624  }
   625  func text(t *testing.T, h *HashSet, prefix, suffix string) {
   626  	const N = 4
   627  	const S = "ABCDEFGHIJKLMNOPQRSTabcdefghijklmnopqrst0123456789"
   628  	const L = len(S)
   629  	b := make([]byte, len(prefix)+N+len(suffix))
   630  	copy(b, prefix)
   631  	copy(b[len(prefix)+N:], suffix)
   632  	c := b[len(prefix):]
   633  	for i := 0; i < L; i++ {
   634  		c[0] = S[i]
   635  		for j := 0; j < L; j++ {
   636  			c[1] = S[j]
   637  			for k := 0; k < L; k++ {
   638  				c[2] = S[k]
   639  				for x := 0; x < L; x++ {
   640  					c[3] = S[x]
   641  					h.addB(b)
   642  				}
   643  			}
   644  		}
   645  	}
   646  	h.check(t)
   647  }
   648  
   649  // Make sure different seed values generate different hashes.
   650  func TestSmhasherSeed(t *testing.T) {
   651  	h := newHashSet()
   652  	const N = 100000
   653  	s := "hello"
   654  	for i := 0; i < N; i++ {
   655  		h.addS_seed(s, uintptr(i))
   656  	}
   657  	h.check(t)
   658  }
   659  
   660  func TestIssue66841(t *testing.T) {
   661  	if *UseAeshash && os.Getenv("TEST_ISSUE_66841") == "" {
   662  		// We want to test the backup hash, so if we're running on a machine
   663  		// that uses aeshash, exec ourselves while turning aes off.
   664  		cmd := testenv.CleanCmdEnv(testenv.Command(t, testenv.Executable(t), "-test.run=^TestIssue66841$"))
   665  		cmd.Env = append(cmd.Env, "GODEBUG=cpu.aes=off", "TEST_ISSUE_66841=1")
   666  		out, err := cmd.CombinedOutput()
   667  		if err != nil {
   668  			t.Errorf("%s", string(out))
   669  		}
   670  		// Fall through. Might as well run this test when aeshash is on also.
   671  	}
   672  	h := newHashSet()
   673  	var b [16]byte
   674  	binary.LittleEndian.PutUint64(b[:8], 0xe7037ed1a0b428db) // runtime.m2
   675  	for i := 0; i < 1000; i++ {
   676  		binary.LittleEndian.PutUint64(b[8:], uint64(i))
   677  		h.addB(b[:])
   678  	}
   679  	h.check(t)
   680  }
   681  
   682  // size of the hash output (32 or 64 bits)
   683  const hashSize = 32 + int(^uintptr(0)>>63<<5)
   684  
   685  func randBytes(r *rand.Rand, b []byte) {
   686  	for i := range b {
   687  		b[i] = byte(r.Uint32())
   688  	}
   689  }
   690  
   691  func benchmarkHash(b *testing.B, n int) {
   692  	s := strings.Repeat("A", n)
   693  
   694  	for i := 0; i < b.N; i++ {
   695  		StringHash(s, 0)
   696  	}
   697  	b.SetBytes(int64(n))
   698  }
   699  
   700  func BenchmarkHash5(b *testing.B)     { benchmarkHash(b, 5) }
   701  func BenchmarkHash16(b *testing.B)    { benchmarkHash(b, 16) }
   702  func BenchmarkHash64(b *testing.B)    { benchmarkHash(b, 64) }
   703  func BenchmarkHash1024(b *testing.B)  { benchmarkHash(b, 1024) }
   704  func BenchmarkHash65536(b *testing.B) { benchmarkHash(b, 65536) }
   705  
   706  func TestArrayHash(t *testing.T) {
   707  	// Make sure that "" in arrays hash correctly. The hash
   708  	// should at least scramble the input seed so that, e.g.,
   709  	// {"","foo"} and {"foo",""} have different hashes.
   710  
   711  	// If the hash is bad, then all (8 choose 4) = 70 keys
   712  	// have the same hash. If so, we allocate 70/8 = 8
   713  	// overflow buckets. If the hash is good we don't
   714  	// normally allocate any overflow buckets, and the
   715  	// probability of even one or two overflows goes down rapidly.
   716  	// (There is always 1 allocation of the bucket array. The map
   717  	// header is allocated on the stack.)
   718  	f := func() {
   719  		// Make the key type at most 128 bytes. Otherwise,
   720  		// we get an allocation per key.
   721  		type key [8]string
   722  		m := make(map[key]bool, 70)
   723  
   724  		// fill m with keys that have 4 "foo"s and 4 ""s.
   725  		for i := 0; i < 256; i++ {
   726  			var k key
   727  			cnt := 0
   728  			for j := uint(0); j < 8; j++ {
   729  				if i>>j&1 != 0 {
   730  					k[j] = "foo"
   731  					cnt++
   732  				}
   733  			}
   734  			if cnt == 4 {
   735  				m[k] = true
   736  			}
   737  		}
   738  		if len(m) != 70 {
   739  			t.Errorf("bad test: (8 choose 4) should be 70, not %d", len(m))
   740  		}
   741  	}
   742  	if n := testing.AllocsPerRun(10, f); n > 6 {
   743  		t.Errorf("too many allocs %f - hash not balanced", n)
   744  	}
   745  }
   746  func TestStructHash(t *testing.T) {
   747  	// See the comment in TestArrayHash.
   748  	f := func() {
   749  		type key struct {
   750  			a, b, c, d, e, f, g, h string
   751  		}
   752  		m := make(map[key]bool, 70)
   753  
   754  		// fill m with keys that have 4 "foo"s and 4 ""s.
   755  		for i := 0; i < 256; i++ {
   756  			var k key
   757  			cnt := 0
   758  			if i&1 != 0 {
   759  				k.a = "foo"
   760  				cnt++
   761  			}
   762  			if i&2 != 0 {
   763  				k.b = "foo"
   764  				cnt++
   765  			}
   766  			if i&4 != 0 {
   767  				k.c = "foo"
   768  				cnt++
   769  			}
   770  			if i&8 != 0 {
   771  				k.d = "foo"
   772  				cnt++
   773  			}
   774  			if i&16 != 0 {
   775  				k.e = "foo"
   776  				cnt++
   777  			}
   778  			if i&32 != 0 {
   779  				k.f = "foo"
   780  				cnt++
   781  			}
   782  			if i&64 != 0 {
   783  				k.g = "foo"
   784  				cnt++
   785  			}
   786  			if i&128 != 0 {
   787  				k.h = "foo"
   788  				cnt++
   789  			}
   790  			if cnt == 4 {
   791  				m[k] = true
   792  			}
   793  		}
   794  		if len(m) != 70 {
   795  			t.Errorf("bad test: (8 choose 4) should be 70, not %d", len(m))
   796  		}
   797  	}
   798  	if n := testing.AllocsPerRun(10, f); n > 6 {
   799  		t.Errorf("too many allocs %f - hash not balanced", n)
   800  	}
   801  }
   802  
   803  var sink uint64
   804  
   805  func BenchmarkAlignedLoad(b *testing.B) {
   806  	var buf [16]byte
   807  	p := unsafe.Pointer(&buf[0])
   808  	var s uint64
   809  	for i := 0; i < b.N; i++ {
   810  		s += ReadUnaligned64(p)
   811  	}
   812  	sink = s
   813  }
   814  
   815  func BenchmarkUnalignedLoad(b *testing.B) {
   816  	var buf [16]byte
   817  	p := unsafe.Pointer(&buf[1])
   818  	var s uint64
   819  	for i := 0; i < b.N; i++ {
   820  		s += ReadUnaligned64(p)
   821  	}
   822  	sink = s
   823  }
   824  
   825  func TestCollisions(t *testing.T) {
   826  	if testing.Short() {
   827  		t.Skip("Skipping in short mode")
   828  	}
   829  	t.Parallel()
   830  	for i := 0; i < 16; i++ {
   831  		for j := 0; j < 16; j++ {
   832  			if j == i {
   833  				continue
   834  			}
   835  			var a [16]byte
   836  			m := make(map[uint16]struct{}, 1<<16)
   837  			for n := 0; n < 1<<16; n++ {
   838  				a[i] = byte(n)
   839  				a[j] = byte(n >> 8)
   840  				m[uint16(BytesHash(a[:], 0))] = struct{}{}
   841  			}
   842  			// N balls in N bins, for N=65536
   843  			avg := 41427
   844  			stdDev := 123
   845  			if len(m) < avg-40*stdDev || len(m) > avg+40*stdDev {
   846  				t.Errorf("bad number of collisions i=%d j=%d outputs=%d out of 65536\n", i, j, len(m))
   847  			}
   848  		}
   849  	}
   850  }
   851  

View as plain text