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