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
5package runtime
6
7import (
8	"internal/cpu"
9	"runtime/internal/sys"
10	"unsafe"
11)
12
13// For gccgo, use go:linkname to export compiler-called functions.
14//
15//go:linkname memhash0
16//go:linkname memhash8
17//go:linkname memhash16
18//go:linkname memhash32
19//go:linkname memhash64
20//go:linkname memhash128
21//go:linkname strhash
22//go:linkname f32hash
23//go:linkname f64hash
24//go:linkname c64hash
25//go:linkname c128hash
26//go:linkname interhash
27//go:linkname nilinterhash
28//go:linkname memequal0
29//go:linkname memequal8
30//go:linkname memequal16
31//go:linkname memequal32
32//go:linkname memequal64
33//go:linkname memequal128
34//go:linkname strequal
35//go:linkname f32equal
36//go:linkname f64equal
37//go:linkname c64equal
38//go:linkname c128equal
39//go:linkname interequal
40//go:linkname nilinterequal
41//go:linkname efaceeq
42//go:linkname ifaceeq
43//go:linkname ifacevaleq
44//go:linkname ifaceefaceeq
45//go:linkname efacevaleq
46//go:linkname cmpstring
47//
48// Temporary to be called from C code.
49//go:linkname alginit
50
51const (
52	c0 = uintptr((8-sys.PtrSize)/4*2860486313 + (sys.PtrSize-4)/4*33054211828000289)
53	c1 = uintptr((8-sys.PtrSize)/4*3267000013 + (sys.PtrSize-4)/4*23344194077549503)
54)
55
56func memhash0(p unsafe.Pointer, h uintptr) uintptr {
57	return h
58}
59
60func memhash8(p unsafe.Pointer, h uintptr) uintptr {
61	return memhash(p, h, 1)
62}
63
64func memhash16(p unsafe.Pointer, h uintptr) uintptr {
65	return memhash(p, h, 2)
66}
67
68func memhash128(p unsafe.Pointer, h uintptr) uintptr {
69	return memhash(p, h, 16)
70}
71
72// runtime variable to check if the processor we're running on
73// actually supports the instructions used by the AES-based
74// hash implementation.
75var useAeshash bool
76
77// in C code
78func aeshashbody(p unsafe.Pointer, h, s uintptr, sched []byte) uintptr
79
80func aeshash(p unsafe.Pointer, h, s uintptr) uintptr {
81	return aeshashbody(p, h, s, aeskeysched[:])
82}
83
84func aeshashstr(p unsafe.Pointer, h uintptr) uintptr {
85	ps := (*stringStruct)(p)
86	return aeshashbody(unsafe.Pointer(ps.str), h, uintptr(ps.len), aeskeysched[:])
87}
88
89func strhash(a unsafe.Pointer, h uintptr) uintptr {
90	x := (*stringStruct)(a)
91	return memhash(x.str, h, uintptr(x.len))
92}
93
94// NOTE: Because NaN != NaN, a map can contain any
95// number of (mostly useless) entries keyed with NaNs.
96// To avoid long hash chains, we assign a random number
97// as the hash value for a NaN.
98
99func f32hash(p unsafe.Pointer, h uintptr) uintptr {
100	f := *(*float32)(p)
101	switch {
102	case f == 0:
103		return c1 * (c0 ^ h) // +0, -0
104	case f != f:
105		return c1 * (c0 ^ h ^ uintptr(fastrand())) // any kind of NaN
106	default:
107		return memhash(p, h, 4)
108	}
109}
110
111func f64hash(p unsafe.Pointer, h uintptr) uintptr {
112	f := *(*float64)(p)
113	switch {
114	case f == 0:
115		return c1 * (c0 ^ h) // +0, -0
116	case f != f:
117		return c1 * (c0 ^ h ^ uintptr(fastrand())) // any kind of NaN
118	default:
119		return memhash(p, h, 8)
120	}
121}
122
123func c64hash(p unsafe.Pointer, h uintptr) uintptr {
124	x := (*[2]float32)(p)
125	return f32hash(unsafe.Pointer(&x[1]), f32hash(unsafe.Pointer(&x[0]), h))
126}
127
128func c128hash(p unsafe.Pointer, h uintptr) uintptr {
129	x := (*[2]float64)(p)
130	return f64hash(unsafe.Pointer(&x[1]), f64hash(unsafe.Pointer(&x[0]), h))
131}
132
133func interhash(p unsafe.Pointer, h uintptr) uintptr {
134	a := (*iface)(p)
135	tab := a.tab
136	if tab == nil {
137		return h
138	}
139	t := *(**_type)(tab)
140	if t.equal == nil {
141		// Check hashability here. We could do this check inside
142		// typehash, but we want to report the topmost type in
143		// the error text (e.g. in a struct with a field of slice type
144		// we want to report the struct, not the slice).
145		panic(errorString("hash of unhashable type " + t.string()))
146	}
147	if isDirectIface(t) {
148		return c1 * typehash(t, unsafe.Pointer(&a.data), h^c0)
149	} else {
150		return c1 * typehash(t, a.data, h^c0)
151	}
152}
153
154func nilinterhash(p unsafe.Pointer, h uintptr) uintptr {
155	a := (*eface)(p)
156	t := a._type
157	if t == nil {
158		return h
159	}
160	if t.equal == nil {
161		// See comment in interhash above.
162		panic(errorString("hash of unhashable type " + t.string()))
163	}
164	if isDirectIface(t) {
165		return c1 * typehash(t, unsafe.Pointer(&a.data), h^c0)
166	} else {
167		return c1 * typehash(t, a.data, h^c0)
168	}
169}
170
171// typehash computes the hash of the object of type t at address p.
172// h is the seed.
173// This function is seldom used. Most maps use for hashing either
174// fixed functions (e.g. f32hash) or compiler-generated functions
175// (e.g. for a type like struct { x, y string }). This implementation
176// is slower but more general and is used for hashing interface types
177// (called from interhash or nilinterhash, above) or for hashing in
178// maps generated by reflect.MapOf (reflect_typehash, below).
179// Note: this function must match the compiler generated
180// functions exactly. See issue 37716.
181func typehash(t *_type, p unsafe.Pointer, h uintptr) uintptr {
182	if t.tflag&tflagRegularMemory != 0 {
183		// Handle ptr sizes specially, see issue 37086.
184		switch t.size {
185		case 4:
186			return memhash32(p, h)
187		case 8:
188			return memhash64(p, h)
189		default:
190			return memhash(p, h, t.size)
191		}
192	}
193	switch t.kind & kindMask {
194	case kindFloat32:
195		return f32hash(p, h)
196	case kindFloat64:
197		return f64hash(p, h)
198	case kindComplex64:
199		return c64hash(p, h)
200	case kindComplex128:
201		return c128hash(p, h)
202	case kindString:
203		return strhash(p, h)
204	case kindInterface:
205		i := (*interfacetype)(unsafe.Pointer(t))
206		if len(i.methods) == 0 {
207			return nilinterhash(p, h)
208		}
209		return interhash(p, h)
210	case kindArray:
211		a := (*arraytype)(unsafe.Pointer(t))
212		for i := uintptr(0); i < a.len; i++ {
213			h = typehash(a.elem, add(p, i*a.elem.size), h)
214		}
215		return h
216	case kindStruct:
217		s := (*structtype)(unsafe.Pointer(t))
218		for _, f := range s.fields {
219			// TODO: maybe we could hash several contiguous fields all at once.
220			if f.name != nil && *f.name == "_" {
221				continue
222			}
223			h = typehash(f.typ, add(p, f.offset()), h)
224		}
225		return h
226	default:
227		// Should never happen, as typehash should only be called
228		// with comparable types.
229		panic(errorString("hash of unhashable type " + t.string()))
230	}
231}
232
233//go:linkname reflect_typehash reflect.typehash
234func reflect_typehash(t *_type, p unsafe.Pointer, h uintptr) uintptr {
235	return typehash(t, p, h)
236}
237
238func memequal0(p, q unsafe.Pointer) bool {
239	return true
240}
241func memequal8(p, q unsafe.Pointer) bool {
242	return *(*int8)(p) == *(*int8)(q)
243}
244func memequal16(p, q unsafe.Pointer) bool {
245	return *(*int16)(p) == *(*int16)(q)
246}
247func memequal32(p, q unsafe.Pointer) bool {
248	return *(*int32)(p) == *(*int32)(q)
249}
250func memequal64(p, q unsafe.Pointer) bool {
251	return *(*int64)(p) == *(*int64)(q)
252}
253func memequal128(p, q unsafe.Pointer) bool {
254	return *(*[2]int64)(p) == *(*[2]int64)(q)
255}
256func f32equal(p, q unsafe.Pointer) bool {
257	return *(*float32)(p) == *(*float32)(q)
258}
259func f64equal(p, q unsafe.Pointer) bool {
260	return *(*float64)(p) == *(*float64)(q)
261}
262func c64equal(p, q unsafe.Pointer) bool {
263	return *(*complex64)(p) == *(*complex64)(q)
264}
265func c128equal(p, q unsafe.Pointer) bool {
266	return *(*complex128)(p) == *(*complex128)(q)
267}
268func strequal(p, q unsafe.Pointer) bool {
269	return *(*string)(p) == *(*string)(q)
270}
271func interequal(p, q unsafe.Pointer) bool {
272	return ifaceeq(*(*iface)(p), *(*iface)(q))
273}
274func nilinterequal(p, q unsafe.Pointer) bool {
275	return efaceeq(*(*eface)(p), *(*eface)(q))
276}
277func efaceeq(x, y eface) bool {
278	t := x._type
279	if t != y._type {
280		return false
281	}
282	if t == nil {
283		return true
284	}
285	eq := t.equal
286	if eq == nil {
287		panic(errorString("comparing uncomparable type " + t.string()))
288	}
289	if isDirectIface(t) {
290		return x.data == y.data
291	}
292	return eq(x.data, y.data)
293}
294
295func ifaceeq(x, y iface) bool {
296	xtab := x.tab
297	if xtab == nil && y.tab == nil {
298		return true
299	}
300	if xtab == nil || y.tab == nil {
301		return false
302	}
303	t := *(**_type)(xtab)
304	if t != *(**_type)(y.tab) {
305		return false
306	}
307	eq := t.equal
308	if eq == nil {
309		panic(errorString("comparing uncomparable type " + t.string()))
310	}
311	if isDirectIface(t) {
312		// Direct interface types are ptr, chan, map, func, and single-element structs/arrays thereof.
313		// Maps and funcs are not comparable, so they can't reach here.
314		// Ptrs, chans, and single-element items can be compared directly using ==.
315		return x.data == y.data
316	}
317	return eq(x.data, y.data)
318}
319
320func ifacevaleq(x iface, t *_type, p unsafe.Pointer) bool {
321	if x.tab == nil {
322		return false
323	}
324	xt := *(**_type)(x.tab)
325	if xt != t {
326		return false
327	}
328	eq := t.equal
329	if eq == nil {
330		panic(errorString("comparing uncomparable type " + t.string()))
331	}
332	if isDirectIface(t) {
333		return x.data == p
334	}
335	return eq(x.data, p)
336}
337
338func ifaceefaceeq(x iface, y eface) bool {
339	if x.tab == nil && y._type == nil {
340		return true
341	}
342	if x.tab == nil || y._type == nil {
343		return false
344	}
345	xt := *(**_type)(x.tab)
346	if xt != y._type {
347		return false
348	}
349	eq := xt.equal
350	if eq == nil {
351		panic(errorString("comparing uncomparable type " + xt.string()))
352	}
353	if isDirectIface(xt) {
354		return x.data == y.data
355	}
356	return eq(x.data, y.data)
357}
358
359func efacevaleq(x eface, t *_type, p unsafe.Pointer) bool {
360	if x._type == nil {
361		return false
362	}
363	if x._type != t {
364		return false
365	}
366	eq := t.equal
367	if eq == nil {
368		panic(errorString("comparing uncomparable type " + t.string()))
369	}
370	if isDirectIface(t) {
371		// See comment in efaceeq.
372		return x.data == p
373	}
374	return eq(x.data, p)
375}
376
377func cmpstring(x, y string) int {
378	a := stringStructOf(&x)
379	b := stringStructOf(&y)
380	l := a.len
381	if l > b.len {
382		l = b.len
383	}
384	i := memcmp(unsafe.Pointer(a.str), unsafe.Pointer(b.str), uintptr(l))
385	if i != 0 {
386		return int(i)
387	}
388	if a.len < b.len {
389		return -1
390	} else if a.len > b.len {
391		return 1
392	}
393	return 0
394}
395
396// For the unsafe.Pointer type descriptor in libgo/runtime/go-unsafe-pointer.c.
397
398func pointerhash(p unsafe.Pointer, h uintptr) uintptr {
399	return memhash(p, h, unsafe.Sizeof(unsafe.Pointer))
400}
401
402func pointerequal(p, q unsafe.Pointer) bool {
403	return *(*unsafe.Pointer)(p) == *(*unsafe.Pointer)(q)
404}
405
406// Force the creation of function descriptors for equality and hash
407// functions.  These will be referenced directly by the compiler.
408var _ = memhash
409var _ = memhash0
410var _ = memhash8
411var _ = memhash16
412var _ = memhash32
413var _ = memhash64
414var _ = memhash128
415var _ = strhash
416var _ = f32hash
417var _ = f64hash
418var _ = c64hash
419var _ = c128hash
420var _ = interhash
421var _ = nilinterhash
422var _ = memequal0
423var _ = memequal8
424var _ = memequal16
425var _ = memequal32
426var _ = memequal64
427var _ = memequal128
428var _ = f32equal
429var _ = f64equal
430var _ = c64equal
431var _ = c128equal
432var _ = strequal
433var _ = interequal
434var _ = nilinterequal
435var _ = pointerhash
436var _ = pointerequal
437
438// Testing adapters for hash quality tests (see hash_test.go)
439func stringHash(s string, seed uintptr) uintptr {
440	return strhash(noescape(unsafe.Pointer(&s)), seed)
441}
442
443func bytesHash(b []byte, seed uintptr) uintptr {
444	s := (*slice)(unsafe.Pointer(&b))
445	return memhash(s.array, seed, uintptr(s.len))
446}
447
448func int32Hash(i uint32, seed uintptr) uintptr {
449	return memhash32(noescape(unsafe.Pointer(&i)), seed)
450}
451
452func int64Hash(i uint64, seed uintptr) uintptr {
453	return memhash64(noescape(unsafe.Pointer(&i)), seed)
454}
455
456func efaceHash(i interface{}, seed uintptr) uintptr {
457	return nilinterhash(noescape(unsafe.Pointer(&i)), seed)
458}
459
460func ifaceHash(i interface {
461	F()
462}, seed uintptr) uintptr {
463	return interhash(noescape(unsafe.Pointer(&i)), seed)
464}
465
466const hashRandomBytes = sys.PtrSize / 4 * 64
467
468// used in asm_{386,amd64,arm64}.s to seed the hash function
469var aeskeysched [hashRandomBytes]byte
470
471// used in hash{32,64}.go to seed the hash function
472var hashkey [4]uintptr
473
474func alginit() {
475	// Install AES hash algorithms if the instructions needed are present.
476	if (GOARCH == "386" || GOARCH == "amd64") &&
477		support_aes &&
478		cpu.X86.HasAES && // AESENC
479		cpu.X86.HasSSSE3 && // PSHUFB
480		cpu.X86.HasSSE41 { // PINSR{D,Q}
481		initAlgAES()
482		return
483	}
484	if GOARCH == "arm64" && cpu.ARM64.HasAES {
485		initAlgAES()
486		return
487	}
488	getRandomData((*[len(hashkey) * sys.PtrSize]byte)(unsafe.Pointer(&hashkey))[:])
489	hashkey[0] |= 1 // make sure these numbers are odd
490	hashkey[1] |= 1
491	hashkey[2] |= 1
492	hashkey[3] |= 1
493}
494
495func initAlgAES() {
496	useAeshash = true
497	// Initialize with random data so hash collisions will be hard to engineer.
498	getRandomData(aeskeysched[:])
499}
500
501// Note: These routines perform the read with a native endianness.
502func readUnaligned32(p unsafe.Pointer) uint32 {
503	q := (*[4]byte)(p)
504	if sys.BigEndian {
505		return uint32(q[3]) | uint32(q[2])<<8 | uint32(q[1])<<16 | uint32(q[0])<<24
506	}
507	return uint32(q[0]) | uint32(q[1])<<8 | uint32(q[2])<<16 | uint32(q[3])<<24
508}
509
510func readUnaligned64(p unsafe.Pointer) uint64 {
511	q := (*[8]byte)(p)
512	if sys.BigEndian {
513		return uint64(q[7]) | uint64(q[6])<<8 | uint64(q[5])<<16 | uint64(q[4])<<24 |
514			uint64(q[3])<<32 | uint64(q[2])<<40 | uint64(q[1])<<48 | uint64(q[0])<<56
515	}
516	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
517}
518