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.
13 // For gccgo, use go:linkname to export compiler-called functions.
15 //go:linkname memhash0
16 //go:linkname memhash8
17 //go:linkname memhash16
18 //go:linkname memhash32
19 //go:linkname memhash64
20 //go:linkname memhash128
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
43 //go:linkname ifacevaleq
44 //go:linkname ifaceefaceeq
45 //go:linkname efacevaleq
46 //go:linkname cmpstring
48 // Temporary to be called from C code.
52 c0
= uintptr((8-goarch
.PtrSize
)/4*2860486313 + (goarch
.PtrSize
-4)/4*33054211828000289)
53 c1
= uintptr((8-goarch
.PtrSize
)/4*3267000013 + (goarch
.PtrSize
-4)/4*23344194077549503)
56 func memhash0(p unsafe
.Pointer
, h
uintptr) uintptr {
60 func memhash8(p unsafe
.Pointer
, h
uintptr) uintptr {
61 return memhash(p
, h
, 1)
64 func memhash16(p unsafe
.Pointer
, h
uintptr) uintptr {
65 return memhash(p
, h
, 2)
68 func memhash128(p unsafe
.Pointer
, h
uintptr) uintptr {
69 return memhash(p
, h
, 16)
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.
78 func aeshashbody(p unsafe
.Pointer
, h
, s
uintptr, sched
[]byte) uintptr
80 func aeshash(p unsafe
.Pointer
, h
, s
uintptr) uintptr {
81 return aeshashbody(p
, h
, s
, aeskeysched
[:])
84 func aeshashstr(p unsafe
.Pointer
, h
uintptr) uintptr {
85 ps
:= (*stringStruct
)(p
)
86 return aeshashbody(unsafe
.Pointer(ps
.str
), h
, uintptr(ps
.len), aeskeysched
[:])
89 func strhash(a unsafe
.Pointer
, h
uintptr) uintptr {
90 x
:= (*stringStruct
)(a
)
91 return memhash(x
.str
, h
, uintptr(x
.len))
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.
99 func f32hash(p unsafe
.Pointer
, h
uintptr) uintptr {
103 return c1
* (c0
^ h
) // +0, -0
105 return c1
* (c0
^ h
^ uintptr(fastrand())) // any kind of NaN
107 return memhash(p
, h
, 4)
111 func f64hash(p unsafe
.Pointer
, h
uintptr) uintptr {
115 return c1
* (c0
^ h
) // +0, -0
117 return c1
* (c0
^ h
^ uintptr(fastrand())) // any kind of NaN
119 return memhash(p
, h
, 8)
123 func 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
))
128 func 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
))
133 func interhash(p unsafe
.Pointer
, h
uintptr) uintptr {
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()))
147 if isDirectIface(t
) {
148 return c1
* typehash(t
, unsafe
.Pointer(&a
.data
), h
^c0
)
150 return c1
* typehash(t
, a
.data
, h
^c0
)
154 func nilinterhash(p unsafe
.Pointer
, h
uintptr) uintptr {
161 // See comment in interhash above.
162 panic(errorString("hash of unhashable type " + t
.string()))
164 if isDirectIface(t
) {
165 return c1
* typehash(t
, unsafe
.Pointer(&a
.data
), h
^c0
)
167 return c1
* typehash(t
, a
.data
, h
^c0
)
171 // typehash computes the hash of the object of type t at address p.
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.
181 func typehash(t
*_type
, p unsafe
.Pointer
, h
uintptr) uintptr {
182 if t
.tflag
&tflagRegularMemory
!= 0 {
183 // Handle ptr sizes specially, see issue 37086.
186 return memhash32(p
, h
)
188 return memhash64(p
, h
)
190 return memhash(p
, h
, t
.size
)
193 switch t
.kind
& kindMask
{
201 return c128hash(p
, h
)
205 i
:= (*interfacetype
)(unsafe
.Pointer(t
))
206 if len(i
.methods
) == 0 {
207 return nilinterhash(p
, h
)
209 return interhash(p
, h
)
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
)
217 s
:= (*structtype
)(unsafe
.Pointer(t
))
218 for _
, f
:= range s
.fields
{
219 if f
.name
!= nil && *f
.name
== "_" {
222 h
= typehash(f
.typ
, add(p
, f
.offset()), h
)
226 // Should never happen, as typehash should only be called
227 // with comparable types.
228 panic(errorString("hash of unhashable type " + t
.string()))
232 //go:linkname reflect_typehash reflect.typehash
233 func reflect_typehash(t
*_type
, p unsafe
.Pointer
, h
uintptr) uintptr {
234 return typehash(t
, p
, h
)
237 func memequal0(p
, q unsafe
.Pointer
) bool {
240 func memequal8(p
, q unsafe
.Pointer
) bool {
241 return *(*int8)(p
) == *(*int8)(q
)
243 func memequal16(p
, q unsafe
.Pointer
) bool {
244 return *(*int16)(p
) == *(*int16)(q
)
246 func memequal32(p
, q unsafe
.Pointer
) bool {
247 return *(*int32)(p
) == *(*int32)(q
)
249 func memequal64(p
, q unsafe
.Pointer
) bool {
250 return *(*int64)(p
) == *(*int64)(q
)
252 func memequal128(p
, q unsafe
.Pointer
) bool {
253 return *(*[2]int64)(p
) == *(*[2]int64)(q
)
255 func f32equal(p
, q unsafe
.Pointer
) bool {
256 return *(*float32)(p
) == *(*float32)(q
)
258 func f64equal(p
, q unsafe
.Pointer
) bool {
259 return *(*float64)(p
) == *(*float64)(q
)
261 func c64equal(p
, q unsafe
.Pointer
) bool {
262 return *(*complex64
)(p
) == *(*complex64
)(q
)
264 func c128equal(p
, q unsafe
.Pointer
) bool {
265 return *(*complex128
)(p
) == *(*complex128
)(q
)
267 func strequal(p
, q unsafe
.Pointer
) bool {
268 return *(*string)(p
) == *(*string)(q
)
270 func interequal(p
, q unsafe
.Pointer
) bool {
271 return ifaceeq(*(*iface
)(p
), *(*iface
)(q
))
273 func nilinterequal(p
, q unsafe
.Pointer
) bool {
274 return efaceeq(*(*eface
)(p
), *(*eface
)(q
))
276 func efaceeq(x
, y eface
) bool {
278 if !eqtype(t
, y
._type
) {
286 panic(errorString("comparing uncomparable type " + t
.string()))
288 if isDirectIface(t
) {
289 return x
.data
== y
.data
291 return eq(x
.data
, y
.data
)
294 func ifaceeq(x
, y iface
) bool {
296 if xtab
== nil && y
.tab
== nil {
299 if xtab
== nil || y
.tab
== nil {
302 t
:= *(**_type
)(xtab
)
303 if !eqtype(t
, *(**_type
)(y
.tab
)) {
308 panic(errorString("comparing uncomparable type " + t
.string()))
310 if isDirectIface(t
) {
311 // Direct interface types are ptr, chan, map, func, and single-element structs/arrays thereof.
312 // Maps and funcs are not comparable, so they can't reach here.
313 // Ptrs, chans, and single-element items can be compared directly using ==.
314 return x
.data
== y
.data
316 return eq(x
.data
, y
.data
)
319 func ifacevaleq(x iface
, t
*_type
, p unsafe
.Pointer
) bool {
323 xt
:= *(**_type
)(x
.tab
)
329 panic(errorString("comparing uncomparable type " + t
.string()))
331 if isDirectIface(t
) {
337 func ifaceefaceeq(x iface
, y eface
) bool {
338 if x
.tab
== nil && y
._type
== nil {
341 if x
.tab
== nil || y
._type
== nil {
344 xt
:= *(**_type
)(x
.tab
)
345 if !eqtype(xt
, y
._type
) {
350 panic(errorString("comparing uncomparable type " + xt
.string()))
352 if isDirectIface(xt
) {
353 return x
.data
== y
.data
355 return eq(x
.data
, y
.data
)
358 func efacevaleq(x eface
, t
*_type
, p unsafe
.Pointer
) bool {
362 if !eqtype(x
._type
, t
) {
367 panic(errorString("comparing uncomparable type " + t
.string()))
369 if isDirectIface(t
) {
370 // See comment in efaceeq.
376 func cmpstring(x
, y
string) int {
377 a
:= stringStructOf(&x
)
378 b
:= stringStructOf(&y
)
383 i
:= memcmp(unsafe
.Pointer(a
.str
), unsafe
.Pointer(b
.str
), uintptr(l
))
389 } else if a
.len > b
.len {
395 // For the unsafe.Pointer type descriptor in libgo/runtime/go-unsafe-pointer.c.
397 func pointerhash(p unsafe
.Pointer
, h
uintptr) uintptr {
398 return memhash(p
, h
, unsafe
.Sizeof(unsafe
.Pointer
))
401 func pointerequal(p
, q unsafe
.Pointer
) bool {
402 return *(*unsafe
.Pointer
)(p
) == *(*unsafe
.Pointer
)(q
)
405 // Force the creation of function descriptors for equality and hash
406 // functions. These will be referenced directly by the compiler.
433 var _
= nilinterequal
437 // Testing adapters for hash quality tests (see hash_test.go)
438 func stringHash(s
string, seed
uintptr) uintptr {
439 return strhash(noescape(unsafe
.Pointer(&s
)), seed
)
442 func bytesHash(b
[]byte, seed
uintptr) uintptr {
443 s
:= (*slice
)(unsafe
.Pointer(&b
))
444 return memhash(s
.array
, seed
, uintptr(s
.len))
447 func int32Hash(i
uint32, seed
uintptr) uintptr {
448 return memhash32(noescape(unsafe
.Pointer(&i
)), seed
)
451 func int64Hash(i
uint64, seed
uintptr) uintptr {
452 return memhash64(noescape(unsafe
.Pointer(&i
)), seed
)
455 func efaceHash(i any
, seed
uintptr) uintptr {
456 return nilinterhash(noescape(unsafe
.Pointer(&i
)), seed
)
459 func ifaceHash(i
interface {
461 }, seed
uintptr) uintptr {
462 return interhash(noescape(unsafe
.Pointer(&i
)), seed
)
465 const hashRandomBytes
= goarch
.PtrSize
/ 4 * 64
467 // used in asm_{386,amd64,arm64}.s to seed the hash function
468 var aeskeysched
[hashRandomBytes
]byte
470 // used in hash{32,64}.go to seed the hash function
471 var hashkey
[4]uintptr
474 // Install AES hash algorithms if the instructions needed are present.
475 if (GOARCH
== "386" || GOARCH
== "amd64") &&
477 cpu
.X86
.HasAES
&& // AESENC
478 cpu
.X86
.HasSSSE3
&& // PSHUFB
479 cpu
.X86
.HasSSE41
{ // PINSR{D,Q}
483 if GOARCH
== "arm64" && cpu
.ARM64
.HasAES
{
487 getRandomData((*[len(hashkey
) * goarch
.PtrSize
]byte)(unsafe
.Pointer(&hashkey
))[:])
488 hashkey
[0] |
= 1 // make sure these numbers are odd
496 // Initialize with random data so hash collisions will be hard to engineer.
497 getRandomData(aeskeysched
[:])
500 // Note: These routines perform the read with a native endianness.
501 func readUnaligned32(p unsafe
.Pointer
) uint32 {
503 if goarch
.BigEndian
{
504 return uint32(q
[3]) |
uint32(q
[2])<<8 |
uint32(q
[1])<<16 |
uint32(q
[0])<<24
506 return uint32(q
[0]) |
uint32(q
[1])<<8 |
uint32(q
[2])<<16 |
uint32(q
[3])<<24
509 func readUnaligned64(p unsafe
.Pointer
) uint64 {
511 if goarch
.BigEndian
{
512 return uint64(q
[7]) |
uint64(q
[6])<<8 |
uint64(q
[5])<<16 |
uint64(q
[4])<<24 |
513 uint64(q
[3])<<32 |
uint64(q
[2])<<40 |
uint64(q
[1])<<48 |
uint64(q
[0])<<56
515 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