Source file src/hash/maphash/smhasher_test.go

Documentation: hash/maphash

		 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  
		 5  package maphash
		 6  
		 7  import (
		 8  	"fmt"
		 9  	"math"
		10  	"math/rand"
		11  	"runtime"
		12  	"strings"
		13  	"testing"
		14  	"unsafe"
		15  )
		16  
		17  // Smhasher is a torture test for hash functions.
		18  // https://code.google.com/p/smhasher/
		19  // This code is a port of some of the Smhasher tests to Go.
		20  
		21  var fixedSeed = MakeSeed()
		22  
		23  // Sanity checks.
		24  // hash should not depend on values outside key.
		25  // hash should not depend on alignment.
		26  func TestSmhasherSanity(t *testing.T) {
		27  	r := rand.New(rand.NewSource(1234))
		28  	const REP = 10
		29  	const KEYMAX = 128
		30  	const PAD = 16
		31  	const OFFMAX = 16
		32  	for k := 0; k < REP; k++ {
		33  		for n := 0; n < KEYMAX; n++ {
		34  			for i := 0; i < OFFMAX; i++ {
		35  				var b [KEYMAX + OFFMAX + 2*PAD]byte
		36  				var c [KEYMAX + OFFMAX + 2*PAD]byte
		37  				randBytes(r, b[:])
		38  				randBytes(r, c[:])
		39  				copy(c[PAD+i:PAD+i+n], b[PAD:PAD+n])
		40  				if bytesHash(b[PAD:PAD+n]) != bytesHash(c[PAD+i:PAD+i+n]) {
		41  					t.Errorf("hash depends on bytes outside key")
		42  				}
		43  			}
		44  		}
		45  	}
		46  }
		47  
		48  func bytesHash(b []byte) uint64 {
		49  	var h Hash
		50  	h.SetSeed(fixedSeed)
		51  	h.Write(b)
		52  	return h.Sum64()
		53  }
		54  func stringHash(s string) uint64 {
		55  	var h Hash
		56  	h.SetSeed(fixedSeed)
		57  	h.WriteString(s)
		58  	return h.Sum64()
		59  }
		60  
		61  const hashSize = 64
		62  
		63  func randBytes(r *rand.Rand, b []byte) {
		64  	r.Read(b) // can't fail
		65  }
		66  
		67  // A hashSet measures the frequency of hash collisions.
		68  type hashSet struct {
		69  	m map[uint64]struct{} // set of hashes added
		70  	n int								 // number of hashes added
		71  }
		72  
		73  func newHashSet() *hashSet {
		74  	return &hashSet{make(map[uint64]struct{}), 0}
		75  }
		76  func (s *hashSet) add(h uint64) {
		77  	s.m[h] = struct{}{}
		78  	s.n++
		79  }
		80  func (s *hashSet) addS(x string) {
		81  	s.add(stringHash(x))
		82  }
		83  func (s *hashSet) addB(x []byte) {
		84  	s.add(bytesHash(x))
		85  }
		86  func (s *hashSet) addS_seed(x string, seed Seed) {
		87  	var h Hash
		88  	h.SetSeed(seed)
		89  	h.WriteString(x)
		90  	s.add(h.Sum64())
		91  }
		92  func (s *hashSet) check(t *testing.T) {
		93  	const SLOP = 10.0
		94  	collisions := s.n - len(s.m)
		95  	pairs := int64(s.n) * int64(s.n-1) / 2
		96  	expected := float64(pairs) / math.Pow(2.0, float64(hashSize))
		97  	stddev := math.Sqrt(expected)
		98  	if float64(collisions) > expected+SLOP*(3*stddev+1) {
		99  		t.Errorf("unexpected number of collisions: got=%d mean=%f stddev=%f", collisions, expected, stddev)
	 100  	}
	 101  }
	 102  
	 103  // a string plus adding zeros must make distinct hashes
	 104  func TestSmhasherAppendedZeros(t *testing.T) {
	 105  	s := "hello" + strings.Repeat("\x00", 256)
	 106  	h := newHashSet()
	 107  	for i := 0; i <= len(s); i++ {
	 108  		h.addS(s[:i])
	 109  	}
	 110  	h.check(t)
	 111  }
	 112  
	 113  // All 0-3 byte strings have distinct hashes.
	 114  func TestSmhasherSmallKeys(t *testing.T) {
	 115  	h := newHashSet()
	 116  	var b [3]byte
	 117  	for i := 0; i < 256; i++ {
	 118  		b[0] = byte(i)
	 119  		h.addB(b[:1])
	 120  		for j := 0; j < 256; j++ {
	 121  			b[1] = byte(j)
	 122  			h.addB(b[:2])
	 123  			if !testing.Short() {
	 124  				for k := 0; k < 256; k++ {
	 125  					b[2] = byte(k)
	 126  					h.addB(b[:3])
	 127  				}
	 128  			}
	 129  		}
	 130  	}
	 131  	h.check(t)
	 132  }
	 133  
	 134  // Different length strings of all zeros have distinct hashes.
	 135  func TestSmhasherZeros(t *testing.T) {
	 136  	N := 256 * 1024
	 137  	if testing.Short() {
	 138  		N = 1024
	 139  	}
	 140  	h := newHashSet()
	 141  	b := make([]byte, N)
	 142  	for i := 0; i <= N; i++ {
	 143  		h.addB(b[:i])
	 144  	}
	 145  	h.check(t)
	 146  }
	 147  
	 148  // Strings with up to two nonzero bytes all have distinct hashes.
	 149  func TestSmhasherTwoNonzero(t *testing.T) {
	 150  	if runtime.GOARCH == "wasm" {
	 151  		t.Skip("Too slow on wasm")
	 152  	}
	 153  	if testing.Short() {
	 154  		t.Skip("Skipping in short mode")
	 155  	}
	 156  	h := newHashSet()
	 157  	for n := 2; n <= 16; n++ {
	 158  		twoNonZero(h, n)
	 159  	}
	 160  	h.check(t)
	 161  }
	 162  func twoNonZero(h *hashSet, n int) {
	 163  	b := make([]byte, n)
	 164  
	 165  	// all zero
	 166  	h.addB(b)
	 167  
	 168  	// one non-zero byte
	 169  	for i := 0; i < n; i++ {
	 170  		for x := 1; x < 256; x++ {
	 171  			b[i] = byte(x)
	 172  			h.addB(b)
	 173  			b[i] = 0
	 174  		}
	 175  	}
	 176  
	 177  	// two non-zero bytes
	 178  	for i := 0; i < n; i++ {
	 179  		for x := 1; x < 256; x++ {
	 180  			b[i] = byte(x)
	 181  			for j := i + 1; j < n; j++ {
	 182  				for y := 1; y < 256; y++ {
	 183  					b[j] = byte(y)
	 184  					h.addB(b)
	 185  					b[j] = 0
	 186  				}
	 187  			}
	 188  			b[i] = 0
	 189  		}
	 190  	}
	 191  }
	 192  
	 193  // Test strings with repeats, like "abcdabcdabcdabcd..."
	 194  func TestSmhasherCyclic(t *testing.T) {
	 195  	if testing.Short() {
	 196  		t.Skip("Skipping in short mode")
	 197  	}
	 198  	r := rand.New(rand.NewSource(1234))
	 199  	const REPEAT = 8
	 200  	const N = 1000000
	 201  	for n := 4; n <= 12; n++ {
	 202  		h := newHashSet()
	 203  		b := make([]byte, REPEAT*n)
	 204  		for i := 0; i < N; i++ {
	 205  			b[0] = byte(i * 79 % 97)
	 206  			b[1] = byte(i * 43 % 137)
	 207  			b[2] = byte(i * 151 % 197)
	 208  			b[3] = byte(i * 199 % 251)
	 209  			randBytes(r, b[4:n])
	 210  			for j := n; j < n*REPEAT; j++ {
	 211  				b[j] = b[j-n]
	 212  			}
	 213  			h.addB(b)
	 214  		}
	 215  		h.check(t)
	 216  	}
	 217  }
	 218  
	 219  // Test strings with only a few bits set
	 220  func TestSmhasherSparse(t *testing.T) {
	 221  	if runtime.GOARCH == "wasm" {
	 222  		t.Skip("Too slow on wasm")
	 223  	}
	 224  	if testing.Short() {
	 225  		t.Skip("Skipping in short mode")
	 226  	}
	 227  	sparse(t, 32, 6)
	 228  	sparse(t, 40, 6)
	 229  	sparse(t, 48, 5)
	 230  	sparse(t, 56, 5)
	 231  	sparse(t, 64, 5)
	 232  	sparse(t, 96, 4)
	 233  	sparse(t, 256, 3)
	 234  	sparse(t, 2048, 2)
	 235  }
	 236  func sparse(t *testing.T, n int, k int) {
	 237  	b := make([]byte, n/8)
	 238  	h := newHashSet()
	 239  	setbits(h, b, 0, k)
	 240  	h.check(t)
	 241  }
	 242  
	 243  // set up to k bits at index i and greater
	 244  func setbits(h *hashSet, b []byte, i int, k int) {
	 245  	h.addB(b)
	 246  	if k == 0 {
	 247  		return
	 248  	}
	 249  	for j := i; j < len(b)*8; j++ {
	 250  		b[j/8] |= byte(1 << uint(j&7))
	 251  		setbits(h, b, j+1, k-1)
	 252  		b[j/8] &= byte(^(1 << uint(j&7)))
	 253  	}
	 254  }
	 255  
	 256  // Test all possible combinations of n blocks from the set s.
	 257  // "permutation" is a bad name here, but it is what Smhasher uses.
	 258  func TestSmhasherPermutation(t *testing.T) {
	 259  	if runtime.GOARCH == "wasm" {
	 260  		t.Skip("Too slow on wasm")
	 261  	}
	 262  	if testing.Short() {
	 263  		t.Skip("Skipping in short mode")
	 264  	}
	 265  	permutation(t, []uint32{0, 1, 2, 3, 4, 5, 6, 7}, 8)
	 266  	permutation(t, []uint32{0, 1 << 29, 2 << 29, 3 << 29, 4 << 29, 5 << 29, 6 << 29, 7 << 29}, 8)
	 267  	permutation(t, []uint32{0, 1}, 20)
	 268  	permutation(t, []uint32{0, 1 << 31}, 20)
	 269  	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)
	 270  }
	 271  func permutation(t *testing.T, s []uint32, n int) {
	 272  	b := make([]byte, n*4)
	 273  	h := newHashSet()
	 274  	genPerm(h, b, s, 0)
	 275  	h.check(t)
	 276  }
	 277  func genPerm(h *hashSet, b []byte, s []uint32, n int) {
	 278  	h.addB(b[:n])
	 279  	if n == len(b) {
	 280  		return
	 281  	}
	 282  	for _, v := range s {
	 283  		b[n] = byte(v)
	 284  		b[n+1] = byte(v >> 8)
	 285  		b[n+2] = byte(v >> 16)
	 286  		b[n+3] = byte(v >> 24)
	 287  		genPerm(h, b, s, n+4)
	 288  	}
	 289  }
	 290  
	 291  type key interface {
	 292  	clear()							// set bits all to 0
	 293  	random(r *rand.Rand) // set key to something random
	 294  	bits() int					 // how many bits key has
	 295  	flipBit(i int)			 // flip bit i of the key
	 296  	hash() uint64				// hash the key
	 297  	name() string				// for error reporting
	 298  }
	 299  
	 300  type bytesKey struct {
	 301  	b []byte
	 302  }
	 303  
	 304  func (k *bytesKey) clear() {
	 305  	for i := range k.b {
	 306  		k.b[i] = 0
	 307  	}
	 308  }
	 309  func (k *bytesKey) random(r *rand.Rand) {
	 310  	randBytes(r, k.b)
	 311  }
	 312  func (k *bytesKey) bits() int {
	 313  	return len(k.b) * 8
	 314  }
	 315  func (k *bytesKey) flipBit(i int) {
	 316  	k.b[i>>3] ^= byte(1 << uint(i&7))
	 317  }
	 318  func (k *bytesKey) hash() uint64 {
	 319  	return bytesHash(k.b)
	 320  }
	 321  func (k *bytesKey) name() string {
	 322  	return fmt.Sprintf("bytes%d", len(k.b))
	 323  }
	 324  
	 325  // Flipping a single bit of a key should flip each output bit with 50% probability.
	 326  func TestSmhasherAvalanche(t *testing.T) {
	 327  	if runtime.GOARCH == "wasm" {
	 328  		t.Skip("Too slow on wasm")
	 329  	}
	 330  	if testing.Short() {
	 331  		t.Skip("Skipping in short mode")
	 332  	}
	 333  	avalancheTest1(t, &bytesKey{make([]byte, 2)})
	 334  	avalancheTest1(t, &bytesKey{make([]byte, 4)})
	 335  	avalancheTest1(t, &bytesKey{make([]byte, 8)})
	 336  	avalancheTest1(t, &bytesKey{make([]byte, 16)})
	 337  	avalancheTest1(t, &bytesKey{make([]byte, 32)})
	 338  	avalancheTest1(t, &bytesKey{make([]byte, 200)})
	 339  }
	 340  func avalancheTest1(t *testing.T, k key) {
	 341  	const REP = 100000
	 342  	r := rand.New(rand.NewSource(1234))
	 343  	n := k.bits()
	 344  
	 345  	// grid[i][j] is a count of whether flipping
	 346  	// input bit i affects output bit j.
	 347  	grid := make([][hashSize]int, n)
	 348  
	 349  	for z := 0; z < REP; z++ {
	 350  		// pick a random key, hash it
	 351  		k.random(r)
	 352  		h := k.hash()
	 353  
	 354  		// flip each bit, hash & compare the results
	 355  		for i := 0; i < n; i++ {
	 356  			k.flipBit(i)
	 357  			d := h ^ k.hash()
	 358  			k.flipBit(i)
	 359  
	 360  			// record the effects of that bit flip
	 361  			g := &grid[i]
	 362  			for j := 0; j < hashSize; j++ {
	 363  				g[j] += int(d & 1)
	 364  				d >>= 1
	 365  			}
	 366  		}
	 367  	}
	 368  
	 369  	// Each entry in the grid should be about REP/2.
	 370  	// More precisely, we did N = k.bits() * hashSize experiments where
	 371  	// each is the sum of REP coin flips. We want to find bounds on the
	 372  	// sum of coin flips such that a truly random experiment would have
	 373  	// all sums inside those bounds with 99% probability.
	 374  	N := n * hashSize
	 375  	var c float64
	 376  	// find c such that Prob(mean-c*stddev < x < mean+c*stddev)^N > .9999
	 377  	for c = 0.0; math.Pow(math.Erf(c/math.Sqrt(2)), float64(N)) < .9999; c += .1 {
	 378  	}
	 379  	c *= 4.0 // allowed slack - we don't need to be perfectly random
	 380  	mean := .5 * REP
	 381  	stddev := .5 * math.Sqrt(REP)
	 382  	low := int(mean - c*stddev)
	 383  	high := int(mean + c*stddev)
	 384  	for i := 0; i < n; i++ {
	 385  		for j := 0; j < hashSize; j++ {
	 386  			x := grid[i][j]
	 387  			if x < low || x > high {
	 388  				t.Errorf("bad bias for %s bit %d -> bit %d: %d/%d\n", k.name(), i, j, x, REP)
	 389  			}
	 390  		}
	 391  	}
	 392  }
	 393  
	 394  // All bit rotations of a set of distinct keys
	 395  func TestSmhasherWindowed(t *testing.T) {
	 396  	windowed(t, &bytesKey{make([]byte, 128)})
	 397  }
	 398  func windowed(t *testing.T, k key) {
	 399  	if runtime.GOARCH == "wasm" {
	 400  		t.Skip("Too slow on wasm")
	 401  	}
	 402  	if testing.Short() {
	 403  		t.Skip("Skipping in short mode")
	 404  	}
	 405  	const BITS = 16
	 406  
	 407  	for r := 0; r < k.bits(); r++ {
	 408  		h := newHashSet()
	 409  		for i := 0; i < 1<<BITS; i++ {
	 410  			k.clear()
	 411  			for j := 0; j < BITS; j++ {
	 412  				if i>>uint(j)&1 != 0 {
	 413  					k.flipBit((j + r) % k.bits())
	 414  				}
	 415  			}
	 416  			h.add(k.hash())
	 417  		}
	 418  		h.check(t)
	 419  	}
	 420  }
	 421  
	 422  // All keys of the form prefix + [A-Za-z0-9]*N + suffix.
	 423  func TestSmhasherText(t *testing.T) {
	 424  	if testing.Short() {
	 425  		t.Skip("Skipping in short mode")
	 426  	}
	 427  	text(t, "Foo", "Bar")
	 428  	text(t, "FooBar", "")
	 429  	text(t, "", "FooBar")
	 430  }
	 431  func text(t *testing.T, prefix, suffix string) {
	 432  	const N = 4
	 433  	const S = "ABCDEFGHIJKLMNOPQRSTabcdefghijklmnopqrst0123456789"
	 434  	const L = len(S)
	 435  	b := make([]byte, len(prefix)+N+len(suffix))
	 436  	copy(b, prefix)
	 437  	copy(b[len(prefix)+N:], suffix)
	 438  	h := newHashSet()
	 439  	c := b[len(prefix):]
	 440  	for i := 0; i < L; i++ {
	 441  		c[0] = S[i]
	 442  		for j := 0; j < L; j++ {
	 443  			c[1] = S[j]
	 444  			for k := 0; k < L; k++ {
	 445  				c[2] = S[k]
	 446  				for x := 0; x < L; x++ {
	 447  					c[3] = S[x]
	 448  					h.addB(b)
	 449  				}
	 450  			}
	 451  		}
	 452  	}
	 453  	h.check(t)
	 454  }
	 455  
	 456  // Make sure different seed values generate different hashes.
	 457  func TestSmhasherSeed(t *testing.T) {
	 458  	if unsafe.Sizeof(uintptr(0)) == 4 {
	 459  		t.Skip("32-bit platforms don't have ideal seed-input distributions (see issue 33988)")
	 460  	}
	 461  	h := newHashSet()
	 462  	const N = 100000
	 463  	s := "hello"
	 464  	for i := 0; i < N; i++ {
	 465  		h.addS_seed(s, Seed{s: uint64(i + 1)})
	 466  		h.addS_seed(s, Seed{s: uint64(i+1) << 32}) // make sure high bits are used
	 467  	}
	 468  	h.check(t)
	 469  }
	 470  

View as plain text