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