...
Run Format

Source file src/runtime/alg.go

     1	// Copyright 2014 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
     6	
     7	import (
     8		"runtime/internal/sys"
     9		"unsafe"
    10	)
    11	
    12	const (
    13		c0 = uintptr((8-sys.PtrSize)/4*2860486313 + (sys.PtrSize-4)/4*33054211828000289)
    14		c1 = uintptr((8-sys.PtrSize)/4*3267000013 + (sys.PtrSize-4)/4*23344194077549503)
    15	)
    16	
    17	// type algorithms - known to compiler
    18	const (
    19		alg_NOEQ = iota
    20		alg_MEM0
    21		alg_MEM8
    22		alg_MEM16
    23		alg_MEM32
    24		alg_MEM64
    25		alg_MEM128
    26		alg_STRING
    27		alg_INTER
    28		alg_NILINTER
    29		alg_FLOAT32
    30		alg_FLOAT64
    31		alg_CPLX64
    32		alg_CPLX128
    33		alg_max
    34	)
    35	
    36	// typeAlg is also copied/used in reflect/type.go.
    37	// keep them in sync.
    38	type typeAlg struct {
    39		// function for hashing objects of this type
    40		// (ptr to object, seed) -> hash
    41		hash func(unsafe.Pointer, uintptr) uintptr
    42		// function for comparing objects of this type
    43		// (ptr to object A, ptr to object B) -> ==?
    44		equal func(unsafe.Pointer, unsafe.Pointer) bool
    45	}
    46	
    47	func memhash0(p unsafe.Pointer, h uintptr) uintptr {
    48		return h
    49	}
    50	func memhash8(p unsafe.Pointer, h uintptr) uintptr {
    51		return memhash(p, h, 1)
    52	}
    53	func memhash16(p unsafe.Pointer, h uintptr) uintptr {
    54		return memhash(p, h, 2)
    55	}
    56	func memhash32(p unsafe.Pointer, h uintptr) uintptr {
    57		return memhash(p, h, 4)
    58	}
    59	func memhash64(p unsafe.Pointer, h uintptr) uintptr {
    60		return memhash(p, h, 8)
    61	}
    62	func memhash128(p unsafe.Pointer, h uintptr) uintptr {
    63		return memhash(p, h, 16)
    64	}
    65	
    66	// memhash_varlen is defined in assembly because it needs access
    67	// to the closure. It appears here to provide an argument
    68	// signature for the assembly routine.
    69	func memhash_varlen(p unsafe.Pointer, h uintptr) uintptr
    70	
    71	var algarray = [alg_max]typeAlg{
    72		alg_NOEQ:     {nil, nil},
    73		alg_MEM0:     {memhash0, memequal0},
    74		alg_MEM8:     {memhash8, memequal8},
    75		alg_MEM16:    {memhash16, memequal16},
    76		alg_MEM32:    {memhash32, memequal32},
    77		alg_MEM64:    {memhash64, memequal64},
    78		alg_MEM128:   {memhash128, memequal128},
    79		alg_STRING:   {strhash, strequal},
    80		alg_INTER:    {interhash, interequal},
    81		alg_NILINTER: {nilinterhash, nilinterequal},
    82		alg_FLOAT32:  {f32hash, f32equal},
    83		alg_FLOAT64:  {f64hash, f64equal},
    84		alg_CPLX64:   {c64hash, c64equal},
    85		alg_CPLX128:  {c128hash, c128equal},
    86	}
    87	
    88	var useAeshash bool
    89	
    90	// in asm_*.s
    91	func aeshash(p unsafe.Pointer, h, s uintptr) uintptr
    92	func aeshash32(p unsafe.Pointer, h uintptr) uintptr
    93	func aeshash64(p unsafe.Pointer, h uintptr) uintptr
    94	func aeshashstr(p unsafe.Pointer, h uintptr) uintptr
    95	
    96	func strhash(a unsafe.Pointer, h uintptr) uintptr {
    97		x := (*stringStruct)(a)
    98		return memhash(x.str, h, uintptr(x.len))
    99	}
   100	
   101	// NOTE: Because NaN != NaN, a map can contain any
   102	// number of (mostly useless) entries keyed with NaNs.
   103	// To avoid long hash chains, we assign a random number
   104	// as the hash value for a NaN.
   105	
   106	func f32hash(p unsafe.Pointer, h uintptr) uintptr {
   107		f := *(*float32)(p)
   108		switch {
   109		case f == 0:
   110			return c1 * (c0 ^ h) // +0, -0
   111		case f != f:
   112			return c1 * (c0 ^ h ^ uintptr(fastrand())) // any kind of NaN
   113		default:
   114			return memhash(p, h, 4)
   115		}
   116	}
   117	
   118	func f64hash(p unsafe.Pointer, h uintptr) uintptr {
   119		f := *(*float64)(p)
   120		switch {
   121		case f == 0:
   122			return c1 * (c0 ^ h) // +0, -0
   123		case f != f:
   124			return c1 * (c0 ^ h ^ uintptr(fastrand())) // any kind of NaN
   125		default:
   126			return memhash(p, h, 8)
   127		}
   128	}
   129	
   130	func c64hash(p unsafe.Pointer, h uintptr) uintptr {
   131		x := (*[2]float32)(p)
   132		return f32hash(unsafe.Pointer(&x[1]), f32hash(unsafe.Pointer(&x[0]), h))
   133	}
   134	
   135	func c128hash(p unsafe.Pointer, h uintptr) uintptr {
   136		x := (*[2]float64)(p)
   137		return f64hash(unsafe.Pointer(&x[1]), f64hash(unsafe.Pointer(&x[0]), h))
   138	}
   139	
   140	func interhash(p unsafe.Pointer, h uintptr) uintptr {
   141		a := (*iface)(p)
   142		tab := a.tab
   143		if tab == nil {
   144			return h
   145		}
   146		t := tab._type
   147		fn := t.alg.hash
   148		if fn == nil {
   149			panic(errorString("hash of unhashable type " + t.string()))
   150		}
   151		if isDirectIface(t) {
   152			return c1 * fn(unsafe.Pointer(&a.data), h^c0)
   153		} else {
   154			return c1 * fn(a.data, h^c0)
   155		}
   156	}
   157	
   158	func nilinterhash(p unsafe.Pointer, h uintptr) uintptr {
   159		a := (*eface)(p)
   160		t := a._type
   161		if t == nil {
   162			return h
   163		}
   164		fn := t.alg.hash
   165		if fn == nil {
   166			panic(errorString("hash of unhashable type " + t.string()))
   167		}
   168		if isDirectIface(t) {
   169			return c1 * fn(unsafe.Pointer(&a.data), h^c0)
   170		} else {
   171			return c1 * fn(a.data, h^c0)
   172		}
   173	}
   174	
   175	func memequal0(p, q unsafe.Pointer) bool {
   176		return true
   177	}
   178	func memequal8(p, q unsafe.Pointer) bool {
   179		return *(*int8)(p) == *(*int8)(q)
   180	}
   181	func memequal16(p, q unsafe.Pointer) bool {
   182		return *(*int16)(p) == *(*int16)(q)
   183	}
   184	func memequal32(p, q unsafe.Pointer) bool {
   185		return *(*int32)(p) == *(*int32)(q)
   186	}
   187	func memequal64(p, q unsafe.Pointer) bool {
   188		return *(*int64)(p) == *(*int64)(q)
   189	}
   190	func memequal128(p, q unsafe.Pointer) bool {
   191		return *(*[2]int64)(p) == *(*[2]int64)(q)
   192	}
   193	func f32equal(p, q unsafe.Pointer) bool {
   194		return *(*float32)(p) == *(*float32)(q)
   195	}
   196	func f64equal(p, q unsafe.Pointer) bool {
   197		return *(*float64)(p) == *(*float64)(q)
   198	}
   199	func c64equal(p, q unsafe.Pointer) bool {
   200		return *(*complex64)(p) == *(*complex64)(q)
   201	}
   202	func c128equal(p, q unsafe.Pointer) bool {
   203		return *(*complex128)(p) == *(*complex128)(q)
   204	}
   205	func strequal(p, q unsafe.Pointer) bool {
   206		return *(*string)(p) == *(*string)(q)
   207	}
   208	func interequal(p, q unsafe.Pointer) bool {
   209		return ifaceeq(*(*iface)(p), *(*iface)(q))
   210	}
   211	func nilinterequal(p, q unsafe.Pointer) bool {
   212		return efaceeq(*(*eface)(p), *(*eface)(q))
   213	}
   214	func efaceeq(x, y eface) bool {
   215		t := x._type
   216		if t != y._type {
   217			return false
   218		}
   219		if t == nil {
   220			return true
   221		}
   222		eq := t.alg.equal
   223		if eq == nil {
   224			panic(errorString("comparing uncomparable type " + t.string()))
   225		}
   226		if isDirectIface(t) {
   227			return eq(noescape(unsafe.Pointer(&x.data)), noescape(unsafe.Pointer(&y.data)))
   228		}
   229		return eq(x.data, y.data)
   230	}
   231	func ifaceeq(x, y iface) bool {
   232		xtab := x.tab
   233		if xtab != y.tab {
   234			return false
   235		}
   236		if xtab == nil {
   237			return true
   238		}
   239		t := xtab._type
   240		eq := t.alg.equal
   241		if eq == nil {
   242			panic(errorString("comparing uncomparable type " + t.string()))
   243		}
   244		if isDirectIface(t) {
   245			return eq(noescape(unsafe.Pointer(&x.data)), noescape(unsafe.Pointer(&y.data)))
   246		}
   247		return eq(x.data, y.data)
   248	}
   249	
   250	// Testing adapters for hash quality tests (see hash_test.go)
   251	func stringHash(s string, seed uintptr) uintptr {
   252		return algarray[alg_STRING].hash(noescape(unsafe.Pointer(&s)), seed)
   253	}
   254	
   255	func bytesHash(b []byte, seed uintptr) uintptr {
   256		s := (*slice)(unsafe.Pointer(&b))
   257		return memhash(s.array, seed, uintptr(s.len))
   258	}
   259	
   260	func int32Hash(i uint32, seed uintptr) uintptr {
   261		return algarray[alg_MEM32].hash(noescape(unsafe.Pointer(&i)), seed)
   262	}
   263	
   264	func int64Hash(i uint64, seed uintptr) uintptr {
   265		return algarray[alg_MEM64].hash(noescape(unsafe.Pointer(&i)), seed)
   266	}
   267	
   268	func efaceHash(i interface{}, seed uintptr) uintptr {
   269		return algarray[alg_NILINTER].hash(noescape(unsafe.Pointer(&i)), seed)
   270	}
   271	
   272	func ifaceHash(i interface {
   273		F()
   274	}, seed uintptr) uintptr {
   275		return algarray[alg_INTER].hash(noescape(unsafe.Pointer(&i)), seed)
   276	}
   277	
   278	const hashRandomBytes = sys.PtrSize / 4 * 64
   279	
   280	// used in asm_{386,amd64}.s to seed the hash function
   281	var aeskeysched [hashRandomBytes]byte
   282	
   283	// used in hash{32,64}.go to seed the hash function
   284	var hashkey [4]uintptr
   285	
   286	func alginit() {
   287		// Install aes hash algorithm if we have the instructions we need
   288		if (GOARCH == "386" || GOARCH == "amd64") &&
   289			GOOS != "nacl" &&
   290			cpuid_ecx&(1<<25) != 0 && // aes (aesenc)
   291			cpuid_ecx&(1<<9) != 0 && // sse3 (pshufb)
   292			cpuid_ecx&(1<<19) != 0 { // sse4.1 (pinsr{d,q})
   293			useAeshash = true
   294			algarray[alg_MEM32].hash = aeshash32
   295			algarray[alg_MEM64].hash = aeshash64
   296			algarray[alg_STRING].hash = aeshashstr
   297			// Initialize with random data so hash collisions will be hard to engineer.
   298			getRandomData(aeskeysched[:])
   299			return
   300		}
   301		getRandomData((*[len(hashkey) * sys.PtrSize]byte)(unsafe.Pointer(&hashkey))[:])
   302		hashkey[0] |= 1 // make sure these numbers are odd
   303		hashkey[1] |= 1
   304		hashkey[2] |= 1
   305		hashkey[3] |= 1
   306	}
   307	

View as plain text