src/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 const (
  13         c0 = uintptr((8-sys.PtrSize)/4*2860486313 + (sys.PtrSize-4)/4*33054211828000289)
  14         c1 = uintptr((8-sys.PtrSize)/4*3267000013 + (sys.PtrSize-4)/4*23344194077549503)
  15 )
  16
  17 // type algorithms - known to compiler
  18 const (
  19         alg_MEM = iota
  20         alg_MEM0
  21         alg_MEM8
  22         alg_MEM16
  23         alg_MEM32
  24         alg_MEM64
  25         alg_MEM128
  26         alg_NOEQ
  27         alg_NOEQ0
  28         alg_NOEQ8
  29         alg_NOEQ16
  30         alg_NOEQ32
  31         alg_NOEQ64
  32         alg_NOEQ128
  33         alg_STRING
  34         alg_INTER
  35         alg_NILINTER
  36         alg_SLICE
  37         alg_FLOAT32
  38         alg_FLOAT64
  39         alg_CPLX64
  40         alg_CPLX128
  41         alg_max
  42 )
  43
  44 // typeAlg is also copied/used in reflect/type.go.
  45 // keep them in sync.
  46 type typeAlg struct {
  47         // function for hashing objects of this type
  48         // (ptr to object, seed) -> hash
  49         hash func(unsafe.Pointer, uintptr) uintptr
  50         // function for comparing objects of this type
  51         // (ptr to object A, ptr to object B) -> ==?
  52         equal func(unsafe.Pointer, unsafe.Pointer) bool
  53 }
  54
  55 func memhash0(p unsafe.Pointer, h uintptr) uintptr {
  56         return h
  57 }
  58 func memhash8(p unsafe.Pointer, h uintptr) uintptr {
  59         return memhash(p, h, 1)
  60 }
  61 func memhash16(p unsafe.Pointer, h uintptr) uintptr {
  62         return memhash(p, h, 2)
  63 }
  64 func memhash32(p unsafe.Pointer, h uintptr) uintptr {
  65         return memhash(p, h, 4)
  66 }
  67 func memhash64(p unsafe.Pointer, h uintptr) uintptr {
  68         return memhash(p, h, 8)
  69 }
  70 func memhash128(p unsafe.Pointer, h uintptr) uintptr {
  71         return memhash(p, h, 16)
  72 }
  73
  74 // memhash_varlen is defined in assembly because it needs access
  75 // to the closure.  It appears here to provide an argument
  76 // signature for the assembly routine.
  77 func memhash_varlen(p unsafe.Pointer, h uintptr) uintptr
  78
  79 var algarray = [alg_max]typeAlg{
  80         alg_MEM:      {nil, nil}, // not used
  81         alg_MEM0:     {memhash0, memequal0},
  82         alg_MEM8:     {memhash8, memequal8},
  83         alg_MEM16:    {memhash16, memequal16},
  84         alg_MEM32:    {memhash32, memequal32},
  85         alg_MEM64:    {memhash64, memequal64},
  86         alg_MEM128:   {memhash128, memequal128},
  87         alg_NOEQ:     {nil, nil},
  88         alg_NOEQ0:    {nil, nil},
  89         alg_NOEQ8:    {nil, nil},
  90         alg_NOEQ16:   {nil, nil},
  91         alg_NOEQ32:   {nil, nil},
  92         alg_NOEQ64:   {nil, nil},
  93         alg_NOEQ128:  {nil, nil},
  94         alg_STRING:   {strhash, strequal},
  95         alg_INTER:    {interhash, interequal},
  96         alg_NILINTER: {nilinterhash, nilinterequal},
  97         alg_SLICE:    {nil, nil},
  98         alg_FLOAT32:  {f32hash, f32equal},
  99         alg_FLOAT64:  {f64hash, f64equal},
 100         alg_CPLX64:   {c64hash, c64equal},
 101         alg_CPLX128:  {c128hash, c128equal},
 102 }
 103
 104 var useAeshash bool
 105
 106 // in asm_*.s
 107 func aeshash(p unsafe.Pointer, h, s uintptr) uintptr
 108 func aeshash32(p unsafe.Pointer, h uintptr) uintptr
 109 func aeshash64(p unsafe.Pointer, h uintptr) uintptr
 110 func aeshashstr(p unsafe.Pointer, h uintptr) uintptr
 111
 112 func strhash(a unsafe.Pointer, h uintptr) uintptr {
 113         x := (*stringStruct)(a)
 114         return memhash(x.str, h, uintptr(x.len))
 115 }
 116
 117 // NOTE: Because NaN != NaN, a map can contain any
 118 // number of (mostly useless) entries keyed with NaNs.
 119 // To avoid long hash chains, we assign a random number
 120 // as the hash value for a NaN.
 121
 122 func f32hash(p unsafe.Pointer, h uintptr) uintptr {
 123         f := *(*float32)(p)
 124         switch {
 125         case f == 0:
 126                 return c1 * (c0 ^ h) // +0, -0
 127         case f != f:
 128                 return c1 * (c0 ^ h ^ uintptr(fastrand1())) // any kind of NaN
 129         default:
 130                 return memhash(p, h, 4)
 131         }
 132 }
 133
 134 func f64hash(p unsafe.Pointer, h uintptr) uintptr {
 135         f := *(*float64)(p)
 136         switch {
 137         case f == 0:
 138                 return c1 * (c0 ^ h) // +0, -0
 139         case f != f:
 140                 return c1 * (c0 ^ h ^ uintptr(fastrand1())) // any kind of NaN
 141         default:
 142                 return memhash(p, h, 8)
 143         }
 144 }
 145
 146 func c64hash(p unsafe.Pointer, h uintptr) uintptr {
 147         x := (*[2]float32)(p)
 148         return f32hash(unsafe.Pointer(&x[1]), f32hash(unsafe.Pointer(&x[0]), h))
 149 }
 150
 151 func c128hash(p unsafe.Pointer, h uintptr) uintptr {
 152         x := (*[2]float64)(p)
 153         return f64hash(unsafe.Pointer(&x[1]), f64hash(unsafe.Pointer(&x[0]), h))
 154 }
 155
 156 func interhash(p unsafe.Pointer, h uintptr) uintptr {
 157         a := (*iface)(p)
 158         tab := a.tab
 159         if tab == nil {
 160                 return h
 161         }
 162         t := tab._type
 163         fn := t.alg.hash
 164         if fn == nil {
 165                 panic(errorString("hash of unhashable type " + *t._string))
 166         }
 167         if isDirectIface(t) {
 168                 return c1 * fn(unsafe.Pointer(&a.data), h^c0)
 169         } else {
 170                 return c1 * fn(a.data, h^c0)
 171         }
 172 }
 173
 174 func nilinterhash(p unsafe.Pointer, h uintptr) uintptr {
 175         a := (*eface)(p)
 176         t := a._type
 177         if t == nil {
 178                 return h
 179         }
 180         fn := t.alg.hash
 181         if fn == nil {
 182                 panic(errorString("hash of unhashable type " + *t._string))
 183         }
 184         if isDirectIface(t) {
 185                 return c1 * fn(unsafe.Pointer(&a.data), h^c0)
 186         } else {
 187                 return c1 * fn(a.data, h^c0)
 188         }
 189 }
 190
 191 func memequal(p, q unsafe.Pointer, size uintptr) bool {
 192         if p == q {
 193                 return true
 194         }
 195         return memeq(p, q, size)
 196 }
 197
 198 func memequal0(p, q unsafe.Pointer) bool {
 199         return true
 200 }
 201 func memequal8(p, q unsafe.Pointer) bool {
 202         return *(*int8)(p) == *(*int8)(q)
 203 }
 204 func memequal16(p, q unsafe.Pointer) bool {
 205         return *(*int16)(p) == *(*int16)(q)
 206 }
 207 func memequal32(p, q unsafe.Pointer) bool {
 208         return *(*int32)(p) == *(*int32)(q)
 209 }
 210 func memequal64(p, q unsafe.Pointer) bool {
 211         return *(*int64)(p) == *(*int64)(q)
 212 }
 213 func memequal128(p, q unsafe.Pointer) bool {
 214         return *(*[2]int64)(p) == *(*[2]int64)(q)
 215 }
 216 func f32equal(p, q unsafe.Pointer) bool {
 217         return *(*float32)(p) == *(*float32)(q)
 218 }
 219 func f64equal(p, q unsafe.Pointer) bool {
 220         return *(*float64)(p) == *(*float64)(q)
 221 }
 222 func c64equal(p, q unsafe.Pointer) bool {
 223         return *(*complex64)(p) == *(*complex64)(q)
 224 }
 225 func c128equal(p, q unsafe.Pointer) bool {
 226         return *(*complex128)(p) == *(*complex128)(q)
 227 }
 228 func strequal(p, q unsafe.Pointer) bool {
 229         return *(*string)(p) == *(*string)(q)
 230 }
 231 func interequal(p, q unsafe.Pointer) bool {
 232         return ifaceeq(*(*iface)(p), *(*iface)(q))
 233 }
 234 func nilinterequal(p, q unsafe.Pointer) bool {
 235         return efaceeq(*(*eface)(p), *(*eface)(q))
 236 }
 237 func efaceeq(x, y eface) bool {
 238         t := x._type
 239         if t != y._type {
 240                 return false
 241         }
 242         if t == nil {
 243                 return true
 244         }
 245         eq := t.alg.equal
 246         if eq == nil {
 247                 panic(errorString("comparing uncomparable type " + *t._string))
 248         }
 249         if isDirectIface(t) {
 250                 return eq(noescape(unsafe.Pointer(&x.data)), noescape(unsafe.Pointer(&y.data)))
 251         }
 252         return eq(x.data, y.data)
 253 }
 254 func ifaceeq(x, y iface) bool {
 255         xtab := x.tab
 256         if xtab != y.tab {
 257                 return false
 258         }
 259         if xtab == nil {
 260                 return true
 261         }
 262         t := xtab._type
 263         eq := t.alg.equal
 264         if eq == nil {
 265                 panic(errorString("comparing uncomparable type " + *t._string))
 266         }
 267         if isDirectIface(t) {
 268                 return eq(noescape(unsafe.Pointer(&x.data)), noescape(unsafe.Pointer(&y.data)))
 269         }
 270         return eq(x.data, y.data)
 271 }
 272
 273 // Testing adapters for hash quality tests (see hash_test.go)
 274 func stringHash(s string, seed uintptr) uintptr {
 275         return algarray[alg_STRING].hash(noescape(unsafe.Pointer(&s)), seed)
 276 }
 277
 278 func bytesHash(b []byte, seed uintptr) uintptr {
 279         s := (*slice)(unsafe.Pointer(&b))
 280         return memhash(s.array, seed, uintptr(s.len))
 281 }
 282
 283 func int32Hash(i uint32, seed uintptr) uintptr {
 284         return algarray[alg_MEM32].hash(noescape(unsafe.Pointer(&i)), seed)
 285 }
 286
 287 func int64Hash(i uint64, seed uintptr) uintptr {
 288         return algarray[alg_MEM64].hash(noescape(unsafe.Pointer(&i)), seed)
 289 }
 290
 291 func efaceHash(i interface{}, seed uintptr) uintptr {
 292         return algarray[alg_NILINTER].hash(noescape(unsafe.Pointer(&i)), seed)
 293 }
 294
 295 func ifaceHash(i interface {
 296         F()
 297 }, seed uintptr) uintptr {
 298         return algarray[alg_INTER].hash(noescape(unsafe.Pointer(&i)), seed)
 299 }
 300
 301 // Testing adapter for memclr
 302 func memclrBytes(b []byte) {
 303         s := (*slice)(unsafe.Pointer(&b))
 304         memclr(s.array, uintptr(s.len))
 305 }
 306
 307 const hashRandomBytes = sys.PtrSize / 4 * 64
 308
 309 // used in asm_{386,amd64}.s to seed the hash function
 310 var aeskeysched [hashRandomBytes]byte
 311
 312 // used in hash{32,64}.go to seed the hash function
 313 var hashkey [4]uintptr
 314
 315 func init() {
 316         // Install aes hash algorithm if we have the instructions we need
 317         if (GOARCH == "386" || GOARCH == "amd64") &&
 318                 GOOS != "nacl" &&
 319                 cpuid_ecx&(1<<25) != 0 && // aes (aesenc)
 320                 cpuid_ecx&(1<<9) != 0 && // sse3 (pshufb)
 321                 cpuid_ecx&(1<<19) != 0 { // sse4.1 (pinsr{d,q})
 322                 useAeshash = true
 323                 algarray[alg_MEM32].hash = aeshash32
 324                 algarray[alg_MEM64].hash = aeshash64
 325                 algarray[alg_STRING].hash = aeshashstr
 326                 // Initialize with random data so hash collisions will be hard to engineer.
 327                 getRandomData(aeskeysched[:])
 328                 return
 329         }
 330         getRandomData((*[len(hashkey) * sys.PtrSize]byte)(unsafe.Pointer(&hashkey))[:])
 331         hashkey[0] |= 1 // make sure these numbers are odd
 332         hashkey[1] |= 1
 333         hashkey[2] |= 1
 334         hashkey[3] |= 1
 335 }