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		"internal/cpu"
     9		"runtime/internal/sys"
    10		"unsafe"
    11	)
    12	
    13	const (
    14		c0 = uintptr((8-sys.PtrSize)/4*2860486313 + (sys.PtrSize-4)/4*33054211828000289)
    15		c1 = uintptr((8-sys.PtrSize)/4*3267000013 + (sys.PtrSize-4)/4*23344194077549503)
    16	)
    17	
    18	// type algorithms - known to compiler
    19	const (
    20		alg_NOEQ = iota
    21		alg_MEM0
    22		alg_MEM8
    23		alg_MEM16
    24		alg_MEM32
    25		alg_MEM64
    26		alg_MEM128
    27		alg_STRING
    28		alg_INTER
    29		alg_NILINTER
    30		alg_FLOAT32
    31		alg_FLOAT64
    32		alg_CPLX64
    33		alg_CPLX128
    34		alg_max
    35	)
    36	
    37	// typeAlg is also copied/used in reflect/type.go.
    38	// keep them in sync.
    39	type typeAlg struct {
    40		// function for hashing objects of this type
    41		// (ptr to object, seed) -> hash
    42		hash func(unsafe.Pointer, uintptr) uintptr
    43		// function for comparing objects of this type
    44		// (ptr to object A, ptr to object B) -> ==?
    45		equal func(unsafe.Pointer, unsafe.Pointer) bool
    46	}
    47	
    48	func memhash0(p unsafe.Pointer, h uintptr) uintptr {
    49		return h
    50	}
    51	
    52	func memhash8(p unsafe.Pointer, h uintptr) uintptr {
    53		return memhash(p, h, 1)
    54	}
    55	
    56	func memhash16(p unsafe.Pointer, h uintptr) uintptr {
    57		return memhash(p, h, 2)
    58	}
    59	
    60	func memhash128(p unsafe.Pointer, h uintptr) uintptr {
    61		return memhash(p, h, 16)
    62	}
    63	
    64	//go:nosplit
    65	func memhash_varlen(p unsafe.Pointer, h uintptr) uintptr {
    66		ptr := getclosureptr()
    67		size := *(*uintptr)(unsafe.Pointer(ptr + unsafe.Sizeof(h)))
    68		return memhash(p, h, size)
    69	}
    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		x := *(*iface)(p)
   210		y := *(*iface)(q)
   211		return x.tab == y.tab && ifaceeq(x.tab, x.data, y.data)
   212	}
   213	func nilinterequal(p, q unsafe.Pointer) bool {
   214		x := *(*eface)(p)
   215		y := *(*eface)(q)
   216		return x._type == y._type && efaceeq(x._type, x.data, y.data)
   217	}
   218	func efaceeq(t *_type, x, y unsafe.Pointer) bool {
   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			// Direct interface types are ptr, chan, map, func, and single-element structs/arrays thereof.
   228			// Maps and funcs are not comparable, so they can't reach here.
   229			// Ptrs, chans, and single-element items can be compared directly using ==.
   230			return x == y
   231		}
   232		return eq(x, y)
   233	}
   234	func ifaceeq(tab *itab, x, y unsafe.Pointer) bool {
   235		if tab == nil {
   236			return true
   237		}
   238		t := tab._type
   239		eq := t.alg.equal
   240		if eq == nil {
   241			panic(errorString("comparing uncomparable type " + t.string()))
   242		}
   243		if isDirectIface(t) {
   244			// See comment in efaceeq.
   245			return x == y
   246		}
   247		return eq(x, y)
   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,arm64}.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 algorithms if the instructions needed are present.
   288		if (GOARCH == "386" || GOARCH == "amd64") &&
   289			GOOS != "nacl" &&
   290			cpu.X86.HasAES && // AESENC
   291			cpu.X86.HasSSSE3 && // PSHUFB
   292			cpu.X86.HasSSE41 { // PINSR{D,Q}
   293			initAlgAES()
   294			return
   295		}
   296		if GOARCH == "arm64" && cpu.ARM64.HasAES {
   297			initAlgAES()
   298			return
   299		}
   300		getRandomData((*[len(hashkey) * sys.PtrSize]byte)(unsafe.Pointer(&hashkey))[:])
   301		hashkey[0] |= 1 // make sure these numbers are odd
   302		hashkey[1] |= 1
   303		hashkey[2] |= 1
   304		hashkey[3] |= 1
   305	}
   306	
   307	func initAlgAES() {
   308		if GOOS == "aix" {
   309			// runtime.algarray is immutable on AIX: see cmd/link/internal/ld/xcoff.go
   310			return
   311		}
   312		useAeshash = true
   313		algarray[alg_MEM32].hash = aeshash32
   314		algarray[alg_MEM64].hash = aeshash64
   315		algarray[alg_STRING].hash = aeshashstr
   316		// Initialize with random data so hash collisions will be hard to engineer.
   317		getRandomData(aeskeysched[:])
   318	}
   319	
   320	// Note: These routines perform the read with an native endianness.
   321	func readUnaligned32(p unsafe.Pointer) uint32 {
   322		q := (*[4]byte)(p)
   323		if sys.BigEndian {
   324			return uint32(q[3]) | uint32(q[2])<<8 | uint32(q[1])<<16 | uint32(q[0])<<24
   325		}
   326		return uint32(q[0]) | uint32(q[1])<<8 | uint32(q[2])<<16 | uint32(q[3])<<24
   327	}
   328	
   329	func readUnaligned64(p unsafe.Pointer) uint64 {
   330		q := (*[8]byte)(p)
   331		if sys.BigEndian {
   332			return uint64(q[7]) | uint64(q[6])<<8 | uint64(q[5])<<16 | uint64(q[4])<<24 |
   333				uint64(q[3])<<32 | uint64(q[2])<<40 | uint64(q[1])<<48 | uint64(q[0])<<56
   334		}
   335		return uint64(q[0]) | uint64(q[1])<<8 | uint64(q[2])<<16 | uint64(q[3])<<24 | uint64(q[4])<<32 | uint64(q[5])<<40 | uint64(q[6])<<48 | uint64(q[7])<<56
   336	}
   337	

View as plain text