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	"runtime/internal/sys"
9	"unsafe"
10)
11
12// For gccgo, use go:linkname to rename compiler-called functions to
13// themselves, so that the compiler will export them.
14//
15//go:linkname memhash0 runtime.memhash0
16//go:linkname memhash8 runtime.memhash8
17//go:linkname memhash16 runtime.memhash16
18//go:linkname memhash32 runtime.memhash32
19//go:linkname memhash64 runtime.memhash64
20//go:linkname memhash128 runtime.memhash128
21//go:linkname strhash runtime.strhash
22//go:linkname f32hash runtime.f32hash
23//go:linkname f64hash runtime.f64hash
24//go:linkname c64hash runtime.c64hash
25//go:linkname c128hash runtime.c128hash
26//go:linkname interhash runtime.interhash
27//go:linkname nilinterhash runtime.nilinterhash
28//go:linkname memequal0 runtime.memequal0
29//go:linkname memequal8 runtime.memequal8
30//go:linkname memequal16 runtime.memequal16
31//go:linkname memequal32 runtime.memequal32
32//go:linkname memequal64 runtime.memequal64
33//go:linkname memequal128 runtime.memequal128
34//go:linkname strequal runtime.strequal
35//go:linkname f32equal runtime.f32equal
36//go:linkname f64equal runtime.f64equal
37//go:linkname c64equal runtime.c64equal
38//go:linkname c128equal runtime.c128equal
39//go:linkname interequal runtime.interequal
40//go:linkname nilinterequal runtime.nilinterequal
41//go:linkname efaceeq runtime.efaceeq
42//go:linkname ifaceeq runtime.ifaceeq
43//go:linkname ifacevaleq runtime.ifacevaleq
44//go:linkname ifaceefaceeq runtime.ifaceefaceeq
45//go:linkname efacevaleq runtime.efacevaleq
46//go:linkname eqstring runtime.eqstring
47//go:linkname cmpstring runtime.cmpstring
48//
49// Temporary to be called from C code.
50//go:linkname alginit runtime.alginit
51
52const (
53	c0 = uintptr((8-sys.PtrSize)/4*2860486313 + (sys.PtrSize-4)/4*33054211828000289)
54	c1 = uintptr((8-sys.PtrSize)/4*3267000013 + (sys.PtrSize-4)/4*23344194077549503)
55)
56
57func memhash0(p unsafe.Pointer, h uintptr) uintptr {
58	return h
59}
60
61func memhash8(p unsafe.Pointer, h uintptr) uintptr {
62	return memhash(p, h, 1)
63}
64
65func memhash16(p unsafe.Pointer, h uintptr) uintptr {
66	return memhash(p, h, 2)
67}
68
69func memhash128(p unsafe.Pointer, h uintptr) uintptr {
70	return memhash(p, h, 16)
71}
72
73var useAeshash bool
74
75// in C code
76func aeshashbody(p unsafe.Pointer, h, s uintptr, sched []byte) uintptr
77
78func aeshash(p unsafe.Pointer, h, s uintptr) uintptr {
79	return aeshashbody(p, h, s, aeskeysched[:])
80}
81
82func aeshashstr(p unsafe.Pointer, h uintptr) uintptr {
83	ps := (*stringStruct)(p)
84	return aeshashbody(unsafe.Pointer(ps.str), h, uintptr(ps.len), aeskeysched[:])
85}
86
87func strhash(a unsafe.Pointer, h uintptr) uintptr {
88	x := (*stringStruct)(a)
89	return memhash(x.str, h, uintptr(x.len))
90}
91
92// NOTE: Because NaN != NaN, a map can contain any
93// number of (mostly useless) entries keyed with NaNs.
94// To avoid long hash chains, we assign a random number
95// as the hash value for a NaN.
96
97func f32hash(p unsafe.Pointer, h uintptr) uintptr {
98	f := *(*float32)(p)
99	switch {
100	case f == 0:
101		return c1 * (c0 ^ h) // +0, -0
102	case f != f:
103		return c1 * (c0 ^ h ^ uintptr(fastrand())) // any kind of NaN
104	default:
105		return memhash(p, h, 4)
106	}
107}
108
109func f64hash(p unsafe.Pointer, h uintptr) uintptr {
110	f := *(*float64)(p)
111	switch {
112	case f == 0:
113		return c1 * (c0 ^ h) // +0, -0
114	case f != f:
115		return c1 * (c0 ^ h ^ uintptr(fastrand())) // any kind of NaN
116	default:
117		return memhash(p, h, 8)
118	}
119}
120
121func c64hash(p unsafe.Pointer, h uintptr) uintptr {
122	x := (*[2]float32)(p)
123	return f32hash(unsafe.Pointer(&x[1]), f32hash(unsafe.Pointer(&x[0]), h))
124}
125
126func c128hash(p unsafe.Pointer, h uintptr) uintptr {
127	x := (*[2]float64)(p)
128	return f64hash(unsafe.Pointer(&x[1]), f64hash(unsafe.Pointer(&x[0]), h))
129}
130
131func interhash(p unsafe.Pointer, h uintptr) uintptr {
132	a := (*iface)(p)
133	tab := a.tab
134	if tab == nil {
135		return h
136	}
137	t := *(**_type)(tab)
138	fn := t.hashfn
139	if fn == nil {
140		panic(errorString("hash of unhashable type " + *t.string))
141	}
142	if isDirectIface(t) {
143		return c1 * fn(unsafe.Pointer(&a.data), h^c0)
144	} else {
145		return c1 * fn(a.data, h^c0)
146	}
147}
148
149func nilinterhash(p unsafe.Pointer, h uintptr) uintptr {
150	a := (*eface)(p)
151	t := a._type
152	if t == nil {
153		return h
154	}
155	fn := t.hashfn
156	if fn == nil {
157		panic(errorString("hash of unhashable type " + *t.string))
158	}
159	if isDirectIface(t) {
160		return c1 * fn(unsafe.Pointer(&a.data), h^c0)
161	} else {
162		return c1 * fn(a.data, h^c0)
163	}
164}
165
166func memequal0(p, q unsafe.Pointer) bool {
167	return true
168}
169func memequal8(p, q unsafe.Pointer) bool {
170	return *(*int8)(p) == *(*int8)(q)
171}
172func memequal16(p, q unsafe.Pointer) bool {
173	return *(*int16)(p) == *(*int16)(q)
174}
175func memequal32(p, q unsafe.Pointer) bool {
176	return *(*int32)(p) == *(*int32)(q)
177}
178func memequal64(p, q unsafe.Pointer) bool {
179	return *(*int64)(p) == *(*int64)(q)
180}
181func memequal128(p, q unsafe.Pointer) bool {
182	return *(*[2]int64)(p) == *(*[2]int64)(q)
183}
184func f32equal(p, q unsafe.Pointer) bool {
185	return *(*float32)(p) == *(*float32)(q)
186}
187func f64equal(p, q unsafe.Pointer) bool {
188	return *(*float64)(p) == *(*float64)(q)
189}
190func c64equal(p, q unsafe.Pointer) bool {
191	return *(*complex64)(p) == *(*complex64)(q)
192}
193func c128equal(p, q unsafe.Pointer) bool {
194	return *(*complex128)(p) == *(*complex128)(q)
195}
196func strequal(p, q unsafe.Pointer) bool {
197	return *(*string)(p) == *(*string)(q)
198}
199func interequal(p, q unsafe.Pointer) bool {
200	return ifaceeq(*(*iface)(p), *(*iface)(q))
201}
202func nilinterequal(p, q unsafe.Pointer) bool {
203	return efaceeq(*(*eface)(p), *(*eface)(q))
204}
205func efaceeq(x, y eface) bool {
206	t := x._type
207	if !eqtype(t, y._type) {
208		return false
209	}
210	if t == nil {
211		return true
212	}
213	eq := t.equalfn
214	if eq == nil {
215		panic(errorString("comparing uncomparable type " + *t.string))
216	}
217	if isDirectIface(t) {
218		return x.data == y.data
219	}
220	return eq(x.data, y.data)
221}
222func ifaceeq(x, y iface) bool {
223	xtab := x.tab
224	if xtab == nil && y.tab == nil {
225		return true
226	}
227	if xtab == nil || y.tab == nil {
228		return false
229	}
230	t := *(**_type)(xtab)
231	if !eqtype(t, *(**_type)(y.tab)) {
232		return false
233	}
234	eq := t.equalfn
235	if eq == nil {
236		panic(errorString("comparing uncomparable type " + *t.string))
237	}
238	if isDirectIface(t) {
239		return x.data == y.data
240	}
241	return eq(x.data, y.data)
242}
243
244func ifacevaleq(x iface, t *_type, p unsafe.Pointer) bool {
245	if x.tab == nil {
246		return false
247	}
248	xt := *(**_type)(x.tab)
249	if !eqtype(xt, t) {
250		return false
251	}
252	eq := t.equalfn
253	if eq == nil {
254		panic(errorString("comparing uncomparable type " + *t.string))
255	}
256	if isDirectIface(t) {
257		return x.data == p
258	}
259	return eq(x.data, p)
260}
261
262func ifaceefaceeq(x iface, y eface) bool {
263	if x.tab == nil && y._type == nil {
264		return true
265	}
266	if x.tab == nil || y._type == nil {
267		return false
268	}
269	xt := *(**_type)(x.tab)
270	if !eqtype(xt, y._type) {
271		return false
272	}
273	eq := xt.equalfn
274	if eq == nil {
275		panic(errorString("comparing uncomparable type " + *xt.string))
276	}
277	if isDirectIface(xt) {
278		return x.data == y.data
279	}
280	return eq(x.data, y.data)
281}
282
283func efacevaleq(x eface, t *_type, p unsafe.Pointer) bool {
284	if x._type == nil {
285		return false
286	}
287	if !eqtype(x._type, t) {
288		return false
289	}
290	eq := t.equalfn
291	if eq == nil {
292		panic(errorString("comparing uncomparable type " + *t.string))
293	}
294	if isDirectIface(t) {
295		return x.data == p
296	}
297	return eq(x.data, p)
298}
299
300func cmpstring(x, y string) int {
301	a := stringStructOf(&x)
302	b := stringStructOf(&y)
303	l := a.len
304	if l > b.len {
305		l = b.len
306	}
307	i := memcmp(unsafe.Pointer(a.str), unsafe.Pointer(b.str), uintptr(l))
308	if i != 0 {
309		return int(i)
310	}
311	if a.len < b.len {
312		return -1
313	} else if a.len > b.len {
314		return 1
315	}
316	return 0
317}
318
319// For the unsafe.Pointer type descriptor in libgo/runtime/go-unsafe-pointer.c.
320
321func pointerhash(p unsafe.Pointer, h uintptr) uintptr {
322	return memhash(p, h, unsafe.Sizeof(unsafe.Pointer))
323}
324
325func pointerequal(p, q unsafe.Pointer) bool {
326	return *(*unsafe.Pointer)(p) == *(*unsafe.Pointer)(q)
327}
328
329// Force the creation of function descriptors for equality and hash
330// functions.  These will be referenced directly by the compiler.
331var _ = memhash
332var _ = memhash0
333var _ = memhash8
334var _ = memhash16
335var _ = memhash32
336var _ = memhash64
337var _ = memhash128
338var _ = strhash
339var _ = f32hash
340var _ = f64hash
341var _ = c64hash
342var _ = c128hash
343var _ = interhash
344var _ = nilinterhash
345var _ = memequal0
346var _ = memequal8
347var _ = memequal16
348var _ = memequal32
349var _ = memequal64
350var _ = memequal128
351var _ = f32equal
352var _ = f64equal
353var _ = c64equal
354var _ = c128equal
355var _ = strequal
356var _ = interequal
357var _ = nilinterequal
358var _ = pointerhash
359var _ = pointerequal
360
361// Testing adapters for hash quality tests (see hash_test.go)
362func stringHash(s string, seed uintptr) uintptr {
363	return strhash(noescape(unsafe.Pointer(&s)), seed)
364}
365
366func bytesHash(b []byte, seed uintptr) uintptr {
367	s := (*slice)(unsafe.Pointer(&b))
368	return memhash(s.array, seed, uintptr(s.len))
369}
370
371func int32Hash(i uint32, seed uintptr) uintptr {
372	return memhash32(noescape(unsafe.Pointer(&i)), seed)
373}
374
375func int64Hash(i uint64, seed uintptr) uintptr {
376	return memhash64(noescape(unsafe.Pointer(&i)), seed)
377}
378
379func efaceHash(i interface{}, seed uintptr) uintptr {
380	return nilinterhash(noescape(unsafe.Pointer(&i)), seed)
381}
382
383func ifaceHash(i interface {
384	F()
385}, seed uintptr) uintptr {
386	return interhash(noescape(unsafe.Pointer(&i)), seed)
387}
388
389const hashRandomBytes = sys.PtrSize / 4 * 64
390
391// used in asm_{386,amd64}.s to seed the hash function
392var aeskeysched [hashRandomBytes]byte
393
394// used in hash{32,64}.go to seed the hash function
395var hashkey [4]uintptr
396
397func alginit() {
398	// Install aes hash algorithm if we have the instructions we need
399	if (GOARCH == "386" || GOARCH == "amd64") &&
400		GOOS != "nacl" &&
401		support_aes &&
402		cpuid_ecx&(1<<25) != 0 && // aes (aesenc)
403		cpuid_ecx&(1<<9) != 0 && // sse3 (pshufb)
404		cpuid_ecx&(1<<19) != 0 { // sse4.1 (pinsr{d,q})
405		useAeshash = true
406		// Initialize with random data so hash collisions will be hard to engineer.
407		getRandomData(aeskeysched[:])
408		return
409	}
410	getRandomData((*[len(hashkey) * sys.PtrSize]byte)(unsafe.Pointer(&hashkey))[:])
411	hashkey[0] |= 1 // make sure these numbers are odd
412	hashkey[1] |= 1
413	hashkey[2] |= 1
414	hashkey[3] |= 1
415}
416