libgo/go/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         "internal/goarch"
  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
  51 const (
  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)
  54 )
  55
  56 func memhash0(p unsafe.Pointer, h uintptr) uintptr {
  57         return h
  58 }
  59
  60 func memhash8(p unsafe.Pointer, h uintptr) uintptr {
  61         return memhash(p, h, 1)
  62 }
  63
  64 func memhash16(p unsafe.Pointer, h uintptr) uintptr {
  65         return memhash(p, h, 2)
  66 }
  67
  68 func 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.
  75 var useAeshash bool
  76
  77 // in C code
  78 func aeshashbody(p unsafe.Pointer, h, s uintptr, sched []byte) uintptr
  79
  80 func aeshash(p unsafe.Pointer, h, s uintptr) uintptr {
  81         return aeshashbody(p, h, s, aeskeysched[:])
  82 }
  83
  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[:])
  87 }
  88
  89 func 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
  99 func 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
 111 func 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
 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))
 126 }
 127
 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))
 131 }
 132
 133 func 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
 154 func 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.
 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.
 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                         if f.name != nil && *f.name == "_" {
 220                                 continue
 221                         }
 222                         h = typehash(f.typ, add(p, f.offset()), h)
 223                 }
 224                 return h
 225         default:
 226                 // Should never happen, as typehash should only be called
 227                 // with comparable types.
 228                 panic(errorString("hash of unhashable type " + t.string()))
 229         }
 230 }
 231
 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)
 235 }
 236
 237 func memequal0(p, q unsafe.Pointer) bool {
 238         return true
 239 }
 240 func memequal8(p, q unsafe.Pointer) bool {
 241         return *(*int8)(p) == *(*int8)(q)
 242 }
 243 func memequal16(p, q unsafe.Pointer) bool {
 244         return *(*int16)(p) == *(*int16)(q)
 245 }
 246 func memequal32(p, q unsafe.Pointer) bool {
 247         return *(*int32)(p) == *(*int32)(q)
 248 }
 249 func memequal64(p, q unsafe.Pointer) bool {
 250         return *(*int64)(p) == *(*int64)(q)
 251 }
 252 func memequal128(p, q unsafe.Pointer) bool {
 253         return *(*[2]int64)(p) == *(*[2]int64)(q)
 254 }
 255 func f32equal(p, q unsafe.Pointer) bool {
 256         return *(*float32)(p) == *(*float32)(q)
 257 }
 258 func f64equal(p, q unsafe.Pointer) bool {
 259         return *(*float64)(p) == *(*float64)(q)
 260 }
 261 func c64equal(p, q unsafe.Pointer) bool {
 262         return *(*complex64)(p) == *(*complex64)(q)
 263 }
 264 func c128equal(p, q unsafe.Pointer) bool {
 265         return *(*complex128)(p) == *(*complex128)(q)
 266 }
 267 func strequal(p, q unsafe.Pointer) bool {
 268         return *(*string)(p) == *(*string)(q)
 269 }
 270 func interequal(p, q unsafe.Pointer) bool {
 271         return ifaceeq(*(*iface)(p), *(*iface)(q))
 272 }
 273 func nilinterequal(p, q unsafe.Pointer) bool {
 274         return efaceeq(*(*eface)(p), *(*eface)(q))
 275 }
 276 func efaceeq(x, y eface) bool {
 277         t := x._type
 278         if !eqtype(t, y._type) {
 279                 return false
 280         }
 281         if t == nil {
 282                 return true
 283         }
 284         eq := t.equal
 285         if eq == nil {
 286                 panic(errorString("comparing uncomparable type " + t.string()))
 287         }
 288         if isDirectIface(t) {
 289                 return x.data == y.data
 290         }
 291         return eq(x.data, y.data)
 292 }
 293
 294 func ifaceeq(x, y iface) bool {
 295         xtab := x.tab
 296         if xtab == nil && y.tab == nil {
 297                 return true
 298         }
 299         if xtab == nil || y.tab == nil {
 300                 return false
 301         }
 302         t := *(**_type)(xtab)
 303         if !eqtype(t, *(**_type)(y.tab)) {
 304                 return false
 305         }
 306         eq := t.equal
 307         if eq == nil {
 308                 panic(errorString("comparing uncomparable type " + t.string()))
 309         }
 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
 315         }
 316         return eq(x.data, y.data)
 317 }
 318
 319 func ifacevaleq(x iface, t *_type, p unsafe.Pointer) bool {
 320         if x.tab == nil {
 321                 return false
 322         }
 323         xt := *(**_type)(x.tab)
 324         if !eqtype(xt, t) {
 325                 return false
 326         }
 327         eq := t.equal
 328         if eq == nil {
 329                 panic(errorString("comparing uncomparable type " + t.string()))
 330         }
 331         if isDirectIface(t) {
 332                 return x.data == p
 333         }
 334         return eq(x.data, p)
 335 }
 336
 337 func ifaceefaceeq(x iface, y eface) bool {
 338         if x.tab == nil && y._type == nil {
 339                 return true
 340         }
 341         if x.tab == nil || y._type == nil {
 342                 return false
 343         }
 344         xt := *(**_type)(x.tab)
 345         if !eqtype(xt, y._type) {
 346                 return false
 347         }
 348         eq := xt.equal
 349         if eq == nil {
 350                 panic(errorString("comparing uncomparable type " + xt.string()))
 351         }
 352         if isDirectIface(xt) {
 353                 return x.data == y.data
 354         }
 355         return eq(x.data, y.data)
 356 }
 357
 358 func efacevaleq(x eface, t *_type, p unsafe.Pointer) bool {
 359         if x._type == nil {
 360                 return false
 361         }
 362         if !eqtype(x._type, t) {
 363                 return false
 364         }
 365         eq := t.equal
 366         if eq == nil {
 367                 panic(errorString("comparing uncomparable type " + t.string()))
 368         }
 369         if isDirectIface(t) {
 370                 // See comment in efaceeq.
 371                 return x.data == p
 372         }
 373         return eq(x.data, p)
 374 }
 375
 376 func cmpstring(x, y string) int {
 377         a := stringStructOf(&x)
 378         b := stringStructOf(&y)
 379         l := a.len
 380         if l > b.len {
 381                 l = b.len
 382         }
 383         i := memcmp(unsafe.Pointer(a.str), unsafe.Pointer(b.str), uintptr(l))
 384         if i != 0 {
 385                 return int(i)
 386         }
 387         if a.len < b.len {
 388                 return -1
 389         } else if a.len > b.len {
 390                 return 1
 391         }
 392         return 0
 393 }
 394
 395 // For the unsafe.Pointer type descriptor in libgo/runtime/go-unsafe-pointer.c.
 396
 397 func pointerhash(p unsafe.Pointer, h uintptr) uintptr {
 398         return memhash(p, h, unsafe.Sizeof(unsafe.Pointer))
 399 }
 400
 401 func pointerequal(p, q unsafe.Pointer) bool {
 402         return *(*unsafe.Pointer)(p) == *(*unsafe.Pointer)(q)
 403 }
 404
 405 // Force the creation of function descriptors for equality and hash
 406 // functions.  These will be referenced directly by the compiler.
 407 var _ = memhash
 408 var _ = memhash0
 409 var _ = memhash8
 410 var _ = memhash16
 411 var _ = memhash32
 412 var _ = memhash64
 413 var _ = memhash128
 414 var _ = strhash
 415 var _ = f32hash
 416 var _ = f64hash
 417 var _ = c64hash
 418 var _ = c128hash
 419 var _ = interhash
 420 var _ = nilinterhash
 421 var _ = memequal0
 422 var _ = memequal8
 423 var _ = memequal16
 424 var _ = memequal32
 425 var _ = memequal64
 426 var _ = memequal128
 427 var _ = f32equal
 428 var _ = f64equal
 429 var _ = c64equal
 430 var _ = c128equal
 431 var _ = strequal
 432 var _ = interequal
 433 var _ = nilinterequal
 434 var _ = pointerhash
 435 var _ = pointerequal
 436
 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)
 440 }
 441
 442 func bytesHash(b []byte, seed uintptr) uintptr {
 443         s := (*slice)(unsafe.Pointer(&b))
 444         return memhash(s.array, seed, uintptr(s.len))
 445 }
 446
 447 func int32Hash(i uint32, seed uintptr) uintptr {
 448         return memhash32(noescape(unsafe.Pointer(&i)), seed)
 449 }
 450
 451 func int64Hash(i uint64, seed uintptr) uintptr {
 452         return memhash64(noescape(unsafe.Pointer(&i)), seed)
 453 }
 454
 455 func efaceHash(i any, seed uintptr) uintptr {
 456         return nilinterhash(noescape(unsafe.Pointer(&i)), seed)
 457 }
 458
 459 func ifaceHash(i interface {
 460         F()
 461 }, seed uintptr) uintptr {
 462         return interhash(noescape(unsafe.Pointer(&i)), seed)
 463 }
 464
 465 const hashRandomBytes = goarch.PtrSize / 4 * 64
 466
 467 // used in asm_{386,amd64,arm64}.s to seed the hash function
 468 var aeskeysched [hashRandomBytes]byte
 469
 470 // used in hash{32,64}.go to seed the hash function
 471 var hashkey [4]uintptr
 472
 473 func alginit() {
 474         // Install AES hash algorithms if the instructions needed are present.
 475         if (GOARCH == "386" || GOARCH == "amd64") &&
 476                 support_aes &&
 477                 cpu.X86.HasAES && // AESENC
 478                 cpu.X86.HasSSSE3 && // PSHUFB
 479                 cpu.X86.HasSSE41 { // PINSR{D,Q}
 480                 initAlgAES()
 481                 return
 482         }
 483         if GOARCH == "arm64" && cpu.ARM64.HasAES {
 484                 initAlgAES()
 485                 return
 486         }
 487         getRandomData((*[len(hashkey) * goarch.PtrSize]byte)(unsafe.Pointer(&hashkey))[:])
 488         hashkey[0] |= 1 // make sure these numbers are odd
 489         hashkey[1] |= 1
 490         hashkey[2] |= 1
 491         hashkey[3] |= 1
 492 }
 493
 494 func initAlgAES() {
 495         useAeshash = true
 496         // Initialize with random data so hash collisions will be hard to engineer.
 497         getRandomData(aeskeysched[:])
 498 }
 499
 500 // Note: These routines perform the read with a native endianness.
 501 func readUnaligned32(p unsafe.Pointer) uint32 {
 502         q := (*[4]byte)(p)
 503         if goarch.BigEndian {
 504                 return uint32(q[3]) | uint32(q[2])<<8 | uint32(q[1])<<16 | uint32(q[0])<<24
 505         }
 506         return uint32(q[0]) | uint32(q[1])<<8 | uint32(q[2])<<16 | uint32(q[3])<<24
 507 }
 508
 509 func readUnaligned64(p unsafe.Pointer) uint64 {
 510         q := (*[8]byte)(p)
 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
 514         }
 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
 516 }